《数据结构》c语言版学习笔记——单链表结构（线性表的链式存储结构Part1）
線性表的鏈式存儲結構
數據結構系列文章 第二章 單鏈表結構
文章目錄
- 線性表的鏈式存儲結構
- 前言
- 一、單鏈表的建立
- 代碼
- 二、單鏈表的讀取
- 代碼
- 三、單鏈表的插入
- 代碼
- 四、單鏈表的刪除
- 代碼
- 五、單鏈表的整表創建
- 1.頭插法建立單鏈表
- 代碼
- 2.尾插法建立單鏈表
- 代碼
- 六、單鏈表的整表刪除
- 代碼
- 總結
前言
提示：本系列文章均使用Visual Studio 2019編程，編程語言為c語言。
一、單鏈表的建立
為了使單鏈表中每個數據元素與其直接后繼的數據元素之間存在邏輯關系，除了存儲其本身的信息之外，還需要存儲一個指示其直接后繼存儲位置的信息（存儲后繼元素的存儲地址，即指針）。
存儲數據元素信息的域稱為數據域，將存儲直接后繼位置的域稱為指針域，其中指針域中存儲的信息稱為指針或鏈，同時這兩部分信息組成數據元素的存儲映像稱為結點。結點由存放數據元素的數據域存放后繼結點地址的指針域組成。n個結點鏈從而結合成一個鏈表，即為線性表的鏈式存儲結構，又由于鏈表的每個結點中只包含一個指針域，所以稱為單鏈表。
代碼
#include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0//單鏈表的建立 typedef int Status; typedef int ElemType; typedef struct Node {ElemType data; //數據域struct Node *next; //指針域 }Node; typedef struct Node* LinkList; //將Node替換為LinkList二、單鏈表的讀取
由于單鏈表與線性表的順序存儲結構不一樣，當我們要查找任意一個元素的存儲位置時，單鏈表的查找得從頭開始找。我們來看看怎么查找吧，可以說
單鏈表的讀取分為以下幾步：（例如讀取鏈表中第n個元素的值）
1、首先聲明一個指針p（結點）指向單鏈表的第一個結點，即p=L->next,同時設定一個計數器j從1開始計數；
2、開始查找，當j<n時，遍歷整個鏈表，讓p的指針向后移動查找下一個結點，同時計數器j累加1（由于沒有定義表長，所以不知道要進行多少次循環語句，所以不用for語句）；
3、若至鏈表末尾，指針p仍為空，即未找到該元素，第n個元素不存在，返回錯誤；
4、否則，查找成功，用e返回L中第n個元素的數據；
5、返回成功。
代碼
//單鏈表的讀取 typedef int Status; Status GetElem(LinkList L, int n, ElemType* e) {int j=1; //j為計數器LinkList p; //聲明一結點p = L->next; //讓p指向鏈表L的第一個結點while (p &&j<n) //當p為空或者計數器j等于n時，結束循環{p = p->next; //讓p指向下一個結點++j;}if (!p || j > n)return ERROR; //第n個元素不存在*e = p->data; //取第n個元素的數據return OK; }三、單鏈表的插入
對于實現單鏈表的插入操作，我們以以下圖示來解釋，我們設要插入的元素e的結點為s，我們要實現將結點s插入到結點p和p->next之間，即可以將p的后繼結點改為s的后繼結點，再把結點s變成p的后繼結點，通過代碼改變其指針實現即s->next=p->next ; p->next=s。（特別注意這兩句的順序不可寫反）
單鏈表的插入分為以下幾步：（例如鏈表中第i個數據元素位置之前插入數據元素e）
1、首先聲明一個指針p（結點）指向單鏈表的第一個結點并且聲明一個空結點s,同時設定一個計數器j從1開始計數；
2、由于要找第i-1個結點，因為要插入的是第i個結點。當j<i且p為空時，遍歷整個鏈表，讓p的指針向后移動查找下一個結點，同時計數器j累加1（循環用于遍歷到需要插入的結點）；
3、若至鏈表末尾，指針p仍為空，即未找到該元素，第i個元素不存在，返回錯誤；
4、否則此時查找成功，此時用動態分配函數生成一個新結點s，即分配整型存儲單元，并將連續的整型存儲單元的首地址存儲到指針變量s當中；
5、將數據元素e賦值給s->data；
6、將p結點的后綴結點賦值給s的后繼并將s賦值給p的后繼；
7、返回成功。
代碼
//單鏈表的插入 typedef int Status; Status ListInsert(LinkList* L, int i, ElemType e) {int j = 1;LinkList p, s;p = *L;while (p && j<i) //當p為空或者計數器j等于i時，結束循環(即尋找第i個結點){p = p->next;++j;}if (!p || j > i)return ERROR; //第i個元素不存在s = (LinkList)malloc(sizeof(Node)); //malloc()是動態分配函數，用來向系統請求分配內存空間，即分配整型存儲單元，并將連續的整型存儲單元的首地址存儲到指針變量s當中s->data = e;s->next = p->next; //將p的后綴結點賦值給s的后繼p->next = s; //將s賦值給p的后繼return OK; }四、單鏈表的刪除
對于實現單鏈表的插入操作，我們以以下圖示來解釋，我們要刪除的結點是q，只要繞過它的前繼結點的指針，直接指向它的后繼結點就行,即①q=p->next②p->next=q->next，我們可以用一步來描述，這一步是p->next=p->next->next。
單鏈表的刪除分為以下幾步：（例如刪除鏈表中第i個數據元素）
1、首先聲明一個指針p（結點）指向單鏈表的第一個結點，同時設定一個計數器j從1開始計數；
2、當j<i且p為空時，遍歷整個鏈表，讓p的指針向后移動查找下一個結點，同時計數器j累加1（循環用于遍歷到需要刪除的結點）；
3、若至鏈表末尾，指針p仍為空，即未找到該元素，第i個元素不存在，返回錯誤；
4、否則此時查找成功，將準備刪除的結點p->next賦值給q；
5、執行刪除操作，p->next=q->next；
6、將q結點中的數據賦給e，作為返回，用e返回其值；
7、使用free（）函數，釋放q結點；
8、返回成功。
代碼
//單鏈表的刪除 typedef int Status; Status ListDelete(LinkList *L, int i, ElemType *e) {int j = 1;LinkList p, q;p = *L;while (p->next && j < i) //遍歷尋找第i個元素{p = p->next;++j;}if (!(p->next) || j > i)return ERROR; //第i個元素不存在q = p->next; p->next = q->next; *e = q->data; //將q結點中的數據給efree(q); //free（）函數，讓系統回收此結點，釋放內存return OK; }五、單鏈表的整表創建
1.頭插法建立單鏈表
頭插法創建單鏈表，即始終讓新結點處于表中第一的位置，最后輸入的元素和輸出的元素順序剛好相反。從一個空表開始，生成新結點，讀取數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭位置上，直到結束為止。（先讓新結點的next指向頭結點之后，然后讓表頭的next指向新結點）
代碼
#include <stdio.h> #include <stdlib.h> typedef int Status; typedef int ElemType; typedef struct Node* LinkList; //將Node替換為LinkList，即結構指針LinkList typedef struct Node //定義一個結構體 {ElemType data; //數據域struct Node* next; //指針域 }Node;Status ListInit(LinkList& L) {L = (LinkList)malloc(sizeof(Node)); //生成新結點if (!L)exit(1); //當單鏈表L為空時，執行exit（1）即表示異常退出L->next = NULL; //否則創建一個帶頭結點的單鏈表，初始化指向NULLreturn 1; //return（1）代表函數非正常終止 }//頭插法 void CreateListHead(LinkList* L, int n) {LinkList p;int i;*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL; //創建一個帶頭結點的單鏈表，初始化指向NULLfor (i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node)); //生成新結點scanf("%d", &i);p->data = i;p->next = (*L)->next;(*L)->next = p; //插入到表頭} }//遍歷函數 void TraverseList(LinkList* L) {Node* p, * q;p = *L;while (p->next != NULL) //遍歷輸出數據元素{q = p->next;printf("%d ", q->data);p = p->next;} }//主函數 int main(int argc, char const* argv[]) {int n;LinkList L;ListInit(L);printf("請輸入創建數據元素的個數：");scanf("%d", &n);CreateListHead(&L, n);printf("頭插法創建單鏈表如下：");TraverseList(&L);printf("\n");return 0; }測試輸入五個數據元素：0、1、2、3、4。
（輸出的順序與輸入的順序是相反的）
2.尾插法建立單鏈表
第二種方法就是尾插法，也就是將所加入的新結點全部插在終端結點的后面依次排下去，就相當于正常排隊的思維來運行程序， 其中
q->next = p;這一語句即將表尾終端結點q的指針指向新的下一個結點p，然后q=p；這一語句q就相當于一個中繼（是當前鏈表的最后結點），在進行下一個元素的創建時，q本來是上一個數據元素的結點，但后面仍有結點，所以這時應該將這個p結點（也就是當前鏈表的最后結點）賦值給q，此時q又是當前鏈表的尾結點。循環結束后q->next = NULL;即讓這個鏈表的指針域置空，以便在之后遍歷時可以知道是其當前鏈表尾部。
代碼
#include<stdio.h> #include<stdlib.h> typedef int Status; typedef int ElemType; typedef struct Node* LinkList; //將Node替換為LinkList，即結構指針LinkList typedef struct Node //定義一個結構體 {ElemType data; //數據域struct Node* next; //指針域 }Node;Status ListInit(LinkList& L) {L = (LinkList)malloc(sizeof(Node)); //生成新結點if (!L)exit(1); //當單鏈表L為空時，執行exit（1）即表示異常退出L->next = NULL; //否則創建一個帶頭結點的單鏈表，初始化指向NULLreturn 1; //return（1）代表函數非正常終止 }//尾插法 void CreatListTail(LinkList& L, int n) {LinkList p, q;q = L;int a;for (int i = 0; i < n; i++){p = (LinkList)malloc(sizeof(Node)); //生成新結點scanf("%d", &a);p->data = a;q->next = p; //將當前的新結點定義為單鏈表尾終端結點q = p;}q->next = NULL; //表示當前單鏈表結束 }//遍歷函數 void TraverseList(LinkList& L) //輸出單鏈表函數 {LinkList r;r = L->next;while (r){printf("%d ", r->data);r = r->next;} }//主函數 int main(int argc, char const* argv[]) {int n;LinkList L;ListInit(L);printf("請輸入創建數據元素的個數：");scanf("%d", &n);CreatListTail(L, n);printf("尾插法創建單鏈表如下：");TraverseList(L);printf("\n");return 0; }測試輸入五個數據元素：0、1、2、3、4。
（輸出的順序與輸入的順序相同）
六、單鏈表的整表刪除
當要刪除這個單鏈表時，即在內存中釋放它時，我們給出以下算法：
1、聲明一結點p和q；
2、將第一個結點賦值給p；
3、循環語句：將下一結點賦值給q，釋放p，將q賦值給p。
代碼
#include<stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType; typedef struct Node* LinkList; //將Node替換為LinkList，即結構指針LinkList typedef struct Node //定義一個結構體 {ElemType data; //數據域struct Node* next; //指針域 }Node;Status ClearList(LinkList* L) {LinkList p, q; p = (*L)->next; //p指向第一個結點while (p) //循環到表尾結束{q = p->next;free(p);p = q;}(*L)->next = NULL; //頭指針指針域為空return OK; }總結
以上就是本次的筆記內容，本文僅僅通過文字和代碼簡單介紹了單鏈表結構的各項操作，建議自己分析總結其各個操作并結合自己的編程能力選擇編程語言再寫一遍代碼從而加深印象，可以使自己的編程能力提升，其實數據結構不難，要有心地去學習和總結，才能事半功倍，若有錯誤歡迎指正。
附： 在本系列下一文章會單獨介紹其他鏈表（如：靜態鏈表、循環鏈表以及雙向鏈表）的各項操作，持續更新ing……
總結
以上是生活随笔為你收集整理的《数据结构》c语言版学习笔记——单链表结构（线性表的链式存储结构Part1）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 《数据结构》c语言版学习笔记——线性表的
- 下一篇： 《数据结构》c语言版学习笔记——其他链表