數(shù)據(jù)結(jié)構(gòu)：鏈表

本文內(nèi)容：
1、什么是鏈表职辨？
2盗蟆、鏈表共分幾類？
3拨匆、鏈表的 C 實(shí)現(xiàn)姆涩！

工程代碼 Github: Data_Structures_C_Implemention -- Link List

1惭每、什么是鏈表？

鏈表 [Linked List]：鏈表是由一組不必相連【不必相連：可以連續(xù)也可以不連續(xù)】的內(nèi)存結(jié)構(gòu) 【節(jié)點(diǎn)】，按特定的順序鏈接在一起的抽象數(shù)據(jù)類型台腥。

補(bǔ)充：
抽象數(shù)據(jù)類型（Abstract Data Type [ADT]）：表示數(shù)學(xué)中抽象出來的一些操作的集合宏赘。
內(nèi)存結(jié)構(gòu)：內(nèi)存中的結(jié)構(gòu)，如：struct黎侈、特殊內(nèi)存塊...等等之類察署；

2、鏈表共分幾類峻汉？

鏈表常用的有 3 類：單鏈表贴汪、雙向鏈表、循環(huán)鏈表休吠。

鏈表.png

鏈表的核心操作集有 3 種：插入扳埂、刪除、查找【遍歷】

單鏈表

單鏈表 [Linked List]：由各個(gè)內(nèi)存結(jié)構(gòu)通過一個(gè) Next 指針鏈接在一起組成瘤礁，每一個(gè)內(nèi)存結(jié)構(gòu)都存在后繼內(nèi)存結(jié)構(gòu)【鏈尾除外】阳懂，內(nèi)存結(jié)構(gòu)由數(shù)據(jù)域和 Next 指針域組成。

單鏈表實(shí)現(xiàn)圖示：

文字解析：

Data 數(shù)據(jù) + Next 指針柜思，組成一個(gè)單鏈表的內(nèi)存結(jié)構(gòu) 岩调；
第一個(gè)內(nèi)存結(jié)構(gòu)稱為鏈頭，最后一個(gè)內(nèi)存結(jié)構(gòu)稱為鏈尾赡盘；
鏈尾的 Next 指針設(shè)置為 NULL [指向空]号枕；
單鏈表的遍歷方向單一【只能從鏈頭一直遍歷到鏈尾】

單鏈表操作集：

單向鏈表-操作.png

雙向鏈表

雙向鏈表 [Double Linked List]：由各個(gè)內(nèi)存結(jié)構(gòu)通過指針 Next 和指針 Prev 鏈接在一起組成，每一個(gè)內(nèi)存結(jié)構(gòu)都存在前驅(qū)內(nèi)存結(jié)構(gòu)和后繼內(nèi)存結(jié)構(gòu)【鏈頭沒有前驅(qū)陨享，鏈尾沒有后繼】葱淳，內(nèi)存結(jié)構(gòu)由數(shù)據(jù)域、Prev 指針域和 Next 指針域組成霉咨。

雙向鏈表實(shí)現(xiàn)圖示：

文字解析：

Data 數(shù)據(jù) + Next 指針 + Prev 指針蛙紫，組成一個(gè)雙向鏈表的內(nèi)存結(jié)構(gòu)；
第一個(gè)內(nèi)存結(jié)構(gòu)稱為鏈頭途戒，最后一個(gè)內(nèi)存結(jié)構(gòu)稱為鏈尾坑傅；
鏈頭的 Prev 指針設(shè)置為 NULL，鏈尾的 Next 指針設(shè)置為 NULL喷斋；
Prev 指向的內(nèi)存結(jié)構(gòu)稱為前驅(qū)唁毒， Next 指向的內(nèi)存結(jié)構(gòu)稱為后繼；
雙向鏈表的遍歷是雙向的星爪，即如果把從鏈頭的 Next 一直到鏈尾的[NULL] 遍歷方向定義為正向浆西，那么從鏈尾的 Prev 一直到鏈頭 [NULL ]遍歷方向就是反向；

雙向鏈表操作集：

雙向鏈表-操作.png

循環(huán)鏈表

單向循環(huán)鏈表 [Circular Linked List] : 由各個(gè)內(nèi)存結(jié)構(gòu)通過一個(gè)指針 Next 鏈接在一起組成顽腾，每一個(gè)內(nèi)存結(jié)構(gòu)都存在后繼內(nèi)存結(jié)構(gòu)近零，內(nèi)存結(jié)構(gòu)由數(shù)據(jù)域和 Next 指針域組成诺核。

雙向循環(huán)鏈表 [Double Circular Linked List] : 由各個(gè)內(nèi)存結(jié)構(gòu)通過指針 Next 和指針 Prev 鏈接在一起組成，每一個(gè)內(nèi)存結(jié)構(gòu)都存在前驅(qū)內(nèi)存結(jié)構(gòu)和后繼內(nèi)存結(jié)構(gòu)久信，內(nèi)存結(jié)構(gòu)由數(shù)據(jù)域窖杀、Prev 指針域和 Next 指針域組成。

循環(huán)鏈表的單向與雙向?qū)崿F(xiàn)圖示：

文字解析：

循環(huán)鏈表分為單向裙士、雙向兩種入客；
單向的實(shí)現(xiàn)就是在單鏈表的基礎(chǔ)上，把鏈尾的 Next 指針直接指向鏈頭腿椎，形成一個(gè)閉環(huán)桌硫；
雙向的實(shí)現(xiàn)就是在雙向鏈表的基礎(chǔ)上，把鏈尾的 Next 指針指向鏈頭啃炸，再把鏈頭的 Prev 指針指向鏈尾铆隘，形成一個(gè)閉環(huán)；
循環(huán)鏈表沒有鏈頭和鏈尾的說法肮帐，因?yàn)槭情]環(huán)的咖驮，所以每一個(gè)內(nèi)存結(jié)構(gòu)都可以充當(dāng)鏈頭和鏈尾；

