目录
1.问题引入
2.结构实现
2.3.1接口实现
2.3.2函数实现
3.总结
,又和大家见面了,今天要给大家分享的是双链表的知识,跟着我的脚步,包学包会哦~
规矩不乱,先赞后看!
ps:(孙权劝学)
1.问题引入
前期学习了单链表,我们尝到了它的甜头,但是容易越界访问这一个问题也是时有出现的,因此也是相对比较棘手的,为了解决这一个问题,特此向大家介绍带头双向链表
带头双向链表,顾名思义含有哨兵位,同时一个节点有两个指针(next / prev),这样的好处是让相邻指针的联系更加紧密,同时将首尾节点相连是其能够非常容易实现找尾。
话不多说,直接上代码!
2.结构实现
2.3.1接口实现
先在头文件(List.h)上进行顺序表结构的创建和对各函数的声明,目的是为了把各部分区分开,使程序便于理解,能清楚的看到各部分对于的作用和功能。
#pragma once #include#include #include #include typedef int LTDataType; typedef struct ListNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }LTNode; bool LTEmpty(LTNode* phead); void LTPushBack(LTNode* phead, LTDataType x); LTNode* LTInit(); void LTPopFront(LTNode* phead); void PushFront(LTNode* phead, LTDataType x); void LTPrint(LTNode* phead); LTNode* BuyLTNode(LTDataType x); void LTPopBack(LTNode* phead); LTNode* LTFind(LTNode* phead, LTDataType x); void LTInsert(LTNode* pos, LTDataType x); void LTErase(LTNode* pos); void LTDestroy(LTNode* phead);
2.3.2函数实现
接着下来是单链表各函数的函数部分,我们在List.c中完成:
a.创造新节点
LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
这些步骤都是和链表一模一样的。
b.初始化链表
LTNode* LTInit() { LTNode* phead = BuyLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
都是链表的一套固定公式
c.查找链表
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
d.在链表中插入节点
由于有了双链表,使得插入十分轻松,同时这一个函数就能简化头插和尾插两个函数,是相当方便的
//在pos前插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* prev = pos->prev; LTNode* newnode = BuyLTNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
e.在链表中删除节点
void LTErase(LTNode* pos) { assert(pos); LTNode* posprev = pos->prev; LTNode* posnext = pos->next; posprev->next = posnext; posnext->prev = posprev; free(pos); pos = NULL; }
有了这个函数,也可以让头删和尾删变得相当的简洁。
f.判断链表是否为空
bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; }
由于头删尾删会改变链表,因此需要一个判空函数来保证程序的安全性
g.头插尾插
//尾插 void LTPushBack(LTNode* phead, LTDataType x)//不需要二级指针(没有改变phead) { assert(phead); //LTNode* newnode = BuyLTNode(x); //LTNode* tail = phead->prev; //tail->next = newnode; //newnode->next = phead; //newnode->prev = tail; //phead->prev = newnode; LTInsert(phead, x); } //头插 //头插---指的是插在头结点之后,首个含数据的结点之前 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); //LTNode* newnode = BuyLTNode(x); //phead->next->prev = newnode; //newnode->next = phead->next; //phead->next = newnode; //newnode->prev = phead; // //香饽饽 LTInsert(phead->next, x); }
注释掉的是没有依靠Insert和Erase函数来写的头插尾插,是相当麻烦的,通过那两个函数,能让你不到10分钟就能写出双链表。
h.头删尾删
void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); //LTNode* tail = phead->prev; //LTNode* tailprev = tail->prev; //free(tail); //tailprev->next = phead; //phead->prev = tailprev; LTErase(phead->prev); } void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); //if (phead->next->next == NULL) //{ // phead->next = phead; // phead->prev = phead; //} //else //{ // LTNode* cur = phead->next; // LTNode* af = phead->next->next; // assert(cur); // assert(af); // phead->next = af; // af->prev = phead; // free(cur); // cur = NULL; //} LTErase(phead->next); }
i.打印链表
void LTPrint(LTNode* phead) { assert(phead); printf("guard<==>"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<==>", cur->data); cur = cur->next; } printf("\n"); }
j.销毁链表
程序执行完毕后需要销毁程序,这样才不会出现内存问题
void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); //LTNode* tail = phead->prev; //LTNode* tailprev = tail->prev; //free(tail); //tailprev->next = phead; //phead->prev = tailprev; LTErase(phead->prev); } void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); //if (phead->next->next == NULL) //{ // phead->next = phead; // phead->prev = phead; //} //else //{ // LTNode* cur = phead->next; // LTNode* af = phead->next->next; // assert(cur); // assert(af); // phead->next = af; // af->prev = phead; // free(cur); // cur = NULL; //} LTErase(phead->next); }
2.3测试程序
实现完函数之后还需要对其进行测试
#include"List.h" void TestList1() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPopFront(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTDestroy(plist); plist = NULL; } void TestList2() { LTNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPushBack(plist, 5); LTPopFront(plist); LTPrint(plist); LTNode* pos = LTFind(plist, 3); if (pos) { LTInsert(pos, 30); } LTPrint(plist); LTDestroy(plist); plist = NULL; } int main() { TestList1(); TestList2(); return 0; }
最后在终端上运行一遍得到结果
结果是这样的小伙伴就是正确掌握了的哟
如果没有跑起来的uu们也不用担心,细心调试一下,慢慢找错也是一种成长。
3.总结
链表的学习我认为是一个先苦后甜的过程,把单链表的原理搞懂之后,再使用双链表就完全是如鱼得水了。学习也是一样,先吃苦,以后才能尝到生活的甜头。
最后关于链表的问题,我强烈建议大家刷题巩固,踏实稳重,才能把数据结构这个难关拿下。