(69条消息) 链表

今天我们继续来完成链表，但是今天我们来实现双向带头循环链表，这与我们之前写的单项不带头非循环链表相对应，链表一共可以有8种形式，学会了这两种，其他6种也都游刃有余。

(7条消息) 链表与其多种接口实现1_KLZUQ的博客-CSDN博客

 这是上一期的链表，大家可以参考一下。

还是和之前一样，我们使用工程一点的写法

我们先来完成链表的结构创建已经宏定义

typedef int LTDataType;typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data;}ListNode;

 接着我们来完成链表的初始化

ListNode* ListInit()//初始化{ ListNode* phead = BuyListNode(0); phead- next = phead; phead- prev = phead; return phead;}

因为初始化时要创建新的节点，并且我们在之后也需要一直创建新的节点，所以我们把创建新节点封装成一个函数

ListNode* BuyListNode(LTDataType x)//创建新节点{ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode- data = x; newnode- next = NULL; newnode- prev = NULL; return newnode;}

有了这些，我们来完成链表的尾插

void ListPushBack(ListNode* phead, LTDataType x)//尾插{ assert(phead); ListNode* tail = phead- prev; ListNode* newnode = BuyListNode(x); tail- next = newnode; newnode- prev = tail; phead- prev = newnode; newnode- next = phead;}

双向带头循环链表的结构看起来很复杂，但我们实现它时却非常简单。加断言是为了防止头节点为空（比如使用链表时因为某些原因导致程序崩溃，断言可以帮助你迅速找到错误的位置），这个链表的结构非常完美，链表不为空和为空时都可以完成自己的工作，容错率非常高。

有了尾插，我们接着来实现打印，方便我们观察和调试

void ListPrint(ListNode* phead)//打印{ ListNode* cur = phead- next; while (cur != phead) { printf("%d ", cur- data); cur = cur- next; } printf("\n");}

我们看到，当链表为空时它仍然不会出现错误，这个结构是最优的，我在结尾会告诉大家这个链表的真正优点，接下来就不再啰嗦。

有了打印，我们来测试一下我们的代码，还是那句话，写一步测一步，不然写到后面几十个错误心态就炸了

很好，我们接着来完成头插

void ListPushFront(ListNode* phead, LTDataType x)//头插{ assert(phead); ListNode* first = phead- next; ListNode* newnode = BuyListNode(x); first- prev = newnode; newnode- next = first; phead- next = newnode; newnode- prev = phead;}

很多人在别的书上看到头插可能有顺序问题，但我们这个是不需要考虑顺序的，如果去掉first的话直接来完成才需要考虑顺序问题。那时候，我们需要先把newnode和它的后续节点连起来，然后再连接头节点和newnode

接着我们来完成头删

void ListPopFront(ListNode* phead)//头删{ assert(phead); assert(phead- next!=phead); ListNode* first = phead- next; ListNode* second = first- next; phead- next = second; second- prev = phead; free(first); first = NULL;}

我们创建first和second两个指针，这样就可以不用考虑顺序问题。第二个断言可以防止链表删除头节点。

接着是尾删

void ListPopBack(ListNode* phead)//尾删{ assert(phead); assert(phead- next != phead); ListNode* tail = phead- prev; ListNode* prev = tail- prev; prev- next = phead; phead- prev = prev; free(tail); tail = NULL;}

尾删同样创建两个指针，不考虑顺序

然后是查找

ListNode* ListFind(ListNode* phead, LTDataType x)//查找{ assert(phead); ListNode* cur = phead- next; while (cur != phead) { if (cur- data == x) { return cur; } cur = cur- next; } return NULL;}

查找也是相当简单，这个查找我们也可以用来修改当前位置的值

 非常的好用

接着我们来写任意位置插入

void ListInsert(ListNode* pos, LTDataType x)//任意位置前插入(pos前){ assert(pos); ListNode* prev = pos- prev; ListNode* newnode = BuyListNode(x); newnode- next = pos; pos- prev = newnode; newnode- prev = prev; prev- next = newnode;}

同样，定义一个指针可以让我们不用考虑顺序。这个配合查找使用非常方便

 然后我们来写任意位置删除

void ListErase(ListNode* pos)//任意位置删除（pos位置）{ assert(pos); ListNode* prev = pos- prev; ListNode* next = pos- next; prev- next = next; next- prev = prev; free(pos);}

到这里，我们的接口也基本都实现了，如果让大家在10分钟内实现这个链表和它的接口，大家可以完成吗？

这里我们就要来提高代码的复用性

我们有了任意位置的插入和删除，我们就可以修改代码

