接著上次的內(nèi)容，我們繼續(xù)！

還是無頭單向非循環(huán)鏈表。假如要刪除某個節(jié)點，如何實現(xiàn)？

//刪除成功返回0，失敗返回-1 int slist_del(struct node_info *node, struct slist_info *info) {assert(info != NULL && node != NULL);assert(!slist_is_empty(info));if(node==info->first)//如果要刪除的就是第一個節(jié)點{info->first = node->next;free(node);return 0;}//如果不是第一個，那么是哪個呢？要刪除必須先找到，可是找到就可以了嗎？//因為是單向鏈表，我們只能知道這個節(jié)點的后面那個，而不知道前面是誰，那怎么刪除呢？//所以，在遍歷的過程中，還要把前面的一個節(jié)點保存起來 else{struct node_info *pre = info->first;struct node_info *cur = pre->next;while(cur!=NULL&&cur!=node){pre = pre->next;cur = cur->next;}if(cur==NULL)return -1; // the node to delete is not in the listpre->next = cur->next;//deletefree(cur);return 0;}}
假設(shè)有個程序員很粗心，讓最后一個節(jié)點的next指針指向了鏈表中的某一個節(jié)點，你能檢查出來嗎？

1----2----3----4----5----6----7----8----9

? ? ? ? ? ? ? ? ? ? ? ? ? ?| ? ? ? ? ? ? ? ? ? ? ? ? ? |

? ? ? ? ? ? ? ? ? ? ? ? ? ?|----------------------|

比如這個圖，1是第一個，9的后面是5，構(gòu)成了一個環(huán)。

思路是這樣的：假設(shè)2個人，一個人每次走1步，另一個每次走2步。同時出發(fā)，如果有環(huán)存在，那么這兩個人肯定會相遇的！因為兩個人都要在圈里面繞，步長差1，那么快的那個肯定會追趕慢的那個，總會追上的！------此思路我們稱為“追趕法”！

int slist_is_dead_loop(struct slist_info *info) {assert(info != NULL);assert(!slist_is_empty(info));assert(info->first->next!=NULL);//節(jié)點數(shù)不少于兩個struct node_info *slow = info->first;struct node_info *fast = info->first;while (fast!= NULL && fast->next != NULL) { //che 2014.4.28fast = fast->next->next;slow = slow->next;if (fast == slow) {break;//相遇}}if (fast != slow) {return 0; //無死環(huán)}//此時相遇。怎么求環(huán)的長度呢？//fast固定，每次移動1步slow,再次相遇的時候，移動的步數(shù)就是環(huán)的長度int step = 1;slow = slow->next;while(fast!=slow){slow = slow->next;++step;}printf("the circle = %d\n",step);//怎么求環(huán)前面那段鏈子的長度？
O----------------------------------------E-----------------------A-------

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? |------------------------------- |

如圖，假設(shè)E點是環(huán)的起點，設(shè)OE長為x,環(huán)的長度是L.

我們安排一個場景，甲乙兩個人，乙先出發(fā)，走到A點時候，甲出發(fā)了，兩個人的速度是一樣的，在E點的時候，兩人相遇了！這時候甲走的步數(shù)就是鏈子的長度！問題是A點是哪里呢？

我們可以列出等式 ? x+L = 乙先走的（OA）+乙后走的(也就是甲走的x)

所以，OA=L

也就是說，先讓乙走L步，然后兩個人都走，相遇的時候，甲走的就是所求，接著上面的代碼

//設(shè)環(huán)的長度為L,讓兩個人都回到起點，先讓P2向前走L步。//然后p1,p2每次往前走一步，當(dāng)他們相遇的時候，p1移動的步數(shù)就是所求fast = slow = info->first;while(step--)fast = fast->next; //P2向前走L步step = 0;while(fast!=slow){slow = slow->next;fast = fast->next;++step;}printf("the line = %d\n",step);//鏈子的長度return 1; //有死環(huán) }

關(guān)于測試代碼，下次再說。 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

總結(jié)

以上是生活随笔為你收集整理的C语言实现通用链表初步(二)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。