第三章：線性表 - 鏈式存儲結構

• 前言
• 一、線性表的鏈式存儲結構是什么？
• • • 頭指針和頭結點的異同
    • 單鏈表存儲示意圖
    • 帶頭結點的單鏈表示意圖
    • 空鏈表示意圖
• 二、用結構指針描述單鏈表（C語言）
• • • 單鏈表的讀取
    • 單鏈表的插入和刪除
    • • 插入算法
      • 刪除算法
    • 單鏈表的創建
    • • 頭插法（少用）
      • 尾插法（常用）
    • 單鏈表的整表刪除
  • 三、簡單對比鏈式存儲和順序存儲
• 后言

---

前言

在學習了 第一章 - 初識數據和結構 、第二章 - 初識算法 、第三章 - 線性表的順序存儲結構 之后，今天我們來學習一下線性表的鏈式存儲（單鏈表）！

一、線性表的鏈式存儲結構是什么？

特點：用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以是連續的，也可以是不連續的。

和順序存儲結構不同，鏈式結構除了要存放數據元素信息外，還要存儲它的直接后繼元素的存儲地址

這里介紹兩個概念：

數據域：存儲數據元素信息的域

指針域：存儲直接后繼位置的域,其中存儲的信息稱為指針或鏈

這兩部分信息組成數據元素 ai 的存儲映像，稱為結點（Node）

n 個結點 ( ai 的存儲映像) 鏈結成一個鏈表，即為線性表（ a1 a2,…, an） 的鏈式存儲結構，此鏈表的每個結點中只包含一個指針域，所以叫做單鏈表

頭指針：鏈表中第一個結點的存儲位置 一般最后一個結點指針為NULL

為了方便操作，會在單鏈表第一個結點前附設一個結點， 稱為頭結點，頭結點的數據域可以不存儲任何信息，也可以存儲線性表長度等附加信息。

頭指針和頭結點的異同

頭指針頭結點

是鏈表指向第一個結點的指針，若鏈表有頭指針，則指向頭結點的指針	放在第一元素的結點之前，數據域一般無意義（也可存放鏈表的長度）
無論鏈表是否為空，頭指針均不為空	頭結點不是鏈表的必須要素
頭指針具有標識作用，所以常用頭指針冠以鏈表的名字

單鏈表存儲示意圖

帶頭結點的單鏈表示意圖

空鏈表示意圖

二、用結構指針描述單鏈表（C語言）

// 線性表的單鏈表存儲結構 //含有自定義變量，需要加上前幾章的define才能運行 typedef struct Node{ElemType data;struct Node *next; }Node; typedef struct Node *LinkList; //定義LinkList

這里我們知道，結點由存放數據元素的數據域和存放后繼結點地址的指針域組成。

結點 ai 的數據域可以用 p-data 表示結點 ai 的指針域可以用 p->next 表示

如果 p->data =ai，那 p->next->data 則=ai+1,如下圖

單鏈表的讀取

思路：

聲明一個結點 p 指向鏈表第一個結點，初始化 j 從1開始；

當 j<i 時，遍歷鏈表，讓 p 的指針向后移動，不斷指向下一個結點，j 累加1；

若看到鏈表末尾 p 為空，則說明第 i 個元素不存在；

否則查找成功，返回結點 p 的數據；

實現代碼算法如下：

// 初始條件：順序線性表L已存在，1<=i<=ListLength(L) // 操作結果：用e返回L中第i個數據元素的值 Status GetElem(LinkList L,int i,ElemType *e){int j; //j為計數器LinkList p; //聲明結點pp = L->next; //L為頭指針，p為頭結點地址j = 1;while(p && j<i){ //p不為空或者計數器小于目標值i時 p = p->next; //p指向下一結點++j;}if( !p || j>i ) //第一個元素不存在，j>i 明顯是為了在while未執行的情況下判斷變量 i 是否小于1（略有多余但使得該算具有健壯性）return ERROR;*e = p->data; //取值并返回return OK; }

單鏈表結構沒有定義表長，不能事先知道要循環多少次，因此更適合用while來控制循環。
由代碼可見，數據的讀取時間復雜度為O（n）

---

單鏈表的插入和刪除

插入思想：先接上尾部，再接上頭部，如下圖

核心思想：s ->next = p->next；p->next = s;（順序不可換）

插入算法

//初始條件：順序線性表L已存在，1<=i<=ListLength(L) //操作結果：在L中第i個位置之前插入新的數據元素e，L的長度加1 Status ListInsert(LinkList *L,int i,ElemType e){int j;LinkList p,s;p = *L;j = 1;while(p && j<i){ //尋找第i個結點 ,可以插在頭結點之后、第一個結點之前==相當于放在第一位p = p->next;++j;}if(!p || j>i)return ERROR;s = (LinkList)malloc(sizeod(Node)); //生成新結點,返回類型為LinkList類型，分配的大小為sizeof(Node)s->data = e;s->next = p->next; //接尾巴p->next = s; //接頭return OK; }

