数据结构学习之链表小结

在任何一本数据结构的书中，都会详细的谈论很多数据结构，比如，线形表，树，图... 而实际项目中，最常用的莫过于数组和链表，以及树（最多的还是二叉树），最近对数据结构复习了一阵， 对链表做一个小结。（以下代码都是C语言实现，由于只是小结，仅对单链表做处理） 链表的基本结构如下： typedef struct node {     int           data;     struct node*  next; }Node; 其中data是一个Type类型的数据，next是指向下一个Node的一个指针，具体如下图所示  -------            ------ | data |         | data |  ------             ------ | next |----->| next | ----> ..... -------            ------ 当然，有些时候为了保证链表的通用型， #define Type int 用Type代替数据的类型，有时候为了想把不同数据都放到一个链表中来，可以考虑把Type 改称 void*， 即 #define Type void * 这样的好处就是，有一个data的指针，可以指向任何类型的数据或者一段内存,当然，对于内存分配， 一定要注意malloc和free（或者用new和delete） 首先我们来看一段代码，计算链表的长度： int  length(Node  * head) ... {      int i=0;          /**//*统计链表的长度*/      Node *p=head;     /**//*用一个指针指向链表的头*/        if (p==NULL)                  return 0;      while (p != NULL)...{             i++;                       p=p->next;      }      return i;      /**//* 返回链表的长度*/} 下面一段代码是往链表里添加加数据，数据在链表头部加入新数据。 类似往栈里压数据一样。 void  Push(Node  ** headRef, int  newData) ... {      Node *head=*headRef;      Node *pNode=(Node*)malloc(sizeof(Node));      if (!pNode)           return NULL;      pNode->data=newData;      pNode->next=head;      *headRef=pNode;} 以下是关于链表的操作的一些代码小结，部分来自网路。 /**/ /* *1.Count(),给定一个链表，和一个整型的数据，返回在这个链表中这个数据出现的个数 */ int  Count(Node *  head,  int  searchFor) ... {      int i=0;      Node *p=head;      if (p==NULL)            return 0;      while(p!=NULL)...{             if (p->data == searchFor)...{                   i++;            }            p=p->next;      }      return i;} /**/ /* *2.GetNth(),给定一个链表和一个下标n，返回链表中第n个数据 *给定下标的范围是0-(length-1) */ int  GetNth(Node  * head, int  index) ... {      Node *current=head;      int count=0;      while (current!=NULL)...{             if (count==index)                    return current->data;             count++;             curent=current->next;      }      assert(0); //没有找到合适的元素，则报错} /**/ /* *3.DeleteList(),删除链表 */ void  DeleteList(Node  ** headRef) ... {      Node *p=*headRef;      while (p!=NULL)...{              *headRef=(*headRef)->next;              free(p);              p=*headRef;      }      return;} /**/ /*  *4.Pop(),弹出一个数据，也就是对于非空链表，移出头结点，并返回这个结点的数据 */ int  Pop(Node  ** headRef) ... {      int data;      Node *p=*headRef;      assert(p!=NULL);      *headRef=p->next;      data=p->data;      free(p);      return data;} /**/ /* *5.InsertNth()，给定链表，插入的位置以及相应的数据，在链表的该位置插入相应的数据 */    void  InsertNth(Node  ** headRef, int  index,  int  data) ... {      if (index==0)            Push(headRef,data);      else...{            Node *current=*headRef;            int i;            for(i=0;i<index-1;i++)... {                  assert(current!=NULL); //如果失败，当前的下标太大了                 current=current->next;            }        assert(current!=NULL);       //检查当前结点是否为空      Push(&(current->next),data); //调用push(),在下一个节点的前面插入数据。      }        }     /**/ /* *6.SortedInsert()，给定一个排好序的单链表，在合适的位置插入一个新节点，保证链表的顺序性 */ void  SortedInsert(Node  ** headRef,Node  * newNode) ... {      Node *p=*headRef;      if (p==NULL || newNode->data <= p->data)...{             newNode->next=p;             *headRef=newNode;      }      else...{              while (p->next!=NULL  &&  p->next->data < newNode->data) ...{                     p=p->next;             }      newNode->next=p->next;      p->next=newNode;     }} /**/ /* *7.InsertSort()，给定一个链表，对链表进行排序，使之成为一个有序的链表 */ void  InsertSort(Node  ** headRef) ... {      Node *p=*headRef,*NewHead=NULL;      if (p==NULL)             return;         while (p!=NULL)... {            SortedInsert(&NewHead,p);            p=p->next;      }      *headRef=NewHead;} /**/ /* *8.Append(),给定两个链表的头，将两个链表连起来 */ void  Append(Node  ** aRef,Node  ** bRef) ... {      Node *current;      if (*aRef==NULL)             *aRef=*bRef;         else...{              current=*aRef;              while (current->next != NULL)... {                    current=current->next;              }              current->next=*bRef;      }      *bRef=NULL;} /**/ /* *9.FrontBackSplit(),给定一个链表，和另外两个结点，使这2个节点分别指向链表的头和尾 */ void  FrontBackSplit(Node  * source,Node  ** frontRef,Node  ** backRef) ... {      Node *p,*p1;      p=p1=source;      *frontRef=source;      *backRef=NULL;      if (p==NULL||p->next==NULL)            return;         while (p1->next!=NULL)...{            p1=p1->next;               if (p1->next!=NULL)...{                  p1=p1->next;                  p=p->next;            }      }      *backRef=p->next;      p->next=NULL;} /**/ /* *10.RemoveDuplicates(),从一个已排序的链表中删除重复的结点 */ void  RemoveDuplicates(Node  * head) ... {      Node *p1,*p2;      p1=head;      if (p1==NULL||p1->next==NULL)             return;         while(p1->next!=NULL)...{             if(p1->data==p1->next->data)...{                    p2=p1->next->next;                    free(p1->next);                    p1->next=p2;             }            else                   p1=p1->next;      }} /**/ /* *11.MoveNode()，两个链表的头节点，把其中的一个链表的头节点移动到另外一个链表的头 */ void  MoveNode(Node  ** destRef,Node  ** sourceRef) ... {     int data;      Node *p=*sourceRef;      if (p==NULL)...{             sprintf(stderr,"Error!Source list is empty ");             return;      }      *sourceRef=p->next;         p->next=*destRef;      *destRef=p;} /**/ /* *12.AlternatingSplit(),将给定的一个链表划分成两个链表，奇数号在一个链表aRef，偶数在bRef */ void  AlterNatingSplit(Node  * source,Node  ** aRef,Node  ** bRef) ... {      Node *a=NULL;      Node *b=NULL;      Node *current=source;      while (current!=NULL)...{              MoveNode(&a,&current);              if (current!=NULL)...{                    MoveNode(&b,&current);              }       }       *aRef=a;       *bRef=b;} /**/ /* *13.ShuffleMerge()，将两个链表合成一个链表，返回新链表的头 */ Node  * ShuffleMerge(Node  * a,Node  * b) ... {      Node *pMerg=NULL;      if (a==NULL)          return b;      else if ( b==NULL)          return a;      else...{          while (a!=NULL&&b!=NULL)...{              MoveNode(&pMerg,&a);              pMerg=pMerg->next;              MoveNode(&pMerg,&b);              pMerg=pMerg->next;         }         if (a==NULL)              pMerg=b;         else if(b==NULL)              pMerg=a;      }      return pMerg;} /**/ /*递归进行合并两个队列 */ Node  * Recursive ShuffleMerge(Node  * a,Node  * b) ... {      Node *result;      Node *recur;      if (a==NULL)            return b;   //如果链表a为空就返回b      else if(b==NULL)            return a;   //如果b为空，返回a      else...{            recur= Recursive ShuffleMerge(a->next,b->next);//递归调用每个节点的下一个节点；            result=a;              //对两个链表的头节点进行处理            a->next=b;            b->next=recur;                   return result;      }} /**/ /* *14.SortedMerge(),将两个排好序的链表合成一个有序链表（为递增链表） */ Node  * SortedMerge(Node  * a,Node  * b)  // 非递归算法 ... {      Node *result=NULL;      Node **lastPtrRef=&result;//指向新链表的头地址      while (1)...{            if (a==NULL)...{                  *lastPtrRef=b;                  break;             }            else if(b==NULL)...{                   *lastPtrRef=a;                   break;            }               if (a->data<=b->data)...                   MoveNode(lastPtrRef,&a);               else...                   MoveNode(lastPtrRef,&b);                lastPtrRef=&((*lastPtrRef)->next); //对下一个节点进行处理      }      return result;} Node  * Recursive SortedMerge(Node  * a,Node  * b) // 递归合成链表 ... {      Node *result;      if (a==NULL) return b;      else if (b==NULL) return a;      if (a->data <= b->data)...{            result=a;            result->next= Recursive SortedMerge(a,b->next);      }      else...{            result=b;            result->next= Recursive SortedMerge(a->next,b);      }      return result;} /**/ /* *15.Mergesort(),对链表进行归并排序 */ void  MergeSort(Node  ** headRef) ... {      Node *p=headRef;      Node **aList,**bList;      if (p==NULL||p->next=NULL)            return;       FrontBAckSplit(p,aList,bList);       MergeSort(aList);       MergeSort(bList);       *headRef=SortedMerge(*aList,*bList);} /**/ /*16.SortedIntersect() *给定两个有序的链表，统计两个链表中相同的数据，将相同的元素放到新链表中，并返回 */ Node  * SortedIntersect(Node  * a,Node  * b) ... {      Node *result=NULL;      Node **lastPtrRef=&result;      //先比较两个链表的头，如果其中一个为空，则返回NULL      while (a!=NULL && b!=NULL)...{            if (a->data==b->data)...{ //找到一个相同的元素                  Push(lastPtrRef,a->data);                  lastPtrRef=&((&lastPtrRef)->next);                  a=a->next;                  b=b->next;            }            else if(a->data < b->data)...                  a=a->next;           else ...                  b=b->next;      }      return result;} /**/ /* *17.Reverse(),给定一个链表，将其反转，即顺序颠倒 */ void  Reverse(Node  ** headRef)    // 非递归算法 ... {      Node *result=NULL;      Node *current=*headRef;      Node *next;      while (current!=NULL)...{            next=current->next;           current->next=result;           result=current;              current=next;      }      *headRef=result;} void  RecursiveReverse(Node  ** headRef) // 递归算法 ... {      Node *p=*headRef,*pNext;      if (p==NULL ||p->next=NULL)            return;      pNext=p->next;         RecursiveReverse(&pNext);       p->next->next=p;      p->next=NULL;      *headRef=pNext;} /**/ /* *18.FindCircle(),判断链表中是否有环. *思路:运用两个指针，一个快指针，一个慢指针，当快的追上慢的，就表示有环 */ bool  FindCircle(Node *  pHead) ... {      if(pHead = = NULL || pHead->next = = NULL)//无节点或只有一个节点并且无自环            return  false;      if(pHead->next = = pHead)//自环            return  true;       Node *pTemp1 = pHead;//step 1       Node *pTemp = pHead->next;//step 2       while(pTemp != pTemp1 && pTemp != NULL && pTemp->next != NULL)...{            pTemp1 = pTemp1->next;            pTemp = pTemp->next->next;       }       if(pTemp = = pTemp1)            return  true;    return  false;}