C语言双向链表

server/2024/12/22 12:57:05/

前面我们已经学完了单链表的知识点（如果还没有看过的主页有哦~），这篇博客我们就来探讨探讨单链表的孪生弟弟——双向链表。

目录

1.链表的分类

2.双向链表的结构

3.双向链表的实现

3.1 List.h

3.2 List.c

4.书写要点总结说明

4.1为什么要使用一级指针

4.2三个使用到的嵌套调用

4.3相对于单链表书写的不同

1.链表的分类

首先，链表中最基础的就是单链表，在单链表里面有提过一嘴一个东西“哨兵位”，其实呢，这个哨兵位才是链表真正的头节点。看到如下图：

从图中我们可以看到，链表的分类有八种（2*2*2）：

  • 带不带头：表示有没有哨兵位（也就是不存储有效值的头结点）；“哨兵位”存在的意义： 遍历循环链表避免死循环。
  • 单向双向：代表链表可以访问的方向
  • 循环不循环：代表链表的头结点和尾节点有没有链接起来

以下为更详细的表示：

其中我们称之前学过的单链表为“不带头单向不循环链表” ，而这篇要讲的双向链表则是“带头双向循环链表”。链表常用的就是这两种。

2.双向链表的结构

用图表示，结构如下： 

想要实现向前访问这样的结构，我们就需要在单链表节点的结构体里面再加上一个指向上一个链表节点的指针。 两个指针实现双向访问！

用代码表示如下：

typedef int LTDateType;
typedef struct LTNode {struct LTNode* prev;//指向上一个链表节点的指针LTDateType val;struct LTNode* next;//指向下一个链表节点的指针
}LTNode;

3.双向链表的实现

下面是实现双向链表的代码：

3.1 List.h

存放双向链表结构体及相关函数声明： 

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//双向链表节点结构体
typedef int LTDateType;
typedef struct LTNode {struct LTNode* prev;LTDateType val;struct LTNode* next;
}LTNode;//申请内存
LTNode* LTBuyNode(LTDateType x);//初始化空链表
LTNode* LTInit();
//头插
void LTPushFront(LTNode* phead,LTDateType x);
//尾插
void LTPushBack(LTNode* phead, LTDateType x);//头删
void LTPopFront(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);//pos前插
void LTInsert(LTNode*pos,LTDateType x);
//pos后插
void LTInsertAfter(LTNode* pos, LTDateType x);//删pos
void LTErase(LTNode* pos);
//删pos后
void LTEraseAfter(LTNode* pos);//查找
LTNode* LTFind(LTNode* phead, LTDateType x);
//打印链表
void LTPrint(LTNode* phead);
//销毁链表
void LTDestroy(LTNode* phead);

3.2 List.c

存放相关函数定义：

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//初始化双向链表
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);phead->next = phead;phead->prev = phead;
}
//申请内存
LTNode* LTBuyNode(LTDateType x)
{LTNode* p = (LTNode*)malloc(sizeof(LTNode));p->next = NULL;p->prev = NULL;p->val = x;return p;
}
//头插
void LTPushFront(LTNode* phead,LTDateType x)
{assert(phead);//为pcur申请内存LTNode* pcur = LTBuyNode(x);//pcur链接到头和下一个节点上pcur->next = phead->next;pcur->prev = phead;//修改头结点的next与下一个节点的prevent指针指向pcur->next->prev = pcur;pcur->prev->next = pcur;
}
//尾插
void LTPushBack(LTNode* phead, LTDateType x)
{assert(phead);//为pcur申请内存LTNode* pcur = LTBuyNode(x);//修改pcur指针指向pcur->next = phead;pcur->prev = phead->prev;//pcur->next->prev = pcur;pcur->prev->next = pcur;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next!=phead);LTNode* pdel = phead->next;//链接前后两个节点phead->next = pdel->next;pdel->next->prev = phead;//删除pdelfree(pdel);pdel = NULL;
}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* pdel = phead->prev;phead->prev = pdel->prev;pdel->prev->next = phead;free(pdel);pdel = NULL;
}
//pos前插
void LTInsert(LTNode* pos, LTDateType x)
{LTPushBack(pos, x);
}
//pos后插
void LTInsertAfter(LTNode* pos, LTDateType x)
{LTPushFront(pos, x);
}
//删pos
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}
//删pos后
void LTEraseAfter(LTNode* pos)
{LTPopFront(pos);
}
//查找
LTNode* LTFind(LTNode* phead, LTDateType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur!= phead){if (pcur->val == x){return pcur;}pcur = pcur->next;}return NULL;
}
//打印链表
void LTPrint(LTNode* phead)
{assert(phead);printf("phead");LTNode* pcur = phead->next;while (pcur != phead){printf("->%d", pcur->val);pcur = pcur->next;}printf("\n");}
//销毁链表
void LTDestroy(LTNode* phead)
{LTNode* pcur = phead->next;LTNode* pdel = pcur;while (pcur != phead){pdel = pcur;pcur = pcur->next;free(pdel);}free(pcur);//出了函数后记得把phead置空
}

