[关闭]
@yudesong 2017-06-24T14:41:52.000000Z 字数 8054 阅读 566

线性表

线性表 yudesong 2017/6/24

线性表（a1，a2…，an）有唯一的第一个和最后一个元素（n≥0）。其余的有唯一的前驱和后继。 顺序表定义：用一组地址连续的存储单元依次存放的数据元素。 在顺序表的第i个位置前插入一个数据元素，需要向后移动n － i ＋1个元素，删除第i个位置的元素需要向前移动n－ i个元素。 

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. typedef char ElemType;
  4. typedef struct
  5. {
  6.     ElemType data[MAX_SIZE];
  7.     int len;
  8. }SqList;
  9. //初始化顺序表
  10. void initList(SqList *&L)
  11. {
  12.     L=(SqList *)malloc(sizeof(SqList));
  13.     L->len=0;
  14. }
  15. //插入元素
  16. void insertList(SqList *&L,int i,ElemType e)
  17. {
  18.     i--;
  19.     int j;
  20.     for(j=L->len;j>i;j--)
  21.         L->data[j]=L->data[j-1];
  22.     L->data[i]=e;
  23.     L->len++;
  24. }
  25. //删除第i个位置的元素
  26. void deleteList(SqList *&L,int i)
  27. {
  28.     i--;
  29.     ElemType e=L->data[i];
  30.     for(int j=i;j<L->len-1;j++)
  31.         L->data[j]=L->data[j+1];
  32.     L->len--;
  33.     printf("%c",e);
  34. }
  35. //输出元素
  36. void disPlay(SqList *L)
  37. {
  38.     int i;
  39.     for(i=0;i<;L->len;i++)
  40.         printf("%c   ",L->data[i]);
  41. }
  42. //释放顺序表
  43. void freeList(SqList *L)
  44. {
  45.     free(L);
  46. }

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的. 

  1. typedef char ElemType;
  2. typedef struct  Node
  3. {
  4.     ElemType data;
  5.     struct Node *next;
  6. }LinkList;
  7. //初始化链表
  8. void initLink(LinkList *&L)
  9. {
  10.     L=(LinkList *)malloc(sizeof(LinkList));
  11.     L->next=NULL;
  12. }
  13. //链表插入
  14. int insertLink(LinkList *&L,int i,ElemType e)
  15. {
  16.     LinkList *p=L,*s;
  17.     int j=0;
  18.     while(j<i-1 && p!=NULL)
  19.     {
  20.     j++;
  21.     p=p->next;
  22.     }
  24.     if(p==NULL) return 0;
  25.     else
  26.     {
  27.     s=(LinkList *)malloc(sizeof(LinkList));
  28.     s->data=e;
  29.     s->next=p->next;
  30.     p->next=s;
  31.     }
  32.     return 1;
  33. }
  34. //删除链表中元素
  35. void deleteList(LinkList *L)
  36. {
  37.     LinkList *p=L,*q=p->next;
  38.     while(q!=NULL)
  39.     {
  40.         free(p);
  41.         p=q;
  42.         q=p->next;
  43.     }
  44. }
  45. //输出链表
  46. void disPlsy(LinkList *L)
  47. {
  48.     LinkList *p=L->next;
  49.     while(p!=NULL)
  50.     {
  51.         printf("%c ",p->data);
  52.         p=p->next;
  53.     }
  54. }
1. 求单链表中结点的个数
  1. // 求单链表中结点的个数   
  2. unsigned int GetListLength(ListNode * pHead)  
  3. {  
  4.  if(pHead == NULL)  
  5.  return 0;   
  6.  unsigned int nLength = 0;  
  7.  ListNode * pCurrent = pHead;  
  8.  while(pCurrent != NULL) 
  9.  { 
  10.  nLength++; 
  11.  pCurrent = pCurrent->m_pNext; 
  12.  } 
  13.  return nLength; 
  14. }
