双向链表的操作函数

DouLink.c
#include "DouLink.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** @brief 创建一个空的双向链表* * 动态分配双向链表管理结构的内存,并初始化头指针和节点计数* * @return 成功返回指向新链表的指针,失败返回NULL*/
DouLinkList *CreateDouLinkList()
{// 为链表管理结构分配内存DouLinkList *dl = malloc(sizeof(DouLinkList));if (NULL == dl){perror("CreateDouLinkList malloc");  // 分配失败时输出错误信息return NULL;}dl->head = NULL;  // 初始化头指针为空(空链表)dl->clen = 0;     // 初始化节点计数为0return dl;
}/*** @brief 在双向链表头部插入新节点* * 动态创建新节点,将数据存入节点并插入到链表头部* * @param dl 指向双向链表的指针* @param data 指向要插入的数据的指针* @return 成功返回0,失败返回1*/
int InsertHeadDouLinkList(DouLinkList *dl, DATATYPE *data)
{// 为新节点分配内存DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertHeadDouLinkList malloc\n");  // 分配失败时输出错误信息return 1;}// 复制数据到新节点memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;  // 初始化新节点的后继指针newnode->prev = NULL;  // 初始化新节点的前驱指针// 如果链表为空,直接将新节点作为头节点if (IsEmptyDouLinkList(dl)){dl->head = newnode;}// 否则将新节点插入到头部else{newnode->next = dl->head;       // 新节点的后继指向原头节点dl->head->prev = newnode;       // 原头节点的前驱指向新节点dl->head = newnode;             // 更新头指针为新节点}dl->clen++;  // 节点计数加1return 0;
}/*** @brief 在双向链表尾部插入新节点* * 动态创建新节点,将数据存入节点并插入到链表尾部* * @param dl 指向双向链表的指针* @param data 指向要插入的数据的指针* @return 成功返回0,失败返回1*/
int InsertTailDouLinkList(DouLinkList *dl, DATATYPE *data)
{// 如果链表为空,直接调用头部插入函数if (IsEmptyDouLinkList(dl)){return InsertHeadDouLinkList(dl, data);}// 否则在尾部插入else{// 为新节点分配内存DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertTailDouLinkList malloc\n");  // 分配失败时输出错误信息return 1;}// 复制数据到新节点memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;  // 新节点的后继为空(作为尾节点)newnode->prev = NULL;  // 初始化前驱指针// 找到当前尾节点DouLinkNode *tmp = dl->head;while (tmp->next)  // 遍历到最后一个节点{tmp = tmp->next;}// 将新节点链接到尾节点后newnode->prev = tmp;  // 新节点的前驱指向原尾节点tmp->next = newnode;  // 原尾节点的后继指向新节点}dl->clen++;  // 节点计数加1return 0;
}/*** @brief 在双向链表指定位置插入新节点* * 在链表的指定索引位置插入新节点,索引从0开始* * @param dl 指向双向链表的指针* @param data 指向要插入的数据的指针* @param pos 插入位置的索引* @return 成功返回0,失败返回1*/
int InsertPosDouLinkList(DouLinkList *dl, DATATYPE *data, int pos)
{int size = GetSizeDouLinkList(dl);// 检查位置是否合法if (pos < 0 || pos > size){printf("InsertPosDouLinkList pos error\n");return 1;}// 位置0等同于头部插入if (0 == pos){return InsertHeadDouLinkList(dl, data);}// 位置等于链表长度等同于尾部插入else if (size == pos){return InsertTailDouLinkList(dl, data);}// 中间位置插入else{// 为新节点分配内存,注意只能再此处为该新节点的分配内存,(因为如果上面的条件符合,调用头插或尾插函数时就会有分配内存这一操作,如果一开始就为该新节点分配内存可能会导致段错误)DouLinkNode *newnode = malloc(sizeof(DouLinkNode));if (NULL == newnode){perror("InsertPosDouLinkList malloc\n");  // 分配失败时输出错误信息return 1;}// 复制数据到新节点memcpy(&newnode->data, data, sizeof(DATATYPE));newnode->next = NULL;newnode->prev = NULL;// 找到要插入位置的节点DouLinkNode *tmp = dl->head;while (pos--)  // 移动到目标位置{tmp = tmp->next;}// 插入新节点newnode->next = tmp;            // 新节点的后继指向当前节点newnode->prev = tmp->prev;      // 新节点的前驱指向当前节点的前驱tmp->prev = newnode;            // 当前节点的前驱指向新节点newnode->prev->next = newnode;  // 当前节点原前驱的后继指向新节点}dl->clen++;  // 节点计数加1return 0;
}/*** @brief 显示双向链表中的所有节点数据* * 可以按照正向或反向遍历并打印链表中的所有数据* * @param dl 指向双向链表的指针* @param direct 遍历方向(正向或反向)* @return 成功返回0*/
int ShowDouLinkList(DouLinkList *dl, DIRECT direct)
{DouLinkNode *tmp = dl->head;// 正向遍历(从头部到尾部)if (DIR_FORWARD == direct){while (tmp)  // 遍历所有节点{// 打印节点数据printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);tmp = tmp->next;  // 移动到下一个节点}}// 反向遍历(从尾部到头部)else{// 先移动到尾节点while (tmp->next){tmp = tmp->next;}// 从尾节点遍历到头部while (tmp){// 打印节点数据printf("name:%s sex:%c age:%d score:%d\n", tmp->data.name, tmp->data.sex, tmp->data.age, tmp->data.score);tmp = tmp->prev;  // 移动到前一个节点}}return 0;
}/*** @brief 判断双向链表是否为空* * @param dl 指向双向链表的指针* @return 链表为空返回1,不为空返回0*/
int IsEmptyDouLinkList(DouLinkList *dl)
{return 0 == dl->clen;  // 通过节点计数判断是否为空
}/*** @brief 按姓名查找双向链表中的节点(旧版实现,通过姓名直接匹配,可与函数指针回调版对比)* * 遍历双向链表,逐个对比节点中存储的姓名与传入的目标姓名,找到则返回对应节点指针,用于简单的按姓名精准查找场景。* 若后续有多样化查找需求(比如按年龄、分数等),更推荐用函数指针回调的通用查找方式( FindDouLinkList 函数)。* * @param dl 指向要操作的双向链表管理结构的指针,通过它能访问链表头节点,进而遍历整个链表* @param name 要查找的目标姓名,以字符串形式传入,用于和链表节点中存储的姓名做对比* @return 找到匹配姓名的节点时,返回该节点的指针;遍历完链表未找到时,返回 NULL */
DouLinkNode *FindDouLinkList(DouLinkList *dl, char *name)
{DouLinkNode* tmp = dl->head;  // 从链表头节点开始遍历while (tmp)  // 只要当前节点指针不为空,就持续遍历{// 调用 strcmp 函数对比当前节点姓名和目标姓名,strcmp 返回 0 表示字符串相等if (0 == strcmp(tmp->data.name, name))  {return tmp;  // 找到匹配姓名的节点,返回该节点指针}tmp = tmp->next;  // 移动到下一个节点,继续遍历}return NULL;  // 遍历完所有节点都没找到匹配姓名的,返回 NULL
}/*** @brief 在双向链表中查找符合条件的节点* * 使用回调函数作为匹配条件,实现灵活的查找功能* * @param dl 指向双向链表的指针* @param fun 回调函数指针,用于判断节点是否符合条件* @param arg 传递给回调函数的参数,作为查找条件* @return 找到返回匹配节点的指针,未找到返回NULL*/
DouLinkNode *FindDouLinkList(DouLinkList *dl, PFUN fun, void *arg)
{DouLinkNode *tmp = dl->head;  // 从头部开始遍历while (tmp)  // 遍历所有节点{// 调用回调函数判断当前节点是否符合条件if (fun(&tmp->data, arg)){return tmp;  // 找到匹配节点,返回该节点指针}tmp = tmp->next;  // 移动到下一个节点}return NULL;  // 未找到匹配节点
}/*** @brief 反转双向链表* * 将双向链表的节点顺序反转,改变节点间的链接关系* * @param dl 指向双向链表的指针* @return 成功返回0,无需反转返回1*/
int ReverseDouLinkList(DouLinkList *dl)
{int size = GetSizeDouLinkList(dl);// 节点数小于2时无需反转if (size < 2){printf("No need to reverse (size < 2)\n");return 1;}DouLinkNode *cur = dl->head;  // 当前节点指针,从头部开始DouLinkNode *Prev = NULL;     // 保存前一个节点的指针while (cur != NULL){  DouLinkNode *tmp = cur->next;  // 保存下一个节点,防止断链cur->next = Prev;              // 反转当前节点的后继指针,指向前一个节点cur->prev = tmp;               // 反转当前节点的前驱指针,指向后一个节点Prev = cur;                    // 更新前一个节点指针cur = tmp;                     // 移动到下一个节点}dl->head = Prev;  // 反转后,原尾节点成为新的头节点return 0;
}/*** @brief 获取双向链表的节点数量* * @param dl 指向双向链表的指针* @return 返回链表中的节点数量*/
int GetSizeDouLinkList(DouLinkList *dl)
{return dl->clen;  // 直接返回节点计数值
}/*** @brief 修改双向链表中符合条件的节点数据* @param dl 双向链表的指针* @param fun 比较函数指针,用于查找目标节点* @param arg 传给比较函数的参数(用于指定查找条件)* @param newdata 指向新数据的指针,将用此数据替换找到节点的数据* @return 0表示修改成功,1表示修改失败(未找到节点)*/
int ModifyDouLinkList(DouLinkList *dl, PFUN fun, void *arg, DATATYPE *newdata)
{// 调用查找函数,根据fun和arg找到目标节点DouLinkNode *tmp = FindDouLinkList(dl, fun, arg);// 若未找到目标节点,打印错误信息并返回失败if (NULL == tmp){printf("ModifyDouLinkList failure failure\n");return 1;}// 将新数据拷贝到找到的节点中(覆盖原有数据)// 使用memcpy确保结构体所有成员都被正确替换memcpy(&tmp->data, newdata, sizeof(DATATYPE));// 修改成功,返回0return 0;
}/*** @brief 从双向链表中删除符合条件的节点* @param dl 双向链表的指针* @param fun 比较函数指针,用于查找目标节点* @param arg 传给比较函数的参数(用于指定查找条件)* @return 0表示删除成功,1表示删除失败(未找到节点)*/
int DeleteDouLinkList(DouLinkList *dl, PFUN fun, void *arg)
{// 调用查找函数,根据fun和arg找到目标节点DouLinkNode *tmp = FindDouLinkList(dl, fun, arg);// 若未找到目标节点,打印错误信息并返回失败if (NULL == tmp){printf("del failure\n");return 1;}// 情况1:删除的是头节点if (tmp == dl->head){// 将头指针指向原头节点的下一个节点dl->head = dl->head->next;// 若新头节点存在,需要将其prev指针置为NULL(断开与原头节点的联系)if (dl->head){dl->head->prev = NULL;}}// 情况2:删除的是中间节点或尾节点else{// 若当前节点不是尾节点,需要将下一个节点的prev指向当前节点的前一个节点if (tmp->next){tmp->next->prev = tmp->prev;}// 将当前节点前一个节点的next指向当前节点的下一个节点tmp->prev->next = tmp->next;}// 释放被删除节点的内存,避免内存泄漏free(tmp);// 链表长度减1dl->clen--;// 删除成功,返回0return 0;
}/*** @brief 销毁整个双向链表,释放所有分配的内存* @param dl 双向链表的指针* @return 0表示销毁成功*/
int DestroyDouLinkList(DouLinkList *dl)
{DouLinkNode *tmp = NULL;// 循环删除链表中的所有节点while (1){// 每次获取当前头节点tmp = dl->head;// 若头节点为NULL,说明所有节点已删除,退出循环if (NULL == tmp){break;}// 将头指针移动到下一个节点dl->head = dl->head->next;// 释放当前头节点的内存free(tmp);}// 释放链表结构体本身的内存free(dl);// 销毁成功,返回0return 0;
}

