1.單鏈表的整表創建

順序存儲結構的創建，其實就是一個數組的初始化，即聲明一個類型和大小的數組并賦值的過程。而單鏈表和順序存儲結構就不一樣，他不像順序存儲結構那么集中，他可以很分散，是一種動態結構。對于每個鏈表來說，它所占用空間的大小和位置是不需要預先分配劃定的，可以根據系統的情況和實際的需求即時生成。

所以，創建單鏈表的過程就是一個動態生成鏈表的過程。即從“空表”的初始狀態起，一次建立各元素結點，并逐個插入鏈表。

單鏈表整表創建的算法思路：

(1)聲明一節點p和計數器變量i;

(2)初始化一空鏈表L;

(3)讓L的頭結點的指針指向NULL，即建立一個帶頭結點的單鏈表；

(4)循環：生成一新結點賦值給P; 隨機生成一數字賦值給p的數據域p->data; 將p插入到頭結點與前一個新節點之間(頭插法)。

頭插法實現代碼算法：

事實上，我們也可以不這樣做。為什么不把新節點都放在最后呢？這種應該說才是排隊的正常思維，及先來后到。這種方法又稱為“尾插法”。

實現代碼算法如下：

void CteateListTail( LinkList* L, int n)
{
LinkList p,r;
int i;
srand( time(0) );
*L = (LinkList) malloc ( sizeof(Node) );
r = *L;
for (i=0; i<n; i++)
{
p = (Node*)malloc( sizeof (Node) );
p->data = rand()%100+1;
r->next = p;
r = p; //保證r代表最后的結點
}
r->next = NULL;
}

2.單鏈表的整表刪除

當我們不打算使用這個單鏈表時，我們需要把它銷毀，其實也就是在內存中將他釋放掉，以便于留出空間給其他程序或軟件使用。
單鏈表整表刪除的算法思路如下：
(1)聲明一結點p和q;
(2)將第一個結點賦值給p;
(3)循環：將下一個結點賦值給q,釋放p，將q賦值給p。
實現代碼算法如下：

[cpp]?view plaincopy

<span?style="font-size:18px;">Status?ClearList（?LinkList*?L）??

{??

??????LinkList?p,q;??

??????p?=?(*L)->next;??

??????while(!p)??

??????{??

????????????q?=?p->next;??

????????????free(p);??

????????????p?=?q;??

???????}??

???????(*L)->next?=?NULL;??

????????return?OK;??

}</span>??

3.單鏈表結構與順序存儲結構優缺點

	單鏈表結構	順序存儲結構
存儲分配方式	采用鏈式存儲結構，用一組任意的存儲單元存放線性表元素	用一段連續的存儲單元一次存儲線性表的數據元素
時間性能	查找：O(n) 插入：O(1) 刪除：O(1)	查找：O(1) 插入：O(n) 刪除：O(n)
空間性能	不需要分配存儲空間，只要有就可以分配，元素個數也不受限制	需要預分配存儲空間，分配大了，浪費，分配小了，易發生上溢

經驗性的結論：

(1)當線性表需要頻繁查找，很少進行插入和刪除操作時，宜采用順序存儲結構。若需要頻繁插入和刪除操作時，宜采用單鏈表結構。比如說，游戲開發中，對于用戶注冊的個人信心，除了注冊時插入數據外，絕大多數情況都是讀取，所以應該老呂用順序存儲結構。而游戲的玩家的武器或者裝備列表，隨著玩家的游戲過程中，可能會隨時增加或刪除，此時再用順序存儲就不太合適，應該偏向使用單鏈表結構。 (2)當線性表中的元素個數變化較大或者根本不知道有多大時，最好用單鏈表結構，這樣可以不需要考慮存儲空間的大小問題。而如果事先知道線性表的大致長度，比如一年12個月，一周就是星期一至星期日共七天，這種用順序存儲結構效率會高很多。

4.循環鏈表

對于單鏈表，由于每個結點只存儲向后的指針，到了尾標志就停止了向后的操作。這樣，當中某一節點就無法找到它的前驅結點，難以查閱前方數據。

將單鏈表中終端結點的指針端由空指針改為指向頭結點，就使整個鏈表形成一個環，這種頭尾項鏈的單鏈表稱為單循環鏈表，簡稱循環鏈表。

其實，循環鏈表和單鏈表的主要差異就在于循環的判斷條件上，原來是判斷p->next = NULL??，現在則是判斷p->next是不是等于頭結點，若不等于，則循環未結束。

在單鏈表中，我們有了頭結點時，我們可以用O(1)的時間訪問第一個結點，但是對于要訪問的最后一個結點，卻要用O(n)時間，因為我們需要將單鏈表全部掃描一遍。

有沒有可能用O(1)的時間由鏈表指針訪問到最后一個結點呢？當然可以，不過我們需要改造一下這個循環鏈表，不用頭指針，而是用指向終端結點的尾指針來表示循環鏈表。

此時，查找開始結點和終端結點就很方便了。如果終端結點用尾指針rear指示，則查找終端節點是O(1)，而開始結點，其實就是rear->next->next，其時間復雜度也為O(1)。

5.雙向鏈表

在單鏈表中，有了next指針，這就使得我們要查找下一節點的時間復雜度為O(1)。可是，如果我們要查找的是上一節點的話，那最壞的時間復雜度就是O(n)，因為我們每次都要從頭開始遍歷查找。

為了克服鏈表單向性這一弊端，相關研究人員設計了雙向鏈表。雙向鏈表是在單鏈表的每個節點中，在設置一個指向其前驅結點的指針域。所以，在雙向鏈表中的結點都有兩個指針域，一個是指向直接后繼，一個是指向直接前驅。

總結

以上是生活随笔為你收集整理的大话数据结构:线性表(3)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。