【数据结构】链表（2）：双向链表和双向循环链表

双向链表（Doubly Linked List）

定义：
每个节点包含三个部分：

  1. 数据域。
  2. 前驱指针域（指向前一个节点）。
  3. 后继指针域（指向下一个节点）。

支持从任意节点向前或向后遍历。

#define datatype int
typedef struct link{datatype data;struct link* next;  //该指针保存的后继结点的地址struct link* prev;  //该指针保存的前驱结点的地址 
}link_t;

双向链表的特点：

  • 双向遍历更灵活，插入和删除操作更高效。
  • 占用更多内存（每个节点需存储两个指针）。
1> 初始化link_init
void link_init(link_t **p)
{//申请堆 *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return;}(*p)->prev = NULL;(*p)->next = NULL;
}
2> 创建结点create_node
static link_t *create_node(datatype d)
{//1>向堆空间申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//2>赋值  p->data = d;p->next = NULL;   p->prev = NULL;return p;
}
3> 插入函数insert_behind
//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{//遵循先连后断 a->next = b->next; a->prev = b;if(b->next != NULL)b->next->prev = a;b->next = a;
}

在这里插入图片描述

4> 头插函数link_insert_head
void link_insert_head(link_t *p,datatype data)
{//创建结点link_t * node = create_node(data);if(NULL == node){perror("create_node");return;}//将node插到p后面insert_behind(node,p);
}
5> 尾插函数link_insert_tail
void link_insert_tail(link_t *p,datatype data)
{//创建结点link_t * node = create_node(data);if(NULL == node){perror("create_node");return;}//遍历找到尾结点while(p->next != NULL)p = p->next;//将node插到尾结点p后面insert_behind(node,p);
}
6> 正序遍历display
void display(link_t *p)
{printf("正序遍历结果为：\n");while(p->next != NULL){p = p->next;       printf("%d ",p->data);}printf("\n");
}
7> 逆序遍历dispaly_reverse
void dispaly_reverse(link_t *p)
{printf("逆序遍历结果为：\n");while(p->next != NULL){p = p->next;       }//往前遍历while(p->prev != NULL){printf("%d ",p->data);p = p->prev;}printf("\n");  
}
8> 删除函数link_del
void link_del(link_t *p,datatype data)
{link_t *node =NULL;//遍历 while(p->next != NULL){//数据对比if(p->next->data == data){//使要删除的结点的前后结点建立联系node = p->next; p->next = node->next;if(p->next != NULL)p->next->prev = p;//释放结点node->next = NULL;node->prev = NULL;free(node);continue;}  p = p->next;  } 
}
9> 替换函数link_replace
void link_replace(link_t *p,datatype old,datatype new)
{link_t *new_node = NULL;link_t *old_node = NULL;//遍历 while(p->next != NULL) {if(p->next->data == old){new_node = create_node(new);if(NULL == new_node){perror("create_node");return;}//替换 old_node = p->next;new_node->prev = p;new_node->next = old_node->next;if(old_node->next != NULL)old_node->next->prev = new_node;p->next = new_node;//释放old_node->next = NULL;old_node->prev = NULL;free(old_node);continue;}p = p->next;  //没找到对于数据才会移动}    
}

在这里插入图片描述

双向循环链表（Doubly Circular Linked List）

定义：

  1. 双向链表的变体，首尾相连，形成循环。
  2. 每个节点的前驱指针指向前一个节点，后继指针指向下一个节点。

双向循环链表的特点：

  • 支持双向循环遍历。
  • 节点链接更紧密，占用更多内存。

代码包含链表的创建、节点插入、节点删除、以及正向和反向遍历、打印等功能：