双向链表特点

双向链表(Doubly Linked List)是一种更复杂的链表,它的每个节点不仅包含指向下一个节点的指针(next),还包含指向前一个节点的指针(prev)。

  1. 双向遍历

    • 核心特点:可以从头节点开始向后遍历,也可以从尾节点开始向前遍历。这是其与单向链表最根本的区别。

  2. 节点结构

    • 每个节点包含三部分:

      • data: 存储数据。

      • next: 指针,指向下一个节点。

      • prev: 指针,指向前一个节点。

  3. 操作效率(与单向链表对比的核心优势)

    • 删除特定节点:在已知某个节点指针的情况下,双向链表可以在 O(1) 时间内删除该节点,因为它可以直接通过 prev 指针找到前驱节点。而单向链表需要从头遍历才能找到前驱节点,时间复杂度为 O(n)。

    • 在特定节点前插入:同样,在已知某个节点指针的情况下,双向链表可以在 O(1) 时间内完成在其前面的插入操作。单向链表无法直接做到,仍需遍历寻找前驱节点。

    • 反向遍历:需要反向遍历链表(例如,从大到小输出一个有序链表)时,双向链表非常高效。单向链表则非常笨拙,通常需要借助栈等辅助数据结构,或者先反转链表(这会修改原链表)。

  4. 缺点

    • 内存开销:每个节点都需要一个额外的指针来存储前驱节点的地址。对于节点数据本身很小的链表(例如,只存储一个整数),这个额外的指针开销占比会很大。

    • 操作复杂性:插入和删除节点时,需要维护两个方向的指针(next 和 prev),共需要修改 4 个指针(在某些边界情况下是 2 个)。而单向链表只需要修改 1 或 2 个指针。代码实现上更复杂,容易出错。


