©2020-2024 ioDraw All rights reserved,
Privacy Policy
哈喽，今天阿紫姐姐召集各位武林侠士，有什么事情了？？？
众人所答：当然是阿紫姐姐又来带领我们学习新的功夫啦！！！
首先，练功夫之前得热身（小声告诉你们哦，阿紫姐姐说的热身是心灵鸡汤哦）
* 坚持就是胜利，每当我们坚持不下去的时候，我们都要告诉自己，胜利就在不远方，要是放弃之前的努力都将会功亏一篑。
* 一定要坚持、坚持 、坚持哦！！！
* 坚持才是做任何事情的秘诀。
回顾：
首先我们来看看单链表有哪些缺点了？？？
单链表主要缺点：①不能从后往前遍历 ②找不到前驱
单链表缺陷解决方案-》双链表：
有八种链表结构：
带头双向循环链表代码实现：
list.h：头文件
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdlib.h>
#include<assert.h> #pragma once typedef 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 = 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 = 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 = 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 == 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; }
今天的双链表武功大家学会了吗？？？
QQ.2186529582
让我们一起加油，离成功更进一步吧！！！
好了今天就到这里！！！