数据结构——带头双向循环链表（c语言实现）

目录

 

1.单链表和双向链表对比

2.双向链表实现

2.1 创建新节点

2.2 链表初始化 

2.3 尾插 

2.4 头插 

2.5 尾删 

2.6 头删 

2.7 查找 

2.8 指定位置后插入数据 

2.9 删除指定节点 

2.10 销毁链表

2.11 打印链表 

 前言：

     我们在前几期详细地讲解了不带头单向不循环链表（单链表），使用它的底层代码实现了一个简单的通讯录项目，也介绍了链表分为八种，但是其中最常用的只有两种：（1）不带头单向不循环链表，（2）带头双向循环链表，今天我们要讲解的就是第二种带头双向循环链表

1.单链表和双向链表对比

在介绍双向链表之前，我们先来对比一下单链表和双向链表的区别。

这是单链表：

这是双向链表：

 

        双向链表的特点是每相邻两个节点都相互连接，每个节点都有三个部分，包括data，next，prev，其中data负责存放数据，next负责存放后一个节点的地址，prev负责存放前一个节点的地址，最后一个节点和头节点（哨兵位）相互连接，形成了一个循环双向链表，那么什么是哨兵位呢，哨兵位就是双向链表的头节点，它不存放有效数据，只存放第一个有序数据的节点的地址和最后一个有序数据节点的地址。 

       那么它们的区别是什么呢？

1. 无头单向非循环链表： 结构简单 ，一般不会单独用来存数据。实际中更多是作为 其他数据结构的子结 构 ，如哈希桶、图的邻接表等等。另外这种结构在 笔试面试 中出现很多。
2. 带头双向循环链表： 结构最复杂 ，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。

2.双向链表实现

  介绍完了双向链表的区别我们接下来就要着手开始用代码实现双向链表了。由于代码可能较多，我们将双向链表的代码分成了三个文件，分别是List.h,List.c和tste.c文件：

在list.h文件中，我们要包含我们会用到的头文件，其他文件只要包含List.h文件就可以使用这些头文件了：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

双向链表的实现也是在此文件中，由于我们不知道将来使用链表会存放什么样的数据，所以我们使用typedef对这个数据的类型改名，我们实现链表使用的是int类型，所以我们对int改名：

typedef int ListNodeData;

链表中的next和prev链表是用来存放节点地址的，所以它们为指针类型，而为了方便使用，我们将链表使用typedf改名，下面是双向链表实现：

typedef struct ListNode
{ListNodeData data;struct ListNode* prev;struct ListNode* next;}LTNode;

2.1 创建新节点

创建新节点我们使用malloc从堆申请一块LTNode类型大小的内存，它的data类型用来存放将来要插入的数据，prev和next指针在创建这个节点时先让它指向自己，如果要创建新节点，就调用这个函数，它会返回一个指向这块空间的指针：

LTNode* LTBuyNode(ListNodeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;}//创建一个新节点

2.2 链表初始化 

 

在最初创建一个链表时，它的内部为空，什么也没有，我们初始化应该此链表让它至少有一个哨兵位：

void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);}//初始化

2.3 尾插 

尾插操作应该先创建一个新节点，插入顺序为：先让新节点的prev指针指向最后一个节点，然后让新节点的next指针指向哨兵位实现循环，以上的两步都不会影响旧节点，接下来就是让最后一个节点的next指针指向这个新节点，然后让哨兵位的prev指针指向新节点完成尾插：

具体实现代码为：

void LTPushBack(LTNode* phead, ListNodeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//尾插

2.4 头插 

     头插操作并不是将新节点放在哨兵位之前，而是将新节点放在第一个有效数据节点之前，所以我们应该将新节点放在哨兵位的后面。先创建一个新节点，让新节点的prev指针指向哨兵位，让它的next指针指向哨兵位的next指向的节点，以上两步不会影响任何节点，做完这两步后，先让哨兵位后面那个节点的prev指针指向新节点，然后让哨兵位的next指针指向新节点，这两步不能调换顺序，否则会找不到哨兵位后面那个节点，下面是代码实现：

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

2.5 尾删 

   执行删除操作之前我们应该先判断这个链表除哨兵位之外有没有其他节点，如果没有，就无法删除，而尾删操作也比较简单，只需要让尾节点的前一个节点的next指针指向哨兵位，然后让哨兵位的prev指针指向位尾节点，以上过程需要创建一个新变量，否则无法找到我们要删除的节点，接着释放掉尾节点后置空就可以了：

void LTPopBack(LTNode* phead)
{assert(phead&&phead->next);LTNode* del = phead->prev;del->prev->next = del->next;del->next->prev = del->prev;free(del);del = NULL;}//尾删

画图演示：

 

2.6 头删 

  头删操作与尾删类似，如果没有两个及以上节点的话无法执行删除操作，头删要删除的是哨兵位后面那个节点，所以我们先创建一个指针存放我们要删除节点的地址，将哨兵位的next指针指向我们要删除节点的下一个节点，然后将我们要删除节点的下一个节点的prev指针指向哨兵位，完成这些操作后释放我们要删除的节点然后置空：

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

2.7 查找 

如果我们要查找一个节点，应该先判断链表是否为空，然后将我们要查找的节点的数据与链表中节点的数据一一对比，如果数据内容相同，说明找到了，将这个节点返回，如果循环一圈还没有找到，说明链表中不存在这样的节点，返回应一个空指针：

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

2.8 指定位置后插入数据 

我们可以先调用查找函数，然后调用它返回的节点，试着在它的后面插入数据，而它的操作与头插非常相像，只是将哨兵位改成了我们指定的节点：

void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x)
{assert(phead&&pop);LTNode* newnode = LTBuyNode(x);newnode->prev = pop;newnode->next = pop->next;pop->next->prev = newnode;pop->next = newnode;
}//指定节点后插入数据

