3.線性表

線性表

線性表的定義

線性表（List）： 零個或多個數(shù)據(jù)元素的 有限 序列

除了首尾兩數(shù)據(jù)元素外，線性表的每個數(shù)據(jù)元素，都有一個 直接前驅(qū) 元素和一個 直接后繼 元素。而首元素只有一個直接后繼元素，沒有直接前驅(qū)元素；尾元素只有一個直接前驅(qū)元素，沒有直接后繼元素

線性表元素的長度： 線性表中數(shù)據(jù)元素的個數(shù)

空表： 當(dāng)線性表的長度為0時，即線性表中數(shù)據(jù)元素個數(shù)為0時，稱該線性表為空表

在復(fù)雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。

線性表的抽象數(shù)據(jù)類型

線性表的抽象數(shù)據(jù)類型如下：

ADT 線性表(List)
Data 
  線性表的數(shù)據(jù)對象為{a1,a2,a3,...,an}，每個數(shù)據(jù)元素的類型均為 Datatype 。
  其中，每一個數(shù)據(jù)元素之間的邏輯關(guān)系是一對一的關(guān)系。
Operation
  InitList(*L);    //初始化操作，創(chuàng)建一個空表
  ListEmpty(L);    //判斷線性表是否為空表，是返回 true ，否返回 false 
  ClearList(*L);    //清空線性表
  GetElem(L, i, *e);    //獲取線性表中第 i 個位置的數(shù)據(jù)元素的值并返回給 e 
  ListInsert(*L, i, e);    //插入數(shù)據(jù)元素 e 到線性表 L 的第 i 個位置
  ListDelete(*L, i, e);    //刪除線性表中第 i 個位置的數(shù)據(jù)元素，并使用 e 返回其值
  ListLength;    //返回線性表的長度
endADT

注意，以上的 Operation 只是線性表的基本操作 。針對于更復(fù)雜的操作，完全可以使用基本操作的組合來完成。

上述函數(shù)參數(shù)為線性表的地址的，均是需要修改線性表長度的。

線性表的順序存儲結(jié)構(gòu)

線性表的順序存儲結(jié)構(gòu)： 指的是用一段 地址連續(xù)的存儲單元 依次存儲線性表的數(shù)據(jù)元素

線性表的順序存儲示意圖

既然線性表的每個數(shù)據(jù)元素的類型都相同，所以可以 用一維數(shù)組來實現(xiàn)順序存儲結(jié)構(gòu) 。

線性表的順序存儲的結(jié)構(gòu)代碼：

#define MAXSIZE 20    //設(shè)置存儲空間初始分配量，這里假設(shè)為 20 個數(shù)據(jù)元素
typedef int ElemType;    //Elemtype 類型根據(jù)實際情況而定，這里假設(shè)為 int 
typedef struct {
  Elemtype data[MAXSIZE];        //數(shù)組存儲數(shù)據(jù)元素，最大值為 MAXSIZE 
  int length;        //線性表當(dāng)前長度，這里用 int 變量存儲
}SqList;

或者可以使用 malloc 函數(shù)動態(tài)申請一片連續(xù)的存儲空間，如何將空間地址返回給鏈表的頭指針成員變量。

#define MAXSIZE 20    //設(shè)置存儲空間初始分配量，這里假設(shè)為 20 個數(shù)據(jù)元素
typedef int ElemType;    //Elemtype 類型根據(jù)實際情況而定，這里假設(shè)為 int 
typedef struct {
  Elemtype *data;        //指向 malloc(MAXSIZE) 分配的空間的頭指針
  int length;        //線性表當(dāng)前長度，這里用 int 變量存儲
}SqList;

然后在 InitList 函數(shù)里使用 malloc 函數(shù)分配空間給并將地址賦值給 data

由結(jié)構(gòu)代碼可得 描述順序存儲結(jié)構(gòu)的三個屬性：

  • 存儲空間的起始位置： 數(shù)組 data ，它的存儲位置就是存儲空間的起始位置。
  • 線性表的最大存儲容量： 數(shù)組長度 MAXSIZE
  • 線性表（當(dāng)前）長度： length

