当前位置: 首页 > news >正文

用C语言实现双向链表

目录

一.双向链表的结构

二. 双向链表的实现

1. 在List.h中结构体的定义和各函数的声明 

1.1 结构体(节点)的定义 

1.2 各函数的声明

2. 在List.c中各函数的实现

2.1 初始化 LTInit

2.2 尾插 LTPushBack

2.3 打印 LTPrint

2.4 头插 LTPushFront

2.5 尾删 LTPopBack

2.6 头删 LTPopFront

2.7 在指定位置后插入数据 LTInsert

2.8 查找 LTFind

2.9 删除指定位置节点 LTErase

2.10 销毁 LTDestroy

三. 顺序表和双向链表的优缺点分析

四. 参考代码

 1. List.h

2. List.c

3. test.c


一.双向链表的结构

双向链表的结构

注意:这里的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了更好的理解就直接称为单链表的头节点。

带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”

“哨兵位”存在的意义:

遍历循环链表避免死循环

二. 双向链表的实现

注:本次我们将实现一个双向带头循环链表。 

1. 在List.h中结构体的定义和各函数的声明 

1.1 结构体(节点)的定义 

//重命名数据类型
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//指向前一个节点struct ListNode* next;//指向后一个节点
}LTNode;

1.2 各函数的声明

//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);//打印
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

2. 在List.c中各函数的实现

2.1 初始化 LTInit

既然涉及到插入新节点,那我们就需要创建一个新节点,由于每次插入都需要创建新节点,所以我们设计一个新函数专门来创建新节点。

LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc failed");exit(1);}node->data = x;node->prev = node->next = node;return node;
}

注意:

1. 每次malloc申请空间后应当检查是否申请成功。

2. 将新申请的节点的前后指针指向自己,实现循环。

初始化操作我们需要创建哨兵节点,哨兵节点所带的值可以任意

LTNode* LTInit(void)
{LTNode* node = LTBuyNode(EOF);return node;
}

2.2 尾插 LTPushBack

要对链表进行尾插,找到链表的哨兵节点,然后新节点插入哨兵节点的前一位,由于链表循环,所以也相当于尾插在链表尾。

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead ..... phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

2.3 打印 LTPrint

我们创建一个指针pcur指向哨兵节点的下一个节点并沿着链表向后依次打印,如果等于哨兵节点,就说明已经遍历完成

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

2.4 头插 LTPushFront

与尾插类似,在哨兵节点的下一位进行插入,注意连接好前后指针。

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

2.5 尾删 LTPopBack

尾删前要注意链表有效且不为空,然后断开要释放节点和前后节点的前后指针,最后释放该节点。

void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表有效且不为空(只有一个哨兵位)//phead  ......  del->prev(phead->prev->prev)  del(phead->prev)LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}

2.6 头删 LTPopFront

与头删类似,在哨兵节点的下一位进行删除,注意连接好前后指针。

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead  del(phead->next)  del->next(phead->next->next) ......phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}

2.7 在指定位置后插入数据 LTInsert

函数参数中提供了插入位置pos,连接好前后指针即可。

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

2.8 查找 LTFind

与打印类似,遍历一次链表,查找是否有符合条件的节点,如果有返回节点指针,如果没有返回空指针

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

2.9 删除指定位置节点 LTErase

与在打印和查找类似,函数参数中提供了删除位置pos,处理好前后指针即可。

void LTErase(LTNode* pos)
{//pos理论上不能为phead,但是参数有限,无法校验assert(pos);//... pos->prev pos pos->next ...pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.10 销毁 LTDestroy

与在指定位置后插入数据类似,从哨兵节点的下一位遍历一次链表,遍历的同时用双指针法依次释放节点,最后释放哨兵节点。

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁pheadfree(phead);phead = NULL;pcur = NULL;
}

我们可以发现,由于双向链表具有指向前后节点的指针,代码量大大减少,但是也需要处理好指针之间的关系。

三. 顺序表和双向链表的优缺点分析

顺序表和双向链表的优缺点

不同点

顺序表

链表(单链表)

存储空间上

物理上一定连续

逻辑上连续,但物理上不一定连续

随机访问

支持O(1)

不支持:O(N)

任意位置插入或者删除元素

可能需要搬移元素,效率低O(N)

只需修改指针指向

插入

动态顺序表,空间不够时需要扩容

没有容量的概念

应用场景

元素高效存储+频繁访问

任意位置插入和删除频繁

四. 参考代码

 1. List.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//重命名数据类型
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//指向前一个节点struct ListNode* next;//指向后一个节点
}LTNode;//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);//打印
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

2. List.c