与单向链表的对比

特性单向链表 (Singly Linked List)双向链表 (Doubly Linked List)
节点结构datanextdatanextprev
遍历方向只能从头到尾单向遍历可以双向遍历(从头到尾或从尾到头)
内存占用更小(每个节点少一个指针)更大(每个节点多一个指针)
删除操作删除已知节点的前驱节点很高效 (O(1))
删除已知节点本身需要找前驱,效率低 (O(n))
删除已知节点本身非常高效 (O(1))
插入操作只能在已知节点后插入 (O(1))
在已知节点前插入需要找前驱,效率低 (O(n))
在已知节点前或后插入都非常高效 (O(1))
灵活性较低很高,前后移动都很方便
代码复杂度相对简单相对复杂,需要维护前后指针的完整性

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/94250.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/94250.shtml
英文地址,请注明出处:http://en.pswp.cn/bicheng/94250.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Wireshark获取数据传输的码元速率

一、Wireshark的物理层参数 Wireshark主界面可以看到数据发送时刻和长度&#xff1a; 这个时刻是Wireshark完整获取数据包的时刻&#xff0c;实际上就是结束时刻。 需要知道的是&#xff1a; Wireshark工作在数据链路层及以上&#xff0c;它能解码 以太网帧 / IP 包 / TCP…

