数据结构——双向链表（保姆级教程，包学包会）

news/2024/11/29 7:51:00/

1.双向链表的概念

双向链表就是带头双向循环链表

我们在学完单链表之后，就感觉这个非常简单了，他的主要表现就是拥有头节点，链表永不为空，不需要二级指针；可以通过一个节点找到上一个或者下一个节点；头尾相连呈环状。

他主要结构是由prev、next、data，这三个结构组成，通过prev找到前一个节点，next就不用多说了。

如图所示

 不多废话，直接上代码

2.双向链表的实现

2.1 结构设计

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;

2.2 接口总览

实现一个双向链表的各个接口

typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;LTNode* LTInit();
void LTPrint(LTNode* phead);bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

注意看一下啊我们的初始化的时候，这里是不带参数的，是为什么呢？

双向链表是带头的，有头节点，就是我们说的哨兵位，哨兵位不存储有效数据，所以链表的第一个节点就是哨兵位后面的第一个节点。

注意：这里面我们用二级指针也可以操作，但是我们在以后的代码中二级指针太麻烦而且容易用错，所以我们直接用哨兵位的办法来解决，不需要用二级指针。

2.3 初始化

创建一个哨兵位，让他自己变成一个环形链表

只需要让他自己指向自己就可以

 

LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

 2.4 创建节点

当我们需要插入元素是，只需要创建节点，然后直接把值存入，两个指针置为空，返回该节点的地址就可。

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;}

2.5 尾插

直接图片更清晰观赏，我们思路是：将tail->next的链接直接连接到newnode，然后将newnode->prev连接到tail。最后phead的prev和next连接即可。

 

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

2.6 头插

头插就是将链表上的第一个节点与哨兵位的链接断开，但是在断开之前我们一定要先保存好将要断开的data，在去改变你将要头插的newnode

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* first = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

 2.7 尾删

这里我们还是一样的要找到tail前一个节点tailprev，然后直接释放掉尾节点就好

这里面注意一下，要是只有哨兵位就不能删除

 

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);//防止把哨兵位删掉LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);phead->prev = tailprev;tailprev->next = phead;
}

2.8 头删

对于头删来说，我需要删除链表的第一个节点，也就是 哨兵位的 next 节点 ，我需要改变 哨兵位 和 第二个节点 的链接关系，然后释放 第一个节点 。

 

void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* firstnext = first->next;free(first);firstnext->prev = phead;phead->next = firstnext;
}

2.9 查找

对于 双向链表 来说，它是没有指向NULL的节点的，它是一个环，停不下来。所以我们要把循环的截止条件设定为 ! = phead，这个条件就表示，已经遍历过一遍链表了

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;
}

2.10 在pos之前插入

通过 pos 的 prev 找到 pos 位置的上一个节点 posprev ，然后改变 posprev 和 新节点 newnode  之间的链接和 newnode 和 pos 之间的链接

 

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* posprev = pos->prev;newnode->prev = posprev;posprev->next = newnode;newnode->next = pos;pos->prev = newnode;
}

2.11 在pos之前插入

在pos位置删除，我们只需找到pos前一个节点posprev，和后一个节点posnext，将prev和next的链接接好，释放pos节点

void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posnext->prev = posprev;
}

 

2.12 判断是否为空

这里我们可以加上这个函数，如果phead下一个等于phead，说明链表为空只剩下哨兵位自己，那么此时我们就不能继续删除了，这里我们可以用这个函数直接替换掉上面的断言

bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

这里我们也可以简写成：

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsert(phead, x);
}void LTPushFront(LTNode* phead, LTDataType x)
{LTInsert(phead->next, x);
}void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);}

2.13 打印

void LTPrint(LTNode* phead)
{assert(phead);printf("guard<==>");LTNode* cur = phead->next;while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

2.14 销毁

我们这时直接把链表节点全部删除，在删除过程中记住我们下一个节点以便于循环

注意：由于在函数中，我释放了哨兵位，并要将其置空。释放是可以的，因为我知道哨兵位的地址，释放就可以，但是置空却完成不了。因为我的 哨兵位 是形参，改变形参并不能影响实参，所以我们还需要在主函数中将 哨兵位 置空

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

完整代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;}LTNode;LTNode* LTInit();
void LTPrint(LTNode* phead);bool LTEmpty(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x);
// 删除pos位置的值
void LTErase(LTNode* pos);
void LTDestroy(LTNode* phead);

List.c

