算法2.8：單鏈表中插入一個節點

下面是書中的偽代碼：

Status ListInsert_L(LinkList &L, int i, ElemType e) { // 在帶頭結點的單鏈線性表L的第i個元素之前插入元素eLinkList p,s;p = L; int j = 0;while (p && j < i-1) { // 尋找第i-1個結點p = p->next;++j;} if (!p || j > i-1) return ERROR; // i小于1或者大于表長s = (LinkList)malloc(sizeof(LNode)); // 生成新結點s->data = e; s->next = p->next; // 插入L中p->next = s;return OK; } // LinstInsert_L
下面我們來分析下：

1.第一行是Status表示一種狀態，因為C語言里面沒有泛型，所以用這個表示。

2.這里的LinkList是*LinkList(書上對這個有定義，在本博客中不再說明)。

3.這里如果LinkList &L，是一個鏈表，這個p指向了L的地址。這樣的話當while循環結束后，那么p就是指向第i-1個元素的地址。

4.s在堆中開辟了一個LNode大小的空間，并且把e賦值給了s->data。

5.插入時我們要注意，先把p->next給s->next（就是先連s后繼，如果先連接p的后繼話這個鏈表是不能連起來的，大家可以試試），然后在連接p的后繼。

算法2.9：帶頭結點的鏈表的刪除

下面是書中的偽代碼：

Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 在帶頭結點的單鏈線性表L中，刪除第i個元素，并由e返回其值LinkList p,q;p = L;int j = 0;while (p->next && j < i-1) { // 尋找第i個結點，并令p指向其前趨p = p->next;++j;}if (!(p->next) || j > i-1) return ERROR; // 刪除位置不合理q = p->next;p->next = q->next; // 刪除并釋放結點e = q->data;free(q);return OK; } // ListDelete_L 下面是思路：

這個程序比較簡單，我們講解下思路就可以了。先用p指向要刪除的LinkList的前面那個元素，用q指向p后面那個元素（也就是要刪除的元素），把q->next賦值各p->next，這樣的化就把q隔離出來了，最后在free就可以了。這個比較簡單。

算法2.10：創建帶頭結點的單鏈表。

下面是書中的偽代碼：

void CreateList_L(LinkList &L, int n) { // 逆位序輸入（隨機產生）n個元素的值，建立帶表頭結點的單鏈線性表L LinkList p;int i;L = (LinkList)malloc(sizeof(LNode));L->next = NULL; // 先建立一個帶頭結點的單鏈表for (i=n; i>0; --i) {p = (LinkList)malloc(sizeof(LNode)); // 生成新結點p->data = random(200); // 改為一個隨機生成的數字(200以內)p->next = L->next; L->next = p; // 插入到表頭} } // CreateList_L
下面是思路：

1.帶頭結點的鏈表是指，鏈表里面的第一個結點，不存數據。

2.這里的i是要包含除頭結點外的還有多少個節點。

3.這里的random函數是產生隨機種子，他在頭文件#include<stdlib.h>中，大小為0~199。

4這里是在表頭中不停的插入，而不是在表尾中插入。

算法2.11：

如何將兩個有序鏈表并為一個有序鏈表。

下面是偽代碼：

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {// 已知單鏈線性表La和Lb的元素按值非遞減排列。// 歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列。LinkList pa, pb, pc;pa = La->next; pb = Lb->next;Lc = pc = La; // 用La的頭結點作為Lc的頭結點while (pa && pb) {if (pa->data <= pb->data) {pc->next = pa; pc = pa; pa = pa->next;}else { pc->next = pb; pc = pb; pb = pb->next; }}pc->next = pa ? pa : pb; // 插入剩余段free(Lb); // 釋放Lb的頭結點 } // MergeList_L
下面我們來分析下：

1.這個程序是思路是，用三個LinkList，pa,pb.pc分別指向La，Lb的第一個元素Lc的頭結點，然后比較，pa->data，和pb->data的值，誰下就把誰放入pc，然后指針后移，在最后，把還剩下的那個鏈的部分，直接接到pc。

2.這偽代碼有個問題，也就是最后的free(Lb)，如果要清理，也要加上free(La)才行。

3.這個例子的巧妙之處在于只需將原來兩個鏈表中節點之間的關系解除，程序按元素非遞減的關系將所有節點鏈接成一個鏈表即可。

算法2.12：

在靜態鏈線性表L中查找第1個值為e的元素

下面是偽代碼：

int LocateElem_SL(SLinkList S, ElemType e) { // 在靜態單鏈線性表L中查找第1個值為e的元素。// 若找到，則返回它在L中的位序，否則返回0。int i;i = S[0].cur; // i指示表中第一個結點while (i && S[i].data != e) i = S[i].cur; // 在表中順鏈查找return i; } // LocateElem_SL 下面我們來分析下：

1.靜態鏈表：在不設置“指針”類型的高級程序設計語言中使用的，需要預先分配一個較大的空間。

2.這個程序的思路是：cur是一個指示器類似于next，如下圖所示，相信看了下圖，就能理解，下圖是插入數據元素SHI和刪除數據元素ZHENG

3.這個cur存的是下標（因為這是SLinkList[MAXSIZE]）。

4.最后返回數組下標的值。

算法2.13：

在靜態鏈中將所有未被使用過以及被刪除的分量用游標鏈成一個備用的鏈表，每當進行插入時便可從備用鏈表上取得第一個結點作為待插入點；反之，在刪除時將此元素插入S表

下面以(A-B)U(B-A)=(AUB)-(A∩B）為例子。

假設由終端輸入集合元素，先建立表示集合A的靜態鏈表S，從而在輸入集合B的元素的同時查找S表，若存在和B相同的元素，則從S表刪除，否則插入S表。

算法2.13功能：將整個數組空間初始化成一個鏈表。

算法2.14功能：從備用空間取得一個結點。

算法2.15功能：將空間節點鏈結到備用鏈表上。

算法2.16功能：完整功能實現

下面是偽代碼：

void InitSpace_SL(SLinkList space) {// 將一維數組space中各分量鏈成一個備用鏈表，space[0].cur為頭指針，// "0"表示空指針for (int i=0; i<MAXSIZE-1; ++i) space[i].cur = i+1;space[MAXSIZE-1].cur = 0; } // InitSpace_SL 下面來分析下：

1.init的全寫為initialization，意思為初始化。

2.這個程序的最后是space[MAXSIZE-1].cur=0;是把這個靜態鏈頭尾相連變成一個環。

算法2.14：從備用空間取得一個結點。

下面是代碼：

int Malloc_SL(SLinkList &space) { // 若備用空間鏈表非空，則返回分配的結點下標，否則返回0int i = space[0].cur;if (space[0].cur) space[0].cur = space[space[0].cur].cur;return i; } // Malloc_SL 下面我們來分析下代碼：

1.malloc的全稱為mallocate，意思是分配。

2.這個程序是首先得到下標為0的鏈表對應的cur，當下標為0的cur不為0時，說明非空，則把space[0].cur這個是數提出來，再把這個數組對應的下標賦值給0對應的下標。

3.不懂的同學，帶幾個數進去就懂了。

算法2.15：將空間節點鏈結到備用鏈表上

下面是偽代碼：

void Free_SL(SLinkList &space, int k) {// 將下標為k的空閑結點回收到備用鏈表space[k].cur = space[0].cur; space[0].cur = k; } // Free_SL 下面我們來分析下：

這個是先把以前0的下標給后數組第k行對應的下標，然后到數組0下標改為k。

算法2.16：完整功能實現

下面是偽代碼：

void difference(SLinkList &space, int &S) {// 依次輸入集合A和B的元素，在一維數組space中建立表示集合(A-B)∪(B-A)// 的靜態鏈表, S為頭指針。假設備用空間足夠大，space[0].cur為頭指針。int i, j, k, m, n, p, r;ElemType b;InitSpace_SL(space); // 初始化備用空間S = Malloc_SL(space); // 生成S的頭結點r = S; // r指向S的當前最后結點m = random(2,8); // 輸入A的元素個數n = random(2,8); // 輸入B的元素個數printf(" A = ( ");initrandom_c1();for (j=1; j<=m; ++j) { // 建立集合A的鏈表i = Malloc_SL(space); // 分配結點//printf("i=%d ",i);space[i].data = random_next_c1(); // 輸入A的元素值printf("%c ", space[i].data); // 輸出A的元素space[r].cur = i; r = i; // 插入到表尾}printf(")\n");space[r].cur = 0; // 尾結點的指針為空initrandom_c1();printf(" B = ( ");for (j=1; j<=n; ++j) {// 依次輸入B的元素,若不在當前表中,則插入,否則刪除b = random_next_c1(); // 輸入B的元素值printf("%c ", b); // 輸出B的元素p = S; k = space[S].cur; // k指向集合A中第一個結點while (k!=space[r].cur && space[k].data!=b) {// 在當前表中查找p = k; k = space[k].cur;}if (k == space[r].cur) {// 當前表中不存在該元素,插入在r所指結點之后，且r的位置不變i = Malloc_SL(space);space[i].data = b;space[i].cur = space[r].cur;space[r].cur = i;} else { // 該元素已在表中,刪除之space[p].cur = space[k].cur;Free_SL(space, k);if (r == k) r = p; // 若刪除的是尾元素，則需修改尾指針}}printf(")\n"); } // difference
下面我們來分析一下：

1.這里面用產生了兩個隨機種子賦值給了m和n。

2.這里的random_next_c1();函數估計就是參數一個隨機字符。

3.第一個for循環結束后把space里面下標為1-m的數都賦值了。

4.第二個for循環里面的while循環，是判斷是否有相同的數，和是不是檢索完了數組。

假設A=(c,b,e,g,f,d),B=(a,b,n,f)則，這圖很好的表示了此算法：

總結

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

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