2.9 删除指定节点 

删除节点我们需要先判断链表中是否有两个及以上节点，否则无法删除，删除指定节操作我们先将指定节点的前一个节点的next指向我们指定节点的下一个节点，然后将指定节点的下一个节点的prev指针指向指定节点的前一个节点，这个过程不需要创建中间变量，因为我们有指定节点的地址：

void LTErase(LTNode* phead, LTNode* pop)
{assert(phead && phead->next);pop->next->prev = pop->prev;pop->prev->next = pop->next;free(pop);pop = NULL;}//指定删除节点

2.10 销毁链表

我们链表的每一个节点都是使用malloc函数手动在堆上申请的，需要我们手动释放：

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

2.11 打印链表 

指行这么多插入删除操作我们如果测试的话就使用这个函数打印出来，而打印函数只需要循环打印这个链表一次就可以了：

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

接下来我们使用这个函数来测试一下我们的方法：

可以看到我们的方法都没有问题，那么这期的双向链表就到此结束啦，我将代码放在下面，感兴趣的小伙伴可以试试哦。

List.h :

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int ListNodeData;
typedef struct ListNode
{ListNodeData data;struct ListNode* prev;struct ListNode* next;}LTNode;LTNode* LTFind(LTNode* phead, ListNodeData x);//查找void LTInit(LTNode** pphead);//初始化void LTPushBack(LTNode* phead, ListNodeData x);
//尾插void LTPrint(LTNode* phead);//打印链表void LTPushFront(LTNode* phead, ListNodeData x);
//头插void LTPopBack(LTNode* phead);//尾删void LTPopFront(LTNode* phead);//头删void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x);
//指定节点后删除void LTErase(LTNode* phead, LTNode* pop);
//指定位置删除void LTDestroy(LTNode* phead);
//销毁链表

List.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"LTNode* LTBuyNode(ListNodeData x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;}//创建一个新节点LTNode* LTFind(LTNode* phead, ListNodeData x)
{assert(phead && phead->next);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}//查找函数void LTInit(LTNode** pphead)
{assert(pphead);*pphead = LTBuyNode(-1);}//初始化void LTPushBack(LTNode* phead, ListNodeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//尾插void LTPushFront(LTNode* phead, ListNodeData x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;}//头插void LTPopBack(LTNode* phead)
{assert(phead&&phead->next);LTNode* del = phead->prev;del->prev->next = del->next;del->next->prev = del->prev;free(del);del = NULL;}//尾删void LTPopFront(LTNode* phead)
{assert(phead && phead->next);LTNode* del = phead->next;phead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//头删void LTInsertAfter(LTNode* phead, LTNode* pop, ListNodeData x)
{assert(phead&&pop);LTNode* newnode = LTBuyNode(x);newnode->prev = pop;newnode->next = pop->next;pop->next->prev = newnode;pop->next = newnode;
}//指定节点后插入数据void LTErase(LTNode* phead, LTNode* pop)
{assert(phead && phead->next);pop->next->prev = pop->prev;pop->prev->next = pop->next;free(pop);pop = NULL;}//指定删除节点void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");}//打印void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}}//销毁链表

test.c :

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void test01()
{LTNode* plist = NULL;LTInit(&plist);printf("尾插\n");LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);printf("头插\n");LTPushFront(plist, 0);LTPrint(plist);/*printf("尾删\n");LTPopBack(plist);LTPopBack(plist);LTPrint(plist);*/printf("头删\n");LTPopFront(plist);LTPopFront(plist);LTPrint(plist);printf("在3后面插入数据:\n");LTNode* Find = LTFind(plist, 3);/*if (Find == NULL){printf("找不到！\n");}else{printf("找到了\n");}*/LTInsertAfter(plist, Find, 56);LTPrint(plist);printf("删除指定节点3：\n");LTErase(plist, Find);LTPrint(plist);printf("销毁链表\n");LTDestroy(plist);plist = NULL;}int main()
{test01();return 0;
}

 

 

 

 

 

 

 

 

 

 

 

 

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

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

