鏈表

轉載自：http://blog.csdn.net/xubin341719/article/details/7091583/

最近不是太忙，整理些東西，工作也許用得到。

1，為什么要用到鏈表

數組作為存放同類數據的集合，給我們在程序設計時帶來很多的方便，增加了靈活性。但數組也同樣存在一些弊病。如數組的大小在定義時要事先規定，不能在程序中進行調整，這樣一來，在程序設計中針對不同問題有時需要3 0個大小的數組，有時需要5 0個數組的大小，難于統一。我們只能夠根據可能的最大需求來定義數組，常常會造成一定存儲空間的浪費。

我們希望構造動態的數組，隨時可以調整數組的大小，以滿足不同問題的需要。鏈表就是我們需要的動態數組。它是在程序的執行過程中根據需要有數據存儲就向系統要求申請存儲空間，決不構成對存儲區的浪費。

鏈表是一種復雜的數據結構，其數據之間的相互關系使鏈表分成三種：單鏈表、循環鏈表、雙向鏈表，下面將逐一介紹。

2，單向鏈表

單鏈表有一個頭節點head，指向鏈表在內存的首地址。鏈表中的每一個節點的數據類型為結構體類型，節點有兩個成員：整型成員（實際需要保存的數據）和指向下一個結構體類型節點的指針即下一個節點的地址（事實上，此單鏈表是用于存放整型數據的動態數組）。鏈表按此結構對各節點的訪問需從鏈表的頭找起，后續節點的地址由當前節點給出。無論在表中訪問那一個節點，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節點由于無后續節點，其指針域為空，寫作為NULL。

上圖還給出這樣一層含義，鏈表中的各節點在內存的存儲地址不是連續的，其各節點的地址是在需要時向系統申請分配的，系統根據內存的當前情況，既可以連續分配地址，也可以跳躍式分配地址。

（1），鏈表節點的數據結構定義

在鏈表節點的定義中，除一個整型的成員外，成員p是指向與節點類型完全相同的指針。

在鏈表節點的數據結構中，非常特殊的一點就是結構體內的指針域的數據類型使用了未定義成功的數據類型。這是在C中唯一規定可以先使用后定義的數據結構。

單鏈表的創建過程有以下幾步：

1 ) 定義鏈表的數據結構;

2 ) 創建一個空表;

3 ) 利用malloc ( )函數向系統申請分配一個節點;

4 ) 將新節點的指針成員賦值為空。若是空表，將新節點連接到表頭；若是非空表，將新

節點接到表尾;

5 ) 判斷一下是否有后續節點要接入鏈表，若有轉到3 )，否則結束;

單鏈表的輸出過程有以下幾步

1) 找到表頭;

2) 若是非空表，輸出節點的值成員，是空表則退出;

3 ) 跟蹤鏈表的增長，即找到下一個節點的地址;

4) 轉到2 ).

（3），程序代碼例子：

創建一個存放正整數單鏈表，輸入0或小于0的數，結束創建鏈表，并打印出鏈表中的值，程序如下：

在鏈表的創建過程中，鏈表的頭指針是非常重要的參數。因為對鏈表的輸出和查找都要從鏈表的頭開始，所以鏈表創建成功后，要返回一個鏈表頭節點的地址，即頭指針。

程序執行流程：