数据结构之双链表的相关知识点及应用

ops/2024/9/24 6:21:00/

 找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构

目录

双链表的实现 

初始化双链表 

在双链表中尾插数据 

在双链表中尾删数据

在双链表中头插数据 

在双链表中头删数据 

在双链表中的指定位置之后插入数据 

在双链表中删除指定位置的数据

在双链表中查找指定位置

销毁双链表 

双链表源码 

学习完单链表后，就要开始学习链表中最重要的双链表了。

双链表是双向带头循环链表。与单链表是恰恰相反。

接下来就用双链表来实现一系列增删查改的功能。 

双链表的实现 

 在创建双链表之前，还得要做一些提起准备。创建三个文件：List.h  List.c  test.c  前面两个是实现双链表的，后面的 test.c 文件是测试双链表的各种功能。同样链表是由一个一个的节点组成的。我们就得由节点的结构。

创建节点：

typedef int LTDataType;typedef struct ListNode
{struct ListNode* next; //指针保存下⼀个节点的地址struct ListNode* prev; //指针保存前⼀个节点的地址LTDataType data;
}LTNode;

初始化双链表 

因为双链表带头，因此，我们就得创建一个哨兵位。这个函数也可以叫做初始化函数。

//初始化
void LTInit(LTNode** pphead)//注意这里需要改变哨兵位，因此用二级指针接收
{//创建一个新的节点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc:");exit(1);}//把哨兵位的数据初始化为-1(无效数据)，后驱指针指向自己，前驱指针指向自己*pphead = phead;(*pphead)->data = -1;(*pphead)->next = (*pphead)->prev = *pphead;
}

只要是增加节点，就会有重复的代码因此我们分装成一个函数，并且我们在初始化函数也可以传我们想要设置的无效数据。

//增加节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc:");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}

//初始化
void LTInit(LTNode** pphead)
{*pphead = LTBuyNode(-1);
}

在双链表中尾插数据 

情况一：链表中只有哨兵位：

情况二：链表中不止有哨兵位：

我们要尾插数据，就是要d3的next指针的指向，还要改变head的prev指针的指向。此外还得把新增加的节点prev指针指向d3，next指向head。

不能改变顺序的原因：如果改变了，就先把哨兵位的指向改变了，后面我们就找不到原链表的尾节点了，除非能把原链表的尾节点的地址提前存起来。

//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)//哨兵位已经确定，不再改变，因此用一级指针
{assert(phead);//链表不能为空LTNode* newnode = LTBuyNode(x);//开始尾插节点  //链表中只有哨兵位if (phead->next == phead){//先把新节点安排好newnode->next = phead;newnode->prev = phead;//哨兵位phead->next = newnode;phead->prev = newnode;}else{//先把新节点安排好newnode->next = phead;newnode->prev = phead->prev;//头节点：phead  尾节点：phead->prev   新节点：newnodephead->prev->next = newnode;phead->prev = newnode;}
}

写完之后，还得测试一下我们所写的代码是否正确：可以用打印函数来判断看看结果是否和我们的预期一样。

//打印数据
void LTPrint(LTNode* phead)
{//遍历寻找LTNode* pcur = phead->next;//头节点的数据是无效的，因此就不需要打印//因为是循环的，所以不能用空指针来判断，要看看是否指向的哨兵位while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}

在双链表中尾删数据

情况一：链表中由多个有效数据：

情况二：链表中只有一个有效数据：

//尾删数据
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素if (phead->next->next == phead)//只有一个有效数据{LTNode* freenode = phead->next;free(freenode);phead->next = phead;phead->prev = phead;}else{phead->prev->prev->next = phead;LTNode* freenode = phead->prev;phead->prev = phead->prev->prev;free(freenode);freenode = NULL;}
}

其实上面的写法可以简化为：

//尾删数据
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素phead->prev->prev->next = phead;LTNode* freenode = phead->prev;phead->prev = phead->prev->prev;free(freenode);freenode = NULL;
}

也就是说不管链表的有效元素的个数有多少，都不影响。（把特殊情况带入这个简化版里判断就可以了）。

在双链表中头插数据 

情况一：链表中不止有哨兵位： 

之所以在哨兵位的前面插入数据叫作尾插，是因为双链表是循环的，当遍历到d3后就会找到前面的节点，这就是在尾部，因此也叫作尾插。 

同样顺序不能变的原因也是因为顺序一旦改变，先把phead的next指向给改变了，就找不到了要更改的数据了。

