数据结构：链表

2017-08-30 本文已影响932人半纸渊

本文内容：
1、什么是链表？
2、链表共分几类？
3、链表的 C 实现！

总表：《数据结构？》

工程代码 Github: Data_Structures_C_Implemention -- Link List

1、什么是链表？

链表 [Linked List]：链表是由一组不必相连【不必相连：可以连续也可以不连续】的内存结构【节点】，按特定的顺序链接在一起的抽象数据类型。

补充：
抽象数据类型（Abstract Data Type [ADT]）：表示数学中抽象出来的一些操作的集合。
内存结构：内存中的结构，如：struct、特殊内存块...等等之类；

2、链表共分几类？

链表常用的有 3 类：单链表、双向链表、循环链表。

链表.png

链表的核心操作集有 3 种：插入、删除、查找【遍历】

单链表

单链表 [Linked List]：由各个内存结构通过一个 Next 指针链接在一起组成，每一个内存结构都存在后继内存结构【链尾除外】，内存结构由数据域和 Next 指针域组成。

单链表实现图示：

文字解析：

Data 数据 + Next 指针，组成一个单链表的内存结构；
第一个内存结构称为链头，最后一个内存结构称为链尾；
链尾的 Next 指针设置为 NULL [指向空]；
单链表的遍历方向单一【只能从链头一直遍历到链尾】

单链表操作集：

单向链表-操作.png

双向链表

双向链表 [Double Linked List]：由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构【链头没有前驱，链尾没有后继】，内存结构由数据域、Prev 指针域和 Next 指针域组成。

双向链表实现图示：

文字解析：

Data 数据 + Next 指针 + Prev 指针，组成一个双向链表的内存结构；
第一个内存结构称为链头，最后一个内存结构称为链尾；
链头的 Prev 指针设置为 NULL，链尾的 Next 指针设置为 NULL；
Prev 指向的内存结构称为前驱， Next 指向的内存结构称为后继；
双向链表的遍历是双向的，即如果把从链头的 Next 一直到链尾的[NULL] 遍历方向定义为正向，那么从链尾的 Prev 一直到链头 [NULL ]遍历方向就是反向；

双向链表操作集：

双向链表-操作.png

循环链表

单向循环链表 [Circular Linked List] : 由各个内存结构通过一个指针 Next 链接在一起组成，每一个内存结构都存在后继内存结构，内存结构由数据域和 Next 指针域组成。

双向循环链表 [Double Circular Linked List] : 由各个内存结构通过指针 Next 和指针 Prev 链接在一起组成，每一个内存结构都存在前驱内存结构和后继内存结构，内存结构由数据域、Prev 指针域和 Next 指针域组成。

循环链表的单向与双向实现图示：

文字解析：

循环链表分为单向、双向两种；
单向的实现就是在单链表的基础上，把链尾的 Next 指针直接指向链头，形成一个闭环；
双向的实现就是在双向链表的基础上，把链尾的 Next 指针指向链头，再把链头的 Prev 指针指向链尾，形成一个闭环；
循环链表没有链头和链尾的说法，因为是闭环的，所以每一个内存结构都可以充当链头和链尾；

循环链表操作集：

循环链表-操作.png

3、链表的 C 实现！

单链表

节点[内存结构]与链表的定义：

节点[内存结构]，

struct __ListNode {
    ElementTypePrt data; // 数据域
    ListNode next; // 指针域 [指向下一个节点]
};

解析：struct __ListNode 就是一个节点的内存结构，因为一个节点包含了两个不同的信息，而且相互没有共享内存，所以在 C 语言环境下选择 struct 去表示；

1、ElementTypePrt 原型是 typedef void * ElementTypePrt;，使用 typedef 是方便后期进行修改；这里使用指针的目的是为了让链表支持更多的数据类型，使代码的可扩展性更强；【如： data 可以直接指向一个单纯的 int 或者一个 struct ，又或者是一个 list 等等】

2、ListNode 原型是

typedef struct __ListNode * _ListNode;
typedef _ListNode ListNode;

这里使用 typedef 是为了后面定义函数接口，以及具体代码实现更为简洁；

单链表【有时也简称，链表】，

struct __List {
    unsigned int size;  // 链表的长度
    MatchFunc matchFunc; // 两个节点的数据匹配
    DestroyFunc destroyFunc; // 节点数据的释放
    ListNode head; // 链表的链头指针
    ListNode tail; // 链表的链尾指针
};

解析：
1、MatchFunc 原型是 typedef _BOOL(*MatchFunc) (const void *key1, const void *key2); 指向形如 _BOOL(*) (const void *key1, const void *key2); 的函数指针；原因，上面提到过 data 是可以指向任意类型的，也就是说两个节点的 data 怎样才算匹配，设计者是不知道的，只有使用者才知道，所以提供一个函数接口，让使用者根据自身的情况进行数据匹配；也是为了代码可扩展性；

