链表的基本操作-白红宇

链表的基本操作

阅读量：5889 次

发布时间：2019-06-19

本文共 6590 字，大约阅读时间需要 21 分钟。

2013-08-17 16:26:51

再次写链表的基本操作，包括前插法创建链表、链表的插入、删除、排序、翻转、显示、销毁。

此次写的链表时带有头指针的，是否有头指针，对于链表的各个操作都会有影响，与之前写的不带头指针的链表相比，确实方便很多，不易出错。

小结：

对于带有头结点的链表，空链表（pHead->next= NULL）与头指针为NULL的链表(pHead = NULL)是不同的，后者是非法的链表，要当做异常处理；

函数入口对于异常输入的处理，比如下面代码中多个函数中的assert(pHead != NULL);排除了链表头结点为空的异常情况；

函数对于特殊输入的处理，比如插入、删除的位置大于链表长度，以及链表为空的处理；链表翻转时链表长度为空或1时直接返回即可；在函数开始时最好就对这些特殊的输入进行处理，以免遗漏；注意插入、删除的是第一个以及最后一个的情况

存放插入、删除的位置、链表长度的变量为size_t类型的，排除了非法的负数的情况，但也要注意这种做法带来的副作用，就是对于size_t类型的变量0-1的结果为最大的正数，而非负数，判断循环结束时，应注意到这个问题。

输入ctrl+z结束键盘输入后，要想再次从键盘接收输入，必须用cin.clear(); cin.sync();清楚流，否则不能接收输入

下面是完整的代码（包括测试）：

