【C语言】双向链表详解

文章目录

  • 关于双向链表
  • 双向链表的初始化
  • 双向链表的打印
  • 双向链表方法调用 - 尾删为例
  • 双向链表的查找 - 指定位置之后插入为例
  • 双向链表结束 - 链表的销毁
  • 小结及整体代码实现

关于双向链表

首先链表有8种基本分法 在这里插入图片描述

其中在笔者之前文章种详细介绍的 单链表 是不带头单项不循环链表
而今天笔者要介绍的就是 带头双向循环链表 双向链表

我们可以把链表理解为下图

在这里插入图片描述
所以我们双向链表的结构往往是这样的
在这里插入图片描述
即

typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

双向链表的初始化

第一步我们需要进行双向链表的初始化，双向链表的初始化需要注意的一个问题是，传进去的参数是一级指针还是二级指针，这本应该后面大致写完了再讨论，但是这里提前说了

在笔者后面的方法中，例如尾插，头插，尾删，头删等都是用一级指针，这是因为双向链表有一个好处，我们存在一个哨兵位，这个节点是初始化时创立的，不需要改变，同时有存储着前后节点的地址，只需要通过成员名调用即可，这里呈现一下会出现的方法参数

//打印
void LTPrint(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);

笔者这里据大多数关于双向链表的地址传参都是一级指针，这在一定程度上，保证了接口的一致性，为后来调用双向链表数据结构者降低了理解成本，这也就是我们在设计程序时需要注意的一点

笔者这里通过二级指针传参和无传参的方法各创建了一个初始化方法
大家可以看到两种方法连语句都基本一致，但是后者明显会比前者好，因为在以后不论是我们还是其他人通过一览所有的方法名后，不需要刻意去记初始化需要传参二级指针，直接空着使用就行了

//申请节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc newnode");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;//指向自己

	return newnode;
}

//初始化1
void LTInit(LTNode** pphead)
{
	//该双向链表创建一个哨兵位
	*pphead = LTBuyNode(-1);
}
//初始化2
LTNode* newLTInit()
{
	return LTBuyNode(-1);
}

双向链表的打印

双向链表的打印比单链表好理解太多了，
因为存在一个无意义的 哨兵位 用来记录开头，链接末尾，
所以只需要新创建一个新的节点用来帮忙定位当前位置，如果这个节点的值跟 哨兵位 一样，便退出

代码如下

//打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->",pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

双向链表方法调用 - 尾删为例

大家可以先看一下下图，我们在双向链表的末尾放上新节点

在这里插入图片描述

为了保证双向链表在使用时不发生意外，
我们先将 newnode 的 prev 和 next 对接好 d3 和 头节点phead
这样做只是给新的节点的前后向确定好，不影响原来的双向链表

再将 d3 的 next 对准 newnode，
phead 的 prev 对准 newnode

下面代码呈现

//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

双向链表的查找 - 指定位置之后插入为例

在这里插入图片描述

指定位置之后插入，除了插入这个重要点，就是指定位置这个大头了，那么我们该如何实现找到指定位置呢

同样因为 哨兵位 的存在，我们新定义节点来一个一个对比下去，知道等于 哨兵位 为止，代表整个双向链表中都没有这个要查找的数据

即

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
			return pcur;
		pcur = pcur->next;
	}
	return NULL;
}

既然知道如何找到指定位置，那么接下来就是插入了，
我们通过指定位置的节点信息，按照前面尾插的方法就行了，也是很简单的

//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);

	newnode->next = pos->next->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}

双向链表结束 - 链表的销毁

因为我们前面有提到为保证接口的一致性我们同意设定为一级指针，但这样我们能做的就是将除 哨兵位 以外的节点全部置为空，但是外部所创建的节点，即我们一开始所初始化的点无法在内部置为空，所以出去后仍然需要置为空

即

//销毁
void LTDestory(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
	pcur = NULL;//这点无所谓，跳出方法，就会为空
}

这是内部的销毁，出去后，在置为空一次，即

LTDestory(plist);
plist = NULL;