循環(huán)鏈表操作集：

循環(huán)鏈表-操作.png

3训枢、鏈表的 C 實(shí)現(xiàn)托修！

單鏈表

節(jié)點(diǎn)[內(nèi)存結(jié)構(gòu)]與鏈表的定義：

節(jié)點(diǎn)[內(nèi)存結(jié)構(gòu)]，

struct __ListNode {
    ElementTypePrt data; // 數(shù)據(jù)域
    ListNode next; // 指針域 [指向下一個(gè)節(jié)點(diǎn)]
};

解析：struct __ListNode 就是一個(gè)節(jié)點(diǎn)的內(nèi)存結(jié)構(gòu)恒界，因?yàn)橐粋€(gè)節(jié)點(diǎn)包含了兩個(gè)不同的信息睦刃，而且相互沒有共享內(nèi)存，所以在 C 語言環(huán)境下選擇 struct 去表示十酣；

1涩拙、ElementTypePrt 原型是 typedef void * ElementTypePrt;，使用 typedef 是方便后期進(jìn)行修改耸采；這里使用指針的目的是為了讓鏈表支持更多的數(shù)據(jù)類型兴泥，使代碼的可擴(kuò)展性更強(qiáng)；【如： data 可以直接指向一個(gè)單純的 int 或者一個(gè) struct 虾宇，又或者是一個(gè) list 等等】

2搓彻、ListNode 原型是

typedef struct __ListNode * _ListNode;
typedef _ListNode ListNode;

這里使用 typedef 是為了后面定義函數(shù)接口，以及具體代碼實(shí)現(xiàn)更為簡潔嘱朽；

單鏈表【有時(shí)也簡稱旭贬，鏈表】，

struct __List {
    unsigned int size;  // 鏈表的長度
    MatchFunc matchFunc; // 兩個(gè)節(jié)點(diǎn)的數(shù)據(jù)匹配
    DestroyFunc destroyFunc; // 節(jié)點(diǎn)數(shù)據(jù)的釋放
    ListNode head; // 鏈表的鏈頭指針
    ListNode tail; // 鏈表的鏈尾指針
};

解析：
1搪泳、MatchFunc 原型是 typedef _BOOL(*MatchFunc) (const void *key1, const void *key2); 指向形如 _BOOL(*) (const void *key1, const void *key2); 的函數(shù)指針稀轨；原因，上面提到過 data 是可以指向任意類型的岸军，也就是說兩個(gè)節(jié)點(diǎn)的 data 怎樣才算匹配奋刽，設(shè)計(jì)者是不知道的瓦侮，只有使用者才知道，所以提供一個(gè)函數(shù)接口杨名，讓使用者根據(jù)自身的情況進(jìn)行數(shù)據(jù)匹配脏榆；也是為了代碼可擴(kuò)展性猖毫；

2台谍、_BOOL 原型是

typedef enum __BOOL {
    LINKEDLIST_TRUE  = 1,
    LINKEDLIST_FALSE = 0,
}_BOOL;

目的是為了提高代碼的可讀性，不建議在代碼中直接使用數(shù)字吁断，因?yàn)檎l也不知道那是個(gè)啥趁蕊；【過個(gè)幾天，你自己估計(jì)也會(huì)忘掉仔役，那個(gè)數(shù)字表示啥】

3掷伙、DestroyFunc 原型是 typedef void(*DestroyFunc) (void * data); 指向形如 void(*) (void * data); 的函數(shù)指針；data 如何進(jìn)行釋放也由使用者決定又兵；也是為了代碼可擴(kuò)展性任柜；

4、size + head + tail 是鏈表的基本要素沛厨，當(dāng)然您也可以根據(jù)自身情況宙地，增加個(gè)別要素；

單鏈表的核心操作集：

/* Create */ 

List List_Create(DestroyFunc des);
void List_Init(List l, DestroyFunc des);
void List_Destroy(List l);

/* Operations */

Position List_Find(List l, MatchFunc mat, ElementTypePrt const x);
Position List_FindPrevious(List l, MatchFunc mat, ElementTypePrt const x);

_BOOL List_Insert(List l, Position p, ElementTypePrt const x);
_BOOL List_Remove(List l, Position deletePrev, ElementTypePrtPrt const x);

單鏈表的創(chuàng)建與銷毀：

創(chuàng)建逆皮，

List List_Create(DestroyFunc des) {
    
    List l = (List)(malloc(sizeof(struct __List)));  // 1
    if (l == NULL) { printf("ERROR: Out Of Space !"); return NULL; } // 2

    List_Init(l, des); // 3

    return l;

}

解析：
1宅粥、List_Create 函數(shù)功能是創(chuàng)建并初始化一個(gè)空鏈表；
// 1 行 1 电谣，malloc 函數(shù)是 C 語言中進(jìn)行內(nèi)存創(chuàng)建的函數(shù)秽梅，需要提供的參數(shù)是 size_t ，就是空鏈表的要占的內(nèi)存大小剿牺，所以使用 sizeof 來計(jì)算內(nèi)存大衅罂选；

2晒来、// 2 行 2 是防止钞诡，內(nèi)存分配失敗潜索；

3臭增、// 3 請(qǐng)移步下面的 初始化 解析;

初始化，

void List_Init(List l, DestroyFunc des) {

    if (l == NULL) { printf("ERROR: Bad List !"); return; }

    l->size = LINKEDLIST_EMPTY; // LINKEDLIST_EMPTY 就是 0
    l->matchFunc = NULL;
    l->destroyFunc = des;
    l->head = NULL;
    l->tail = NULL;

}