2. 将单链表反转
  2. // 反转单链表   
  3. ListNode * ReverseList(ListNode * pHead)  
  4. {  
  6. // 如果链表为空或只有一个结点，无需反转，直接返回原链表头指针   
  7.  if(pHead == NULL || pHead->m_pNext == NULL)  
  8.  return pHead;    
  9.  ListNode * pReversedHead = NULL; 
  10. // 反转后的新链表头指针，初始为NULL   
  11.  ListNode * pCurrent = pHead; 
  12.  while(pCurrent != NULL) 
  13.  { 
  14.  ListNode * pTemp = pCurrent; 
  15.  pCurrent = pCurrent->m_pNext; 
  16.  pTemp->m_pNext = pReversedHead; 
  17. // 将当前结点摘下，插入新链表的最前端  
  18.  pReversedHead = pTemp; 
  19.  } 
  20.  return pReversedHead; 
  21. }
3. 查找单链表中的倒数第K个结点（k > 0）
  1. // 查找单链表中倒数第K个结点  
  2. ListNode * RGetKthNode(ListNode * pHead, unsigned int k) 
  3. // 函数名前面的R代表反向  
  4. {  
  5.     if(k == 0 || pHead == NULL) 
  6. // 这里k的计数是从1开始的，若k为0或链表为空返回NULL  
  7.         return NULL;  
  9.     ListNode * pAhead = pHead;  
  10.     ListNode * pBehind = pHead;  
  11.     while(k > 1 && pAhead != NULL) 
  12. // 前面的指针先走到正向第k个结点  
  13.     {  
  14.         pAhead = pAhead->m_pNext;  
  15.         k--;  
  16.     }  
  17.     if(k > 1)     
  18. // 结点个数小于k，返回NULL  
  19.         return NULL;  
  20.     while(pAhead->m_pNext != NULL)  
  21. // 前后两个指针一起向前走，直到前面的指针指向最后一个结点  
  22.     {  
  23.         pBehind = pBehind->m_pNext;  
  24.         pAhead = pAhead->m_pNext;  
  25.     }  
  26.     return pBehind;  
  27. // 后面的指针所指结点就是倒数第k个结点  
  28. }
4. 查找单链表的中间结点
  1. // 获取单链表中间结点，若链表长度为n(n>0)，则返回第n/2+1个结点  
  2. ListNode * GetMiddleNode(ListNode * pHead)  
  3. {  
  4.     if(pHead == NULL || pHead->m_pNext == NULL) 
  5. // 链表为空或只有一个结点，返回头指针  
  6.         return pHead;  
  8.     ListNode * pAhead = pHead;  
  9.     ListNode * pBehind = pHead;  
  10.     while(pAhead->m_pNext != NULL) 
  11. // 前面指针每次走两步，直到指向最后一个结点，后面指针每次走一步  
  12.     {  
  13.         pAhead = pAhead->m_pNext;  
  14.         pBehind = pBehind->m_pNext;  
  15.         if(pAhead->m_pNext != NULL)  
  16.             pAhead = pAhead->m_pNext;  
  17.     }  
  18.     return pBehind; // 后面的指针所指结点即为中间结点  
  19. }
5. 从尾到头打印单链表
  1. // 从尾到头打印链表，使用栈  
  2. void RPrintList(ListNode * pHead)  
  3. {  
  4.     std::stack<ListNode *> s;  
  5.     ListNode * pNode = pHead;  
  6.     while(pNode != NULL)  
  7.     {  
  8.         s.push(pNode);  
  9.         pNode = pNode->m_pNext;  
  10.     }  
  11.     while(!s.empty())  
  12.     {  
  13.         pNode = s.top();  
  14.         printf("%d\t", pNode->m_nKey);  
  15.         s.pop();  
  16.     }  
  17. }
  19. //使用递归函数： 
  20. // 从尾到头打印链表，使用递归  
  21. void RPrintList(ListNode * pHead)  
  22. {  
  23.     if(pHead == NULL)  
  24.     {  
  25.         return;  
  26.     }  
  27.     else  
  28.     {  
  29.         RPrintList(pHead->m_pNext);  
  30.         printf("%d\t", pHead->m_nKey);  
  31.     }  
  32. }