#include "List.h"LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc failed");exit(1);}node->data = x;node->prev = node->next = node;return node;
}//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit(void)
{LTNode* node = LTBuyNode(EOF);return node;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead ..... phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->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 LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->next ......newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表有效且不为空(只有一个哨兵位)//phead  ......  del->prev(phead->prev->prev)  del(phead->prev)LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead  del(phead->next)  del->next(phead->next->next) ......phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}void LTErase(LTNode* pos)
{//pos理论上不能为phead,但是参数有限,无法校验assert(pos);//... pos->prev pos pos->next ...pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁pheadfree(phead);phead = NULL;pcur = NULL;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//... pos newnode pos->next ...newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

3. test.c

#include "List.h"void ListTest01()
{LTNode* plist = NULL;plist = LTInit();//LTPushBack(plist, 1);//LTPushBack(plist, 2);//LTPushBack(plist, 3);//LTPushBack(plist, 4);//LTPushBack(plist, 5);//LTPrint(plist);LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPushFront(plist, 5);LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTNode* find = NULL;//find = LTFind(plist, 2);//if (find)//{//	printf("找到了!\n");//}//else//{//	printf("找不到!\n");//}//find = LTFind(plist, 7);//if (find)//{//	printf("找到了!\n");//}//else//{//	printf("找不到!\n");//}//LTNode* find = NULL;//find = LTFind(plist, 2);//if (find)//{//	printf("找到了!\n");//}//else//{//	printf("找不到!\n");//}//LTInsert(find, 6);//LTPrint(plist);//LTErase(find);//find = NULL;//LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{ListTest01();return 0;
}

相关文章:

用C语言实现双向链表

目录 一.双向链表的结构 二. 双向链表的实现 1. 在List.h中结构体的定义和各函数的声明 1.1 结构体&#xff08;节点&#xff09;的定义 1.2 各函数的声明 2. 在List.c中各函数的实现 2.1 初始化 LTInit 2.2 尾插 LTPushBack 2.3 打印 LTPrint 2.4 头插 LTPushFron…...

Github 2024-08-10 Rust开源项目日报Top10

根据Github Trendings的统计,今日(2024-08-10统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Rust项目10Python项目1Turbo:下一代前端开发工具链 创建周期:977 天开发语言:Rust协议类型:MIT LicenseStar数量:25308 个Fork数量:1713 …...

深入解析 ESLint 配置:从零到精通

深入解析 ESLint 配置&#xff1a;从零到精通 ESLint 是一个强大的代码检查工具&#xff0c;主要用于识别 JavaScript 和其他支持的语言中的常见编程错误&#xff0c;并强制执行一致的编码风格。自2013年6月由Nicholas C. Zakas创建以来&#xff0c;ESLint 已成为前端开发中不…...

BTC连续拉涨,击碎空头幻想

原创 | 刘教链 隔夜BTC继续拉涨&#xff0c;急破6万刀&#xff0c;“过了黄洋界&#xff0c;险处不须看”&#xff0c;一度逼近63k&#xff0c;目前暂于61-62k区间休整。从8月5日极限插针下探49k&#xff0c;仅仅3天多时间&#xff0c;就连续拉涨到了61k&#xff0c;总涨幅接近…...

【Spring】Sping笔记01

参考学习&#xff1a;b站浪飞yes ---------------------------------------------------- # 一、Spring 引入 **事务实现** java public class EmployeeServiceImpl implements IEmployeeService { public void save(Employee employee){ // 打开资源 /…...

Gridcontrol纵向/横向合并单元格

指定列值相同&#xff0c;纵向合并&#xff1a; this.gridView1.OptionsView.AllowCellMerge true;//启用合并列 // 启用指定合并列事件 this.gridView1.CellMerge new DevExpress.XtraGrid.Views.Grid.CellMergeEventHandler(gridView1_CellMerge);#region 合并指定的列 pri…...

从周杰伦的《青花瓷》三次更名看方文山的国学情怀与工匠精神

《青花瓷》三次更名&#xff0c;方文山的国学情怀与工匠精神 在华语乐坛上&#xff0c;周杰伦与方文山的合作堪称黄金组合&#xff0c;他们的作品不仅引领了流行音乐的潮流&#xff0c;更让传统文化焕发出新的生机。在这其中&#xff0c;《青花瓷》无疑是他们合作的经典之一&a…...

HATS:分层图注意力神经网络用于股票预测

HATS&#xff1a;分层图注意力神经网络用于股票预测 原创 QuantML QuantML 2024年08月09日 19:08 上海 Content 本文提出了一种名为HATS&#xff08;Hierarchical Graph Attention Network&#xff09;的分层图注意力网络&#xff0c;用于预测股市动向。HATS通过选择性地聚合…...

【日常记录-MySQL】MySQL设置root用户密码

Author&#xff1a;赵志乾 Date&#xff1a;2024-08-09 Declaration&#xff1a;All Right Reserved&#xff01;&#xff01;&#xff01; 1. 简介 MySQL8.0.30安装后启动&#xff0c;发现root用户尚未设置密码。以下是两种设置root用户密码的方式。 2. 示例 2.1 mysqladmin…...

高级Web安全技术(第二篇)

我们继续第二篇&#xff0c;继续深入了解web的安全 一、概述 在Web应用的开发与部署中&#xff0c;安全问题不仅是技术挑战&#xff0c;更是对系统整体架构的考验。本篇文章将继续深入探讨高级Web安全技术&#xff0c;重点关注API安全的最佳实践、OAuth的安全实施以及安全编码…...

前端实现文件下载常用几种方式

项目中前端下载一般分为两种情况&#xff1a; 后端直接提供一个文件地址&#xff0c;通过浏览器打开就可以下载。需要发送请求&#xff0c;后端返回二进制流数据&#xff0c;前端解析流数据&#xff0c;生成URL实现下载。 前端对应的实质是a标签和Blob文件下载&#xff0c;这…...

Isaac Lab 安装 (ubuntu22.04环境)

Windows下的安装见这篇博客&#xff1a; Isaac Lab 安装与初体验 &#xff08;windows环境&#xff09;-CSDN博客 ubuntu22.04下的安装与windows下十分类似&#xff0c;还是参考官方的&#xff0c;Installation using Isaac Sim Binaries Installation using Isaac Sim Bina…...

todoList清单(HTML+CSS+JavaScript)

&#x1f30f;个人博客主页&#xff1a; 前言&#xff1a; 前段时间学习了JavaScript&#xff0c;然后写了一个todoList小项目&#xff0c;现在和大家分享一下我的清单以及如何实现的&#xff0c;希望对大家有所帮助 &#x1f525;&#x1f525;&#x1f525;文章专题&#xff…...

LVS集群实现四层负载均衡详解(以nat,dr模式为例)

目录 一、LVS集群的介绍 1、LVS 相关术语&#xff1a; 2、lvs四层负载均衡工作原理 3、相关名词概念 4、lvs集群的类型 二、lvs的nat模式 1、介绍&#xff1a; 2、数据逻辑&#xff1a; 3、nat实验部署 环境搭建&#xff1a; 1、lvs中要去打开内核路由功能&#xff0c…...

七夕表白网页效果实现与解析

七夕是中国传统的情人节&#xff0c;是一个充满浪漫与爱的节日。在这个特别的日子里&#xff0c;用代码来表达心意也是一种独特且有趣的方式。本篇文章将带你一步步实现一个简单但充满心意的七夕表白网页。通过使用HTML、CSS和少量的JavaScript&#xff0c;我们将创建一个包含跳…...

人工智能算法工程师(高级)课程11-自然语言处理之NLP的语言模型-seq2seq模型,seq+注意力与代码详解

大家好,我是微学AI,今天给大家介绍一下人工智能算法工程师(高级)课程11-自然语言处理之NLP的语言模型-seq2seq模型,seq+注意力,word2vec与代码详解。本课程面向高级人工智能算法工程师,深入讲解自然语言处理(NLP)中的关键语言模型技术,包括seq2seq模型及其增强版加入注意力…...

从PyTorch官方的一篇教程说开去(6.2 - 张量 tensor 矩阵运算等)

您的进步和反馈是我写作最大的动力&#xff0c;小伙伴来个三连呗&#xff01;共勉~ 话不多说&#xff0c;书接上文&#xff0c;需要温习的小伙伴请移步 - 从PyTorch官方的一篇教程说开去&#xff08;6.1 - 张量 tensor 基本操作&#xff09;-CSDN博客 借图镇楼 - 1 - 矩阵乘…...

【网络层】直连路由、静态路由、动态路由

文章目录 路由表直连路由直连路由 技术背景直连路由 实战训练 静态路由静态路由 技术背景静态路由 概述静态路由 配置命令静态路由 实战训练 动态路由动态路由 技术背景路由协议概述路由协议分类 路由表 路由表的形成&#xff0c;路由的来源&#xff1a; 路由来源备注直连路由…...

tkinter用法总结

Tkinter 是 Python 标准库中的一个模块&#xff0c;用于创建图形用户界面 (GUI)。它是 Python 中最常用的 GUI 库之一&#xff0c;因为它集成在 Python 的标准发行版中&#xff0c;无需额外安装即可使用。 一、基本用法 1. 简单示例 import tkinter as tk# 创建主窗口 root …...

iOS基础-Block

系列文章目录 文章目录 系列文章目录一、Block是什么二、Block的使用场景1. 异步操作和完成处理器2. 动画3. 集合操作4. 定时器5. 自定义控件的事件处理6.错误处理 三、Block的底层实现1.结构分析2.Block的类型3.Block的copy4.变量捕捉 四、Block的使用细节1.auto变量的生命周期…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...