解析：
1竹习、List_Init 目的就是要把一個(gè)創(chuàng)建好的表初始化為需要的空表狀態(tài)誊抛；

2、LINKEDLIST_EMPTY 原型是 #define LINKEDLIST_EMPTY 0 提高代碼可讀性整陌；

3拗窃、l->head = NULL; l->tail = NULL; 因?yàn)闆]有節(jié)點(diǎn)瞎领，直接置空即可；

銷毀随夸，

void List_Destroy(List l) {
    
    if (l == NULL) { printf("ERROR: Please Using List_Create(...) First !"); return; }

    ElementTypePrt data;

    while (!List_IsEmpty(l)) { // 1
        if ((List_Remove(l, NULL, (ElementTypePrtPrt)&data) == LINKEDLIST_TRUE) &&
            (l->destroyFunc != NULL)) { // 2
            
            l->destroyFunc(data);
        }
    }

    memset(l, 0, sizeof(struct __List)); // 3
    
}

解析：這個(gè)函數(shù)的功能就是九默，釋放鏈表中所有的節(jié)點(diǎn)，并把鏈表置成空鏈表宾毒；
1驼修、 // 1 List_IsEmpty 原型是

_BOOL List_IsEmpty(List l) { return ((l->size == LINKEDLIST_EMPTY) ? LINKEDLIST_TRUE
                                                                   : LINKEDLIST_FALSE); }

2、// 2 請(qǐng)移步下面 刪除操作 的解析诈铛；

3乙各、 // 3 memset 原型是 void* memset(void* _Dst, int _Val, size_t _Size); 功能是，設(shè)置內(nèi)存塊的值幢竹，這三個(gè)參數(shù)分別表示耳峦，內(nèi)存塊個(gè)數(shù)、設(shè)置的內(nèi)存單元的值焕毫、要設(shè)置的內(nèi)存空間大卸卓馈；

插入操作：

_BOOL List_Insert(List l, Position p, ElementTypePrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }

    /* Create New Node */
    ListNode lNew = ListNode_Create(x);  // 1

    int isLastNode = (p == NULL); // 2

    if (isLastNode) {
    
        if (List_IsEmpty(l)) { l->tail = lNew; }

        /* Insert Operations */ // 3
        lNew->next = l->head;
        l->head = lNew;

    } else {

        if (p->next == NULL) { l->tail = p; }

        /* Insert Operations */ // 4
        lNew->next = p->next;
        p->next = lNew;

    }

    /* Size ++ */
    l->size++;

    return LINKEDLIST_TRUE;

}

解析：函數(shù)的功能是在指定的節(jié)點(diǎn)后面插入一個(gè)新的節(jié)點(diǎn)邑飒；
鏈表中的插入循签，不外乎鏈頭后面、中間位置幸乒、鏈尾后面三個(gè)位置懦底；

1、// 1 ListNode_Create 原型是

ListNode ListNode_Create(ElementTypePrt const x) {
    
    ListNode lNew = (ListNode)malloc(sizeof(struct __ListNode));
    if (lNew == NULL) { printf("ERROR: Out Of Space !"); return NULL; }

    lNew->data = x;
    lNew->next = NULL;

    return lNew;

}

此處不解析;

2罕扎、// 2 這里是為了區(qū)分插入發(fā)生在鏈頭與鏈尾聚唐，還是中間位置與鏈尾；

3腔召、// 3 與 // 4 就是鏈表插入的核心操作杆查，

插入操作圖示，

// 對(duì)應(yīng)的核心代碼
lNew->next = p->next;
p->next = lNew;

刪除操作：

_BOOL List_Remove(List l, Position deletePrev, ElementTypePrtPrt const x) {
    
    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (List_IsEmpty(l)) { printf("ERROR: Empty List !"); return LINKEDLIST_FALSE; }

    int isHeadNode = (deletePrev == NULL);

    ListNode lDelete = NULL;
    if (isHeadNode) {
    
        /* Get The Deleted Data ! */
        *x = l->head->data;

        /* Delete Operations */
        lDelete = l->head;
        l->head = l->head->next;

        if (List_Size(l) == 1) { l->tail = NULL; }

    } else {

        /* Can`t Delete ... */
        if (deletePrev->next == NULL) { return LINKEDLIST_FALSE; }

        /* Get The Deleted Data ! */
        *x = deletePrev->next->data;

        /* Delete Operations */
        lDelete = deletePrev->next;
        deletePrev->next = deletePrev->next->next;

        if (deletePrev->next == NULL) { l->tail = deletePrev; }

    }

    /* Free The Deleted Node */
    free(lDelete);

    /* Size -- */
    l->size--;

    return LINKEDLIST_TRUE;
}

解析：函數(shù)功能是刪除鏈表節(jié)點(diǎn)臀蛛；
刪除操作在單鏈表中比較特殊亲桦，因?yàn)殒湵硎菃蜗颍磸逆滎^到鏈尾浊仆，而要?jiǎng)h除的節(jié)點(diǎn)并沒有指向前面節(jié)點(diǎn)的能力客峭，所以要使用需刪除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)進(jìn)行刪除操作；

刪除操作圖示抡柿，

// 對(duì)應(yīng)的核心代碼
lDelete = deletePrev->next;
deletePrev->next = deletePrev->next->next;

free(lDelete);

遍歷操作：

上面的插入與刪除操作都要提供一個(gè) Position 參數(shù)舔琅，不然兩個(gè)函數(shù)沒法用，而尋找這個(gè)行為就是遍歷操作洲劣；

這里提供兩個(gè)遍歷操作备蚓，

Position List_Find(List l, MatchFunc mat, ElementTypePrt const x);
Position List_FindPrevious(List l, MatchFunc mat, ElementTypePrt const x);