malloc函數：動態分配內存，生成一個新的結點，類型與Node結構一樣( LinkList是Node的實現 )

---

刪除算法

刪除思想：記下 p->next 為 q ，重新記錄 p->next =q->next

核心思想：q=p->next; p - >next=q- >next ;

//初始條件：順序線性表L已存在，1<=i<=ListLength(L) //操作結果：刪除L中第i個數據元素，并用e返回其值，L的長度減1 Status ListDelete(LinkList *L,int i,ElemType *e){int j;LinkList p,q;p = *L;j = 1;while(p->next && j<i){ //尋找第i個結點,只能從第一個結點開始刪除，不得刪除頭結點，也不得刪除空結點，要下一項存在才能取下一項p = p->next;++j;}if(!（p->next） || j>i) //這里p->next 的意思是，若空，則！空==真return ERROR; //j>i,在找到尾部還沒找到，此時j+1就會比i大，所以可以判斷第i個元素不存在q = p->next; //記錄中間值p->next = q->next; //接上尾巴*e = q->data;free(q); //系統回收此結點，釋放內存return OK; }

---

單鏈表的創建

單鏈表是一種動態結構，所占空間的大小和位置都不需要預先分配，可根據系統的情況和實際的需求即時生成。

頭插法（少用）

代碼算法如下：在頭結點和首結點之間插入

// 隨機產生n個元素的值，建立帶頭結點的單鏈線性表L void CreateListHead(LinkList *L,int n){LinkList p;srand(time(0)); //設置隨機函數種子為系統時間,種子不同產生的隨機數不同*L = (LinkList)malloc(sizeof(Node)); //分配內存給頭結點L(*L)->next = NULL;for(int i=0;i<n;i++){p = (ListList)malloc(sizeof(Node));p->data = rand()%100+1; //隨機生成100以內的數字p->next = (*L)->next; //接尾巴(*L)->next = p; //接頭} }

尾插法（常用）

將新結點都放在最后面，符合排隊思維（先來后到）

代碼算法如下：

// 隨機產生n個元素的值，建立帶頭結點的單鏈線性表L void CreateListTail(LinkList *L,int n){LinkList p,r;srand(time(0)); //設置隨機函數種子為系統時間,種子不同產生的隨機數不同*L = (LinkList)malloc(sizeof(Node)); //分配內存給頭結點Lr=*L; //r為指向尾部的結點for(int i=0;i<n;i++){p = (Node*)malloc(sizeof(Node));p->data = rand()%100+1; //隨機生成100以內的數字r->next = p; //先接頭r = p; //在移動尾部指標結點r到最新尾部}r->next = NULL; //最后設置尾部next結點為NULL }

---

單鏈表的整表刪除

思想：

聲明結點 p 和 q；

將第一個結點賦值給 p；

循環：
1. 將下一結點賦值給 q ；
2. 釋放 p ；
3. 將 q 賦值給 p ；

實現代碼如下：

//初始條件：順序線性表L已存在，操作結果：將L重置為空表 Status ClearList(LinkList *L){LinkList p,q;p = (*L)->next; //p記錄第一個結點地址while(p){ //沒到表尾q = p->next; //q暫時記錄p->nextfree(p); //釋放p內存p = q;}(*L)->next = NULL; //頭結點指針域為空return OK; }

---

三、簡單對比鏈式存儲和順序存儲

單鏈表順序存儲結構

不需要分配存儲空間，元素個數不受限	需要預先分配存儲空間，分大了浪費，分小了上溢
存儲空間任意	連續的存儲單元依次存儲
查找時間復雜度O(n)	查找時間復雜度O(1)
插入、刪除時間復雜度O(1)	插入、刪除時間復雜度O(n)

若線性表需要頻繁查找，很少進行插入和刪除操作時，宜采用順序存儲結構。

若需要頻繁插入和刪除時，宜采用單鏈表結構。

運用場景舉例：比如說游戲開發中，對于用戶注冊的個人信息，除了注冊時插入數據外，絕大多數情況都是讀取，所以應該考慮用順序存儲結構。而游戲中的玩家的武器或者裝備列表，隨著玩家的游戲過程中，可能會隨時增加或刪除，適合用鏈表結構

---

后言

以上內容為 大話數據結構 – 程杰 第三章關于單鏈表的學習筆記。
雖然和成為Java工程師有一段距離，但是沒關系，我是一個一旦確立目標就很有干勁的人，一定能成功！
如果有跟我一起學習的同學可以幫我指正那就更好了，歡迎加入我的交流群 916352394。

總結

以上是生活随笔為你收集整理的大话数据结构4 - 初识单链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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