單鏈表之遍歷演算法精析

1、單鏈表的演算法之遍歷節點

1.1、什麼是遍歷

資料有存就肯定會有取，既然鍊錶是我們用來存有效資料的資料結構，那麼肯定要有從鍊錶中讀取資料的方法，這個方法就是遍歷鍊錶也就是把鍊錶中的各個節點挨個拿出來訪問。

遍歷的要點：不能遺漏，不能重複，效率要盡量高。

1.2、如何遍歷單鏈表

（1）分析乙個資料結構如何遍歷，關鍵是分析這個資料結構本身的特點，然後根據它的特點來定製它的遍歷演算法。

（2）單鏈表的特點就是它由很多個節點組成，頭指標加頭節點為整個鍊錶的起始，最後乙個節點的特徵是它內部的pnext指標值為null。從起始到結尾中間由各個節點內部的pnext指標來掛接。由起始到結尾的路徑有且只有一條。

（3）遍歷方法：從頭指標+頭節點開始，順著鍊錶的掛接指標依次訪問鍊錶的各個節點，取出當前訪問節點的資料，然後再訪問下乙個節點，直到最後乙個節點，結束返回。

（4）遍歷過程分析

第一步：指標p訪問第乙個有效節點並判斷此節點是否是尾節點，取出資料，指標p移動到下一

節點。第二步：判斷當前節點是否是尾節點，取出資料，移動到下一節點。

第三步：判斷當前節點是否是尾節點，發現它就是尾節點，取出資料，停止遍歷。

1.3、**分析

//遍歷單鏈表，ph為指向單鏈表的頭指標，將遍歷的節點資料列印出來void list_for_each_1(struct node*ph)

printf("node data:%d.\n",p->data);

printfendn");

}list_for_each_1()演算法在結束while迴圈後還要列印一次p->data，原因是

當p走到最後乙個節點的時候，p->pnext已經等於null了，所以不會進入迴圈體，因此尾節點的data並不會被列印出來，所以在退出迴圈後還要新增一行**來訪問尾節點的資料。

請接著看第二個遍歷演算法，它與第乙個演算法有什麼不同？

void list_for_each_2(struct node*ph)

printfendn");

}是不是發現僅僅是修改了指標p的初始位置並且交換了取出資料與移動指標的順序**就變的優美的許多？如果沒有頭結點的存在還能不能使用第二個遍歷演算法？顯然是不可以的，這樣的話我們就會漏掉第乙個節點的有效資料。

當我們寫出第二種演算法而不是第一種的時候是不是感覺渾身舒坦？這也是**的魅力之一。