1> 初始化link_init
void link_init(link_t **p)
{//申请堆 *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return;}/*修改处*/ //自己指向自己(*p)->prev = (*p);(*p)->next = (*p);
}
2> 创建结点create_node
static link_t *create_node(datatype d)
{//1>向堆空间申请link_t *p = (link_t *)malloc(sizeof(link_t));if(NULL == p){perror("malloc");return NULL;}//2>赋值  /*修改处*/ p->data = d;p->next = p;   p->prev = p;return p;
}
3> 插入函数insert_behind
//将一个结点(a)插到另一个结点(b)的后面
static void insert_behind(link_t *a,link_t *b)
{//遵循先连后断  /*修改处*/a->next = b->next; a->prev = b;b->next->prev = a;b->next = a;
}
4> 头插函数link_insert_head
void link_insert_head(link_t *p,datatype data)
{//创建结点link_t * node = create_node(data);if(NULL == node){perror("create_node");return;}//将node插到p后面insert_behind(node,p);
}
5> 尾插函数link_insert_tail
void link_insert_tail(link_t *p,datatype data)
{//创建结点link_t * node = create_node(data);if(NULL == node){perror("create_node");return;}//将node插到头结点前面 /*修改处*/insert_forward(node,p);
}
5.5> 插入到头前函数insert_forward
static void insert_forward(link_t *node,link_t *p)
{//先连后断  //尾结点地址用头节点去表示node->next = p;node->prev = p->prev;p->prev->next = node;p->prev = node;
}
6> 正序遍历display
void display(link_t *p)
{/*修改处*/link_t *head = p;printf("正序遍历结果为：\n");while(p->next != head) /*修改处*/{p = p->next;       printf("%d ",p->data);}printf("\n");
}
7> 逆序遍历dispaly_reverse
void dispaly_reverse(link_t *p)
{/*修改处*/link_t *head = p;printf("逆序遍历结果为：\n");//往前遍历 /*修改处*/while(p->prev != head){p = p->prev;printf("%d ",p->data);}printf("\n");  
}
8> 删除函数link_del
void link_del(link_t *p,datatype data)
{/*修改处*/link_t *head =p;link_t *node =NULL;//遍历 while(p->next != head){//数据对比if(p->next->data == data){//使要删除的结点的前后结点建立联系 /*修改处*/node = p->next; p->next = node->next;p->next->prev = p;//释放结点 /*修改处*/node->next = node;node->prev = node;free(node);continue;}  p = p->next;  } 
}
9> 替换函数link_replace
void link_replace(link_t *p,datatype old,datatype new)
{/*修改处*/link_t *head = p;link_t *new_node = NULL;link_t *old_node = NULL;//遍历 while(p->next != head)  /*修改处*/{if(p->next->data == old){new_node = create_node(new);if(NULL == new_node){perror("create_node");return;}//替换  /*修改处*/old_node = p->next;new_node->prev = p;new_node->next = old_node->next;old_node->next->prev = new_node;p->next = new_node;//释放  /*修改处*/old_node->next = old_node;old_node->prev = old_node;free(old_node);continue;}p = p->next;  //没找到对于数据才会移动}    
}
一段完整的代码片
#include <stdio.h>
#include <stdlib.h>// 定义节点结构
typedef struct Node {int data;               // 数据域struct Node* next;      // 指向下一个节点struct Node* prev;      // 指向前一个节点
} Node;// 创建一个新节点
Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;newNode->prev = NULL;return newNode;
}// 插入节点到链表末尾
void append(Node** head, int data) {Node* newNode = createNode(data);// 如果链表为空if (*head == NULL) {*head = newNode;newNode->next = newNode; // 自己指向自己（形成循环）newNode->prev = newNode;return;}// 查找到链表的最后一个节点Node* tail = (*head)->prev;// 更新新节点的指针newNode->next = *head;      // 新节点的 next 指向头节点newNode->prev = tail;       // 新节点的 prev 指向尾节点// 更新头节点和尾节点的指针tail->next = newNode;       // 尾节点的 next 指向新节点(*head)->prev = newNode;    // 头节点的 prev 指向新节点
}// 删除链表中的指定节点
void deleteNode(Node** head, int key) {if (*head == NULL) return;  // 链表为空，直接返回Node* current = *head;      // 从头节点开始查找Node* temp = NULL;// 遍历链表找到值为 key 的节点do {if (current->data == key) {temp = current;break;}current = current->next;} while (current != *head); // 回到头节点时终止循环if (temp == NULL) {printf("节点 %d 未找到。\n", key);return;}// 如果链表中只有一个节点if (temp->next == temp && temp->prev == temp) {*head = NULL; // 删除唯一节点后链表为空free(temp);return;}// 更新前驱和后继节点的指针temp->prev->next = temp->next;temp->next->prev = temp->prev;// 如果删除的是头节点，更新头指针if (temp == *head) {*head = temp->next;}free(temp); // 释放删除的节点
}// 正向遍历链表
void printListForward(Node* head) {if (head == NULL) {printf("链表为空。\n");return;}Node* temp = head;printf("正向遍历链表：");do {printf("%d -> ", temp->data);temp = temp->next;} while (temp != head); // 回到头节点时终止printf("(head)\n");
}// 反向遍历链表
void printListBackward(Node* head) {if (head == NULL) {printf("链表为空。\n");return;}Node* tail = head->prev; // 从尾节点开始Node* temp = tail;printf("反向遍历链表：");do {printf("%d -> ", temp->data);temp = temp->prev;} while (temp != tail); // 回到尾节点时终止printf("(tail)\n");
}// 主函数
int main() {Node* head = NULL; // 初始化空链表// 添加节点append(&head, 10);append(&head, 20);append(&head, 30);append(&head, 40);// 打印链表printListForward(head);printListBackward(head);// 删除节点printf("删除节点 20：\n");deleteNode(&head, 20);printListForward(head);printListBackward(head);// 删除节点 10（头节点）printf("删除节点 10：\n");deleteNode(&head, 10);printListForward(head);printListBackward(head);return 0;
}
完整代码片 分析：
  1. 结构定义：
    • 每个节点结构包含：
      • data：存储节点数据。
      • next：指向下一个节点。
      • prev：指向前一个节点。
  2. append 函数：
    • 用于在链表末尾插入新节点。
    • 维护双向循环链表的特性：更新新节点、头节点和尾节点的指针。
  3. deleteNode 函数：
    • 在链表中查找值等于key的节点并删除。
    • 特别处理了链表为空、只有一个节点、删除头节点等特殊情况。
  4. 遍历函数：
    • printListForward：正向遍历，从头节点出发，依次打印每个节点。
    • printListBackward：反向遍历，从尾节点出发，依次打印每个节点。
  5. 主函数测试：
    • 插入多个节点。
    • 正向和反向打印链表。
    • 删除指定节点，并再次验证。