1 #include 
     
        2 #include 
      
         3 using namespace std;  4   5 typedef int DataType;  //链表元素类型  6   7 typedef struct node    //链表结点  8 {  9     DataType data; 10     node *next; 11  12 }LNode,*PLNode; 13  14 //创建带有头结点的链表 15 //输入ctrl+z结束 16 //有无头结点将会影响到对链表的所有操作，包括显示链表元素、插入、删除、销毁等 17 PLNode CreatLink() 18 { 19     PLNode pHead = new LNode;  //注意delete 20     PLNode pPre = pHead; 21     PLNode pCur = NULL; 22     pHead->data = 0;        //空头 23     pHead->next = pCur; 24  25     DataType dataTmp = 0; 26  27     cout<<"Please enter the elements of the link  ,separate with space,and end with ctrl+z :"<
       
        >dataTmp) 29     { 30         pCur = new LNode; 31         pCur->data = dataTmp; 32         pCur->next = NULL; 33  34         pPre->next = pCur; 35         pPre = pCur; 36     } 37  38     return pHead; 39 } 40  41 //创建不带头结点的链表 42 //输入ctrl+z结束 43 PLNode CreatLinkWithNonNullHead() 44 { 45     PLNode pHead = NULL;  //delete 46     PLNode pPre = NULL; 47     PLNode pCur = NULL; 48      49     DataType dataTmp = 0; 50  51     cout<<"Please enter the elements of the link  ,separate with space,and end with ctrl+z :"<
        
         >dataTmp) 53     { 54         pCur = new LNode; 55         pCur->data = dataTmp; 56         pCur->next = NULL; 57  58         if (NULL == pHead)   //对头的特别处理 59         { 60             pHead = pCur; 61             pPre = pCur; 62         } 63         else 64         { 65             pPre->next = pCur; 66         } 67         pPre = pCur; 68     } 69     return pHead; 70 } 71  72 //对头结点为pHead的链表，在位置posToInsert处插入元素dataToInsert 73 //posToInsert定义为size_t类型，排除了位置为负数的异常输入 74 //注意对输入位置超过链表长度的处理 75 PLNode InsertLink(PLNode &pHead,size_t posToInsert,const DataType dataToInsert) 76 { 77     assert(pHead != NULL); 78  79     PLNode pCur = pHead; 80     PLNode pNew = new LNode; 81     pNew->data = dataToInsert; 82     pNew->next = NULL; 83  84     while (posToInsert--) 85     { 86         //assert(pCur != NULL);  //保证不超过链表长度 87         pCur = pCur->next; 88         assert(pCur != NULL);  //保证不超过链表长度，放在前面当posToInsert减到0时会出错 89     } 90  91     pNew->next = pCur->next; 92     pCur->next = pNew; 93  94     return pHead; 95 } 96  97 //删除结点指针指向的元素，未测试 98 PLNode InsertLinkAtNode(PLNode &pHead,const PLNode pPosToInsert,const DataType dataToInsert) 99 {100     assert(pHead != NULL);101 102     PLNode pCur = pHead;103     PLNode pNew = new LNode;104     pNew->data = dataToInsert;105     pNew->next = NULL;106 107     while (pCur != pPosToInsert)108     {109         assert(pCur != NULL);  //保证不超过链表长度110         pCur = pCur->next;111     }112 113     pNew->next = pCur->next;114     pCur->next = pNew;115 116     return pHead;117 }118 119 //对头结点为pHead的链表，在位置posToInsert处插入元素dataToInsert120 //posToInsert定义为size_t类型，排除了位置为负数的异常输入121 //注意对输入位置超过链表长度的处理122 PLNode DeleteLink(PLNode &pHead,size_t posToDelete)123 {124     assert(pHead != NULL);125 126     if (0 == posToDelete)127     {128         return pHead;129     }130 131     PLNode pCur = pHead;132     PLNode pNodeToDelete = NULL;133     size_t posPriorToDelete = posToDelete - 1;134 135     while (posPriorToDelete--)136     {137         pCur = pCur->next;138         assert(pCur != NULL);  //保证不超过链表长度，放在前面当posToInsert减到0时会出错139     }140 141     pNodeToDelete = pCur->next;142     assert(pNodeToDelete != NULL);  ////保证不超过链表长度143     pCur->next = pNodeToDelete->next;144     delete pNodeToDelete;145     return pHead;146 }147 148 //获取链表长度149 size_t GetLengthOfLink(PLNode pHead)150 {151     assert(NULL != pHead);152 153     size_t lengthOfLink = 0;154     PLNode pCur = pHead;155 156     while (NULL != pCur->next)157     {158         ++lengthOfLink;159         pCur = pCur->next;160     }161 162     return lengthOfLink;163 }164 165 //冒泡法最链表元素排序166 PLNode BubbleSortLink(PLNode &pHead)167 {168     assert(NULL != pHead);169     170     PLNode pCur = pHead->next;171     172     size_t lengthOfLink = GetLengthOfLink(pHead);  173     size_t tmp = 0;174     int i = (int)lengthOfLink; //定义为int型，在lengthOfLink为0时，lengthOfLink--为-1175     int j = 0;176 177     while (i-- > 1)178     {179         pCur = pHead->next;  //每次都指向第一个结点180         j = i;181         /*while (j--)*/182         while (j-- > 0)183         {184             if (pCur->data > pCur->next->data)185             {186                 tmp = pCur->data;187                 pCur->data = pCur->next->data;188                 pCur->next->data = tmp;189             }190 191             pCur = pCur->next;192         }193     }194     return pHead;195 }196 197 //链表元素翻转198 PLNode ReverseLink(PLNode &pHead)199 {200     assert(NULL != pHead);201 202     if (NULL == pHead->next || NULL == pHead->next->next)  //短路求值的特性保证pHead->next->next不会因为pHead->next == NULL而非法操作203     {204         return pHead;205     }206     207     PLNode pPre = pHead->next;  //上面的if保证此处的访问都是合法的208     PLNode pCur = pPre->next;209     PLNode pNxt = NULL;210 211     pPre->next = NULL;  //此时pPre为翻转后链表的最后一个结点，将next置为NULL212 213     while (pCur != NULL)214     {215         pNxt = pCur->next;216         pCur->next = pPre;  //指正方向翻转217 218         pPre = pCur;219         pCur = pNxt;220     }221 222     //pHead = pPre;223     pHead->next = pPre;224     return pHead;225 }226 227 //显示有头结点的链表的元素228 void Displaylink(const PLNode &pHead)229 {230     assert(pHead != NULL);231     PLNode pCur = pHead->next;232     while (pCur != NULL)233     {234         cout<
         
          data<<"\t";235         pCur = pCur->next;236     }237     cout<
          
           data<<"\t";247 pCur = pCur->next;248 }249 cout<
           
            next;257 while (pCur != NULL)258 {259 delete pHead; //删除头结点260 pHead = pCur;261 pCur = pCur->next;262 }263 }264 265 //测试链表操作266 //除了作为比较的建立链表操作，链表的所有操作都基于带有头结点的链表267 //因为带有头结点的链表在各种操作上都会比较方便268 void Testlink()269 {270 PLNode pHead = NULL;271 272 //Test CreatLinkWithNullHead...273 cout<<"Test CreatLink..."<
            
             >posToInsert>>dataToInsert)287 {288 cout<<"The link before insertion : "<
             
              >posToDelete)306 //{307 // cout<<"The link before insertion : "<