4.书写要点总结说明

4.1为什么要使用一级指针

我们可以回顾一下，在编写单链表的时候，函数的形参使用的都是二级指针

那么同是链表，为什么单链表使用二级指针，但是双向链表就可以用一级指针了呢？

对于单链表为什么使用二级指针可以回顾博主之前的单链表博客

对于双向链表：

区别于单链表，双向链表有一个哨兵位，哨兵位不存储有效数据，也就是说，对于链表的增删查改都不改变哨兵位，真正会改变的是哨兵位head的head->prev和head->next，而这两者虽是链表节点指针，但却使head指向的结构体里面的成员，改变成员的话，传入结构体的地址，即传入一个指向成员对应的结构体的指针就足够了。

双向链表中唯一需要改变head指向的操作时销毁链表操作，因为销毁链表后需要将head指向NULL。然而，为了保持函数传入接口的统一（为了方便记忆），所以我们把销毁操作传入指针也设置为一级指针，不过要注意在函数结束后要手动将head置空，防止野指针的出现。

4.2三个使用到的嵌套调用

 

其实代码不一定要这样去写，只是博主单纯觉得这样写更加简单明了。

由于双向链表是一个循环的链表，所以在进行插入删除操作时，不用担心会出现对空指针解引用的现象。也就是说，相比于单链表，双向链表的头结点也可以成为中间节点，中间节点也可以看做头结点（但注意不能改变head指向），所以博主进行了一下操作：

  • pos前插调用尾插：尾插是在head前面插入元素，那么将传入指针改为pos后，尾插也能实现在pos前插入元素。
  • pos后插调用头插： 头插是在head后，第一个有效节点前插入元素，那么将传入指针改为pos后，头插也能实现在pos后插入元素。
  • pos后删调用头删：头删是删除head后的第一个节点，pos后删也是删除pos后的第一个节点，所以调用头删也能实现该功能。

4.3相对于单链表书写的不同

  1. 单链表的相关函数传参传的是二级指针；双向链表传的是一级指针。
  2. 单链表中，指针解引用访问next是需要考虑空指针的情况（尾插、尾删、pos前插，删pos）；双向链表由于是循环结构，故不管访问到第几个next或prev，都不会遇到空指针，所以不需要考虑空指针解引用的情况。
  3. 销毁链表后：单链表中不用再对头指针置空（传入二级指针，函数内部可进行置空）；双向链表中销毁链表后需要再对头指针置空（传入一级指针，函数内部无法改变传入指针指向）。
  4. 单链表中所有不在头节点的操作（除了删除pos后节点）都需要遍历链表找到要操作的节点；双向链表不需要遍历，直接通过传入节点就可以找到前后节点。 

--------------------------------------------------------------------------------------------------------------------------------