注意：數(shù)組長度 MAXSIZE 與線性表的長度 length 不同 ，數(shù)組的長度是指存放線性表數(shù)據(jù)元素的存儲空間的長度。在任意時刻，線性表長度都小于或等于數(shù)組長度。

一般來說，數(shù)組長度 MAXSIZE 設(shè)置完后是不會改變的。而線性表的長度是可以改變的。

由于數(shù)組的下標(biāo)是從0開始的，所以一般線性表的第 i 個元素存儲在數(shù)組下標(biāo)為 i-1 的位置。

存儲器中的每個存儲單元都有自己的編號，這個編號成為地址。

假設(shè)存儲每個數(shù)據(jù)元素的空間大小為 c ，那么線性表中第 i+1 個數(shù)據(jù)元素的存儲位置和第 i 個數(shù)據(jù)元素的存儲位置滿足下列關(guān)系（LOC 表示獲得存儲位置的函數(shù)）。

LOC(ai+1) = LOC(ai)+c

所以線性表中第 i 個元素 ai 的存儲位置由 a1 推導(dǎo)為：

LOC(ai) = LOC(a1)+(i-1)*c

示意圖

通過這個公式可以隨時算出線性表中任意位置的地址，且時間相同，其時間復(fù)雜度為 O(1) ，所以基于此之上的操作的時間復(fù)雜度都為 O(1) ，例如查找。

我們將具有 隨時算出任意位置地址 的存儲結(jié)構(gòu)稱為 隨機存取結(jié)構(gòu) 。

順序存儲結(jié)構(gòu)的插入與刪除

對于線性表的順序存儲結(jié)構(gòu)來說，我們要實現(xiàn) GetElem 操作（將線性表中第 i 個元素的值返回）的方法很簡單，只要 i 的數(shù)值在數(shù)組下標(biāo)范圍內(nèi)，就是把數(shù)組第第 i-1 下標(biāo)的值返回即可。

例子代碼：

# OK 1
# ERROR 0
# TRUE 1
# FALSE 0
typedef int Status;    //Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如 OK 等

//初始條件：線性表 L 已存在
Status GetElem (Sqlist L, int i, Elemtype *e){
  //用于判斷 L 是否為空表，i 是否在 1~MAXSIZE-1 內(nèi)
  if(L.length == 0 || i<1 || i>L.length)
    return ERROR;
  *e = L.data[i-1];
  return OK;
}

注意： 要加上判斷條件用于檢測 L 和 i 是否符合要求 。

線性表的順序存儲結(jié)構(gòu)的插入

插入算法的思路：

  • 如果插入的位置不合理，拋出異常；
  • 如果線性表長度已到最大，則拋出異?；騽討B(tài)增加容量；
  • 從最后一個元素開始向前遍歷到第 i 個位置，分別將它們都向后移動一個位置；
  • 將要插入元素填入位置 i 處；
  • 線性表長度+1

實現(xiàn)代碼如下：

Status ListInsert(SqList *L, int i, Elemtype e){
    if(L->length == MAXSIZE)
        return ERROR;
    if(i < 1 || i>L->length + 1)
        return ERROR;
    if(i <= L->length){
        for(int k = L->length; k >= i-1; k--)
            L->data[k+1] = L->data[k];
    }
    L->data[i-1] = e;
    L->length++;
    return OK;
}

線性表的順序存儲結(jié)構(gòu)的刪除

刪除算法的思路：

  • 如果刪除位置不合理或線性表為空，則拋出異常；
  • 取出刪除元素；
  • 從刪除元素位置遍歷到最后一個元素，分別將其向前移動一個位置；
  • 線性表長度-1

實現(xiàn)代碼如下：

Status ListDelete(SqList *L, int i, Elemtype *e){
    if(L->length == 0)
        return ERROR;
    if(i < 1 || i > L->length)
        return ERROR;
    if(i < L->length){
        for(int k = i; k < L->length; k++)
            L->data[k-1] = L->data[k];
    }
    L->length--;
    return OK;
}

