seo网站营销推广全...,卓伊科技网站建设,使用oss做静态网站,wordpress4.7中文前言
hello#xff0c;大家好呀#xff0c;我是Humble#xff0c;本篇博客承接之前的C语言进阶——数据结构之链表
的内容#xff08;没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~#xff09;#xff0c;上次我们重点说了链表中…前言
hello大家好呀我是Humble本篇博客承接之前的C语言进阶——数据结构之链表
的内容没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~上次我们重点说了链表中的单链表即不带头单向不循环链表
还说到了链表的分类虽然有8种但实际上最常用的还是单链表和双向链表带头双向循环链表
所以今天我们就来讲讲双向链表的实现吧~ 双向链表的结构 下面是双向链表的一个图示 双向链表全称为带头双向循环链表
双向与循环这2个概念很好理解所以我们下面看一下什么是带头
这个“带头”跟之前我们说的“头节点”是两个概念
实际前面在说单链表时有称呼并不严谨但是为了大家更好的理解就直接称为单链表的头节点 带头链表里的头节点实际为“哨兵位”哨兵位节点不存储任何有效元素只是站在这里“放哨 的
哨兵位”存在的意义 遍历循环链表避免死循环 对于双向链表的节点我们这样定义 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; //指针保存下一个节点的地址 struct ListNode* prev; //指针保存前一个节点的地址 }LTNode; 双向链表的实现 下面我们来实现一下双向链表的各个功能
其实当我们掌握了单链表的各个操作后我们会发现其实双向链表虽然在结构上看着比单链表复杂不少但在实现上并不难~
我们首先在VS上创建一个List的工程再分别创建List.h头文件List.c源文件以及Test.c测试文件在这之上我们依次去实现双向链表的各个功能~ 初始化 LTInit
首先是初始化因为双向链表多了一个头节点即哨兵位所以我们需要对其初始化~ 代码如下
LTNode* LTInit() //对哨兵位初始化~
{LTNode* phead (LTNode*)malloc(sizeof(LTNode));if (phead NULL) {perror(malloc fail!);exit(1);}phead-data -1;phead-next phead-prev phead;return phead;} 下面来测试一下~
void ListTest()
{LTNode* plist LTInit();}int main()
{ListTest();return 0;
} 这里我们通过调试来观察一下初始化是否成功 另外因为我们后面还要多次用到申请节点空间所以我们单独封装一个函数LTBuyNode
这样后面再使用只需要调用它就可以了
LTNode* LTBuyNode(LTDataType x) //申请新节点
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL) {perror(malloc fail!);exit(1);}newnode-data x;newnode-next newnode-prev newnode;return newnode;
}同时关于上面初始化的代码我们也可以进行简化
LTNode* LTInit()
{LTNode* phead LTBuyNode(-1);return phead;
}尾插LTPushBack
好有了这样一个链表下面我们实现一下尾插LTPushBack 代码如下
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead); //phead不能为空LTNode* newnode LTBuyNode(x);newnode-next phead;newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}同样我们在Test.c文件中进行测试
void ListTest()
{LTNode* plist LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);
}int main()
{ListTest();return 0;
}
调试后结果如下 这样尾插的功能就实现了~
不过我们后续如果一直用调试的方式去观察未免有些麻烦所以这里我们也封装一个打印的函数 //打印
void LTPrint(LTNode* phead)
{//phead不能为空assert(phead);LTNode* pcur phead-next;while (pcur ! phead){printf(%d-, pcur-data);pcur pcur-next;}}
有了打印函数我们再测试尾插只要运行代码就可以了
结果如下 头插LTPushFront
接下来我们来实现一下头插LTPushFront
关于头插有一个需要注意的点头插要插在第一个、有效节点之前而不是在哨兵位之前 头插代码如下
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode LTBuyNode(x);//phead newnode phead-nextnewnode-next phead-next;newnode-prev phead;phead-next-prev newnode;phead-next newnode;
} 老规矩写完后我们来测试一下
void ListTest()
{LTNode* plist LTInit();//头插LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);}int main()
{ListTest();return 0;
} 尾删 LTPopBack 写删除操作时要注意当链表为空时只有一个哨兵位节点要assert断言 代码如下
void LTPopBack(LTNode* phead)
{assert(phead);//链表为空只有一个哨兵位节点assert(phead-next ! phead);LTNode* del phead-prev;LTNode* prev del-prev;prev-next phead;phead-prev prev;free(del);del NULL;} 下面是测试代码以及结果
void ListTest()
{LTNode* plist LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);//尾删LTPopBack(plist);LTPrint(plist);printf(\n);LTPopBack(plist);LTPrint(plist);printf(\n);LTPopBack(plist);LTPrint(plist);}int main()
{ListTest();return 0;
} 头删LTPopFront 接下来我们来实现头部删除LTPopFront 直接上代码
//头删
void LTPopFront(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* del phead-next;LTNode* next del-next;next-prev phead;phead-next next;free(del);del NULL;
} 下面来测试
void ListTest()
{LTNode* plist LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);//头删LTPopFront(plist);LTPrint(plist);printf(\n);LTPopFront(plist);LTPrint(plist);printf(\n);LTPopFront(plist);LTPrint(plist);printf(\n);
}int main()
{ListTest();return 0;
}
运行结果如下 查找LTFind
在前面我们已经实现了插入的4种操作下面我们看一下查找
代码如下
LTNode* LTFind(LTNode* phead, LTDataType x)//查找
{assert(phead);LTNode* pcur phead-next;while (pcur ! phead){if (pcur-data x) return pcur;pcur pcur-next;}return NULL;}来测试一下吧~
void ListTest()
{LTNode* plist LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTNode* findRet LTFind(plist, 3);if (findRet NULL) printf(未找到\n);else printf(找到了\n);
}int main()
{ListTest();return 0;
} 在指定位置之后插入数据LTInsert 插入代码如下
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode LTBuyNode(x);newnode-next pos-next;newnode-prev pos;pos-next-prev newnode;pos-next newnode;
}测试代码如下
void ListTest()
{LTNode* plist LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4); //4-3-2-1-LTNode* findRet LTFind(plist, 3);LTInsert(findRet,66); //预期结果为 //4-3-66-2-1-LTPrint(plist);}int main()
{ListTest();return 0;
} 运行结果 删除pos位置的数据LTErase 删除代码如下
//删除pos位置的数据
void LTErase(LTNode * pos)
{assert(pos);pos-next-prev pos-prev;pos-prev-next pos-next;}下面我们来进行测试~
void ListTest()
{LTNode* plist LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4); //4-3-2-1-LTNode* findRet LTFind(plist, 3);LTErase(findRet);LTPrint(plist); //预期结果为4-2-1-
}int main()
{ListTest();return 0;
} 链表的销毁LTDestroy
最后我们看一下双向链表的销毁LTDestroy 注意我们这里的函数要传的是地址也就是要用到二级指针因为这里我们直接要对链表的哨兵位做修改要与前面的代码相区分哦~
销毁的代码如下
void LTDesTroy(LTNode** pphead)
{assert(pphead);//哨兵位不能为空assert(*pphead);LTNode* pcur (*pphead)-next;while (pcur ! *pphead){LTNode* next pcur-next;free(pcur);pcur next;}//链表中只有一个哨兵位free(*pphead);*pphead NULL;
} 至于销毁操作的调试大家可以自行测试这里就不再赘述了 到此我们就把双向链表的操作给讲完了
事实上学会了单链表和双向链表的操作即使将来遇到链表的其他6种类型也可以游刃有余很快上手并解决问题的所以建议大家还是要好好掌握单链表和双向链表的操作~ 结语 好了今天关于链表的分享就到这里了如果对大家有帮助就太好啦~ 在学习编程的道路上Humble与各位同行,加油吧各位 最后希望大家点个免费的赞或者关注吧感谢感谢也欢迎大家订阅我的专栏 让我们在接下来的时间里一起成长一起进步吧