情况二：链表中只有哨兵位：

//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);if (phead->next == phead)//只有哨兵位{newnode->next = phead;newnode->prev = phead;phead->next = newnode;phead->prev = newnode;}else{//先安排新节点newnode->next = phead->next;newnode->prev = phead;//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnodephead->next->prev = newnode;phead->next = newnode;}
}

这个头插也是可以简化的：

//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//先安排新节点newnode->next = phead->next;newnode->prev = phead;//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnodephead->next->prev = newnode;phead->next = newnode;
}

简化判断的方法就是把特殊情况带入进去，看看能否成功。

在双链表中头删数据 

//头删数据
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);//链表不为空并且链表的有效数据不能为空phead->next->next->prev = phead;LTNode* freenode = phead->next;phead->next = phead->next->next;free(freenode);freenode = NULL;
}

在双链表中的指定位置之后插入数据 

情况一：pos是哨兵位：

情况二：pos是中间位置：

情况三：pos是尾节点： 

上面的代码不管是在哪个位置都满足。

//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//先安排好新节点newnode->prev = pos;newnode->next = pos->next;pos->next = newnode;pos->next->prev = newnode;
}

在双链表中删除指定位置的数据

 情况一：pos在中间位置

情况二：pos在结尾位置：

注意：这个指定位置不能是哨兵位。

//在pos位置删除数据
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);
}

在双链表中查找指定位置

这个也比较简单，就是直接遍历整个双链表，如果没找到就返回NULL，找到就返回这个地址。

//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead && phead->next != phead);//链表不能为空并且链表不能只有哨兵位LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}

销毁双链表 

就是把链表中的节点一个一个的释放空间就行了。

//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);//就是节点一个一个的销毁LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(pcur);pcur = NULL;
}

综合上面的代码来看，还有一个地方有点小瑕疵，就是初始化链表时，我们用的是二级指针，为了保持接口一致性，我们要用一级指针或者不传参数。

//初始化
LTNode* LTInit()
{LTNode* pplist = LTBuyNode(-1);return pplist;
}

双链表源码 

下面就是双链表完整的源码：

List.c

#include "List.h"//增加节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc:");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//初始化
LTNode* LTInit()
{LTNode* pplist = LTBuyNode(-1);return pplist;
}//尾插数据
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//开始尾插节点  //链表中只有哨兵位if (phead->next == phead){//先把新节点安排好newnode->next = phead;newnode->prev = phead;//哨兵位phead->next = newnode;phead->prev = newnode;}else{//先把新节点安排好newnode->next = phead;newnode->prev = phead->prev;//头节点：phead  尾节点：phead->prev   新节点：newnodephead->prev->next = newnode;phead->prev = newnode;}
}//打印数据
void LTPrint(LTNode* phead)
{//遍历寻找LTNode* pcur = phead->next;//头节点的数据是无效的，因此就不需要打印//因为是循环的，所以不能用空指针来判断，要看看是否指向的哨兵位while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//尾删数据
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表不能为空并且链表中不能没有有效元素phead->prev->prev->next = phead;LTNode* freenode = phead->prev;phead->prev = phead->prev->prev;free(freenode);freenode = NULL;
}//头插数据
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//先安排新节点newnode->next = phead->next;newnode->prev = phead;//头节点：phead  尾节点（相较于新节点）：phead->prev  新节点：newnodephead->next->prev = newnode;phead->next = newnode;
}//头删数据
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);//链表不为空并且链表的有效数据不能为空phead->next->next->prev = phead;LTNode* freenode = phead->next;phead->next = phead->next->next;free(freenode);freenode = NULL;
}//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//先安排好新节点newnode->prev = pos;newnode->next = pos->next;pos->next = newnode;pos->next->prev = newnode;
}//在pos位置删除数据
void LTErase(LTNode* pos)
{assert(pos);pos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead && phead->next != phead);//链表不能为空并且链表不能只有哨兵位LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//销毁链表
void LTDestroy(LTNode* phead)
{assert(phead);//就是节点一个一个的销毁LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(pcur);pcur = NULL;
}