遍歷其實(shí)就是匹配內(nèi)容课蔬，也就是要用到前面提到的 MatchFunc 函數(shù)，這個(gè)具體的匹配函數(shù)由用使用者實(shí)現(xiàn)郊尝；

Position List_Find(List l, MatchFunc mat, ElementTypePrt const x) 函數(shù)：

// Position 就是 ListNode 的別名
Position List_Find(List l, MatchFunc mat, ElementTypePrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return NULL; }
    if (List_IsEmpty(l)) { printf("ERROR: Empty List !"); return NULL; }

    if (mat == NULL) { printf("ERROR: Bad Match Function !"); return NULL; }
    l->matchFunc = mat;

    Position p = NULL;
    for (p = List_Head(l); p != NULL; p = List_NodeNext(p)) {  // 1
        if (mat(x, List_NodeData(p))) { return p; } // 2
    }

    return NULL;

}

解析：函數(shù)功能是遍歷鏈表二跋，查找與當(dāng)前節(jié)點(diǎn)內(nèi)容匹配的節(jié)點(diǎn)；
1流昏、// 1 從鏈頭開始扎即，不斷地用 next 來進(jìn)行指針偏移，一直到鏈尾才結(jié)束【因?yàn)殒溛驳?next 肯定是 NULL 所以使用它來結(jié)束循環(huán)】横缔；

2铺遂、// 2 這一次的匹配都使用用戶實(shí)現(xiàn)的 MatchFunc 函數(shù)；

3茎刚、List_Head 就是 l->head，List_NodeNext 就是 p->next撤逢，List_NodeData 就是 p->data膛锭；

List_FindPrevious (...): 函數(shù)功能是遍歷鏈表，查找與當(dāng)前節(jié)點(diǎn)內(nèi)容匹配的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)蚊荣；遍歷原理與 List_Find (...) 是一樣的;

雙向鏈表

節(jié)點(diǎn)[內(nèi)存結(jié)構(gòu)]與雙向鏈表的定義：

節(jié)點(diǎn)[內(nèi)存結(jié)構(gòu)]初狰，

typedef struct __DoubleListNode * _DoubleListNode;
typedef _DoubleListNode DoubleListNode;
typedef _DoubleListNode DoublePosition;

struct __DoubleListNode {
    ElementTypePrt data;
    DoubleListNode prev;
    DoubleListNode next;
};

解析：
因?yàn)殡p向鏈表有前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，所以內(nèi)存結(jié)構(gòu)要在單鏈表的內(nèi)存結(jié)構(gòu)基礎(chǔ)上互例，增加一個(gè) prev 指針指向節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)奢入；

雙向鏈表，

typedef struct __DoubleList * _DoubleList;
typedef _DoubleList DoubleList;

struct __DoubleList {
    unsigned int size;
    MatchFunc matchFunc;
    DestroyFunc destroyFunc;
    DoubleListNode head;
    DoubleListNode tail;
};

因?yàn)殡p向鏈表只是在單鏈表的基礎(chǔ)上增加了一個(gè)遍歷方向媳叨，并沒有改變鏈表的其它內(nèi)容腥光，所以與單鏈表的定義一致，不再進(jìn)行解析糊秆；

雙向鏈表的核心操作集：

/* Create */

DoubleList DoubleList_Create(DestroyFunc des);
void DoubleList_Init(DoubleList l, DestroyFunc des);
void DoubleList_Destroy(DoubleList l);

/* Operations */

DoublePosition DoubleList_Find(DoubleList l, MatchFunc mat, ElementTypePrt const x);
DoublePosition DoubleList_Find_Reverse(DoubleList l, MatchFunc mat, ElementTypePrt const x);

_BOOL DoubleList_Insert_Prev(DoubleList l, DoublePosition p, ElementTypePrt const x);
_BOOL DoubleList_Insert_Next(DoubleList l, DoublePosition p, ElementTypePrt const x);
_BOOL DoubleList_Remove(DoubleList l, DoublePosition p, ElementTypePrtPrt const x);

雙向鏈表的創(chuàng)建與銷毀：

創(chuàng)建武福、初始化、銷毀痘番，這三個(gè)操作與單鏈表的實(shí)現(xiàn)基本一致捉片，具體的可以查看工程代碼；

插入操作 [分為兩種汞舱，在指定節(jié)點(diǎn)前插入和在指定節(jié)點(diǎn)后插入] ：

在指定節(jié)點(diǎn)后插入

// 在指定節(jié)點(diǎn)后插入
_BOOL DoubleList_Insert_Next(DoubleList l, DoublePosition p, ElementTypePrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (p == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }

    /* Create New Node */
    DoubleListNode lNew = DoubleListNode_Create(x);

    if (DoubleList_IsEmpty(l)) {
    
        l->head = l->tail = lNew;  // 1

    } else {
    
        // 2
        lNew->prev = p;
        lNew->next = p->next;

        _BOOL isLastNode = (p->next == NULL);
        if (isLastNode) {
            l->tail = lNew;
        } else {
            p->next->prev = lNew;
        }

        p->next = lNew;

    }

    /* Size ++ */
    l->size++;

    return LINKEDLIST_TRUE;

}

解析：
1伍纫、當(dāng)鏈表是空表的時(shí)候，鏈頭和鏈尾就要指向新創(chuàng)建的節(jié)點(diǎn)昂芜，這是要注意的莹规；

2、雙向鏈表插入圖示说铃，

// 對(duì)應(yīng)代碼
// 2
lNew->prev = p;
lNew->next = p->next;
p->next->prev = lNew;
p->next = lNew;

在指定節(jié)點(diǎn)前插入