双向循环链表运行结果示例：

正向遍历链表：10 -> 20 -> 30 -> 40 -> (head)
反向遍历链表：40 -> 30 -> 20 -> 10 -> (tail)删除节点 20：
正向遍历链表：10 -> 30 -> 40 -> (head)
反向遍历链表：40 -> 30 -> 10 -> (tail)删除节点 10：
正向遍历链表：30 -> 40 -> (head)
反向遍历链表：40 -> 30 -> (tail)

双向循环链表提供了灵活的正向和反向遍历功能，同时保持循环特性，适合需要频繁插入、删除并支持循环操作的场景。代码实现中考虑了各种边界条件（如链表为空、只有一个节点等），确保程序安全性。

综上。希望该内容能对你有帮助，感谢！

以上。仅供学习与分享交流，请勿用于商业用途！转载需提前说明。

我是一个十分热爱技术的程序员，希望这篇文章能够对您有帮助，也希望认识更多热爱程序开发的小伙伴。
感谢！

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

RK3588+麒麟国产系统+FPGA+AI在电力和轨道交通视觉与采集系统的应用

RK3588+麒麟国产系统+FPGA+AI在电力和轨道交通视觉与采集系统的应用

工业视觉识别系统厂家提供的功能主要包括&#xff1a; 这些厂家通过先进的视觉识别技术&#xff0c;实现图像的采集、处理与分析。系统能够自动化地完成质量检测、物料分拣、设备监控等任务&#xff0c;显著提升生产效率和产品质量。同时&#xff0c;系统具备高度的灵活性和可扩…
阅读更多...
3 抢红包系统

3 抢红包系统

我们还是按照我们分析问题的方法论开展 一 场景分析 我们分析的是集体活动的抢红包&#xff0c;比如春晚&#xff0c;大型活动红包&#xff0c;需要在网页操作的抢红包 抢红包的问题也是多个人抢资源的问题&#xff0c;可以和秒杀进行比对。但是也有很多不同的地方。 用户打…
阅读更多...
数据库中的并发控制

数据库中的并发控制