List.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef int LTDataType;typedef struct ListNode
{struct ListNode* next; //指针保存下⼀个节点的地址struct ListNode* prev; //指针保存前⼀个节点的地址LTDataType data;
}LTNode;//初始化
LTNode * LTInit();//销毁链表
void LTDestroy(LTNode* phead);//打印数据
void LTPrint(LTNode* phead);//尾插数据
void LTPushBack(LTNode* phead, LTDataType x);//尾删数据
void LTPopBack(LTNode* phead);//头插数据
void LTPushFront(LTNode* phead, LTDataType x);//头删数据
void LTPopFront(LTNode* phead);//在pos位置之后插⼊数据
void LTInsert(LTNode* pos, LTDataType x);//在pos位置删除数据
void LTErase(LTNode* pos);//查找指定数据
LTNode* LTFind(LTNode* phead, LTDataType x);

好啦！本期数据结构双链表的学习就到此为止啦！我们下一期再一起学习吧！


http://www.ppmy.cn/ops/14438.html

相关文章

课时105：正则表达式_进阶知识_扩展符号

课时105：正则表达式_进阶知识_扩展符号

1.1.1 扩展符号 学习目标 这一节&#xff0c;我们从 基础知识、简单实践、小结 三个方面来学习 基础知识 简介 字母模式匹配[:alnum:] 字母和数字[:alpha:] 代表任何英文大小写字符&#xff0c;亦即 A-Z, a-z[:lower:] 小写字母,示例:[[:lower:]],相当于[a-z][:upper:] 大…
阅读更多...
智慧物流时代：数字化转型下的物流新篇章

智慧物流时代：数字化转型下的物流新篇章

一、什么是智慧物流&#xff1f; 智慧物流是一种利用先进科技和信息技术优化物流供应链系统的新型模式。以数据为核心&#xff0c;智慧物流通过物联网、云计算、大数据和人工智能等技术手段实现物流信息的全面记录、无缝对接和智能化处理。其核心在于实现物流各环节的精细化、…
阅读更多...
Spark pivot数据透视从句

Spark pivot数据透视从句

1. 概念2. 实战 2.1. 新列的决定因素2.2. 新列别名2.3. column_list中指定多个字段2.4. 多个聚合函数的使用2.5. 最终出现在SQL结果中的决定因素 Spark pivot数据透视从句 1. 概念 描述 用于数据透视&#xff0c;根据特定的列获取聚合值&#xff0c;聚合值将转换为select子句…
阅读更多...
Vue接收接口返回的mp3格式数据并支持在页面播放音频

Vue接收接口返回的mp3格式数据并支持在页面播放音频

一、背景简介 在实际工作中需要开发一个转音频工具&#xff0c;并且能够在平台页面点击播放按钮播放音频 二、相关知识介绍 2.1 JS内置对象Blob Blob对象通常用于处理大量的二进制数据&#xff0c;可以读取/写入/操作文件、音视频等二进制数据流。Blob表示了一段不可变的二…
阅读更多...
42. 【Android教程】活动：Activity

42. 【Android教程】活动：Activity

从今天开始将会学习一个非常重要的概念——Android 四大组件&#xff0c;在 Android 中几乎所有的功能都和四大组件密不可分&#xff0c;而 Activity 是其中出场率最高的组件&#xff0c;也是对用户感知度最高的组件&#xff0c;当然也可以说是四大组件中最重要的一个组件。我们…
阅读更多...
架构师系列-Nginx、OpenResty（三）- 负载均衡配置

架构师系列-Nginx、OpenResty（三）- 负载均衡配置

Nginx负载均衡 负载均衡用于从“upstream”模块定义的后端服务器列表中选取一台服务器接受用户的请求&#xff0c;一个最基本的upstream模块是这样的&#xff0c;模块内的server是服务器列表&#xff1a; #动态服务器组 upstream dynamicserver {server 172.16.44.47:9001; #…
阅读更多...
【c/c++】cpp对c的增强

【c/c++】cpp对c的增强

&#xff08;1&#xff09;hello world代码 main.cpp文件 //包含c输出输出流的头文件&#xff0c;iostream.h //c中头文件的命名可以不再写.h的后缀&#xff0c;比如这里的iostream和test //#include "iostream" #include <iostream> #include "test&q…
阅读更多...
在使用Dubbo时，如何高效地进行网络通信？有哪些优化策略？

在使用Dubbo时，如何高效地进行网络通信？有哪些优化策略？

在使用Dubbo时&#xff0c;如何高效地进行网络通信及其优化策略 在当前的分布式系统架构中&#xff0c;微服务已经成为了一种主流的设计模式&#xff0c;而RPC&#xff08;远程过程调用&#xff09;则是微服务之间通信的基石。Apache Dubbo作为一款高性能、轻量级的开源Java R…
阅读更多...
最新文章

Copyright @ 2022~2023