6. 已知两个单链表pHead1 和pHead2 各自有序，把它们合并成一个链表依然有序
  1. // 合并两个有序链表  
  2. ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  
  3. {  
  4.     if(pHead1 == NULL)  
  5.         return pHead2;  
  6.     if(pHead2 == NULL)  
  7.         return pHead1;  
  8.     ListNode * pHeadMerged = NULL;  
  9.     if(pHead1->m_nKey < pHead2->m_nKey)  
  10.     {  
  11.         pHeadMerged = pHead1;  
  12.         pHeadMerged->m_pNext = NULL;  
  13.         pHead1 = pHead1->m_pNext;  
  14.     }  
  15.     else  
  16.     {  
  17.         pHeadMerged = pHead2;  
  18.         pHeadMerged->m_pNext = NULL;  
  19.         pHead2 = pHead2->m_pNext;  
  20.     }  
  21.     ListNode * pTemp = pHeadMerged;  
  22.     while(pHead1 != NULL && pHead2 != NULL)  
  23.     {  
  24.         if(pHead1->m_nKey < pHead2->m_nKey)  
  25.         {  
  26.             pTemp->m_pNext = pHead1;  
  27.             pHead1 = pHead1->m_pNext;  
  28.             pTemp = pTemp->m_pNext;  
  29.             pTemp->m_pNext = NULL;  
  30.         }  
  31.         else  
  32.         {  
  33.             pTemp->m_pNext = pHead2;  
  34.             pHead2 = pHead2->m_pNext;  
  35.             pTemp = pTemp->m_pNext;  
  36.             pTemp->m_pNext = NULL;  
  37.         }  
  38.     }  
  39.     if(pHead1 != NULL)  
  40.         pTemp->m_pNext = pHead1;  
  41.     else if(pHead2 != NULL)  
  42.         pTemp->m_pNext = pHead2;  
  43.     return pHeadMerged;  
  44. }
  46. //也有如下递归解法： 
  47. ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)  
  48. {  
  49.     if(pHead1 == NULL)  
  50.         return pHead2;  
  51.     if(pHead2 == NULL)  
  52.         return pHead1;  
  53.     ListNode * pHeadMerged = NULL;  
  54.     if(pHead1->m_nKey < pHead2->m_nKey)  
  55.     {  
  56.      pHeadMerged = pHead1;
  57.      pHeadMerged->m_pNext=MergeSortedList(pHead1->m_pNext,pHead2);  
  58.     }  
  59.     else  
  60.     {  
  61.      pHeadMerged = pHead2;  
  62.      pHeadMerged->m_pNext=MergeSortedList(pHead1,pHead2->m_pNext);  
  63.     }  
  64.     return pHeadMerged;  
  65. }
7. 判断一个单链表中是否有环
  1. bool HasCircle(ListNode * pHead)  
  2. {  
  3.     // 快指针每次前进两步
  4.     ListNode * pFast = pHead;
  5.     // 慢指针每次前进一步   
  6.     ListNode * pSlow = pHead;   
  7.     while(pFast != NULL && pFast->m_pNext != NULL)  
  8.     {  
  9.         pFast = pFast->m_pNext->m_pNext;  
  10.         pSlow = pSlow->m_pNext;  
  11.         if(pSlow == pFast) // 相遇，存在环  
  12.             return true;  
  13.     }  
  14.     return false;  
  15. }
8. 判断两个单链表是否相交