線性表順序存儲結(jié)構(gòu)的優(yōu)缺點

時間復(fù)雜度： 查找操作為 O(1) ，刪除和查找為 O(n)

其中造成存儲空間的“碎片”指的是，當(dāng)線性表長度小于數(shù)組長度時，會造成存儲空間的浪費。

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

由于線性表的順序存儲結(jié)構(gòu)在進行刪除和插入操作時，往往需要花費大量時間。所以可以采用線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)來解決這一問題。

線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)： 用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素，且數(shù)據(jù)元素是一對一的關(guān)系， 其中存儲單元可以是連續(xù)的，也可以是不連續(xù)的 。

為了表示每個數(shù)據(jù)元素 ai 與其直接后繼元素 ai+1 之間的線性邏輯關(guān)系，數(shù)據(jù)元素 ai 除了要存儲自身的數(shù)據(jù) data 外，還要存儲其直接后繼數(shù)據(jù)元素的位置（比如地址）。我們把存儲數(shù)據(jù)的域稱為 數(shù)據(jù)域 ，并把存儲直接后繼元素的位置的域稱為 指針域 。其中存儲的位置信息稱為 指針或鏈 。這兩部分信息組成的數(shù)據(jù)元素 ai 被稱為 結(jié)點（Node） 。

n 個結(jié)點鏈結(jié)成一個鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。因為此鏈表的每個結(jié)點中只包含一個指向直接后繼元素的指針域，所以叫做 單鏈表 。

頭指針： 鏈表中第一個結(jié)點的存儲位置。
注意頭指針不是第一個結(jié)點的指針域。

程序員一般約定線性鏈表的最后一個結(jié)點的指針域為空（也就是值為 NULL ）

注意頭指針和第一個結(jié)點的關(guān)系

為了方便和統(tǒng)一對鏈表進行操作，一般 會在單鏈表的第一個結(jié)點前附設(shè)一個結(jié)點，稱為頭結(jié)點 ，但頭結(jié)點并不是鏈表的必須要素。

頭結(jié)點的數(shù)據(jù)域可以不存儲任何數(shù)據(jù)，也可以存儲線性表的長度之類等附加信息。頭結(jié)點的指針域存儲著頭指針。

若鏈表有頭結(jié)點，那么頭指針指向的則是頭結(jié)點。

頭指針與頭結(jié)點的區(qū)別

若線性表為空表，則頭結(jié)點的指針域為空，值為 NULL 。

在 C 中的單鏈表代碼描述如下：

typedef struct Node{
    Elemtype data;    //data 存儲 Elemtype 類型的數(shù)據(jù)元素 
    struct Node* next;    //next 存儲直接后繼元素的位置
}Node, *LinkList;

單鏈表的讀取

注意：該鏈表具有頭結(jié)點

獲取鏈表第 i 個數(shù)據(jù)元素的算法思路：

  • 聲明一個結(jié)點指針 p 指向鏈表第一個結(jié)點，初始化 j 從 1 開始；
  • 當(dāng) j < i 時，就遍歷鏈表，讓 p 向后移動，不斷指向下一結(jié)點， j 不斷遞增1；
  • 若到鏈表末尾 p 值為 NULL ，則說明第 i 個元素不存在；
  • 否則查找成功，返回結(jié)點指針 p 指向的結(jié)點的數(shù)據(jù) p->data

單鏈表的插入和刪除

注意：該鏈表具有頭結(jié)點

單鏈表第 i 個數(shù)據(jù)插入結(jié)點的算法思路：

  • 聲明一結(jié)點指針 p 指向鏈表第一個結(jié)點，初始化 j 為1；
  • 當(dāng) j < i 時，就遍歷鏈表，讓 p 向后移動，沿著鏈不斷指向下一結(jié)點，j 遞增1；
  • 若到鏈表末尾 p 為空，則說明第 i 個元素不存在， return ERROR?；蛘弋?dāng) i 為0或負(fù)數(shù)時， return ERROR ；
  • 否則查找成功，并在系統(tǒng)中通過生成一個空結(jié)點 s ；
  • 將數(shù)據(jù)元素 e 賦值給 s->data ；
  • 單鏈表的插入標(biāo)準(zhǔn)語句： s->next = p->next; p->next = s ；
  • return OK;