小结及整体代码实现

有一说一，双向链表真的很好理解，而且写方法时，往往不用循环就能很容易解出来，比单链表和数组方便许多，大家如果想要自己实现双向链表，尽量没完成一次方法时，调试检验一下，方便找到错误

下面为大家展现一下笔者的代码

“List.h”

#pragma once

#define _CRT_SECURE_NO_WARNINGS  1
#pragma warning(disable:6031)

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{
	int data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;


//声明双向链表中提供的方法
//尽量都用一级指针，降低调用方的理解成本，保持接口的一致性
//初始化
//void LTInit(LTNode** pphead);
LTNode* newLTInit();

//打印
void LTPrint(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);

“List.c”

#include"List.h"


//申请节点
LTNode* LTBuyNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc newnode");
		exit(1);
	}
	newnode->data = x;
	newnode->next = newnode->prev = newnode;//指向自己

	return newnode;
}


//初始化
void LTInit(LTNode** pphead)
{
	//该双向链表创建一个哨兵位
	*pphead = LTBuyNode(-1);
}

LTNode* newLTInit()
{
	return LTBuyNode(-1);
}

//销毁
void LTDestory(LTNode* phead)
{
	assert(phead);

	LTNode* pcur = phead;
	while (pcur != phead)
	{
		LTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = NULL;
	pcur = NULL;//这点无所谓，跳出方法，就会为空
}


//打印
void LTPrint(LTNode* phead)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->",pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}


//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	newnode->prev = phead->prev;
	newnode->next = phead;

	phead->prev->next = newnode;
	phead->prev = newnode;
}

//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* newnode = LTBuyNode(x);

	newnode->prev = phead;
	newnode->next = phead->next;

	phead->next->prev = newnode;
	phead->next = newnode;
}

//尾删
void LTPopBack(LTNode* phead)
{
	//链表必须有效且不为空
	assert(phead && phead->next != phead);

	phead->prev->prev->next = phead;
	phead->prev = phead->prev->prev;
}
//头删
void LTPopFront(LTNode* phead)
{
	assert(phead && phead->next != phead);

	phead->next->next->prev = phead;
	phead->next = phead->next->next;
}

//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
	LTNode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->data == x)
			return pcur;
		pcur = pcur->next;
	}
	return NULL;
}

//在pos之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);

	newnode->next = pos->next->next;
	newnode->prev = pos;

	pos->next->prev = newnode;
	pos->next = newnode;
}
//在pos之前插入数据
void LTInsertAfter(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* newnode = LTBuyNode(x);
	
	newnode->next = pos;
	newnode->prev = pos->prev;

	pos->prev->next = newnode;
	pos->prev = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)
{
	assert(pos);

	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;

	free(pos);
	pos = NULL;
}

测试文件就不展示了，没有什么参考价值，能够独自理解并写出上述方法名，一个简简单单的调试自然不在话下

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/538325.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Leetcode算法训练日记 | day24

Leetcode算法训练日记 | day24

一、组合问题 1.题目 Leetcode&#xff1a;第 77 题 给定两个整数 n 和 k&#xff0c;返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按 任何顺序 返回答案。 示例 1&#xff1a; 输入&#xff1a;n 4, k 2 输出&#xff1a; [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4…
阅读更多...
别人起诉你你不服，到底是写上诉状还是反诉状？李秘书讲写作讲给你听！

别人起诉你你不服，到底是写上诉状还是反诉状？李秘书讲写作讲给你听！

别人起诉你你不服&#xff0c;到底是写上诉状还是反诉状&#xff1f;李秘书讲写作讲给你听&#xff01; 别人向法院告了你&#xff0c;你不服气&#xff0c;这时你可能想到要申辩或“报复”&#xff0c;但又不知是写上诉状呢还是写反诉状呢&#xff1f;#李秘书讲写作#这节就讲…
阅读更多...
深度学习入门（2）

深度学习入门（2）

