首页 > 代码库 > C++数据结构面试题

C++数据结构面试题

2024-07-10 15:34:50   225人阅读

原文：http://1527zhaobin.iteye.com/blog/1537110

 

一.判断链表是否存在环型链表问题：

  说明：判断一个链表是否存在环，例如下面这个链表就存在环，n1-->n2-->n3-->n4-->n5-->n2，环的开始结点是n5

  解法：这里有个比较简单的解法：设两个指针p1,p2，每次循环p1向前走一步，之向前走两步，直到p2碰到NULL指针(无环)或两个指针相等结束循环算法(有环)，即如果两个指针相等则说明存在环。

代码如下：

         

[cpp] view plaincopyprint?
  1. /*节点数据结构*/  
  2. struct link{  
  3.     int data;  
  4.     link * next;  
  5. };  
  6.   
  7. /* 
  8. *判断是否有环的方法 
  9. * 
  10. *参数来头节点的指针 
  11. */  
  12. bool isLoop(link * head){  
  13.     //p1步长为1；p2步长为2   
  14.     link* p1 = head,*p2 = head;  
  15.       
  16.     //如果只有一个节点或两个节点，直接return false   
  17.     if(head == NULL || head->next == NULL){  
  18.         return false;  
  19.     }  
  20.       
  21.     //循环前进，直到p2走到NULL或p2追上p1   
  22.     do{  
  23.         p1 = p1->next;  
  24.         p2 = p2->next->next;  
  25.     }while(p2 && p2->next && p1!=p2);  
  26.   
  27.     //如果有环   
  28.     if(p1 == p2){  
  29.         return true;  
  30.     else  
  31.         return false;  
  32. }  
Cpp代码
  1. /*节点数据结构*/  
  2. struct link{  
  3.     int data;  
  4.     link * next;  
  5. };  
  6.   
  7. /* 
  8. *判断是否有环的方法 
  9. * 
  10. *参数来头节点的指针 
  11. */  
  12. bool isLoop(link * head){  
  13.     //p1步长为1；p2步长为2  
  14.     link* p1 = head,*p2 = head;  
  15.       
  16.     //如果只有一个节点或两个节点，直接return false  
  17.     if(head == NULL || head->next == NULL){  
  18.         return false;  
  19.     }  
  20.       
  21.     //循环前进，直到p2走到NULL或p2追上p1  
  22.     do{  
  23.         p1 = p1->next;  
  24.         p2 = p2->next->next;  
  25.     }while(p2 && p2->next && p1!=p2);  
  26.   
  27.     //如果有环  
  28.     if(p1 == p2){  
  29.         return true;  
  30.     else  
  31.         return false;  
  32. }  

 

二.链表反转：

说明：链表反转，比如原链表是1-->2-->3-->4-->5 通过反转后成为5-->4-->3-->2-->1

解法一：利用三个指针，指向当前要反转的节点的指针，这个当前节点之前的节点指针，这个当前节点之后的节点指针；反转后再向后继续遍历

代码如下：

 

[cpp] view plaincopyprint?
  1. /*节点数据结构*/  
  2. struct linka{  
  3.     int data;  
  4.     link * next;  
  5. };  
  6.   
  7. /* 
  8. *反转 
  9. * 
  10. *参数：头节点的指针的引用 
  11. */  
  12. bool reverse(link * &head){  
  13.     //只有一个节点，即不用反转，直接返回   
  14.     if(head == NULL)  
  15.         return;  
  16.   
  17.     //定义3个辅助指针,pre指向当前要反转的节点的前一个节点；cur为当前要反转的节点；ne指向当前反转的节点的下一个节点   
  18.     linka * pre,*cur,*ne;  
  19.     //初始化指针   
  20.     pre = head;  
  21.     cur = head->next;  
  22.     //循环，直到cur为NULL   
  23.     while(cur){  
  24.         ne = cur->next;  
  25.         cur->next = pre;  
  26.         pre = cur;  
  27.         cur = ne;  
  28.     }  
  29.       
  30.     //反转到最后，设置头节点指针   
  31.     head->next = NULL;  
  32.     head = pre;  
  33. }  
Cpp代码
  1. /*节点数据结构*/  
  2. struct linka{  
  3.     int data;  
  4.     link * next;  
  5. };  
  6.   
  7. /* 
  8. *反转 
  9. * 
  10. *参数：头节点的指针的引用 
  11. */  
  12. bool reverse(link * &head){  
  13.     //只有一个节点，即不用反转，直接返回  
  14.     if(head == NULL)  
  15.         return;  
  16.   
  17.     //定义3个辅助指针,pre指向当前要反转的节点的前一个节点；cur为当前要反转的节点；ne指向当前反转的节点的下一个节点  
  18.     linka * pre,*cur,*ne;  
  19.     //初始化指针  
  20.     pre = head;  
  21.     cur = head->next;  
  22.     //循环，直到cur为NULL  
  23.     while(cur){  
  24.         ne = cur->next;  
  25.         cur->next = pre;  
  26.         pre = cur;  
  27.         cur = ne;  
  28.     }  
  29.       
  30.     //反转到最后，设置头节点指针  
  31.     head->next = NULL;  
  32.     head = pre;  
  33. }  

解法二：利用递归。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。不过，这个方法有个缺点：在反转后的最后一个节点会形成一个环，所以必须将函数的返回节点的next设为NULL.因为要改变head指针，所以我用了引用

 

代码如下：

 

[cpp] view plaincopyprint?
  1. /*节点数据结构*/  
  2. struct linka{  
  3.     int data;  
  4.     link * next;  
  5. };  
  6.   
  7. /* 
  8. *反转 
  9. * 
  10. *参数：头节点的指针的引用 
  11. */  
  12. linka * reverse(linka * p,link * &head){  
  13.     if(p == NULL || p->next == NULL){  
  14.         head = p;  
  15.         return p;  
  16.     }else {  
  17.         linka* tmp = reverse(p->next,head);  
  18.         tmp->next = p;  
  19.         return p;     
  20.     }  
  21. }  
Cpp代码
  1. /*节点数据结构*/  
  2. struct linka{  
  3.     int data;  
  4.     link * next;  
  5. };  
  6.   
  7. /* 
  8. *反转 
  9. * 
  10. *参数：头节点的指针的引用 
  11. */  
  12. linka * reverse(linka * p,link * &head){  
  13.     if(p == NULL || p->next == NULL){  
  14.         head = p;  
  15.         return p;  
  16.     }else {  
  17.         linka* tmp = reverse(p->next,head);  
  18.         tmp->next = p;  
  19.         return p;     
  20.     }  
  21. }  


三.链表的合并：

 

说明：递增有序的2个单链表合并成一个递增有序的单链表，不用任何库函数调用

代码如下：

 

[cpp] view plaincopyprint?
  1. <pre name="code" class="cpp">#include <iostream>  
  2. using namespace std;  
  3.   
  4. /* 单链表节点 */  
  5. struct node{  
  6.     int value;  
  7.     node* next;  
  8. };  
  9.   
  10. /* 给单链表添加节点 */  
  11. void insertNode(node* head, int value){  
  12.     node* p = head->next;  
  13.     if ( p == NULL ){  
  14.        p = new node;  
  15.        p->value = value;  
  16.        p->next = NULL;  
  17.        head->next = p;  
  18.        return;  
  19.     }  
  20.   
  21.     while ( p->next != NULL ){  
  22.        p = p->next;  
  23.     }  
  24.     node* tmp = new node;  
  25.     tmp->value = value;  
  26.     tmp->next = NULL;  
  27.     p->next = tmp;  
  28. }  
  29.   
  30. /* 遍历输出链表节点 */  
  31. void print(node* head){  
  32.     node* p = head->next;  
  33.     while ( p != NULL ){  
  34.        cout << p->value << " ";  
  35.        p = p->next;  
  36.     }  
  37.     cout << endl;  
  38. }  
  39.   
  40.   
  41. /* 下面实现不使用任何库函数， 利用交换的方法在原空间实现整体有序。 方法是先确定哪一个链表 
  42. 的第一个节点的值小，把这个链表的头结点作为合并后链表的头结点，然后比较2个有序链表的当前节点 
  43. 的值，如果代表最后合并链表的值小，则不用交换，否则把两个值交换，最后合并链表始终保持两个值中 
  44. 的小值。另一个链表由于交换了一个元素，当前元素可能影响该链表的有序递增，对其进行调整使其保持 
  45. 递增有序，然后重复上述动作，直到一个链表遍历结束，然后把剩余的链表连接起来就行。*/  
  46.   
  47. /* 调整链表的第一个节点，使其变成递增有序 */  
  48. void chg2sort(node* head, node* &p){  
  49.   
  50.     if (head->next == NULL ){ //没有节点，直接返回   
  51.         return;  
  52.     }  
  53.   
  54.     node* s = head;  
  55.     while ( s->next != p ){ //s指向p的前一个节点   
  56.        s = s->next;  
  57.     }  
  58.   
  59.     //下面的一段找到第一个大于p节点值的节点   
  60.     node* q = p;  
  61.     node* r = q;  
  62.       
  63.     while ( q != NULL ){  
  64.       
  65.        if ( q->value <= p->value ){  
  66.         r = q; //r始终指向q的前一个节点   
  67.         q = q->next;  
  68.        }else {  
  69.         break;  
  70.        }  
  71.     }  
  72.   
  73.     //下面调整指针，其实可以统一写出来，为了阅读清晰把q为NULL和非NULL分开写出来   
  74.       
  75.     if ( q == NULL ){  
  76.        r->next = p;  
  77.        s->next = p->next;  
  78.        p->next = NULL;  
  79.     }else if ( q != NULL ){  
  80.        s->next = p->next;  
  81.        r->next = p;  
  82.        p->next = q;  
  83.     }  
  84.       
  85.     //由于链表进行了调换，当前链表指针也需要改变   
  86.     p = s->next;  
  87. }  
  88.   
  89.   
  90. /* 两个有序链表进行合并 */  
  91. node* merge(node* head1, node* head2){  
  92.     node* head; //合并后的头指针   
  93.     node* p = head1->next;  
  94.     node* q = head2->next;  
  95.   
  96.     //有一个链表为空的情况，直接返回另一个链表   
  97.     if ( p == NULL ){  
  98.        head = head2;  
  99.        return head;  
  100.     }else if ( q == NULL ){  
  101.        head = head1;  
  102.        return head;  
  103.     }  
  104.   
  105.     //两个都不为空,先确定哪个链表作为合并后的链表   
  106.     if ( (p != NULL) && (q != NULL) ){  
  107.        if ( p->value < q->value ){  
  108.         head = head1;  
  109.        }else{  
  110.         head = head2;  
  111.        }  
  112.     }  
  113.   
  114.     node* p_prior; //始终指向p节点的前一个节点   
  115.     node* q_prior;  
  116.   
  117.     while ( (p != NULL) && (q != NULL) ){  
  118.        if ( p ->value < q->value ){  
  119.             if ( head == head1 ){//如果链表1的值小于链表2的值，链表1的指针向下指   
  120.                  p_prior = p;  
  121.                  p = p->next;  
  122.             }else if ( head == head2 ){  
  123.                  //进行当前节点值的交换   
  124.                  int tmp = p->value;  
  125.                  p->value = q->value;  
  126.                  q->value = tmp;  
  127.                  chg2sort(head1, p); //交换元素后的调整   
  128.                  q_prior = q;  
  129.                  q = q->next;  
  130.             }  
  131.        }else if ( p->value == q->value ){//链表1的值等于链表2时，两链表指针都向下指   
  132.             p_prior = p;  
  133.             p = p->next;  
  134.             q_prior = q;  
  135.             q = q->next;  
  136.        }else if ( p->value > q->value ){  
  137.             if ( head == head1 ){//如果链表1的值大于链表2的值，交接两节点的值后，排序链表2后，再下指   
  138.                  int tmp = p->value;  
  139.                  p->value = q->value;  
  140.                  q->value = tmp;  
  141.                  chg2sort(head2, q);  
  142.                  p_prior = p;  
  143.                  p = p->next;  
  144.             }else if ( head == head2 ){  
  145.                  q_prior = q;  
  146.                  q = q->next;  
  147.             }  
  148.        }  
  149.     }  
  150.   
  151.     if ( p != NULL ){  
  152.        q_prior->next = p;  
  153.     }  
  154.   
  155.     if ( q != NULL ){  
  156.        p_prior->next = q;  
  157.     }  
  158.   
  159.     return head;  
  160. }  
  161.   
  162. int main(){  
  163.     /* 建立有序链表A */  
  164.     int a[5] = {1, 5, 8, 10, 20};  
  165.     node* headA = new node;  
  166.     headA->next = NULL;  
  167.       
  168.     for (int i = 0; i < 5; ++i){  
  169.        insertNode(headA, a[i]);  
  170.     }  
  171.       
  172.     print(headA);  
  173.   
  174.     /* 建立有序链表B */  
  175.     int b[3] = {3, 4, 9};  
  176.     node* headB = new node;  
  177.     headB->next = NULL;  
  178.       
  179.     for (int i = 0; i < 3; ++i){  
  180.        insertNode(headB, b[i]);  
  181.     }  
  182.       
  183.     print(headB);  
  184.   
  185.     head = merge(headA, headB);  
  186.     print(head);  
  187.       
  188.     return 0;  
  189. }  
Cpp代码
  1. <pre name="code" class="cpp">#include <iostream>  
  2. using namespace std;  
  3.   
  4. /* 单链表节点 */  
  5. struct node{  
  6.     int value;  
  7.     node* next;  
  8. };  
  9.   
  10. /* 给单链表添加节点 */  
  11. void insertNode(node* head, int value){  
  12.     node* p = head->next;  
  13.     if ( p == NULL ){  
  14.        p = new node;  
  15.        p->value = value;  
  16.        p->next = NULL;  
  17.        head->next = p;  
  18.        return;  
  19.     }  
  20.   
  21.     while ( p->next != NULL ){  
  22.        p = p->next;  
  23.     }  
  24.     node* tmp = new node;  
  25.     tmp->value = value;  
  26.     tmp->next = NULL;  
  27.     p->next = tmp;  
  28. }  
  29.   
  30. /* 遍历输出链表节点 */  
  31. void print(node* head){  
  32.     node* p = head->next;  
  33.     while ( p != NULL ){  
  34.        cout << p->value << " ";  
  35.        p = p->next;  
  36.     }  
  37.     cout << endl;  
  38. }  
  39.   
  40.   
  41. /* 下面实现不使用任何库函数， 利用交换的方法在原空间实现整体有序。 方法是先确定哪一个链表 
  42. 的第一个节点的值小，把这个链表的头结点作为合并后链表的头结点，然后比较2个有序链表的当前节点 
  43. 的值，如果代表最后合并链表的值小，则不用交换，否则把两个值交换，最后合并链表始终保持两个值中 
  44. 的小值。另一个链表由于交换了一个元素，当前元素可能影响该链表的有序递增，对其进行调整使其保持 
  45. 递增有序，然后重复上述动作，直到一个链表遍历结束，然后把剩余的链表连接起来就行。*/  
  46.   
  47. /* 调整链表的第一个节点，使其变成递增有序 */  
  48. void chg2sort(node* head, node* &p){  
  49.   
  50.     if (head->next == NULL ){ //没有节点，直接返回  
  51.         return;  
  52.     }  
  53.   
  54.     node* s = head;  
  55.     while ( s->next != p ){ //s指向p的前一个节点  
  56.        s = s->next;  
  57.     }  
  58.   
  59.     //下面的一段找到第一个大于p节点值的节点  
  60.     node* q = p;  
  61.     node* r = q;  
  62.       
  63.     while ( q != NULL ){  
  64.       
  65.        if ( q->value <= p->value ){  
  66.         r = q; //r始终指向q的前一个节点  
  67.         q = q->next;  
  68.        }else {  
  69.         break;  
  70.        }  
  71.     }  
  72.   
  73.     //下面调整指针，其实可以统一写出来，为了阅读清晰把q为NULL和非NULL分开写出来  
  74.       
  75.     if ( q == NULL ){  
  76.        r->next = p;  
  77.        s->next = p->next;  
  78.        p->next = NULL;  
  79.     }else if ( q != NULL ){  
  80.        s->next = p->next;  
  81.        r->next = p;  
  82.        p->next = q;  
  83.     }  
  84.       
  85.     //由于链表进行了调换，当前链表指针也需要改变  
  86.     p = s->next;  
  87. }  
  88.   
  89.   
  90. /* 两个有序链表进行合并 */  
  91. node* merge(node* head1, node* head2){  
  92.     node* head; //合并后的头指针  
  93.     node* p = head1->next;  
  94.     node* q = head2->next;  
  95.   
  96.     //有一个链表为空的情况，直接返回另一个链表  
  97.     if ( p == NULL ){  
  98.        head = head2;  
  99.        return head;  
  100.     }else if ( q == NULL ){  
  101.        head = head1;  
  102.        return head;  
  103.     }  
  104.   
  105.     //两个都不为空,先确定哪个链表作为合并后的链表  
  106.     if ( (p != NULL) && (q != NULL) ){  
  107.        if ( p->value < q->value ){  
  108.         head = head1;  
  109.        }else{  
  110.         head = head2;  
  111.        }  
  112.     }  
  113.   
  114.     node* p_prior; //始终指向p节点的前一个节点  
  115.     node* q_prior;  
  116.   
  117.     while ( (p != NULL) && (q != NULL) ){  
  118.        if ( p ->value < q->value ){  
  119.             if ( head == head1 ){//如果链表1的值小于链表2的值，链表1的指针向下指  
  120.                  p_prior = p;  
  121.                  p = p->next;  
  122.             }else if ( head == head2 ){  
  123.                  //进行当前节点值的交换  
  124.                  int tmp = p->value;  
  125.                  p->value = q->value;  
  126.                  q->value = tmp;  
  127.                  chg2sort(head1, p); //交换元素后的调整  
  128.                  q_prior = q;  
  129.                  q = q->next;  
  130.             }  
  131.        }else if ( p->value == q->value ){//链表1的值等于链表2时，两链表指针都向下指  
  132.             p_prior = p;  
  133.             p = p->next;  
  134.             q_prior = q;  
  135.             q = q->next;  
  136.        }else if ( p->value > q->value ){  
  137.             if ( head == head1 ){//如果链表1的值大于链表2的值，交接两节点的值后，排序链表2后，再下指  
  138.                  int tmp = p->value;  
  139.                  p->value = q->value;  
  140.                  q->value = tmp;  
  141.                  chg2sort(head2, q);  
  142.                  p_prior = p;  
  143.                  p = p->next;  
  144.             }else if ( head == head2 ){  
  145.                  q_prior = q;  
  146.                  q = q->next;  
  147.             }  
  148.        }  
  149.     }  
  150.   
  151.     if ( p != NULL ){  
  152.        q_prior->next = p;  
  153.     }  
  154.   
  155.     if ( q != NULL ){  
  156.        p_prior->next = q;  
  157.     }  
  158.   
  159.     return head;  
  160. }  
  161.   
  162. int main(){  
  163.     /* 建立有序链表A */  
  164.     int a[5] = {1, 5, 8, 10, 20};  
  165.     node* headA = new node;  
  166.     headA->next = NULL;  
  167.       
  168.     for (int i = 0; i < 5; ++i){  
  169.        insertNode(headA, a[i]);  
  170.     }  
  171.       
  172.     print(headA);  
  173.   
  174.     /* 建立有序链表B */  
  175.     int b[3] = {3, 4, 9};  
  176.     node* headB = new node;  
  177.     headB->next = NULL;  
  178.       
  179.     for (int i = 0; i < 3; ++i){  
  180.        insertNode(headB, b[i]);  
  181.     }  
  182.       
  183.     print(headB);  
  184.   
  185.     head = merge(headA, headB);  
  186.     print(head);  
  187.       
  188.     return 0;  
  189. }  

如果可以用库函数合并的话：代码如下：

 

[cpp] view plaincopyprint?
  1. Node* mergeAction(Node* head1, Node* head2){  
  2. //两个链表的合并操作    
  3.         Node* head=(Node*)malloc(sizeof(Node));   
  4.         Node* q=head; //q指向合并后的链表的最后一个   
  5.         while(head1 && head2){ //   
  6.                 if(head1->data<=head2->data){   
  7.                         Node* p=(Node*)malloc(sizeof(Node)); //p是新生节点的指针   
  8.                         p->data=http://www.mamicode.com/head1->data;
  9.                         p->next=NULL;   
  10.                         q->next=p;   
  11.                         q=q->next;   
  12.                         head1=head1->next;   
  13.                 }   
  14.                 else if(head1->data > head2->data){   
  15.                         Node* p=(Node*)malloc(sizeof(Node));   
  16.                         p->data=http://www.mamicode.com/head2->data;
  17.                         p->next=NULL;   
  18.                         q->next=p;   
  19.                         q=q->next;   
  20.                         head2=head2->next;   
  21.                 }   
  22.         }   
  23.         return head->next;   
  24. }  
Cpp代码
  1. Node* mergeAction(Node* head1, Node* head2){  
  2. //两个链表的合并操作   
  3.         Node* head=(Node*)malloc(sizeof(Node));   
  4.         Node* q=head; //q指向合并后的链表的最后一个  
  5.         while(head1 && head2){ //  
  6.                 if(head1->data<=head2->data){   
  7.                         Node* p=(Node*)malloc(sizeof(Node)); //p是新生节点的指针  
  8.                         p->data=http://www.mamicode.com/head1->data;
  9.                         p->next=NULL;   
  10.                         q->next=p;   
  11.                         q=q->next;   
  12.                         head1=head1->next;   
  13.                 }   
  14.                 else if(head1->data > head2->data){   
  15.                         Node* p=(Node*)malloc(sizeof(Node));   
  16.                         p->data=http://www.mamicode.com/head2->data;
  17.                         p->next=NULL;   
  18.                         q->next=p;   
  19.                         q=q->next;   
  20.                         head2=head2->next;   
  21.                 }   
  22.         }   
  23.         return head->next;   
  24. }  

 

 

四.判断两个数组中是否存在相同的数字，给定两个排好序的数据，怎么高效得判断这两个数组中存在相同的数字：

说明：O(n)算法，因为两个数组都是排序好的，所以只要一次遍历就行了，首先设两个下标，分别初始化为两个数组的起始地址，依次向前推进，推进的规则是比较两个数组中的数字，小的那个数组的下标各前推进一步，直到任何一个数组的下标到达数组末尾时，如果这时还没碰到相同的数字，说明数组中没有相同的数字。

代码如下：

 

[cpp] view plaincopyprint?
  1. bool findcommon2(int a[], int size1,int b[],int size2){  
  2.     int i = 0, j = 0;  
  3.       
  4.     while(i<size1 && j<size2){  
  5.         if(a[i]==b[j])  
  6.             return true;  
  7.           
  8.         if(a[i]>b[j])  
  9.             j++;//j标记b数组   
  10.           
  11.         if(a[i]<b[j])  
  12.             i++;//i标记a数组   
  13.     }  
  14.       
  15.     return false;  
  16. }  
Cpp代码
  1. bool findcommon2(int a[], int size1,int b[],int size2){  
  2.     int i = 0, j = 0;  
  3.       
  4.     while(i<size1 && j<size2){  
  5.         if(a[i]==b[j])  
  6.             return true;  
  7.           
  8.         if(a[i]>b[j])  
  9.             j++;//j标记b数组  
  10.           
  11.         if(a[i]<b[j])  
  12.             i++;//i标记a数组  
  13.     }  
  14.       
  15.     return false;  
  16. }  


五.按单词反转字符串：

 

说明：单词用空格分开，如，Here is blog.csdn.net/wufenglong 经过反转后变为：blog.csdn.net/wufenglong is Here如果只是简单的将所有字符串翻转的话，可以遍历字符串，将第一个字符和最后一个交换，第二个和倒数第二个交换，依次循环。其实按照单词反转的话可以在第一遍遍历的基础上，再遍历一遍字符串，对每一个单词再反转一次，这样每个单词又恢复了原来的顺序

代码如下：

 

[cpp] view plaincopyprint?
  1. char * reverse_word(const char *str){  
  2.     int len = strlen(str);  
  3.     char * restr = new char[len+1];  
  4.       
  5.     strcpy(restr,str);  
  6.       
  7.     //首尾交换，i是首的索引 j是尾的索引   
  8.     for(int i=0,j=len-1;i<j;i++,j--){  
  9.         char tmp = restr[i];  
  10.         restr[i] = restr[j];  
  11.         restr[j] = tmp;  
  12.     }  
  13.       
  14.     //再把每个单词反转   
  15.     int i,j,k = 0;  
  16.     while(k<len){  
  17.         i=j=k;  
  18.         while(restr[j]!=‘ ‘ && restr[j]!=‘\0‘)  
  19.             j++;//j为空格的索引   
  20.           
  21.         k = j+1;//k为   
  22.         j--;  
  23.           
  24.         //反转单词   
  25.         for(;i<j;i++,j--){  
  26.             char tmp = restr[i];  
  27.             restr[i] = restr[j];  
  28.             restr[j] = tmp;  
  29.         }  
  30.     }  
  31.       
  32.     return restr;  
  33. }  
Cpp代码
  1. char * reverse_word(const char *str){  
  2.     int len = strlen(str);  
  3.     char * restr = new char[len+1];  
  4.       
  5.     strcpy(restr,str);  
  6.       
  7.     //首尾交换，i是首的索引 j是尾的索引  
  8.     for(int i=0,j=len-1;i<j;i++,j--){  
  9.         char tmp = restr[i];  
  10.         restr[i] = restr[j];  
  11.         restr[j] = tmp;  
  12.     }  
  13.       
  14.     //再把每个单词反转  
  15.     int i,j,k = 0;  
  16.     while(k<len){  
  17.         i=j=k;  
  18.         while(restr[j]!=‘ ‘ && restr[j]!=‘\0‘)  
  19.             j++;//j为空格的索引  
  20.           
  21.         k = j+1;//k为  
  22.         j--;  
  23.           
  24.         //反转单词  
  25.         for(;i<j;i++,j--){  
  26.             char tmp = restr[i];  
  27.             restr[i] = restr[j];  
  28.             restr[j] = tmp;  
  29.         }  
  30.     }  
  31.       
  32.     return restr;  
  33. }  


六.字符串反转：

 

题意：给定一个字符串，一个这个字符串的子串，将第一个字符串反转，但保留子串的顺序不变。

例如：输入 每一个串 “this is wufl‘s Chinese site: http://blog.csdn.net/wufenglong”

子串：“wufl”

输出： gnolgnefuw/tne.ndsc/golb//:ptth:eits esenihC s‘wufl si siht

说明：一般的方法是先扫描一边第一个字符串，然后用stack把它反转，同时记录下子串出现的位置。然后再扫描一遍把记录下来的子串再用stack反转，我用的方法是用一遍扫描数组的方法，扫描中如果发现子串，就将子串倒过来压入堆栈。

代码如下：

 

[cpp] view plaincopyprint?
  1. #include <stack>   
  2. using namespace std;  
  3.   
  4. //reverse the string ‘s1‘ ,the substring ‘token‘   
  5. const char * reverse(const char * s1, const char * token){  
  6.     assert(s1 && token);  
  7.       
  8.     stack<char> stack1;  
  9.       
  10.     const char * ptoken = token, *head = s1, *rear =s1;  
  11.       
  12.     while(*head !=‘‘){  
  13.         while(*head !=‘‘ && *ptoken == *head){  
  14.             ptoken++;  
  15.             head++;  
  16.         }  
  17.           
  18.         if(*ptoken==‘‘){  
  19.             const char *p;  
  20.               
  21.             for(p=head-1;p>=rear;p--){  
  22.                 stark1.push(*p);  
  23.             }  
  24.               
  25.             ptoken = token;  
  26.             rear = head;  
  27.         }else{  
  28.             stack1.push(*rear);  
  29.             head = ++rear;  
  30.             ptoken = token;  
  31.         }  
  32.     }  
  33.       
  34.     char * returnV = new char[strlen(s1)+1];  
  35.     int i=0;  
  36.       
  37.     while(!stack1.empty()){  
  38.         returnV[i++] = stack1.top();  
  39.         stack1.top();  
  40.     }  
  41.       
  42.     returnV[i]="";  
  43.     return returnV;  
  44. }  
Cpp代码
    1. #include <stack>  
    2. using namespace std;  
    3.   
    4. //reverse the string ‘s1‘ ,the substring ‘token‘  
    5. const char * reverse(const char * s1, const char * token){  
    6.     assert(s1 && token);  
    7.       
    8.     stack<char> stack1;  
    9.       
    10.     const char * ptoken = token, *head = s1, *rear =s1;  
    11.       
    12.     while(*head !=‘‘){  
    13.         while(*head !=‘‘ && *ptoken == *head){  
    14.             ptoken++;  
    15.             head++;  
    16.         }  
    17.           
    18.         if(*ptoken==‘‘){  
    19.             const char *p;  
    20.               
    21.             for(p=head-1;p>=rear;p--){  
    22.                 stark1.push(*p);  
    23.             }  
    24.               
    25.             ptoken = token;  
    26.             rear = head;  
    27.         }else{  
    28.             stack1.push(*rear);  
    29.             head = ++rear;  
    30.             ptoken = token;  
    31.         }  
    32.     }  
    33.       
    34.     char * returnV = new char[strlen(s1)+1];  
    35.     int i=0;  
    36.       
    37.     while(!stack1.empty()){  
    38.         returnV[i++] = stack1.top();  
    39.         stack1.top();  
    40.     }  
    41.       
    42.     returnV[i]="";  
    43.     return returnV;  
    44. } 

       

 

1.    在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：
q=head;
while (q->next!=p)   q=q->next;
s= new   Node; s->data=http://www.mamicode.com/e;
q->next=     ; //填空
s->next=     ; //填空


2.    线性表的顺序存储结构是一种 的存储结构，而链式存储结构是一种___的存储结构。
A．随机存取     B．索引存取 C．顺序存取 D．散列存取


3.    线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。
A. 必须是连续的    B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续或不连续都可以

4.    在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。
A. s->next=p->next;   p->next=s; B. p->next=s->next;   s->next=p;
C. q->next=s; s->next=p;        D. p->next=s; s->next=q;


5.    在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。
A.   s->next=p;   p->next=s;    B. s->next=p->next;   p->next=s;
C.   s->next=p->next;   p=s;    C. p->next=s;   s->next=p;


6.    在一个单链表中，若删除p所指结点的后续结点，则执行____。
A. p->next= p->next->next； B. p= p->next;   p->next= p->next->next；
C. p->next= p->next;       D. p= p->next->next；

7.    链表不具备的特点是 ____ 。
A 可随机访问任何一个元素              B 插入、删除操作不需要移动元素
C 无需事先估计存储空间大小              D 所需存储空间与线性表长度成正比

8.    以下关于线性表的说法不正确的是 。  
A 线性表中的数据元素可以是数字、字符、记录等不同类型。  
B 线性表中包含的数据元素个数不是任意的。  
C 线性表中的每个结点都有且只有一个直接前趋和直接后继。  
D 存在这样的线性表：表中各结点都没有直接前趋和直接后继。

9.    在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果要在第i个元素前插入一个元素，要后移( )个元素。 N-I N-I+1




--------------------------------------------------------------------------------------------------
1.    栈操作数据的原则是( )，队列操作数据的原则是 ( ) 。

2.    在栈中，可进行插入和删除操作的一端称    。

3.    栈和队列都是____结构；对于栈只能在____插入和删除元素；对于队列只能在____插入元素和____删除元素。

4.    栈结构通常采用的两种存储结构是    和    。

5.    计算机在运行递归程序时，要用到    提供的栈。

6.    一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。
A. edcba B. decba C. dceab D. abcde

7.    一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。
A. 4，3，2，1        B. 1，2，3，4 C. 1，4，3，2        D. 3，2，4，1


8.    判断一个表达式中左右括号是否匹配，采用 ____ 实现较为方便。
A 线性表的顺序存储        B 队列        C 线性表的链式存储        D 栈

9.    栈与一般线性表区别主要在方面    。
A 元素个数        B 元素类型        C 逻辑结构        D 插入、删除元素的位置

10.    “假上溢”现象会出现在     中。  
A   循环队列             B 队列             C 链队列             D 顺序队列

11.    在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是 。  
A   R=F->next;       B   R=R->next;       C   F=F->next;             D   F=R->next;

12.    表达式a*(b+c)-d的后缀表达式是 。
A．abcd*+-             B. abc+*d-             C. abc*+d-             D. -+*abcd


联系
我们