// 在指定節(jié)點(diǎn)前插入
_BOOL DoubleList_Insert_Prev(DoubleList l, DoublePosition p, ElementTypePrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (p == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }

    /* Create New Node */
    DoubleListNode lNew = DoubleListNode_Create(x);

    if (DoubleList_IsEmpty(l)) {

        l->head = l->tail = lNew;

    } else {

        lNew->next = p;
        lNew->prev = p->prev;

        _BOOL isFirstNode = (p->prev == NULL);
        if (isFirstNode) {
            l->head = lNew;
        } else {
            p->prev->next = lNew;
        }

        p->prev = lNew;

    }

    /* Size ++ */
    l->size++;

    return LINKEDLIST_TRUE;

}

解析：這個(gè)插入方法的核心代碼是访惜，

lNew->next = p;
lNew->prev = p->prev;
p->prev->next = lNew;
p->prev = lNew;

其實(shí)原理是一樣的嘹履，只是插入的方向不同；你把上面的兩個(gè)插入方法的核心代碼對(duì)比一下就知道了债热，只是把 prev 和 next 的位置改了一下砾嫉；而能輕松的原因是，鏈表的雙向遍歷只是單純的方向不同窒篱，其它沒有任何區(qū)別焕刮，非常像兩個(gè)單鏈表組合在一起；

刪除操作：

_BOOL DoubleList_Remove(DoubleList l, DoublePosition p, ElementTypePrtPrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (p == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }
    if (DoubleList_IsEmpty(l)) { printf("ERROR: Empty List !"); return LINKEDLIST_FALSE; }

    /* Get Data */
    *x = p->data;

    _BOOL isHeadNode = ( p == l->head );

    if (isHeadNode) {
        
        l->head = p->next;

        _BOOL isEmpty = (l->head == NULL);
        if (isEmpty) {
            l->tail = NULL;
        } else {
            // p->next->prev = NULL;
            l->head->prev = NULL; 
        }

    } else {
    
        p->prev->next = p->next;

        _BOOL isLastNode = (p->next == NULL);
        if (isLastNode) {
            l->tail = p->prev;
        } else {
            p->next->prev = p->prev;
        }

    }

    /* Free The Deleted Node */
    free(p);

    /* Size -- */
    l->size--;

    return LINKEDLIST_TRUE;

}

解析：函數(shù)功能是刪除指定的節(jié)點(diǎn)墙杯；由于雙向鏈表有前驅(qū)節(jié)點(diǎn)配并，所以可以輕松地通過指定的節(jié)點(diǎn)的 prev 指針得到前一個(gè)節(jié)點(diǎn)，而不像單鏈表的刪除那樣要使用指定節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)再進(jìn)行刪除操作高镐；

核心刪除操作圖示溉旋，

// 對(duì)應(yīng)的核心代碼
p->prev->next = p->next;
p->next->prev = p->prev;

free(p);

與單鏈表的刪除相比，雙向鏈表的刪除操作更加簡單嫉髓；

遍歷操作：因?yàn)槭请p向鏈表所以遍歷就有兩個(gè)方向观腊；

DoublePosition DoubleList_Find(DoubleList l, MatchFunc mat, ElementTypePrt const x);
DoublePosition DoubleList_Find_Reverse(DoubleList l, MatchFunc mat, ElementTypePrt const x);

從鏈頭到鏈尾的遍歷 DoubleList_Find ，

DoublePosition DoubleList_Find(DoubleList l, MatchFunc mat, ElementTypePrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return NULL; }
    if (DoubleList_IsEmpty(l)) { printf("ERROR: Empty List !"); return NULL; }

    if (mat == NULL) { printf("ERROR: Bad Match Function !"); return NULL; }
    l->matchFunc = mat;

    DoublePosition p = NULL;
    for (p = DoubleList_Head(l); p != NULL; p = DoubleList_NodeNext(p)) {
        if (mat(x, DoubleList_NodeData(p))) { return p; }
    }

    return NULL;

}

它的實(shí)現(xiàn)與單鏈表的 List_Find 方法實(shí)現(xiàn)原理上完全一樣算行，不同的就是函數(shù)名和節(jié)點(diǎn)而已梧油，所以你如果單鏈表的看懂了，那么這里也就懂了州邢。

從鏈尾到鏈頭的遍歷 DoubleList_Find_Reverse儡陨，

DoublePosition DoubleList_Find_Reverse(DoubleList l, MatchFunc mat, ElementTypePrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return NULL; }
    if (DoubleList_IsEmpty(l)) { printf("ERROR: Empty List !"); return NULL; }

    if (mat == NULL) { printf("ERROR: Bad Match Function !"); return NULL; }
    l->matchFunc = mat;

    DoublePosition p = NULL;
    for (p = DoubleList_Tail(l); p != NULL; p = DoubleList_NodePrev(p)) {
        if (mat(x, DoubleList_NodeData(p))) { return p; }
    }

    return NULL;

}

原理與上面的方法是一致的，它們不同的只是方向量淌，前者是骗村，
for (p = DoubleList_Head(l); p != NULL; p = DoubleList_NodeNext(p))
[ head --到-- Tail (next) ]
后者是，for (p = DoubleList_Tail(l); p != NULL; p = DoubleList_NodePrev(p))
[ Tail --到-- Next (prev) ] ;

循環(huán)鏈表

單向循環(huán)鏈表：

單向循環(huán)鏈表的節(jié)點(diǎn)與鏈表：

/* struct */
struct __CircularListNode {
    ElementTypePrt data;
    CircularListNode next;
};

struct __CircularList {
    unsigned int size;
    MatchFunc matchFunc;
    DestroyFunc destroyFunc;
    CircularListNode head;
};

與單鏈表唯一的不同是类少，沒有 tail 指針叙身，因?yàn)殒湵硎茄h(huán)的，所以不存在尾這個(gè)說法硫狞；

