文章目录
- 💦 malloc空间
- 💦 初始化数据１
- 💦 初始化数据２
- 💦 尾插数据
- 💦 头插数据
- 💦 判空链表
- 💦 尾删数据
- 💦 头删数据
- 💦 查找数据
- 💦 pos位置之前插入数据
- 💦 pos位置删除数据
- 💦 链表的长度
- 💦 打印数据
- 💦 销毁动态内存开辟的空间
一、南北大战
首先有请北方代表和南方代表开团
1️⃣ 北方代表首先给我们展示了当地特色——大耗子
2️⃣ 南方人表示不服，抬出了老鼠界的扛把子
接着就进入了南北大混战
1️⃣ 北方的消防员
2️⃣ 南方的牛肉面
1️⃣ 北方的鸭血
2️⃣南方的话梅
1️⃣北方的裤衩
2️⃣ 南方的显卡
但当我们遇见外人时总是意料之中的团结
还有我国的珍稀品种——狗雀
二、前言
实际中链表的结构非常多样，组合起来共有8种结构，但是最常用的只有2种：
1️⃣ 无头单向非循环链表
无头单向非循环链表，结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2️⃣ 带头双向循环链表
带头双向循环链表，结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了(果真闻起来臭吃起来香)。
typedef int LTDataType; typedef struct ListNode { struct ListNode* prev;//前驱指针 struct ListNode* next;//后驱指针 LTDataType data;//值 }LTNode;
三、函数各接口的实现
💦 malloc空间
函数原型
函数实现
LTNode* BuyListNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); //malloc失败 if (node == NULL) { printf("malloc fail"); exit(-1); } //malloc成功 node->next = NULL; node->prev = NULL; node->data = x; //返回起始地址 return node; }
💦 初始化数据１
函数原型
函数实现
void ListInit1(LTNode** pphead) { assert(pphead); //据析，这里需要传二级指针，因为它要改变plist本身(NULL->0x...) *pphead = BuyListNode(-1); //初始化前驱指针和后驱指针(一开始同时指向自己) (*pphead)->next = *pphead; (*pphead)->prev = *pphead; }
💦 初始化数据２
为了接口的一致性
函数原型
函数实现
LTNode* ListInit2() { LTNode* phead = BuyListNode(0); //初始化前驱指针和后驱指针(一开始同时指向自己) phead->next = phead; phead->prev = phead; //返回哨兵位的地址 return phead; }
💦 尾插数据
函数原型
函数实现
void ListPushBack(LTNode* phead, LTDataType x) { 据析，这里不需要对plist变量改变，所以不用传二级指针 assert(phead); tail记录尾地址 //LTNode* tail = phead->prev; newnode接收malloc空间的起始地址 //LTNode* newnode = BuyListNode(x); 原尾和新尾相互链接 //tail->next = newnode; //newnode->prev = tail; 哨兵位和新尾相互链接 //newnode->next = phead; //phead->prev = newnode; //当实现了ListInser，ListPushBack就可以复用了 ListInser(phead, x); }
💦 头插数据
函数原型
函数实现
void ListPushFront(LTNode* phead, LTDataType x) { assert(phead); tail记录第一个有效节点 //LTNode* tail = phead->next; newnode接收malloc空间的起始地址 //LTNode* newnode = BuyListNode(x); 头和新节点相互链接 //phead->next = newnode; //newnode->prev = phead; 新节点和旧节点相互链接 //newnode->next = tail; //tail->prev = newnode; //当实现了ListInser，ListPushFront就可以复用了 ListInser(phead->next, x); }
💦 判空链表
当链表为空时，不能尾删、头删，所以先实现ListEmpty
函数原型
函数实现
bool ListEmpty(LTNode* phead) { assert(phead); //链表为空返回true return phead->next == phead; }
💦 尾删数据
函数原型
函数实现
void ListPopBack(LTNode* phead) { assert(phead); //空链表需要报错，调用ListEmpty：不为空时返回false，再!为真；为空时返回true，再!为假 assert(!ListEmpty(phead)); tail记录尾 //LTNode* tail = phead->prev; cur记录尾的前一个 //LTNode* tailPrev = tail->prev; 释放尾 //free(tail); 重新链接 //phead->prev = tailPrev; //tailPrev->next = phead; //当实现了ListErase，ListPopBack就可以复用了 ListErase(phead->prev); }
💦 头删数据
函数原型
函数实现
void ListPopFront(LTNode* phead) { assert(phead); 空链表报错，调用ListEmpty：不为空时返回false，再!为真；为空时返回true，再!为假 //assert(!ListEmpty(phead)); tail记录第一个有效节点的后一个节点 //LTNode* tail = phead->next->next; 释放第一个有效节点 //free(phead->next); 头和第一个有效节点相互链接 //phead->next = tail; //tail->prev = phead; //当实现了ListErase，ListPopFront就可以复用了 ListErase(phead->next); }