相关文章

数据分析python基础实战分析

数据分析python基础实战分析

数据分析python基础实战分析 安装python&#xff0c;建议安装Anaconda 【Anaconda下载链接】https://repo.anaconda.com/archive/ 记得勾选上这个框框 安装完后&#xff0c;然后把这两个框框给取消掉再点完成 在电脑搜索框输入"Jupyter"&#xff0c;牛马启动&am…
阅读更多...
网易严选礼品卡有什么用？

网易严选礼品卡有什么用？

网易严选的礼品卡可以在网易商城里买东西 但是现在好多人买东西基本上都用的是淘宝京东之类的 很少会有人用网易吧 但是最近我朋友送了我几张网易的卡&#xff0c;我自己也用积分兑换一张&#xff0c;一直不知道怎么用 最后还是在收卡云上转让出去了&#xff0c;价格高不说…
阅读更多...
2024年JCR分区，将发生重大变化

2024年JCR分区，将发生重大变化

科睿唯安官方微信发布消息&#xff0c;指出今年的期刊排名及相应JCR分区将发生重大变化。 原文比较长&#xff0c;不熟悉相关规则的朋友也不太容易读懂。因此&#xff0c;我们今天做一个详细的解读。 首先明确几个基本概念&#xff1a; &#xff08;1&#xff09;2024年发布2…
阅读更多...
File类和IO流

File类和IO流

File类和IO流 文章目录 File类和IO流[TOC](文章目录)前言一、java.io.File类&IO流原理及流的分类1.1 File类及其API1.2 IO流原理及分类 二、节点流的介绍&#xff08;字符/字节&#xff09;2.1 Reader\Writer--字符IO抽象基类2.2 FileReader\FileWriter--字符IO节点流2.3 I…
阅读更多...
Android 多媒体开发——Media3与MediaSession最全使用指南

Android 多媒体开发——Media3与MediaSession最全使用指南

一、Media3库简介 1.1 Media3是什么&#xff1f; 官方释义&#xff1a; Jetpack Media3 is the new home for media libraries that enables Android apps to display rich audio and visual experiences. Media3 offers a simple architecture with powerful customization,…
阅读更多...
Git 和 TortoiseGit 安装和配置（图文详解）

Git 和 TortoiseGit 安装和配置（图文详解）

使用git&#xff0c;需要在Windows上需要安装两个软件&#xff1a;1&#xff09;Git 2&#xff09;TortoiseGit 若需要&#xff0c;可以下载TortoiseGit汉化语言包。 注意&#xff1a;tortoiseGit是在安装了Git的基础上运行的&#xff0c;所以需要先安装Git&#xff0c;后安装…
阅读更多...
Mysql索引的实现原理，B+Tree，WAL

Mysql索引的实现原理，B+Tree，WAL

InnoDB 引擎&#xff0c;每一个数据表有两个文件 .frm和.ibd&#xff0c;分别为表结构&#xff0c;数据和索引&#xff0c;数据挂在主索引的叶子节点上&#xff0c;此主索引称为聚簇索引。 MyISAM 引擎&#xff0c;每一个数据表有三个文件.frm和.MYI和.MYD&#xff0c;分别为表…
阅读更多...
深入理解计算机系统 CSAPP 家庭作业7.13

深入理解计算机系统 CSAPP 家庭作业7.13

用一下496页提到的工具咯 A: whereis libm.a file lidm.a gedit libm.a libm.a是个ASCII text文件打开一看原来 libm-2.27.a 和libmvec.a才是我们要看的 所以我们cd到目标地址后 ar -t libm-2.27.a ar -t libmvec.a B: gcc -Og bar5.c foo5.c 用之前的两个文件链接后生成…
阅读更多...
【CS.DS】数据结构 —— 图：深入了解三种表示方法之邻接表(Adjacency List)

【CS.DS】数据结构 —— 图：深入了解三种表示方法之邻接表(Adjacency List)

文章目录 1 概念2 无向图的邻接表2.1 示例2.2 Mermaid 图示例2.3 C实现2.3.1 简单实现2.3.2 优化封装 2.4 总结 3 有向图的邻接表3.1 示例3.2 C实现3.3 总结 4 邻接图的遍历5 拓展补充References 数据结构 1 概念 优点&#xff1a;空间效率高&#xff0c;适合稀疏图。动态性强…
阅读更多...
springboot 整合redis

springboot 整合redis