并发操作带来的数据不一致性 1、并发控制:为了保证事务的隔离性和一致性&#xff0c;数据库管理系统需要对并发操作进行正确调度 并发控制的主要技术有:封锁、时间戳、乐观控制法、多版本并发控制等 并发操作带来的数据不一致性: ① 丟失修改:两个事务 T1 和 T2 读入同一数据…
阅读更多...
ArcGIS Server 10.2授权文件过期处理

ArcGIS Server 10.2授权文件过期处理

新的一年&#xff0c;arcgis server授权过期了&#xff0c;服务发不不了。查看ecp授权文件&#xff0c;原来的授权日期就到2024.12.31日。好吧&#xff0c;这里直接给出处理方法。 ArcGIS 10.2安装时&#xff0c;有的破解文件中会有含一个这样的注册程序&#xff0c;没有的话&…
阅读更多...
学英语学压测：02jmeter组件-测试计划和线程组ramp-up参数的作用

学英语学压测：02jmeter组件-测试计划和线程组ramp-up参数的作用

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#xff1a;先看关键单词&#xff0c;再看英文&#xff0c;最后看中文总结&#xff0c;再回头看一遍英文原文&#xff0c;效果更佳&#xff01;&#xff01; 关键词 Functional Testing功能测试[ˈfʌŋkʃənəl ˈtɛstɪŋ]Sample样…
阅读更多...
MCGS学习记录

MCGS学习记录

软件包 用户窗口 主窗口 元件&#xff1a;工具箱->输入框上面 数据对象 在工作台的实时数据库可以新增数据对象 理解为中间变量&#xff0c;控件改变其值&#xff0c;控件监测其值做出变化 基本属性 设定变量名和初始值 指针化&#xff1f; 变化时自动保存初始值&#x…
阅读更多...
【网络协议】IPv4 地址分配 - 第一部分

【网络协议】IPv4 地址分配 - 第一部分

文章目录 十进制与二进制网络如何被寻址地址类型网络地址广播地址主机地址 如何确定网络和主机部分的位数&#xff1f;网络中的主机数量与前缀号的关系计算每个前缀的主机数量公式 子网掩码二进制与操作&#xff08;Binary ANDing&#xff09;与操作&#xff08;AND Operation&…
阅读更多...
数据挖掘——集成学习

数据挖掘——集成学习

数据挖掘——集成学习 集成学习Bagging&#xff1a;有放回采样随机森林 BoostingStacking 集成学习 集成学习&#xff08;Ensemble learning&#xff09;方法通过组合多种学习算法来获得比单独使用任何一种算法更好的预测性能。 动机是为了提高但分类器的性能 Bagging&…
阅读更多...
ansible-性能优化

ansible-性能优化

一. 简述&#xff1a; 搞过运维自动化工具的人&#xff0c;肯定会发现很多运维伙伴们经常用saltstack和ansible做比较&#xff0c;单从执行效率上来说&#xff0c;ansible确实比不上saltstack(ansible使用的是ssh,salt使用的是zeromq消息队列[暂没深入了解])&#xff0c;但其实…
阅读更多...
NLP CH10 问答系统复习

NLP CH10 问答系统复习

1. 专家系统 特点 问题聚焦&#xff1a;限定在特定领域。数据结构化&#xff1a;使用结构化的领域知识。数据库支持&#xff1a;后台有一个数据库&#xff0c;保存系统可提供的各种数据。查询机制&#xff1a;用户提问时&#xff0c;系统将问题转换为 SQL 查询语句&#xff0…
阅读更多...
vite6+vue3+ts+prettier+eslint9配置前端项目（后台管理系统、移动端H5项目通用配置）

vite6+vue3+ts+prettier+eslint9配置前端项目（后台管理系统、移动端H5项目通用配置）

很多小伙伴苦于无法搭建一个规范的前端项目&#xff0c;导致后续开发不规范&#xff0c;今天给大家带来一个基于Vite6TypeScriptVue3ESlint9Prettier的搭建教程。 目录 一、基础配置1、初始化项目2、代码质量风格的统一2.1、配置prettier2.2、配置eslint2.3、配置typescript 3、…
阅读更多...
【2025年最新】OpenWrt 更换国内源的指南（图形界面版)

【2025年最新】OpenWrt 更换国内源的指南（图形界面版)