單向循環(huán)鏈表的核心操作集：與單鏈表的操作集也是一樣的信轿，這里就列出來一下；

/* Create */

CircularList CircularList_Create(DestroyFunc des);
void CircularList_Init(CircularList l, DestroyFunc des);
void CircularList_Destroy(CircularList l);

/* Operations */
CircularPosition CircularList_Find(CircularList l, MatchFunc mat, ElementTypePrt const x);
CircularPosition CircularList_FindPrevious(CircularList l, MatchFunc mat, ElementTypePrt const x);

_BOOL CircularList_Insert(CircularList l, CircularPosition p, ElementTypePrt const x);
_BOOL CircularList_Remove(CircularList l, CircularPosition deletePrev, ElementTypePrtPrt const x);

單向循環(huán)鏈表的創(chuàng)建與銷毀：與單鏈表的實(shí)現(xiàn)完全一樣残吩；
插入操作：

_BOOL CircularList_Insert(CircularList l, CircularPosition p, ElementTypePrt const x) {
    
    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (p == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }

    /* Create New Node */
    CircularListNode lNew = CircularListNode_Create(x);

    if (CircularList_IsEmpty(l)) {
        
        p->next = p;
        l->head = p;

    } else {
    
        /* Insert Operations */
        lNew->next = p->next;
        p->next = lNew;

    }

    /* Size ++ */
    l->size++;

    return LINKEDLIST_TRUE;

}

因?yàn)闆]有 NULL 指針的存在财忽，所以插入過程的出錯(cuò)判斷就變得很少；

單向循環(huán)鏈表插入操作圖示泣侮，

// 對(duì)應(yīng)的代碼
lNew->next = p->next;
p->next = lNew;

這里的核心代碼與單鏈表插入操作的核心代碼是一樣的即彪；

刪除操作：

_BOOL CircularList_Remove(CircularList l, CircularPosition deletePrev, ElementTypePrtPrt const x) {
    
    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (deletePrev == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }
    if (CircularList_IsEmpty(l)) { printf("ERROR: Empty List !"); return LINKEDLIST_FALSE; }

    *x = deletePrev->next->data;

    CircularListNode lDelete = NULL;

    _BOOL isOnlyOneNode = (deletePrev->next == deletePrev);
    if (isOnlyOneNode) {
        
        lDelete = deletePrev->next;
        l->head = NULL;

    } else {
    
        /* Delete Operations */
        lDelete = deletePrev->next;
        deletePrev->next = deletePrev->next->next;

        if (lDelete == l->head) { l->head = lDelete->next; }

    }

    /* Free The Deleted Node */
    if (lDelete != NULL) { free(lDelete); }

    /* Size -- */
    l->size--;

    return LINKEDLIST_TRUE;

}

單向鏈表刪除操作圖示，

// 對(duì)應(yīng)核心代碼
lDelete = p->next;
p->next = p->next->next;

free(lDelete);

這里的核心代碼與單鏈表刪除操作的核心代碼是一樣的；

遍歷操作：與單鏈表的遍歷原理一樣隶校，不同的是結(jié)束條件漏益；

CircularPosition CircularList_Find(...) 函數(shù)：

CircularPosition CircularList_Find(CircularList l, MatchFunc mat, ElementTypePrt const x) {
    
    if (l == NULL) { printf("ERROR: Bad List !"); return NULL; }
    if (CircularList_IsEmpty(l)) { printf("ERROR: Empty List !"); return NULL; }

    if (mat == NULL) { printf("ERROR: Bad Match Function !"); return NULL; }
    l->matchFunc = mat;

    CircularPosition p = CircularList_Head(l);

    while ( ! mat(x, CircularList_NodeData(p))) {
        p = CircularList_NodeNext(p);
        if (p == CircularList_Head(l)) { p = NULL; break; }
    }

    return p;

}

解析，
這里主要是結(jié)束條件的選擇深胳，循環(huán)鏈表的起點(diǎn)是 head 那么結(jié)束自然而然也是 head 了绰疤，所以 if (p == CircularList_Head(l)) { p = NULL; break; } 直接跳出循環(huán)就可以了；

CircularPosition CircularList_FindPrevious(...) 函數(shù)：

CircularPosition CircularList_FindPrevious(CircularList l, MatchFunc mat, ElementTypePrt const x) {

    if (l == NULL) { printf("ERROR: Bad List !"); return NULL; }
    if (CircularList_IsEmpty(l)) { printf("ERROR: Empty List !"); return NULL; }

    if (mat == NULL) { printf("ERROR: Bad Match Function !"); return NULL; }
    l->matchFunc = mat;

    CircularPosition p = CircularList_Head(l);

    while ( ! mat(x, CircularList_NodeData(CircularList_NodeNext(p)))) {

        CircularPosition nextP = CircularList_NodeNext(p);
        if (nextP == CircularList_Head(l)) {

            if ( ! mat(x, CircularList_NodeData(CircularList_NodeNext(p)))) { 
                p = NULL; 
                break;
            }

            break;
        }

        p = nextP;

    }

    return p;

}

解析舞终，
這里的起點(diǎn)是 head->next 轻庆，但是由于循環(huán)與前一個(gè)節(jié)點(diǎn)的約束條件，結(jié)束點(diǎn)就是 head 的 next 節(jié)點(diǎn)敛劝，因?yàn)?head->next 要被訪問兩次余爆，所以最后一次的訪問，就是鏈表遍歷結(jié)束的條件夸盟；

        CircularPosition nextP = CircularList_NodeNext(p);
        if (nextP == CircularList_Head(l)) {

            if ( ! mat(x, CircularList_NodeData(CircularList_NodeNext(p)))) { 
                p = NULL; 
                break;
            }

            break;
        }