實現(xiàn)代碼如下：

Status ListInsert(LinkList *L, int i, Elemtype e){
    int j = 1;
    LinkList s, p = *L;
    while(p && j < i){
        p = p->next;
        j++;
    }
    if(!p || j > i)
        return ERROR;
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

雖然這里用到了指向指向鏈表的指針的指針 L ，但是其實沒必要，因為我們并沒有修改 L 的值。

插入的示意圖

單鏈表第 i 個數(shù)據(jù)插入結(jié)點的算法思路：

  • 聲明一個結(jié)點 p 指向鏈表的第一個結(jié)點，初始化 j 為1；
  • 當(dāng) j < i 時，就遍歷鏈表，讓 p 的向后移動，不斷指向下一個結(jié)點，j 不斷遞增 1 ；
  • 若到鏈表末尾 p 為空，則說明第 i 個元素不存在， return ERROR?；蛘弋?dāng) i 為0或負(fù)數(shù)時， return ERROR ；
  • 否則查找成功，將要刪除的結(jié)點 p->next 賦值給 q ；
  • 單鏈表的刪除標(biāo)準(zhǔn)語句： p->next = q->next;
  • 將結(jié)點 q 中的數(shù)據(jù)賦值給 e 用于返回；
  • 釋放 q 結(jié)點；
  • return OK;

實現(xiàn)代碼如下：

