定義

線性表的鏈式存儲又稱單鏈表，它是指通過任意的存儲單元來存儲線性表的數據。注意此時的數據在物理地址上不在連續，內存是動態分配的，而且數據是存放在結點中，結點組成鏈表，每個節點分為數據域和指針域，所以我們在定義的時候，數據域來存放數據，指針域存放后面結點的地址（因為地址不連續。必須有一個變量來知道下一個結點在哪里）
代碼描述：

typedef int ElemType; typedef struct LNode {ElemType data;struct LNode* Next; }LNode,*LinkList;

特點

• 可以解決順序表需要大量連續存儲空間的缺點
• 單鏈表有指針域，我們只要存儲數據，現在又存儲了個指針，浪費了內存
• 知道第i個位置，就知道后面所有的結點內容了，但不能知道前面的結點

基本操作

再說基本操作之前，我們先來了解頭指針和頭結點

• 頭指針：標識一個單鏈表
• 頭結點：第一個結點之前附加的一個結點，可有可無。頭結點的數據域可以不設置任何信息，指針域指向第一個元素結點，就是數據域有存放我們要的數據的結點
• 區別：頭指針就是鏈表的名字，指向第一個結點，這個理解的時候，可以聯想數組，數組名就是頭指針。如果有頭結點，假如數組名叫a，a[1]就是頭結點，只是這個里面不存放數據，頭指針指向頭結點，頭指針的值就是頭結點的首地址，，頭結點的指針域的值是存放第一個數據的首地址

1、建立單鏈表：
1.1頭插法
假如現在鏈表只有一個數據是1，按照頭插法在插入數據2，那么現在的數據是2,1,第一個數據是2，這就是頭插法

/* 頭插法建立單鏈表，將新的數據插入當前鏈表的表頭 */LinkList List_HeadInsert(LinkList& L) {LNode* s; int x;L = (LinkList)malloc(sizeof(LNode)); //創建頭結點L->next = NULL;scanf("%d", &x);while (x != 9999) //輸入9999表示結束{s = (LNode*)malloc(sizeof(LNode)); //創建新的結點s->data = x;s->next = L->next;L->next = s;scanf("%d", &x);}return L; }

我們知道頭結點L是第一個結點，里面不存放數據，所以我們在插入數據s時，只需將頭結點L的指針域的值賦值給新插入數據S的指針，這樣新插入的數據S就指向頭指針L指向的結點，現在新插入的結點s和頭結點L都指向了一個結點，相當于兩個頭結點了，但頭結點只能有一個，所以我們的L還要指向S，始終保證L都是第一個節點，s就是第一個帶有我們存放數據的結點

1.2 尾插法

/* 尾插法：在尾部插入數據 */ LinkList List_TailInsert(LinkList& L) {int x;L = (LinkList)malloc(sizeof(LNode));LNode* s, * r = L; //r為表尾指針scanf("%d", &x);while (x != 9999) //輸入9999表示結束{s = (LNode*)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d", &x);}r->next = NULL;return L; }

此時多了個r指針，r始終表示最后一個結點，它的值是最后一個結點的首地址，我們插入一個新結點s時，尾插法要把s放到數據最后，沒有插入s前，r表示最后一個結點，所以讓r的指針域指向s，r現在是倒數第二個結點，但r始終表示最后一個結點，所以要把r指向s

1.3 尾插法和頭插法

• 尾插法生成的鏈表結點的次序與輸入數據的順序相同，而頭插法不一致
• 每個結點插入的時間為0（1），鏈表表長為n，則時間復雜度為0（n）
• 頭插法的L始終表示頭結點，尾插法的r始終要表示最后一個結點

2、按序號查找結點值
思路：從第一個節點出發，順指針next依次往下找，當找到第i個結點結束，否則返回null

/*按序號查找結點值： */ LNode* GetElem(LinkList L, int i) {int j = 1; //計數LNode* p = L->next;if (i <= 0)return NULL;while (p && j < i) {p = p->next;j++;}return p; }

頭結點為第一個結點，不存放值，所以不必要查找，直接j=1就行，為什么要p&&j<i呢？因為我們在創建我們的鏈表時，沒有定義變量來記錄長度，所以我們就不知道鏈表的長度，當j<i，但已經超過鏈表的長度時，我們就不能查找下去了，剛好最后一個結點的next是null，能判斷有沒有到達最后一個結點

3、按值查找
返回第一個等于我們要查找值的結點

/*按照值來查找 */LNode* LocateElem(LinkList L, ElemType e) {LNode* p = L->next;while (p != NULL && p->data!=e){p = p->next;}return p; }

4、插入結點
將數據e插入到第i個結點上，首先判斷i的合法性

/* 插入到第i個位置 */bool Insert(LinkList& L, int i,ElemType e) {LNode* p = GetElem(L, i - 1);if (p != NULL) {LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;}else{return false;}}

首先查找第i-1位置結點，為什么不是i呢？因為插入的時候，相當于第i個位置后移一步，所以第i-1的next要指向新插入的i位置，新插入的i位置要指向舊的i位置結點，如果查找i，就沒辦法知道i-1位置。根據查找i-1位置來判斷i的合法性。如果不合法返回false

5、刪除操作
將單鏈表的第i個結點刪除。
思路：先判斷刪除位置的合法性，然后查找第i-1個結點，刪除第i位置

/* 刪除操作 */bool Delete(LinkList& L, int i) {LNode* p = GetElem(L, i - 1);if (p != NULL) {LNode* q;q = p->next;p->next = q->next;free(q);return true;}else{return false;} }

總結

以上是生活随笔為你收集整理的线性表----链式表的全部內容，希望文章能夠幫你解決所遇到的問題。

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