如果两个链表相交于某一节点，那么在这个相交节点之后的所有节点都是两个链表所共有的。也就是说，如果两个链表相交，那么最后一个节点肯定是共有的。先遍历第一个链表，记住最后一个节点，然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则不相交。时间复杂度为O(len1+len2)，因为只需要一个额外指针保存最后一个节点地址，空间复杂度为O(1)。参考代码如下： 

  1. bool IsIntersected(ListNode * pHead1, ListNode * pHead2)  
  2. {  
  3.     if(pHead1 == NULL || pHead2 == NULL)  
  4.         return false;  
  5.     ListNode * pTail1 = pHead1;  
  6.     while(pTail1->m_pNext != NULL)  
  7.         pTail1 = pTail1->m_pNext;  
  9.     ListNode * pTail2 = pHead2;  
  10.     while(pTail2->m_pNext != NULL)  
  11.         pTail2 = pTail2->m_pNext;  
  12.     return pTail1 == pTail2;  
  13. }
9. 求两个单链表相交的第一个节点

对第一个链表遍历，计算长度len1，同时保存最后一个节点的地址。 对第二个链表遍历，计算长度len2，同时检查最后一个节点是否和第一个链表的最后一个节点相同，若不相同，不相交，结束。 两个链表均从头节点开始，假设len1大于len2，那么将第一个链表先遍历len1-len2个节点，此时两个链表当前节点到第一个相交节点的距离就相等了，然后一起向后遍历，知道两个节点的地址相同。 时间复杂度，O(len1+len2)。参考代码如下： 

  1. ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)  
  2. {  
  3.     if(pHead1 == NULL || pHead2 == NULL)  
  4.         return NULL;  
  6.     int len1 = 1;  
  7.     ListNode * pTail1 = pHead1;  
  8.     while(pTail1->m_pNext != NULL)  
  9.     {  
  10.         pTail1 = pTail1->m_pNext;  
  11.         len1++;  
  12.     }  
  14.     int len2 = 1;  
  15.     ListNode * pTail2 = pHead2;  
  16.     while(pTail2->m_pNext != NULL)  
  17.     {  
  18.         pTail2 = pTail2->m_pNext;  
  19.         len2++;  
  20.     }  
  22.     if(pTail1 != pTail2) // 不相交直接返回NULL  
  23.         return NULL;  
  25.     ListNode * pNode1 = pHead1;  
  26.     ListNode * pNode2 = pHead2;  
  27.         // 先对齐两个链表的当前结点，使之到尾节点的距离相等  
  28.     if(len1 > len2)  
  29.     {  
  30.         int k = len1 - len2;  
  31.         while(k--)  
  32.             pNode1 = pNode1->m_pNext;  
  33.     }  
  34.     else  
  35.     {  
  36.         int k = len2 - len1;  
  37.         while(k--)  
  38.             pNode2 = pNode2->m_pNext;  
  39.     }  
  40.     while(pNode1 != pNode2)  
  41.     {  
  42.         pNode1 = pNode1->m_pNext;  
  43.         pNode2 = pNode2->m_pNext;  
  44.     }  
  45.         return pNode1;  
  46. }
10. 已知一个单链表中存在环，求进入环中的第一个节点