Status ListDelete(LinkList *L, int i, Elemtype *e){
    int j = 1;
    LinkList p = *L;
    while(p->next && j < i){
        p = p->next;
        j++;
    }
    if(!(p->next) || j > i)
        return ERROR;
    LinkList q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

對于單鏈表來說，刪除和插入的時間復(fù)雜度都是 O(n) 。但是在刪除和插入頻率高的情況下，單鏈表的效率會比順序存儲結(jié)構(gòu)要高很多。 假設(shè)要在第 i 個數(shù)據(jù)元素插入10個元素，單鏈表只需要找到并通過賦值每次移動兩次結(jié)點的指針域，而順序存儲結(jié)構(gòu)需要每次移動后面全部的數(shù)據(jù)元素。

單鏈表的創(chuàng)建

單鏈表的創(chuàng)建的算法思路：

  • 聲明一個結(jié)點 p 和計數(shù)器變量 i ；
  • 初始化一空鏈表；
  • 讓 L 的頭結(jié)點的指針指向 NULL ，即建立一個帶頭結(jié)點的單鏈表；
  • 循環(huán)以下步驟：①生成一新結(jié)點賦值給 p ②令每一個數(shù)據(jù)元素的 data 都為 0 ③將 p 插入到頭結(jié)點與前一新結(jié)點之間

實現(xiàn)代碼如下：

void CreateListHead(LinkList *L, int n){
    LinkList p;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for(int i = 0; i < n; i++){
        p = (LinkList)malloc(sizeof(Node));
        p->data = 0;
        p->next = (*L)->next;
        (*L)->next = p;
    }
}

我們在這里采用了頭插法來插入新結(jié)點。 頭插法 是指始終讓新結(jié)點位于數(shù)據(jù)元素的第一位，當(dāng)有頭結(jié)點時，新結(jié)點從緊跟著頭結(jié)點后的位置插入。

頭插法示意圖

當(dāng)然，我們也可以采用尾插法。 尾插法 指的是每次都把新結(jié)點插到終端結(jié)點的后面。

實現(xiàn)代碼如下：

void CreateListHead(LinkList *L, int n){
    LinkList p, r;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    r = *L;  // r 指向終端結(jié)點
    for(int i = 0; i < n; i++){
        p = (LinkList)malloc(sizeof(Node));
        p->data = 0;
        r->next = p;
        r = p;
    }
    r->next = NULL;  //讓終端結(jié)點的指針域為空
}
關(guān)于 r->next = p; 和 r = p; 的示意圖

最后將終端結(jié)點的指針域置空。

單鏈表的整表刪除

單鏈表的整表刪除的算法思路如下：

  • 聲明一結(jié)點指針 p 和 q；
  • 將第一個結(jié)點的地址賦值給 p ；
  • 循環(huán)：①將下一結(jié)點賦值給 p ②釋放 p ③將 q 賦值給 p

實現(xiàn)代碼如下：

Status ClearList(LinkList *L){
    LinkList p, q;
    p = (*L)->next;
    while(p){
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;
    return OK;
}

這里最后得到的是空表，如果不想使用這個空表，只需要再把頭指針指向的空間釋放即可。

單鏈表與順序存儲結(jié)構(gòu)的優(yōu)缺點

靜態(tài)鏈表

靜態(tài)鏈表（游標(biāo)實現(xiàn)法）： 就是通過 用數(shù)組替代指針來描述鏈表 ，讓數(shù)組的元素具有兩個數(shù)據(jù)域—— data 和 cur 。其中 data 存儲數(shù)據(jù)元素， cur 相當(dāng)于鏈表的 next ，存儲該元素的直接后繼元素在數(shù)組中的下標(biāo)。

同時，為了方便插入數(shù)據(jù)，我們通常會把數(shù)組建立得大一些，以便有一些空閑空間可以便于插入而不溢出。

靜態(tài)鏈表的實現(xiàn)代碼：

#define MAXSIZE 1000
typedef struct {
    Elemtype data;
    int cur;    //游標(biāo)（cursor），為0時表示無指向
}Component,StaticLinkList[MAXSIZE];

其中，我們要把數(shù)組 StaticLinkList 中的 首尾兩元素作為特殊元素處理，不存數(shù)據(jù)元素 。
我們通常將 StaticLinkList 中尚未使用的數(shù)組元素稱為 備用鏈表 。而數(shù)組中第一個元素（即下標(biāo)為0）的 cur 就存放備用鏈表的第一個結(jié)點的下標(biāo)；而數(shù)組的最后一個元素的 cur 則存放第一個有數(shù)據(jù)元素的元素的下標(biāo)，相當(dāng)于單鏈表中的頭結(jié)點。所以，當(dāng)整個靜態(tài)鏈表為空表時，則為 02 。

初始化靜態(tài)鏈表的代碼實現(xiàn)如下：

Status InitList(StaticLinkList space){
    for(int i = 0; i < MAXSIZE; i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur = 0;
    return OK;
}

其中， 靜態(tài)鏈表最后一個存放數(shù)據(jù)元素的元素的 cur 的值為0 ，表示下一位置數(shù)據(jù)為空，相當(dāng)于 NULL 。

當(dāng)靜態(tài)鏈表的備用鏈表為空時，數(shù)組的首元素的 cur 的值為0。

例子

靜態(tài)鏈表的插入與刪除

為了辨明數(shù)組 StaticLinkList 中有哪些分量未被使用，解決的方法是將所有未被使用過的以及已經(jīng)被刪除的分量用游標(biāo)鏈成一個備用的鏈表 ，每當(dāng)進行插入時，便可以從備用鏈表上取得第一個結(jié)點作為待插入的新結(jié)點。

取得備用鏈表上第一個新結(jié)點的游標(biāo) 的代碼實現(xiàn)：

//若備用鏈表非空，則返回備用鏈表分配的結(jié)點下標(biāo)，否則返回 0 
int Malloc_SLL(StaticLinkList space){
    int i = space[0].cur;
    if(space[0].cur)
        space[0].cur = space[i].cur;
    return i;
}

其中 space[0].cur = space[i].cur; 表示將下一個新結(jié)點作為備用鏈表的表頭。

靜態(tài)鏈表的數(shù)據(jù)元素個數(shù)獲取 的代碼實現(xiàn)：

//初始條件： L 的已存在
int ListLength(StaticLinkList L){
    int j = 0, i = L[MAXSIZE-1].cur;
    while(i){
        i = L[i].cur;
        j++;
    }
    return j;
}
//操作結(jié)果：返回 L 中數(shù)據(jù)元素的個數(shù)

靜態(tài)鏈表的插入算法 的代碼實現(xiàn)：

//在 L 中第 i 個元素的位置插入新的數(shù)據(jù)元素 e
Status ListInsert(StaticLinkList L,int i, Elemtype e){
    int k = MAXSIZE - 1;
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
    int j = Malloc_SLL(L);
    if(j){
        L[j].data = e;
        for(int l = 1; l <= i-1; l++)
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return OK;
    }
    return ERROR;
}

靜態(tài)鏈表的刪除算法 代碼實現(xiàn)：

//刪除在 L 中第 i 個數(shù)據(jù)元素
Status ListDelete(StaticLinkList L, int i){
    int k = MAXSIZE - 1;
    if(i < 1 || i > ListLength(L))
        return ERROR;
    for(int j = 1; j <= i-1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L, j);
    return OK;
}

//回收下標(biāo)為 k 的空閑結(jié)點到備用鏈表里
void Free_SSL(StaticLinkList space, int k){
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

靜態(tài)鏈表的優(yōu)缺點：

優(yōu)點

在插入和刪除操作時，只需要修改游標(biāo)，不需要移動元素，改進了在順序存儲結(jié)構(gòu)中的插入和刪除操作需要移動大量元素的缺點。

缺點

  1. 沒有解決連續(xù)存儲分配(數(shù)組)帶來的表長難以確定的問題。
  2. 失去了順序存儲結(jié)構(gòu)隨機存取的特性

循環(huán)鏈表

循環(huán)列表（circular linked list）： 只要將單鏈表中終端結(jié)點的指針域由空指針改為指向頭結(jié)點 ，就可以使得整個單鏈表形成一個環(huán)，這種頭尾相連的單鏈表被稱為單循環(huán)鏈表，簡稱循環(huán)列表。

同樣的，為了使得循環(huán)列表的空鏈表和非空鏈表的操作統(tǒng)一，我們可以像單鏈表一樣設(shè)置一個頭結(jié)點，但同樣的，頭結(jié)點對于循環(huán)鏈表并不是必需的。

循環(huán)鏈表的空表
循環(huán)鏈表的非空表

對于有頭結(jié)點的循環(huán)鏈表，判斷非空的條件為： p->next != p 為真，則循環(huán)列表非空，反之為空。

對于這樣的循環(huán)鏈表，我們只需要 O(1) 的時間即可訪問到頭結(jié)點和第一個元素。然后我們將頭指針修改為指向終端元素的指針，就可以只需要 O(1) 的時間即可訪問到頭結(jié)點和第一個元素，以及終端結(jié)點。

頭指針指向終端結(jié)點的循環(huán)鏈表

當(dāng)頭指針指向終端結(jié)點時，要將兩循環(huán)鏈表合并，操作會方便很多。

頭指針指向終端結(jié)點的循環(huán)鏈表的合并操作 代碼實現(xiàn)：

p = rearA->next;
q = rearB->next;
rearA->next = rearB->next-next;
rearB->next = p;
free(q);

雙向鏈表

雙向鏈表（double linked list）： 是指在單鏈表的每個結(jié)點中再設(shè)置一個指針域，用于指向其直接前驅(qū)元素。

雙向鏈表的代碼實現(xiàn)如下：

typedef struct DulNode{
    Elemtype data;
    struct DulNode *next;    //直接后繼
    struct DulNode *prior;    //直接前驅(qū)
}DulNode, *DulNodeList;

同樣地，雙向鏈表也有循環(huán)鏈表。

相比于單鏈表，雙向鏈表多了反向遍歷的操作。不過插入和刪除的代碼復(fù)雜度會高一些。

雙向鏈表插入算法的代碼實現(xiàn)如下：

//假設(shè) s 是要插入的結(jié)點的地址
s->prior = p;
s->next = p->next;
s->next->prior = s;
p->next = s;
插入

雙向鏈表刪除算法的代碼實現(xiàn)如下：

//假設(shè) s 是要刪除的結(jié)點的地址
s->prior->next = s->next;
s->next->prior = s->prior;
free(s);
刪除
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容