在上一篇文章中我们讲解了如何使用命令行更换国内源&#xff0c;如果你没有终端工具&#xff0c;或者不喜欢命令行&#xff0c;那么图形界面方式将会是更简单有效的方式。 命令行版本&#xff1a;【2025年最新】OpenWrt 更换国内源的指南(命令行)-CSDN博客 为什么选择通过图形…
阅读更多...
uni-app:实现普通选择器，时间选择器，日期选择器，多列选择器

uni-app:实现普通选择器，时间选择器，日期选择器，多列选择器

效果 选择前效果 1、时间选择器 2、日期选择器 3、普通选择器 4、多列选择器 选择后效果 代码 <template><!-- 时间选择器 --><view class"line"><view classitem1><view classleft>时间</view><view class"right&quo…
阅读更多...
NVIDIA DLI课程《NVIDIA NIM入门》——学习笔记

NVIDIA DLI课程《NVIDIA NIM入门》——学习笔记

先看老师给的资料&#xff1a; NVIDIA NIM是 NVIDIA AI Enterprise 的一部分&#xff0c;是一套易于使用的预构建容器工具&#xff0c;目的是帮助企业客户在云、数据中心和工作站上安全、可靠地部署高性能的 AI 模型推理。这些预构建的容器支持从开源社区模型到 NVIDIA AI 基础…
阅读更多...
深度学习中的步数指的是什么

深度学习中的步数指的是什么

Lora微调的截图如下: 在深度学习中，步数（steps） 是指模型参数更新的次数。每次参数更新通常对应一个或多个批次的梯度计算和优化器更新。以下是计算总步数的方法以及步数的具体含义： 1. 步数的计算公式 总步数（Total Optimization Steps）可以通过以下公式计算： [ \te…
阅读更多...
【可实战】测试用例组成、用例设计方法、用例编写步骤、测试用例粒度、用例评审（包含常见面试题）

【可实战】测试用例组成、用例设计方法、用例编写步骤、测试用例粒度、用例评审（包含常见面试题）

一、测试用例组成 &#xff08;一&#xff09;测试用例的组成 用例编号&#xff0c;模块&#xff0c;测试点&#xff08;测试标题&#xff09;&#xff0c;优先级&#xff0c;前提条件&#xff0c;测试步骤&#xff0c;期望结构&#xff0c;实际结果并不是每一项都必须&#…
阅读更多...
Redis两种主要的持久化方式是什么？

Redis两种主要的持久化方式是什么？

Redis支持两种主要的持久化方式&#xff0c;它们分别是RDB&#xff08;Redis Database Snapshotting&#xff09;和AOF&#xff08;Append Only File&#xff09;。以下是这两种持久化方式的详细介绍&#xff1a; 一、RDB&#xff08;Redis Database Snapshotting&#xff09; …
阅读更多...
【强化学习】演员评论家Actor-Critic算法(万字长文、附代码)

【强化学习】演员评论家Actor-Critic算法(万字长文、附代码)

&#x1f4e2;本篇文章是博主强化学习&#xff08;RL&#xff09;领域学习时&#xff0c;用于个人学习、研究或者欣赏使用&#xff0c;并基于博主对相关等领域的一些理解而记录的学习摘录和笔记&#xff0c;若有不当和侵权之处&#xff0c;指出后将会立即改正&#xff0c;还望谅…
阅读更多...
《新概念模拟电路》-电流源电路

《新概念模拟电路》-电流源电路

电流源电路 本系列文章主要学习《新概念模拟电路》中的知识点。在工作过程中&#xff0c;碰到一些问题&#xff0c;于是又翻阅了模电这本书。我翻阅的是ADI出版的&#xff0c;西安交通大学电工中心杨建国老师编写的模电书。 本文主要是基于前文《新概念模拟电路》-三极管的基础…
阅读更多...
Linux下编译安装PETSc

Linux下编译安装PETSc

本文记录在Linux下编译安装PETSc的流程。 零、环境 操作系统Ubuntu 22.04.4 LTSVS Code1.92.1Git2.34.1GCC11.4.0CMake3.22.1oneAPI2024.2.1 一、安装依赖 1.1 安装oneAPI 参见&#xff1a;Get the Intel oneAPI Base Toolkit , Get the Intel oneAPI HPC Toolkit 1.2 安…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023