一。Matplotlib模块添加 Matplotlib是用于绘制图形的库&#xff0c;使用 Matplotlib 可以轻松地绘制图形和实现数据的可视化。 pip install matplotlib -i https://pypi.tuna.tsinghua.edu.cn/simple 二、绘制简单图形 import numpy as np import matplotlib.pyplot as plt #…
阅读更多...
【电控笔记7】速度回路+系统延迟

【电控笔记7】速度回路+系统延迟

2.3.1速度回路pi控制器设计 Tl：负载转矩
阅读更多...
ubuntu16.04安装Eclipse C/C++

ubuntu16.04安装Eclipse C/C++

1.安装 JDK 官网源码安装 首先打开JDK官网&#xff0c;JDK1.8的下载网址为&#xff1a;https://www.oracle.com/cn/java/technologies/downloads/#java8-windows&#xff0c;进入到网址如下图所示&#xff1a; 向下滑动到 JDK1.8的下载界面&#xff0c;如下图所示&#xff1a…
阅读更多...
面试题：重写equals()，为什么还要重写hashcode()

面试题：重写equals()，为什么还要重写hashcode()

认识equals(): Object类中的equals; public boolean equals(Object obj) {return (this obj);}当我们没有重写equals&#xff08;&#xff09;&#xff0c;我们是调用父类object中的方法&#xff0c;比较的是对象的内存地址 重写equals后&#xff0c; public class Student…
阅读更多...
【群智能算法改进】一种改进的鹦鹉优化算法 改进鹦鹉优化器 IPO算法【Matlab代码#73】

【群智能算法改进】一种改进的鹦鹉优化算法 改进鹦鹉优化器 IPO算法【Matlab代码#73】

文章目录 【获取资源请见文章第5节&#xff1a;资源获取】1. 原始鹦鹉优化算法PO2. 改进后的IPO算法2.1 自适应切换因子2.2 混合柯西和高斯变异 3. 部分代码展示4. 仿真结果展示5. 资源获取 【获取资源请见文章第5节&#xff1a;资源获取】 1. 原始鹦鹉优化算法PO 鹦鹉优化算法…
阅读更多...
java程序 .exe启动nginx防止重复启动，已解决

java程序 .exe启动nginx防止重复启动，已解决

java代码生成好的.exe启动nginx服务程序 根据nginx占用端口来解决nginx服务重复启动问题&#xff08;下面代码了解代码逻辑后根据自己的业务需求修改即可&#xff09; 代码&#xff1a; package org.example;import javax.swing.*; import java.awt.*; import java.io.*; …
阅读更多...
6.Burp Suite 入门篇 —— Burp Scanner 漏洞扫描

6.Burp Suite 入门篇 —— Burp Scanner 漏洞扫描

目录 前言 扫描网站 打开扫描启动页面 填写目标网站地址 配置扫描参数 开始扫描 查看网站结构 查看扫描结果 生成漏洞扫描报告 选择扫描结果 配置报告选项 生成并保存报告 查看或分享报告 前言 Burp Scanner 既可以是独立的全自动扫描器&#xff0c;也可以在手动…
阅读更多...
约瑟夫问题---C++

约瑟夫问题---C++

今天来讲一道饶有名气的题目&#xff0c;约瑟夫问题 约瑟夫问题 这道题目有许多大佬用队列、递归、链表来解这道题目而这题的难度也确实非同小可&#xff01; 可是你们难道没有想过&#xff1f;用数组去解决吗&#xff1f;没错一维数组&#xff01;为了想出解决办法我掉了23根头…
阅读更多...
福建单航次最大批量汽车“出海”

福建单航次最大批量汽车“出海”

3月12日这一天&#xff0c;在福州海关的严密监管下&#xff0c;共有4000辆上汽名爵品牌的汽车被高效有序地装载到“安吉智慧”号滚装船上&#xff0c;这批车辆即将启程前往荷兰、埃及、英国等多个海外市场。在这批出口汽车中&#xff0c;新能源车型占据了显著的比例&#xff0c…
阅读更多...
飞书api增加权限

飞书api增加权限