11.1.3 完善注册登录,实现文件上传和展示

1、完善注册/登录 1. 涉及的数据库表单&#xff1a;user_info 2. 引用MySQL线程池&#xff0c;Redis线程池 3. 完善注册功能 4. 完善登录功能 2.1 涉及的数据库表单&#xff1a;user_info 重新创建数据库 #创建数据库 DROP DATABASE IF EXISTS 0voice_tuchuang;CREATE D…

【Linux文件系统】目录结构

有没有刚进入Linux世界时&#xff0c;对着黑乎乎的终端&#xff0c;输入一个 ls / 后&#xff0c;看着蹦出来的一堆名字 like bin, etc, usr&#xff0c;感觉一头雾水&#xff0c;像是在看天书&#xff1f; 别担心&#xff0c;你不是一个人。Linux的文件系统就像一个超级有条理…

螺旋槽曲面方程的数学建模与偏导数求解

螺旋槽曲面的数学描述 在钻头设计和机械加工领域,螺旋槽的几何建模至关重要。螺旋槽通常由径向截形绕轴做螺旋运动形成,其数学模型可通过参数方程和隐函数方程两种方式描述。 设螺旋槽的径向截形方程为: y=f(z)y = f(z)y=f(z) x=xcx = x_cx=xc​ 其中 xcx_cxc​ 为常数,…