這里是先判斷下一個(gè)節(jié)點(diǎn)是否是 head 已經(jīng)結(jié)束了蛾方，因?yàn)?head 是最后一個(gè)要被訪問的；

雙向循環(huán)鏈表：

雙向循環(huán)鏈表的節(jié)點(diǎn)與鏈表：

/* struct */
struct __DoubleCircularListNode {
    ElementTypePrt data;
    DoubleCircularListNode prev;
    DoubleCircularListNode next;
};

struct __DoubleCircularList {
    unsigned int size;
    MatchFunc matchFunc;
    DestroyFunc destroyFunc;
    DoubleCircularListNode head;
};

與雙向鏈表的實(shí)現(xiàn)區(qū)別就是满俗，沒有 tail 指針转捕；

雙向循環(huán)鏈表的核心操作集：與雙向鏈表的操作集一致；

/* Create */

DoubleCircularList DoubleCircularList_Create(DestroyFunc des);
void DoubleCircularList_Init(DoubleCircularList l, DestroyFunc des);
void DoubleCircularList_Destroy(DoubleCircularList l);

/* Operations */
DoubleCircularPosition DoubleCircularList_Find(DoubleCircularList l, MatchFunc mat, ElementTypePrt const x);
DoubleCircularPosition DoubleCircularList_Find_Reverse(DoubleCircularList l, MatchFunc mat, ElementTypePrt const x);

_BOOL DoubleCircularList_InsertInTail(DoubleCircularList l, ElementTypePrt const x);
_BOOL DoubleCircularList_Insert_Prev(DoubleCircularList l, DoubleCircularPosition p, ElementTypePrt const x);
_BOOL DoubleCircularList_Insert_Next(DoubleCircularList l, DoubleCircularPosition p, ElementTypePrt const x);
_BOOL DoubleCircularList_Remove(DoubleCircularList l, DoubleCircularPosition p, ElementTypePrtPrt const x);

雙向循環(huán)鏈表的創(chuàng)建與銷毀：與雙向鏈表的實(shí)現(xiàn)一致唆垃；
插入操作：

指定節(jié)點(diǎn)前的插入，

_BOOL 
DoubleCircularList_Insert_Prev( DoubleCircularList l, 
                                DoubleCircularPosition p, 
                                ElementTypePrt const x ) {
    
    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (p == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }

    /* Create New Node */
    DoubleCircularListNode lNew = DoubleCircularListNode_Create(x);

    if (DoubleCircularList_IsEmpty(l)) {

        l->head = lNew;
        l->head->prev = lNew;
        l->head->next = lNew;
    }
    else {

        lNew->next = p;
        lNew->prev = p->prev;

        p->prev->next = lNew;
        p->prev = lNew;

    }

    /* Size ++ */
    l->size++;

    return LINKEDLIST_TRUE;

}

指定節(jié)點(diǎn)后的插入痘儡，

_BOOL 
DoubleCircularList_Insert_Next( DoubleCircularList l,
                                DoubleCircularPosition p, 
                                ElementTypePrt const x ) {

    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (p == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }

    /* Create New Node */
    DoubleCircularListNode lNew = DoubleCircularListNode_Create(x);

    if (DoubleCircularList_IsEmpty(l)) {

        l->head = lNew;
        l->head->prev = lNew;
        l->head->next = lNew;

    }
    else {

        lNew->prev = p;
        lNew->next = p->next;

        p->next->prev = lNew;
        p->next = lNew;

    }

    /* Size ++ */
    l->size++;

    return LINKEDLIST_TRUE;

}

解析辕万，
上面的兩個(gè)插入操作與雙向鏈表的實(shí)現(xiàn)原理是一樣的，區(qū)別就是插入操作的錯(cuò)誤處理更少沉删；

雙向循環(huán)鏈表插入操作圖示渐尿，

// 對(duì)應(yīng)核心代碼
lNew->prev = p;
lNew->next = p->next;
p->next->prev = lNew;
p->next = lNew;

刪除操作：

_BOOL 
DoubleCircularList_Remove( DoubleCircularList l,
                           DoubleCircularPosition p,
                           ElementTypePrtPrt const x ) {

    if (l == NULL) { printf("ERROR: Bad List !"); return LINKEDLIST_FALSE; }
    if (p == NULL) { printf("ERROR: Bad Position !"); return LINKEDLIST_FALSE; }

    if (DoubleCircularList_IsEmpty(l)) { 
        printf("ERROR: Empty List !");
        return LINKEDLIST_FALSE; 
    }

    /* Get Data */
    *x = p->data;

    _BOOL isHeadNode = (p == l->head);
    if (isHeadNode) {

        l->head = p->next;
        if (l->size == 1) { l->head = NULL; }

    }

    p->next->prev = p->prev;
    p->prev->next = p->next;

    /* Free The Deleted Node */
    free(p);

    /* Size -- */
    l->size--;

    return LINKEDLIST_TRUE;

}

解析，
上面的刪除操作與雙向鏈表的實(shí)現(xiàn)原理一致矾瑰，區(qū)別在于這里的錯(cuò)誤處理更少砖茸；

雙向循環(huán)鏈表刪除操作圖示，

// 對(duì)應(yīng)的核心代碼
p->next->prev = p->prev;
p->prev->next = p->next;

free(p);

遍歷操作：與雙向鏈表的實(shí)現(xiàn)原理一致殴穴，區(qū)別在于結(jié)束條件的判斷凉夯；

DoubleCircularPosition DoubleCircularList_Find(DoubleCircularList l, MatchFunc mat, ElementTypePrt const x);
DoubleCircularPosition DoubleCircularList_Find_Reverse(DoubleCircularList l, MatchFunc mat, ElementTypePrt const x);