文章目录 一、Jedis二、Lettuce三、RedisTemplate(重点)单机3.1 springboot 整合swagger3.2 序列化中文问题集群3.3 applications配置3.4 问题 一、Jedis package com.example.redis;import redis.clients.jedis.Jedis;import javax.print.DocFlavor; import java.util.*;/***…
阅读更多...
【编译原理】绪论

【编译原理】绪论

1.计算机程序语言以及编译 编译是对高级语言的翻译 源程序是句子的集合&#xff0c;树可以较好的反应句子的结构 编译程序是一种翻译程序 2.编号器在语言处理系统中的位置 可重定位&#xff1a;在内存中存放的起始位置不是固定的 加载器&#xff1a;修改可重定位地址&#x…
阅读更多...
古文字识别笔记

古文字识别笔记

前置知识 部件&#xff1a;大部分的汉字是由若干组笔画结构拼合而成的&#xff0c;这些相对独立的笔画结构称为「部件」。 部件是大于基本笔画&#xff08;例如&#xff1a;点、横、撇、捺等&#xff09;而小于或等同于 偏旁 的结构单位。 例如「测」字有三个部件&#xff1a;…
阅读更多...
【学习】使用PyTorch训练与评估自己的ResNet网络教程

【学习】使用PyTorch训练与评估自己的ResNet网络教程

参考&#xff1a;保姆级使用PyTorch训练与评估自己的ResNet网络教程_训练自己的图像分类网络resnet101 pytorch-CSDN博客 项目地址&#xff1a;GitHub - Fafa-DL/Awesome-Backbones: Integrate deep learning models for image classification | Backbone learning/comparison…
阅读更多...
高效修复机床导轨磨损，保障加工精度！

高效修复机床导轨磨损，保障加工精度！

机床导轨是支承和引导运动构件沿着一定轨迹运动的传动装置&#xff0c;在机器设备中是个十分重要的部件&#xff0c;在机床中是常见的部件。机床的加工精度与导轨精度有直接的联系&#xff0c;且导轨一旦损坏&#xff0c;维修较复杂且困难。我们简单总结了以下几点对于机床导轨…
阅读更多...
编程设计思想

编程设计思想

健康检查脚本 nmap:扫描端口 while true do healthycurl B:httpPORT/healthy -i | grep HTTP/1.1 | tail -n 1 | awk {print $2} done 批量操作类型脚本&#xff08;记录每一步日志&#xff09; 将100个nginx&#xff1a;vn推送到harbor仓库192.168.0.100 根据镜像对比sha值…
阅读更多...
【开源项目】自然语言处理领域的明星项目推荐：Hugging Face Transformers

【开源项目】自然语言处理领域的明星项目推荐：Hugging Face Transformers

在当今人工智能与大数据飞速发展的时代&#xff0c;自然语言处理&#xff08;NLP&#xff09;已成为推动科技进步的重要力量。而在NLP领域&#xff0c;Hugging Face Transformers无疑是一个备受瞩目的开源项目。本文将从项目介绍、代码解释以及技术特点等角度&#xff0c;为您深…
阅读更多...
面向对象修炼手册（四）（多态与空间分配）（Java宝典）

面向对象修炼手册（四）（多态与空间分配）（Java宝典）

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;面向对象修炼手册 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 前言 1 多态 1.1 多态的形式&…
阅读更多...
需求之 实现获取调试信息在h5页面，在手机端可以查看调试（二）

需求之 实现获取调试信息在h5页面，在手机端可以查看调试（二）

事实证明 chatgpt很好用&#xff0c;有不懂的问题可以问它 https://zhuanlan.zhihu.com/p/690118775 国内外9个免费的ChatGPT网站 我筛选出来的比较好用免费的网站 fchat.dykyzdh.cn/ 这个也可以 阿里云的 通义灵码 在vscode中安装使用 而且阿里云有一个产品&#xff0c;可以…
阅读更多...
面试-Java线程池

面试-Java线程池

1.利用Excutors创建不同的线程池满足不同场景的需求 分析&#xff1a; 如果并发的请求的数量非常多&#xff0c;但每个线程执行的时间非常短&#xff0c;这样就会频繁的创建和销毁线程。如此一来&#xff0c;会大大降低系统的效率。 可能出现&#xff0c;服务器在为每个线程创建…
阅读更多...
jdk1.8升级到jdk11遇到的各种问题

jdk1.8升级到jdk11遇到的各种问题

一、第三方依赖使用了BASE64Decoder 如果项目中使用了这个类 sun.misc.BASE64Decoder&#xff0c;就会导致错误&#xff0c;因为再jdk11中&#xff0c;该类已经被删除。 Caused by: java.lang.NoClassDefFoundError: sun/misc/BASE64Encoder 当然这个类也有替换方式&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023