线性回归:机器学习中的基石

在机器学习的众多算法中&#xff0c;线性回归无疑是最基础也是最常被提及的一种。它不仅在统计学中占有重要地位&#xff0c;而且在预测分析和数据建模中也发挥着关键作用。本文将深入探讨线性回归的基本概念、评估指标以及在实际问题中的应用&#xff0c;并通过一个模拟的气象…

编程刷题-资料分发1 图论/DFS

P2097 资料分发 1 题目描述 有一些电脑&#xff0c;一部分电脑有双向数据线连接。 如果一个电脑得到数据&#xff0c;它可以传送到的电脑都可以得到数据。 现在&#xff0c;你有这个数据&#xff0c;问你至少将其输入几台电脑&#xff0c;才能使所有电脑得到数据。 输入格式 第…

RabbitMQ:延时消息(死信交换机、延迟消息插件)

目录一、死信交换机【不推荐】二、延迟消息插件【推荐】2.1 安装插件【Linux】2.2 安装插件【Windows】2.3 如何使用延时消息&#xff1a;生产者发送消息时指定一个时间&#xff0c;消费者不会立刻收到消息&#xff0c;而是在指定时间之后才收到消息。 延时任务&#xff1a;设置…

动学学深度学习05-深度学习计算

动学学深度学习pytorch 参考地址&#xff1a;https://zh.d2l.ai/ 文章目录动学学深度学习pytorch1-第05章-深度学习计算1. 层&#xff08;Layer&#xff09;与块&#xff08;Block&#xff09;1.1 什么是深度学习中的“层”&#xff1f;1.2 什么是“块”&#xff08;Block&…

智慧工厂烟雾检测:全场景覆盖与精准防控

智慧工厂烟雾检测&#xff1a;构建工业安全的智能防线&#xff08;所有图片均为真实项目案例&#xff09;在工业4.0时代&#xff0c;智慧工厂通过物联网、人工智能与大数据技术的深度融合&#xff0c;实现了生产流程的数字化与智能化。然而&#xff0c;工厂环境中的火灾隐患始终…

@JsonIgnoreProperties注解详解

JsonIgnoreProperties是 Jackson 库中的一个重要注解&#xff0c;用于在 JSON 序列化&#xff08;对象转 JSON&#xff09;和反序列化&#xff08;JSON 转对象&#xff09;过程中​​控制属性的可见性​​。它提供了更高级别的属性忽略能力&#xff0c;特别适合处理复杂场景。一…

红酒数据集预处理实战:缺失值处理的 5 种打开方式,从入门到进阶一步到位

在数据分析与建模流程中&#xff0c;缺失值处理是数据预处理阶段的关键步骤&#xff0c;直接影响后续模型的准确性与稳定性。本文以红酒数据集为研究对象&#xff0c;详细介绍如何通过基础统计方法&#xff08;均值、中位数、众数&#xff09;、完整案例分析&#xff08;CCA&am…