2、_BOOL 原型是

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

目的是为了提高代码的可读性，不建议在代码中直接使用数字，因为谁也不知道那是个啥；【过个几天，你自己估计也会忘掉，那个数字表示啥】

3、DestroyFunc 原型是 typedef void(*DestroyFunc) (void * data); 指向形如 void(*) (void * data); 的函数指针；data 如何进行释放也由使用者决定；也是为了代码可扩展性；

4、size + head + tail 是链表的基本要素，当然您也可以根据自身情况，增加个别要素；

单链表的核心操作集：

/* 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);

单链表的创建与销毁：

创建，

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 函数功能是创建并初始化一个空链表；
// 1 行 1 ，malloc 函数是 C 语言中进行内存创建的函数，需要提供的参数是 size_t ，就是空链表的要占的内存大小，所以使用 sizeof 来计算内存大小；

2、// 2 行 2 是防止，内存分配失败；

3、// 3 请移步下面的 初始化 解析;

初始化，

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 目的就是要把一个创建好的表初始化为需要的空表状态；

2、LINKEDLIST_EMPTY 原型是 #define LINKEDLIST_EMPTY 0 提高代码可读性；

3、l->head = NULL; l->tail = NULL; 因为没有节点，直接置空即可；

销毁，

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
    
}

解析：这个函数的功能就是，释放链表中所有的节点，并把链表置成空链表；
1、 // 1 List_IsEmpty 原型是

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

2、// 2 请移步下面 删除操作 的解析；

3、 // 3 memset 原型是 void* memset(void* _Dst, int _Val, size_t _Size); 功能是，设置内存块的值，这三个参数分别表示，内存块个数、设置的内存单元的值、要设置的内存空间大小；

插入操作：

_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;

}

解析：函数的功能是在指定的节点后面插入一个新的节点；
链表中的插入，不外乎链头后面、中间位置、链尾后面三个位置；

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 这里是为了区分插入发生在链头与链尾，还是中间位置与链尾；

3、// 3 与 // 4 就是链表插入的核心操作，

插入操作图示，

// 对应的核心代码
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;
}

解析：函数功能是删除链表节点；
删除操作在单链表中比较特殊，因为链表是单向，即从链头到链尾，而要删除的节点并没有指向前面节点的能力，所以要使用需删除的节点的前一个节点进行删除操作；

删除操作图示，

// 对应的核心代码
lDelete = deletePrev->next;
deletePrev->next = deletePrev->next->next;

free(lDelete);

遍历操作：

上面的插入与删除操作都要提供一个 Position 参数，不然两个函数没法用，而寻找这个行为就是遍历操作；

这里提供两个遍历操作，

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

遍历其实就是匹配内容，也就是要用到前面提到的 MatchFunc 函数，这个具体的匹配函数由用使用者实现；

Position List_Find(List l, MatchFunc mat, ElementTypePrt const x) 函数：

// 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;

}

解析：函数功能是遍历链表，查找与当前节点内容匹配的节点；
1、// 1 从链头开始，不断地用 next 来进行指针偏移，一直到链尾才结束【因为链尾的 next 肯定是 NULL 所以使用它来结束循环】；

2、// 2 这一次的匹配都使用用户实现的 MatchFunc 函数；

3、List_Head 就是 l->head，List_NodeNext 就是 p->next，List_NodeData 就是 p->data；

List_FindPrevious (...): 函数功能是遍历链表，查找与当前节点内容匹配的节点的前一个节点；遍历原理与 List_Find (...) 是一样的;

双向链表

节点[内存结构]与双向链表的定义：

节点[内存结构]，

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

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

解析：
因为双向链表有前驱节点和后继节点，所以内存结构要在单链表的内存结构基础上，增加一个 prev 指针指向节点的前驱节点；

双向链表，

typedef struct __DoubleList * _DoubleList;
typedef _DoubleList DoubleList;

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

因为双向链表只是在单链表的基础上增加了一个遍历方向，并没有改变链表的其它内容，所以与单链表的定义一致，不再进行解析；

双向链表的核心操作集：

/* 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);

双向链表的创建与销毁：

创建、初始化、销毁，这三个操作与单链表的实现基本一致，具体的可以查看工程代码；

插入操作 [分为两种，在指定节点前插入和在指定节点后插入] ：

在指定节点后插入

// 在指定节点后插入
_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、当链表是空表的时候，链头和链尾就要指向新创建的节点，这是要注意的；

2、双向链表插入图示，

// 对应代码
// 2
lNew->prev = p;
lNew->next = p->next;
p->next->prev = lNew;
p->next = lNew;

在指定节点前插入

// 在指定节点前插入
_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;

}

解析：这个插入方法的核心代码是，

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

其实原理是一样的，只是插入的方向不同；你把上面的两个插入方法的核心代码对比一下就知道了，只是把 prev 和 next 的位置改了一下；而能轻松的原因是，链表的双向遍历只是单纯的方向不同，其它没有任何区别，非常像两个单链表组合在一起；

删除操作：

_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;

}

解析：函数功能是删除指定的节点；由于双向链表有前驱节点，所以可以轻松地通过指定的节点的 prev 指针得到前一个节点，而不像单链表的删除那样要使用指定节点的前一个节点再进行删除操作；

核心删除操作图示，

// 对应的核心代码
p->prev->next = p->next;
p->next->prev = p->prev;

free(p);

与单链表的删除相比，双向链表的删除操作更加简单；

遍历操作：因为是双向链表所以遍历就有两个方向；

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;

}

它的实现与单链表的 List_Find 方法实现原理上完全一样，不同的就是函数名和节点而已，所以你如果单链表的看懂了，那么这里也就懂了。

从链尾到链头的遍历 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) ] ;

循环链表

单向循环链表：

单向循环链表的节点与链表：

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

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

与单链表唯一的不同是，没有 tail 指针，因为链表是循环的，所以不存在尾这个说法；

单向循环链表的核心操作集：与单链表的操作集也是一样的，这里就列出来一下；

/* 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);

单向循环链表的创建与销毁：与单链表的实现完全一样；
插入操作：

_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;

}

因为没有 NULL 指针的存在，所以插入过程的出错判断就变得很少；

单向循环链表插入操作图示，

// 对应的代码
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;

}

单向链表删除操作图示，

// 对应核心代码
lDelete = p->next;
p->next = p->next->next;

free(lDelete);

这里的核心代码与单链表删除操作的核心代码是一样的；

遍历操作：与单链表的遍历原理一样，不同的是结束条件；

CircularPosition CircularList_Find(...) 函数：

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;

}

解析，
这里主要是结束条件的选择，循环链表的起点是 head 那么结束自然而然也是 head 了，所以 if (p == CircularList_Head(l)) { p = NULL; break; } 直接跳出循环就可以了；

CircularPosition CircularList_FindPrevious(...) 函数：

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;

}

解析，
这里的起点是 head->next ，但是由于循环与前一个节点的约束条件，结束点就是 head 的 next 节点，因为 head->next 要被访问两次，所以最后一次的访问，就是链表遍历结束的条件；

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

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

            break;
        }

这里是先判断下一个节点是否是 head 已经结束了，因为 head 是最后一个要被访问的；

双向循环链表：

双向循环链表的节点与链表：

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

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

与双向链表的实现区别就是，没有 tail 指针；

双向循环链表的核心操作集：与双向链表的操作集一致；

/* 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);

双向循环链表的创建与销毁：与双向链表的实现一致；
插入操作：

指定节点前的插入，

_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;

}

指定节点后的插入，

_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;

}

解析，
上面的两个插入操作与双向链表的实现原理是一样的，区别就是插入操作的错误处理更少；

双向循环链表插入操作图示，

// 对应核心代码
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;

}

解析，
上面的删除操作与双向链表的实现原理一致，区别在于这里的错误处理更少；

双向循环链表删除操作图示，

// 对应的核心代码
p->next->prev = p->prev;
p->prev->next = p->next;

free(p);

遍历操作：与双向链表的实现原理一致，区别在于结束条件的判断；

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

DoubleCircularList_Find(...) 函数：

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 不断地向后访问后继节点，到达 head 处结束，对应的结束代码 if (p == DoubleCircularList_Head(l)) { p = NULL; break; } ;

DoubleCircularList_Find_Reverse(...) 函数：

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 不断地向后访问前驱节点，到达 head 处结束，对应的结束代码同样是 if (p == DoubleCircularList_Head(l)) { p = NULL; break; } ;

参考书籍：
1、《算法精解_C语言描述(中文版)》
2、《数据结构与算法分析—C语言描述》

写到这里，本文结束！下一篇，《数据结构：栈与队列》

数据结构：链表

1、什么是链表？

2、链表共分几类？

单链表

双向链表

循环链表

3、链表的 C 实现！

单链表

双向链表

循环链表

猜你喜欢

热点阅读

数据结构：链表

1、什么是链表？

2、链表共分几类？

单链表

双向链表

循环链表

3、 链表的 C 实现！

单链表

双向链表

循环链表

猜你喜欢

热点阅读

3、链表的 C 实现！