2024年大数据最新C C++数据结构（三） ，2024年最新推荐学习
网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。
一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
📝 代码示例
//双向链表打印
void ListPrint(LTNode\* phead) {
assert(phead);
LTNode\* cur = phead->next; // 从头结点的后一个结点开始打印
while (cur != phead) { // 当cur指针指向头结点时，说明链表全部打印完成
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
注意：第一个是 头结点，也被称为 带哨兵位 的结点，它是用来 站岗 的，所以不需要打印。
3. 查找元素
给定一个值，在链表中寻找与该值相同的结点，若找到了，则返回结点地址；
若没有找到，则返回空指针（NULL）。
📝 代码示例
//双向链表查找
LTNode\* ListFind(LTNode\* phead, LTDataType x) {
assert(phead);
LTNode\* cur = phead->next; // 从头结点的后一个结点开始查找
while (cur != phead) { // 从头结点的后一个结点开始查找
if (cur->data == x) {
return cur; // 返回目标结点的地址
}
cur = cur->next;
}
return NULL; // 没有找到目标结点
}
4. 插入结点
双向链表的插入操作分为 3 种情况：
（1）头插
（2）尾插
（3）在指定 pos 位置之前插入
🍑 头插
进行头插时，需要申请一个新的结点，将 新结点 插入到 头结点 与 头结点的后一个结点 之间即可。
动图演示👇
📝 代码示例
//双向链表头插
void ListPushFront(LTNode\* phead, LTDataType x)
{
assert(phead);
LTNode\* newnode = BuyLTNode(x); // 申请一个结点，数据域赋值为 x
LTNode\* after = phead->next; // 记录头结点的后一个结点位置
/\*建立新结点与头结点之间的双向关系\*/
phead->next = newnode;
newnode->prev = phead;
//建立新结点与beHind结点之间的双向关系
newnode->next = after;
after->prev = newnode;
}
注意：第一个是 哨兵结点，所以不能在它的前面插入。
🍑 尾插
尾插也是一样，申请一个新结点，将新结点插入到头结点和头结点的前一个结点之间即可。
因为链表是循环的，头结点的前驱指针直接指向最后一个结点，所以我们不必遍历链表找尾。
动图演示👇
📝 代码示例
//双向链表尾插
void ListPushBack(LTNode\* phead, LTDataType x) {
assert(phead);
LTNode\* tail = phead->prev; //尾节点就是头节点的前驱指针
LTNode\* newnode = BuyLTNode(x); // 申请一个结点，数据域赋值为x
/\*建立新结点与头结点之间的双向关系\*/
newnode->next = phead;
phead->prev = newnode;
//建立新结点与tail结点之间的双向关系
tail->next = newnode;
newnode->prev = tail;
}
🍑 指定位置插入
这里的指定插入，是在指定的 pos 位置的 前面 插入结点。
这里 pos 是指定位置的 地址，那么如何得到这个地址呢？很简单，需要用到上面的 查找函数。
然后，我们只需申请一个新结点插入到 指定位置结点 和其 前一个结点 之间即可。
动图演示👇
📝 代码示例
//双向链表在pos的前面进行插入
void ListInsert(LTNode\* pos, LTDataType x) {
assert(pos);
LTNode\* newnode = BuyLTNode(x); // 申请一个结点，数据域赋值为x
LTNode\* posPrev = pos->prev; // 记录 pos 指向结点的前一个结点
/\*建立新结点与posPrev结点之间的双向关系\*/
posPrev->next = newnode;
newnode->prev = posPrev;
/\*建立新结点与pos指向结点之间的双向关系\*/
newnode->next = pos;
pos->prev = newnode;
}
🍑 插入升级
我们仔细回顾一下，刚刚写的 头插 和 尾插，有没有发现什么规律呢？
没错，头插 其实就是在 哨兵结点 的 下一个结点 插入数据，所以我们可以用上面写的 ListInsert 函数来实现。
📝 代码升级
//头插升级
void ListPushFront(LTNode\* phead, LTDataType x) {
assert(phead);
ListInsert(phead->next, x);
}
那么 尾插 呢？其实就是在 哨兵结点 的 前面 插入结点。
📝 代码升级
//尾删升级
void ListPopBack(LTNode\* phead) {
assert(phead);
ListErase(phead->prev);
}
5. 删除结点
双向链表的删除操作分为 3 种情况：
（1）头删
（2）尾删
（3）在指定 pos 位置删除
🍑 头删
头删，即释 哨兵结点 的后一个结点，并建立 哨兵结点 与 被删除结点的后一个结点 之间的双向关系即可。
动图演示👇
📝 代码示例
//双链表头删
void ListPopFront(LTNode\* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode\* after = phead->next; // 记录头结点的后一个结点
LTNode\* newAfter = after->next; // 记录after结点的后一个结点
/\*建立头结点与newAfter结点之间的双向关系\*/
phead->next = newAfter;
newAfter->prev = phead;
free(after); // 释放after结点
}
🍑 尾删
尾删，即释放最后一个结点，并建立 哨兵结点 和 被删除结点的前一个结点 之间的双向关系即可。
📝 代码示例
//双链表尾删
void ListPopBack(LTNode\* phead) {
assert(phead);
assert(phead->next != phead); //检查链表是否为空
LTNode\* tail = phead->prev; //记录头结点的前一个结点
LTNode\* newTail = tail->prev; // 记录tail结点的前一个结点
free(tail); // 释放tail结点
tail = NULL;
/\*建立头结点与newTail结点之间的双向关系\*/
newTail->next = phead;
phead->prev = newTail;
}
🍑 指定位置删除
删除指定 pos 位置的结点，这里不是删除 pos 前面的结点，也不是删除 pos 后面的结点，而是删除 pos 地址的结点。
同样，释放掉 pos 位置的结点后，建立该结点前一个结点和后一个结点之间的双向关系即可。
动图演示👇
📝 代码示例
//双向链表删除pos位置的节点
void ListErase(LTNode\* pos) {
assert(pos); //pos不为空
LTNode\* posPrev = pos->prev; // 记录pos指向结点的前一个结点
LTNode\* posNext = pos->next; // 记录pos指向结点的后一个结点
free(pos); //free是把指针指向的节点还给操作系统
pos = NULL;
/\*建立posPrev结点与posNext结点之间的双向关系\*/
posPrev->next = posNext;
posNext->prev = posPrev;
}
🍑 删除升级
同样，对于 头删 和 尾删 还是可以进行简化。
头删 实际上就是删除 哨兵结点 的 下一个结点。
📝 代码升级
//头删升级
void ListPopFront(LTNode\* phead) {
assert(phead);
assert(phead->next != NULL); //只有一个节点的时候，就别删了
ListErase(phead->next);
}
尾删 实际上就是删除 哨兵结点 的 前一个结点。
📝 代码升级
//尾删升级
void ListPopBack(LTNode\* phead) {
assert(phead);
ListErase(phead->prev);
}
6. 链表判空
当链表的 头结点的前驱 或是 后驱 指向的是自己时，即 双向链表为空。
换句话说，当只有 哨兵结点 时，链表为空。
📝 代码示例
//双向链表判空
bool ListEmpty(LTNode\* phead)
{
assert(phead);
return phead->next == phead; // 当链表中只有头结点时为空
}
7. 获取链表中的元素个数
获取链表中的元素个数，即遍历一次链表，统计结点的个数（哨兵结点 不纳入总数）并返回即可。
📝 代码示例
//获取链表中的元素个数
int ListSize(LTNode\* phead)
{
assert(phead);
int count = 0; // 记录元素个数
LTNode\* cur = phead->next; // 从头结点的后一个结点开始遍历
while (cur != phead) // 当cur指向头结点时，遍历完毕，头结点不计入总元素个数
{
count++;
cur = cur->next;
}
return count; //返回元素个数
}
8. 销毁链表
当链表使用完以后，要进行销毁。
销毁链表，从 哨兵结点 的 后一个结点 处开始向后遍历并释放结点，直到遍历到 哨兵结点 时，停止遍历并将 哨兵结点 也释放掉。
📝 代码示例
**网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。**
**[需要这份系统化资料的朋友，可以戳这里获取](https://bbs.csdn.net/topics/618545628)**
**一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！**
``
## 8. 销毁链表
当链表使用完以后，要进行销毁。
销毁链表，从 **哨兵结点** 的 **后一个结点** 处开始向后遍历并释放结点，直到遍历到 **哨兵结点** 时，停止遍历并将 **哨兵结点** 也释放掉。
📝 代码示例
[外链图片转存中…(img-eiIFmwGG-1715608484486)]
[外链图片转存中…(img-IrGPE70C-1715608484486)]
网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。
一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
27
0- 0
已为社区贡献1条内容
所有评论(0)