当前位置: 首页 > 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变量的生命周期…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...