OK，那双向链表的讲解就到这里啦，看完的小伙伴记得点赞关注哦~ 


http://www.ppmy.cn/server/36810.html

相关文章

XSS攻击分析---（原理、危害、防御、应急响应）

XSS攻击分析---（原理、危害、防御、应急响应）

1、攻击原理 造成XSS漏洞的原因就是&#xff0c;对攻击者的输入没有经过严格的控制&#xff0c;使得攻击者通过巧妙的方法注入恶意指令代码到网页&#xff0c;进行加载并执行。这些恶意网页程序通常是JavaScript&#xff0c;但实际上也可以包括Java&#xff0c; VBScript&…
阅读更多...
数据可视化准备：动态识别echarts的横纵坐标数据字段

数据可视化准备：动态识别echarts的横纵坐标数据字段

前言 继上一篇文章 自动选择图表类型&#xff1a;基于数据特征智能决策 分析了如何根据sql和数据结果判断应该自动使用哪种图表类型&#xff0c;本文继续将图表的x轴和y轴横纵坐标识别出来&#xff0c;基本一个二维数据类普通图表就可以直接输出为echarts参数了。 在数据可视…
阅读更多...
Android 桌面小组件 AppWidgetProvider

Android 桌面小组件 AppWidgetProvider

Android 桌面小组件 AppWidgetProvider 简介 小组件就是可以添加到手机桌面的窗口。点击窗口可以进入应用或者进入应用的某一个页面。 widget 组件 如需创建 widget&#xff0c;您需要以下基本组件&#xff1a; AppWidgetProviderInfo 对象 描述 widget 的元数据&#xff0…
阅读更多...
解决连接不上VPN问题

解决连接不上VPN问题

解决连接不上VPN问题 错误描述&#xff1a;错误描述&#xff1a; 错误描述&#xff1a; 无法建立计算机与VPN服务器之间的网络连接&#xff0c;因为远程服务器未响应。这可能是因为未将计算机与远程服务器之间的某种网络设备&#xff08;如防火墙、NAT、路由器等&#xff09;配…
阅读更多...
node.js中的断言

node.js中的断言

assert.ok(value, [message])&#xff1a;如果value不为真&#xff0c;则抛出一个AssertionError&#xff0c;可选地包含message。 const assert require(assert); assert.ok(true); // 没有错误 assert.ok(false, 这里应该是true); // 抛出 AssertionError: 这里应该是tru…
阅读更多...
远程桌面连接不上，远程桌面连接不上的专业解决策略

远程桌面连接不上，远程桌面连接不上的专业解决策略

在信息技术领域&#xff0c;远程桌面连接是一种非常重要的工具&#xff0c;它允许用户从任何地点、任何时间访问和操作远程计算机。然而&#xff0c;当远程桌面连接出现问题时&#xff0c;可能会严重影响工作效率。以下是一些可能导致远程桌面连接不上的原因以及相应的解决方案…
阅读更多...
通过颜色学习css

通过颜色学习css

文章目录 1.生成html2.添加css链接3.将h1标签text-align元素4.添加div标签4.1、为类marker添加元素4.2、添加两个新的div标签4.3、修改div标签的类型并修改css元素4.4、为类container添加元素4.5、以数字形式添加颜色4.5、container添加padding属性4.6、组合css中的颜色属性4.7…
阅读更多...
CMakeLists.txt语法规则：条件判断中表达式说明一

CMakeLists.txt语法规则：条件判断中表达式说明一

一. 简介 前面学习了 CMakeLists.txt语法中的 部分常用命令&#xff0c;常量变量&#xff0c;双引号的使用。 前面一篇文章也简单了解了 CMakeLists.txt语法中的条件判断&#xff0c;文章如下&#xff1a; CMakeLists.txt语法规则&#xff1a;条件判断说明一-CSDN博客 本文…
阅读更多...
最新文章

Copyright @ 2022~2023