#include "List.h"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;}LTNode* LTInit()
{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;
}bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* first = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);//防止把哨兵位删掉LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);phead->prev = tailprev;tailprev->next = phead;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);LTNode* first = phead->next;LTNode* firstnext = first->next;free(first);firstnext->prev = phead;phead->next = firstnext;
}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;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = BuyListNode(x);LTNode* posprev = pos->prev;newnode->prev = posprev;posprev->next = newnode;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posnext->prev = posprev;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}void LTPrint(LTNode* phead)
{assert(phead);printf("guard<==>");LTNode* cur = phead->next;while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

Test.c

#include"List.h"void TestList1()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPopBack(plist);LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);LTDestroy(plist);plist = NULL;
}void TestList2()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTPopFront(plist);LTPrint(plist);/*LTPopFront(plist);LTPrint(plist);*/LTDestroy(plist);plist = NULL;
}void TestList3()
{LTNode* plist = LTInit();LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPrint(plist);LTNode* pos = LTFind(plist, 3);if (pos){LTInsert(pos, 30);}LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{TestList3();return 0;
}

以上就是今天的分享喜欢的话请三联支持一下我们下期再见哦


http://www.ppmy.cn/news/69834.html

相关文章

【C++刷题集】-- day1

【C++刷题集】-- day1

目录 选择题 单选 编程题 组队竞赛⭐ 【题目解析】 【解题思路】(排序 贪心) 删除公共字符⭐ 【题目解析】 【解题思路】(哈希映射) 选择题 单选 1、 以下for循环的执行次数是 ( ) for(int x 0, y 0; (y 123) && (x < 4); x); 是无限循环 循环次数不…
阅读更多...
计算机图形学-GAMES101-7

计算机图形学-GAMES101-7

引言 场景中有很多的三角形&#xff0c;如果实现可见性和遮挡呢&#xff1f;  一个简单的想法是&#xff0c;从远到近画&#xff0c;近处的物体自然会覆盖掉远处的物体&#xff0c;这种画法也叫画家算法。  但是实际绘制中物体的顺序是不容易确定的&#xff0c;比如如下图绘制…
阅读更多...
（2）数码管

（2）数码管

LED数码管:数码管是一种简单、廉价的显示器&#xff0c;是由多个发光二极管封装在一起组成"8"字器件 51单片机是共阴极连接 74HC245这个芯片有什么作用呢&#xff1f;解&#xff1a;这个芯片被称之为双向数据缓冲器这个芯片的作用&#xff0c;用来进行数据缓冲(提高驱…
阅读更多...
java前端程序员职业生涯规划，我来分享一下升职加薪的六大技巧

java前端程序员职业生涯规划，我来分享一下升职加薪的六大技巧

今天给大家分享一下java前端程序员的职业生涯规划&#xff0c;我把它分成四个阶段。 第一个阶段是你还是一名在校大学生。这个时候一定要好好学习学校的专业技术知识&#xff0c;尤其是C语言、数据结构和算法。然后及时关注你身边名校的这些校园招聘机会&#xff0c;获得一些名…
阅读更多...
tpm2-tools源码分析之tpm2_verifysignature.c（1）

tpm2-tools源码分析之tpm2_verifysignature.c（1）

TPM 2.0中的tpm2_verifysignature命令对应的源文件就是tpm2_verifysignature.c&#xff0c;该文件位于tpm2-tools/tools/下&#xff0c;一共有293行&#xff08;版本5.5&#xff09;。 tpm2_verifysignature的功能是使用TPM验证签名。使用加载的密钥验证带有传递给TPM的消息摘…
阅读更多...
Spring Cloud Alibaba(二)Nacos统一配置管理

Spring Cloud Alibaba(二)Nacos统一配置管理

目录 一、为什么需要配置中心 二、常用的配置中心 Nacos 的几个概念 三、Nacos配置中心的使用 &#xff08;一&#xff09;properties格式 1、导入依赖 2、在配置中心新建配置 3、修改配置文件名为bootstrap.yml 4、在微服务中添加nacos config服务地址的配置 5、测试…
阅读更多...
2013蓝桥杯真题省赛翻硬币 C语言/C++

2013蓝桥杯真题省赛翻硬币 C语言/C++

[蓝桥杯 2013 省 B] 翻硬币 题目背景 小明正在玩一个“翻硬币”的游戏。 题目描述 桌上放着排成一排的若干硬币。我们用 * 表示正面&#xff0c;用 o 表示反面&#xff08;是小写字母&#xff0c;不是零&#xff09;&#xff0c;比如可能情形是 **oo***oooo&#xff0c;如果…
阅读更多...
【Python_Pandas】reset_index() 函数解析

【Python_Pandas】reset_index() 函数解析

【Python_Pandas】reset_index函数解析 文章目录 【Python_Pandas】reset_index函数解析1. 介绍2. 示例2.1 参数drop2.2 参数inplace2.3 参数level2.4 参数col_level2.5 参数col_fill 参考 1. 介绍 pandas.DataFrame.reset_index reset_index(levelNone, dropFalse, inplaceF…
阅读更多...
最新文章

Copyright @ 2022~2023