链表|秒懂双链表链表|数据结构

文章图片
哈喽，今天阿紫姐姐召集各位武林侠士，有什么事情了？？？
众人所答：当然是阿紫姐姐又来带领我们学习新的功夫啦！！！
首先，练功夫之前得热身（小声告诉你们哦，阿紫姐姐说的热身是心灵鸡汤哦）

坚持就是胜利，每当我们坚持不下去的时候，我们都要告诉自己，胜利就在不远方，要是放弃之前的努力都将会功亏一篑。
一定要坚持、坚持、坚持哦！！！
坚持才是做任何事情的秘诀。

回顾：

文章图片

首先我们来看看单链表有哪些缺点了？？？
单链表主要缺点：①不能从后往前遍历 ②找不到前驱

文章图片

单链表缺陷解决方案-》双链表：
有八种链表结构：

文章图片

文章图片

带头双向循环链表代码实现：
list.h：头文件

#define_CRT_SECURE_NO_WARNINGS 1 #include #include #include #pragma oncetypedef int LTDataType; //带头双向循环---最有链表结构，任意位置插入删除数据都是O（1） typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode; //初始化 ListNode* ListInit(ListNode* phead); //尾插 void ListPushBack(ListNode* phead,LTDataType x); //头插 void ListPushFront(ListNode* phead, LTDataType x); //打印 void ListPrint(ListNode* phead); //头删 void ListPopFront(ListNode* phead); //尾删 void ListPopBack(ListNode* phead); //查找 ListNode* ListFind(ListNode* phead, LTDataType x); //pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x); //删除pos位置的值 void ListErase(ListNode* pos); //销毁链表 void ListDestory(ListNode* phead);

在头文件里面进行了库函数的头文件包含、结构体声明、类型重定义、自定义函数声明
test.c：测试文件

#define_CRT_SECURE_NO_WARNINGS 1 #include"list.h" void TestList1() { ListNode* plist = NULL; plist = ListInit(plist); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPushBack(plist, 6); ListPrint(plist); ListPushFront(plist, 0); ListPrint(plist); ListPopFront(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { //查找附带修改作用 pos->data *= 10; printf("找到了,并且*10\n"); } else { printf("没有找到\n"); } ListPrint(plist); ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist); ListDestory(plist); } int main() { TestList1(); return 0; }

主要测试我们双链表的功能
接下来我们一个一个看自定义函数的实现：
链表初始化：

ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { return; } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; newnode->prev = NULL; return newnode; }ListNode* ListInit(ListNode* phead) { phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; }

文章图片

尾插

ListNode* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { return; } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; newnode->prev = NULL; return newnode; } void ListPushBack(ListNode* phead, LTDataType x) { ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }

文章图片

【链表|秒懂双链表】 尾删

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* BuyListNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { return; } newnode->data = https://www.it610.com/article/x; newnode->next = NULL; newnode->prev = NULL; return newnode; } void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = 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; }

文章图片

打印：

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

文章图片

查找：

ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data =https://www.it610.com/article/= x) { return cur; } cur = cur->next; } return NULL; }

cur指向第一个结点，当结点的数据域不等于x，就去看下一个结点，要是最后找到phead都没有找到，就说明没有.
在某个结点前插入一个结点：

void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = BuyListNode(x); ListNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }

文章图片

删除某个结点：

void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }

文章图片

销毁链表：

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