Node.js 开发 JavaScript SDK 包的完整指南(AI)

一、核心概念SDK 包定义 专为特定服务/平台封装的工具库&#xff0c;提供标准化 API 调用、错误处理、类型声明等功能。示例&#xff1a;支付宝 SDK、AWS SDK、微信小程序 SDK。技术栈选择 语言&#xff1a;JavaScript/TypeScript&#xff08;推荐 TS&#xff0c;便于类型提示&…

Redis实战-基于Session实现分布式登录

1.流程分析1.1发送短信验证码提交手机号的时候要进行校验手机号&#xff0c;校验成功才会去生成验证码&#xff0c;将验证码保存到session&#xff0c;发生他把这部分那。1.2短信验证码登录/注册如果提交手机号和验证码之后&#xff0c;校验一致才进行根据手机号查询用户&#…

疯狂星期四文案网第47天运营日记

网站运营第47天&#xff0c;点击观站&#xff1a; 疯狂星期四 crazy-thursday.com 全网最全的疯狂星期四文案网站 运营报告 今日访问量 今日搜索引擎收录情况 必应现在是边收录边k页面 百度快倒闭 网站优化点 完善工作流&#xff0c;全面实现文案自动化采集&#xff0c;se…

Vue生命周期以及自定义钩子和路由

Vue生命周期常用的onMounted挂载后执行和onUnmounted卸载前以及onupdated更新后实际上用react对比就是useEffect&#xff0c;而且挂载顺序也是子组件先于父组件然后往外的栈结构&#xff0c;先进后出。1.Vue的生命周期<template><h2>当前求和为{{ sum }}</h2>…

探索Thompson Shell:Unix初代Shell的智慧

引言 在计算机科学的漫漫长河中&#xff0c;Thompson Shell 无疑占据着举足轻重的开创性地位&#xff0c;它是 Unix 系统的第一个 shell&#xff0c;诞生于 1971 年&#xff0c;由计算机领域的传奇人物 Ken Thompson 开发。在那个计算机技术刚刚起步、硬件资源极度匮乏的年代&a…

MySQL B+ 树索引详解:从原理到实战优化

引言在现代数据库应用中&#xff0c;查询效率是影响系统性能的关键因素之一。而索引&#xff0c;尤其是 B 树索引&#xff0c;是 MySQL 中最常用、最重要的性能优化手段。正确使用索引可以将查询时间从毫秒级降低到微秒级&#xff0c;极大地提升应用响应速度。1. B 树索引的重要…

计算机内存中的整型存储奥秘、大小端字节序及其判断方法

目录 一、回顾与引入&#xff1a;整数在内存中的存储方式 为什么要采用补码存储&#xff1f; 二、大小端字节序及其判断方法 1、什么是大小端&#xff1f; 2、为什么存在大小端&#xff1f; 3、练习 练习1&#xff1a;简述大小端概念并设计判断程序&#xff08;百度面试…

Redis 最常用的 5 种数据类型

Redis 支持多种灵活的数据类型&#xff0c;每种类型针对特定场景优化。以下是 **Redis 最常用的 5 种数据类型**及其核心特点和应用场景&#xff1a;1. 字符串&#xff08;String&#xff09;描述&#xff1a;最基本的数据类型&#xff0c;可存储文本、数字&#xff08;整数/浮…

【嵌入式】RK3588 对比 NVIDIA Jetson,Radxa Rock 5B vs Orange Pi 5 Max

RK3588这个芯片,适合AI应用么,为什么这么贵呢 AI 边缘盒子里的旗舰芯 深度分析一下 RK3588(瑞芯微 Rockchip RK3588) 为什么被很多人关注在 AI 应用,以及它价格偏高的原因。 🧩 1. RK3588 的基本情况 制程:8nm(Samsung 8nm LP) CPU:8 核 big.LITTLE 架构(4 Cortex-…