1&#xff0c;进入飞书开发者后台&#xff1a;飞书开放平台 给应用增加权限 2&#xff0c;进入飞书管理后台 https://fw5slkpbyb3.feishu.cn/admin/appCenter/audit 审核最新发布的版本 如果还是不行&#xff0c;则需要修改数据权限&#xff0c;修改为全部成员可修改。 改完…
阅读更多...
【避坑NOC】关于举办2023-2024学年全国中小学信息技术创新与实践大赛的通知

【避坑NOC】关于举办2023-2024学年全国中小学信息技术创新与实践大赛的通知

01-关于2024年赛事信息 2024年NOC比赛已经可以开始报名了，今年的报名比去年提前了接近2个月，这项白名单赛事去年问题比较多，推荐指数不高，当然，如果愿意参加的，下面老师还有一些避坑信息，参加的同学和机构老师必须要了解。先来看一下完整的通知： 02-比赛类别 共设有三…
阅读更多...
CMD命令窗口提示文字乱码

CMD命令窗口提示文字乱码

我下面说的是日文版系统&#xff0c;中文版会有差异。 一般情况下是 Shiftjis 通常我是用sakura editor来写bat&#xff0c;但是运行后会在cmd窗口出现乱码 test.bat set HENSU这是一个变数 echo %HENSU% pause 执行后出现乱码 原因是不做设置时&#xff0c;command prom…
阅读更多...
多线程java

多线程java

多线程的创建 前两种方法无法返回直接结果,而有的线程执行完毕后需要返回结果 方式一:java是通过java.lang.Thread类的对象来代表线程的 启动线程必须调用strat方法,不是调用run方法不要把主线程任务放在启动子线程之前 //1.让子类继承Thread线程类 public class MyThread …
阅读更多...
数据库体系概述：详述其基本概念、多样分类、关键作用及核心特性

数据库体系概述：详述其基本概念、多样分类、关键作用及核心特性

数据库是一个用于存储、管理和检索数据的系统&#xff0c;它按照特定的数据结构和模式组织数据&#xff0c;确保数据的一致性、安全性和高效访问。 数据库&#xff08;Database, DB&#xff09;是一个长期存储在计算机内&#xff0c;用来组织、存储和管理大量数据的集合。数据…
阅读更多...
spispi

spispi

数据手册里面有这么一段解释&#xff0c;就是说如果我们开启了看门狗&#xff0c;那么LSI就会跟随强制打开&#xff0c;等待LSI稳定之后就可以自动为独立看门狗提供时钟了。所以这里的第一步开启时钟不需要我们写代码来执行 2.写入预分频器和重装寄存器 在写入这两个寄存器之前…
阅读更多...
第十三届蓝桥杯真题：x进制减法，数组切分，gcd，青蛙过河

第十三届蓝桥杯真题：x进制减法，数组切分，gcd，青蛙过河

目录 x进制减法 数组切分 gcd 青蛙过河 x进制减法 其实就是一道观察规律的题。你发现如果a这个位置上的数x&#xff0c;b这个位置上的数是y&#xff0c;那么此位置至少是max(x,y)1进制。一定要把位置找对啊 #include <bits/stdc.h> using namespace std; typedef l…
阅读更多...
题目:建造房屋 (蓝桥OJ3362)

题目:建造房屋 (蓝桥OJ3362)

问题描述: 代码: #include<bits/stdc.h> using namespace std; int n, m, k, ans, mod 1e9 7; long long dp[55][2605]; /*dp[i][j]&#xff1a;第i个街道上建j个房屋的总方案数枚举所有的转移&#xff0c;累加到dp[n][k]即总方案数 */ int main() {cin >> n &…
阅读更多...
秋招数据库学习2（20240408-20240412共10道）

秋招数据库学习2（20240408-20240412共10道）

由于感觉数据库难度可能暂时面试用不到&#xff0c;就先不刷啦 20240408 1.从不订购的客户 SELECT Name AS Customers FROM Customers C LEFT JOIN Orders O ON C.Id O.CustomerId WHERE CustomerId is nullselect customers.name as Customers from Customers wher…
阅读更多...
最新文章

Copyright @ 2022~2023