首先判断是否存在环，若不存在结束。在环中的一个节点处断开（当然函数结束时不能破坏原链表），这样就形成了两个相交的单链表，求进入环中的第一个节点也就转换成了求两个单链表相交的第一个节点。参考代码如下： 

  1. ListNode* GetFirstNodeInCircle(ListNode * pHead)  
  2. {  
  3.     if(pHead == NULL || pHead->m_pNext == NULL)  
  4.         return NULL;  
  6.     ListNode * pFast = pHead;  
  7.     ListNode * pSlow = pHead;  
  8.     while(pFast != NULL && pFast->m_pNext != NULL)  
  9.     {  
  10.         pSlow = pSlow->m_pNext;  
  11.         pFast = pFast->m_pNext->m_pNext;  
  12.         if(pSlow == pFast)  
  13.             break;  
  14.     }  
  15.     if(pFast == NULL || pFast->m_pNext == NULL)  
  16.         return NULL;  
  18.     // 将环中的此节点作为假设的尾节点,将它变成两个单链表相交问题  
  19.     ListNode * pAssumedTail = pSlow;   
  20.     ListNode * pHead1 = pHead;  
  21.     ListNode * pHead2 = pAssumedTail->m_pNext;  
  23.     ListNode * pNode1, * pNode2;  
  24.     int len1 = 1;  
  25.     ListNode * pNode1 = pHead1;  
  26.     while(pNode1 != pAssumedTail)  
  27.     {  
  28.         pNode1 = pNode1->m_pNext;  
  29.         len1++;  
  30.     }  
  32.     int len2 = 1;  
  33.     ListNode * pNode2 = pHead2;  
  34.     while(pNode2 != pAssumedTail)  
  35.     {  
  36.         pNode2 = pNode2->m_pNext;  
  37.         len2++;  
  38.     }  
  40.     pNode1 = pHead1;  
  41.     pNode2 = pHead2;  
  42.     // 先对齐两个链表的当前结点，使之到尾节点的距离相等  
  43.     if(len1 > len2)  
  44.     {  
  45.         int k = len1 - len2;  
  46.         while(k--)  
  47.             pNode1 = pNode1->m_pNext;  
  48.     }  
  49.     else  
  50.     {  
  51.         int k = len2 - len1;  
  52.         while(k--)  
  53.             pNode2 = pNode2->m_pNext;  
  54.     }  
  55.     while(pNode1 != pNode2)  
  56.     {  
  57.         pNode1 = pNode1->m_pNext;  
  58.         pNode2 = pNode2->m_pNext;  
  59.     }  
  60.     return pNode1;  
  61. }
11. 给出一单链表头指针pHead和一节点指针pToBeDeleted,O(1)时间复杂度删除节点pToBeDeleted

对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)。参考代码如下： 

  1. void Delete(ListNode * pHead, ListNode * pToBeDeleted)  
  2. {  
  3.     if(pToBeDeleted == NULL)  
  4.         return;  
  5.     if(pToBeDeleted->m_pNext != NULL)  
  6.     {  
  7.        // 将下一个节点的数据复制到本节点，然后删除下一个节点 
  8.         pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey; 
  9.         ListNode * temp = pToBeDeleted->m_pNext;  
  10.         pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;  
  11.         delete temp;  
  12.     }  
  13.     // 要删除的是最后一个节点 
  14.     else 
  15.     {  
  16.        // 链表中只有一个节点的情况  
  17.         if(pHead == pToBeDeleted) 
  18.         {  
  19.             pHead = NULL;  
  20.             delete pToBeDeleted;  
  21.         }  
  22.         else  
  23.         {  
  24.             ListNode * pNode = pHead;  
  25.            // 找到倒数第二个节点
  26.             while(pNode->m_pNext != pToBeDeleted)   
  27.                 pNode = pNode->m_pNext;  
  28.             pNode->m_pNext = NULL;  
  29.             delete pToBeDeleted;  
  30.         }     
  31.     }  
  32. }
12. 将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表。

问题解答： 算法思想：首先，按顺序不断取下两个顺序表表头较小的结点存入新的顺序表中。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。

  1. bool Merge(SeqList A, SeqList B, SeqList &C){
  2.     //合并有序顺序表A与B成为一个新的有序顺序表C
  3.     if(A.length+B.length>C.maxSize)  //大于顺序表的最大长度
  4.         return false;
  5.     int i=0,j=0,k=0;
  6.     while(i<A.length && j<B.length){
  7.         //循环，两两比较，小者存入结果表
  8.         if(A.data[i] < B.data[j])
  9.             C.data[k++] = A.data[i++];
  10.         else
  11.             C.data[k++]=B.data[j++];
  12.     }
  13.     while(i<A.length)  //还剩一个没有比较完的顺序表
  14.         C.data[k++] =A.data[i++];
  15.     while(j<B.length)
  16.         C.data[k++] = B.data[j++];
  17.     C.length=k;
  18.     return true;
  19. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注