DoubleCircularList_Find(...) 函數(shù)：

DoubleCircularPosition 
DoubleCircularList_Find( DoubleCircularList l, 
                         MatchFunc mat,
                         ElementTypePrt const x ) {

    if (l == NULL) { printf("ERROR: Bad List !"); return NULL; }
    if (DoubleCircularList_IsEmpty(l)) { printf("ERROR: Empty List !"); return NULL; }

    DoubleCircularPosition p = DoubleCircularList_Head(l);

    while ( ! mat(x, DoubleCircularList_NodeData(p)) ) {
        p = DoubleCircularList_NodeNext(p);
        if (p == DoubleCircularList_Head(l)) { p = NULL; break; }
    }

    return p;

}

解析，
從 head 開始采幌，通過 next 不斷地向后訪問后繼節(jié)點(diǎn)劲够，到達(dá) head 處結(jié)束，對(duì)應(yīng)的結(jié)束代碼 if (p == DoubleCircularList_Head(l)) { p = NULL; break; } ;

DoubleCircularList_Find_Reverse(...) 函數(shù)：

DoubleCircularPosition
DoubleCircularList_Find_Reverse( DoubleCircularList l,
                                 MatchFunc mat,
                                 ElementTypePrt const x ) {
    
    if (l == NULL) { printf("ERROR: Bad List !"); return NULL; }
    if (DoubleCircularList_IsEmpty(l)) { printf("ERROR: Empty List !"); return NULL; }
    
    DoubleCircularPosition p = DoubleCircularList_Head(l);

    while ( ! mat(x, DoubleCircularList_NodeData(p))) {
        p = DoubleCircularList_NodePrev(p);
        if (p == DoubleCircularList_Head(l)) { p = NULL; break; }
    }

    return p;

}

解析休傍，
從 head 開始征绎，通過 prev 不斷地向后訪問前驅(qū)節(jié)點(diǎn)，到達(dá) head 處結(jié)束磨取，對(duì)應(yīng)的結(jié)束代碼同樣是 if (p == DoubleCircularList_Head(l)) { p = NULL; break; } ;

參考書籍：
1人柿、《算法精解_C語言描述(中文版)》
2柴墩、《數(shù)據(jù)結(jié)構(gòu)與算法分析—C語言描述》

寫到這里，本文結(jié)束凫岖！下一篇江咳，《數(shù)據(jù)結(jié)構(gòu)：棧與隊(duì)列》

最后編輯于：2018.01.05 15:24:24

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市隘截，隨后出現(xiàn)的幾起案子扎阶，更是在濱河造成了極大的恐慌，老刑警劉巖婶芭，帶你破解...
沈念sama閱讀 218,755評(píng)論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件东臀，死亡現(xiàn)場離奇詭異，居然都是意外死亡犀农，警方通過查閱死者的電腦和手機(jī)惰赋，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,305評(píng)論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來呵哨，“玉大人赁濒，你說我怎么就攤上這事∶虾Γ” “怎么了拒炎？”我有些...
開封第一講書人閱讀 165,138評(píng)論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長挨务。經(jīng)常有香客問我击你，道長，這世上最難降的妖魔是什么谎柄？我笑而不...
開封第一講書人閱讀 58,791評(píng)論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任丁侄，我火速辦了婚禮，結(jié)果婚禮上朝巫，老公的妹妹穿的比我還像新娘鸿摇。我一直安慰自己，他們只是感情好劈猿，可當(dāng)我...
茶點(diǎn)故事閱讀 67,794評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布拙吉。她就那樣靜靜地躺著，像睡著了一般糙臼。火紅的嫁衣襯著肌膚如雪庐镐。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,631評(píng)論 1贊 305
城市分裂傳說
那天变逃，我揣著相機(jī)與錄音必逆，去河邊找鬼。笑死，一個(gè)胖子當(dāng)著我的面吹牛名眉，可吹牛的內(nèi)容都是我干的粟矿。我是一名探鬼主播，決...
沈念sama閱讀 40,362評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼损拢，長吁一口氣：“原來是場噩夢啊……” “哼陌粹！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起福压，我...
開封第一講書人閱讀 39,264評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤掏秩，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后荆姆，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體蒙幻，經(jīng)...
沈念sama閱讀 45,724評(píng)論 1贊 315
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,900評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年胆筒，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了邮破。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,040評(píng)論 1贊 350
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡仆救，死狀恐怖抒和，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情彤蔽，我是刑警寧澤摧莽，帶...
沈念sama閱讀 35,742評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站顿痪，受9級(jí)特大地震影響范嘱，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜员魏，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,364評(píng)論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望叠聋。院中可真熱鬧撕阎，春花似錦、人聲如沸碌补。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,944評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽厦章。三九已至镇匀，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間袜啃，已是汗流浹背汗侵。一陣腳步聲響...
開封第一講書人閱讀 33,060評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工滞造，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人宰睡。一個(gè)月前我還...
沈念sama閱讀 48,247評(píng)論 3贊 371
代替公主和親
正文我出身青樓拆魏，卻偏偏與公主長得像，于是被迫代替她去往敵國和親雪猪。傳聞我的和親對(duì)象是個(gè)殘疾皇子栏尚，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,979評(píng)論 2贊 355

數(shù)據(jù)結(jié)構(gòu)：鏈表

1惭每、什么是鏈表？

2、鏈表共分幾類峻汉？

單鏈表

雙向鏈表

循環(huán)鏈表

3训枢、 鏈表的 C 實(shí)現(xiàn)托修！

單鏈表

雙向鏈表

循環(huán)鏈表

推薦閱讀更多精彩內(nèi)容

3训枢、鏈表的 C 實(shí)現(xiàn)托修！