void ListPopBack(ListNode* phead)//尾删{ /*assert(phead); assert(phead- next != phead); ListNode* tail = phead- prev; ListNode* prev = tail- prev; prev- next = phead; phead- prev = prev; free(tail); tail = NULL;*/ ListErase(phead- prev);}

void ListPopFront(ListNode* phead)//头删{ /*assert(phead); assert(phead- next!=phead); ListNode* first = phead- next; ListNode* second = first- next; phead- next = second; second- prev = phead; free(first); first = NULL;*/ ListErase(phead- next);}

最后，我们来写一下清空链表

void ListDestory(ListNode* phead)//清空{ assert(phead); ListNode* cur = phead- next; while (cur != phead) { ListNode* next = cur- next; free(cur); cur = next; } free(phead); phead = NULL;}

以上就是我们完成的所有接口，大家自己试一下会发现，这个链表的结构非常完美，它的插入和删除的时间复杂度都是o(1)，只有查找我们是用的是正常方法，时间复杂度为o(n)。

最后附上所有代码，希望各位有所收获

#pragma once//List.h#include stdio.h #include stdlib.h #include assert.h #include stdbool.h typedef int LTDataType;typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data;}ListNode;void ListPrint(ListNode* phead);//打印ListNode* ListInit();//初始化void ListDestory(ListNode* phead);//清空void ListPushBack(ListNode* phead, LTDataType x);//尾插void ListPushFront(ListNode* phead, LTDataType x);//头插void ListPopBack(ListNode* phead);//尾删void ListPopFront(ListNode* phead);//头删ListNode* ListFind(ListNode* phead, LTDataType x);//查找void ListInsert(ListNode* pos, LTDataType x);//任意位置前插入(pos前)void ListErase(ListNode* pos);//任意位置删除（pos位置）

//List.c#include"List.h"ListNode* BuyListNode(LTDataType x)//创建新节点{ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); newnode- data = x; newnode- next = NULL; newnode- prev = NULL; return newnode;}ListNode* ListInit()//初始化{ ListNode* phead = BuyListNode(0); phead- next = phead; phead- prev = phead; return phead;}void ListDestory(ListNode* phead)//清空{ assert(phead); ListNode* cur = phead- next; while (cur != phead) { ListNode* next = cur- next; free(cur); cur = next; } free(phead); phead = NULL;}void ListPrint(ListNode* phead)//打印{ ListNode* cur = phead- next; while (cur != phead) { printf("%d ", cur- data); cur = cur- next; } printf("\n");}void ListPushBack(ListNode* phead, LTDataType x)//尾插{ assert(phead); ListNode* tail = phead- prev; ListNode* newnode = BuyListNode(x); tail- next = newnode; newnode- prev = tail; phead- prev = newnode; newnode- next = phead;}void ListPushFront(ListNode* phead, LTDataType x)//头插{ assert(phead); ListNode* first = phead- next; ListNode* newnode = BuyListNode(x); first- prev = newnode; newnode- next = first; phead- next = newnode; newnode- prev = phead;}void ListPopBack(ListNode* phead)//尾删{ /*assert(phead); assert(phead- next != phead); ListNode* tail = phead- prev; ListNode* prev = tail- prev; prev- next = phead; phead- prev = prev; free(tail); tail = NULL;*/ ListErase(phead- prev);}void ListPopFront(ListNode* phead)//头删{ /*assert(phead); assert(phead- next!=phead); ListNode* first = phead- next; ListNode* second = first- next; phead- next = second; second- prev = phead; free(first); first = NULL;*/ ListErase(phead- next);}ListNode* ListFind(ListNode* phead, LTDataType x)//查找{ assert(phead); ListNode* cur = phead- next; while (cur != phead) { if (cur- data == x) { return cur; } cur = cur- next; } return NULL;}void ListInsert(ListNode* pos, LTDataType x)//任意位置前插入(pos前){ assert(pos); ListNode* prev = pos- prev; ListNode* newnode = BuyListNode(x); newnode- next = pos; pos- prev = newnode; newnode- prev = prev; prev- next = newnode;}void ListErase(ListNode* pos)//任意位置删除（pos位置）{ assert(pos); ListNode* prev = pos- prev; ListNode* next = pos- next; prev- next = next; next- prev = prev; free(pos);}

//test.c#include"List.h"void test1() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 9); ListPushFront(plist, 8); ListPushFront(plist, 7); ListPushFront(plist, 6); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListDestory(plist);}void test2() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { ListInsert(pos, 20); } else { printf("没找到\n"); } ListPrint(plist); ListDestory(plist);}int main() { test2(); return 0;}

如有错误，还请指正。

本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。