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

【数据结构与算法】之双向链表及其实现!

                                                                                个人主页:秋风起,再归来~

                                                                                            数据结构与算法                             

                                                                       个人格言:悟已往之不谏,知来者犹可追

                                                                                        克心守己,律己则安!

目录

1、双向链表的结构及概念

2、双向链表的实现

2.1 要实现的接口(List.h)

2.2 链表的初始化

2.3 链表的销毁

2.4 链表的打印

2.5 链表的尾插

2.6 链表的尾删

2.7 链表的头插

2.8 链表的头删

2.8 链表的查找

2.9 pos位置插入数据

2.10 pos位置删除数据

3、完整代码

List.h

List.c

Test.c(本人在实现双向链表时的测试代码) 

4、 完结散花


1、双向链表的结构及概念

我们这里要实现的数据结构是带头双向循环的链表(简称双向链表)

下面就是该链表的物理模型啦~

2、双向链表的实现

2.1 要实现的接口(List.h)

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//前驱指针LTDataType data;struct ListNode* next;//后驱指针
}LTNode;//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit();//链表销毁
void LTDestroy(LTNode* phead);//链表的打印
void LTPrint(LTNode* phead);//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);//链表的尾删
void LTPopBack(LTNode* phead);//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);//链表的头删
void LTPopFront(LTNode* phead);//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置节点
void LTErase(LTNode* pos);

2.2 链表的初始化

注意:在初始化的时候一定要让头结点的prev指针和next指针都指向自己!

//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit()
{//初始化时创建一个带哨兵卫的头结点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc fail!\n");return NULL;}phead->next = phead->prev = phead;phead->data = -1;return phead;
}

2.3 链表的销毁

注意:我们一定是从链表的头结点(头结点中并没有有效数据的存储)的下一个位置开始销毁链表的!

//链表销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur=phead->next;LTNode* next = NULL;//结束条件是当pcur不等于篇pheadwhile (pcur!=phead){next = pcur->next;free(pcur);pcur = next;}
}

并且我们在调用链表的销毁函数后依然要手动释放动态内存开辟的phead头结点 !

为尽量确保接口传递参数的一致性我们并没有传递头结点的地址,所以我们并不能在链表的销毁函数中free我们的头结点!

LTDestroy(plist);
//动态开辟的头结点需要手动释放
free(plist);
plist = NULL;

2.4 链表的打印

遍历链表打印头结点,循环结束的条件是pcur=phead,继续的条件是pcur!=phead

//链表的打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = NULL;//结束条件是当pcur不等于篇pheadwhile (pcur != phead){next = pcur->next;printf("%d->", pcur->data);pcur = next;}printf("\n");
}

2.5 链表的尾插

新节点的创建(单独封装成为一个函数)

//新节点的创建
LTNode* ListCreatNode(LTDataType x)
{LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));//开辟空间if (NewNode == NULL)//判断空间是否开辟成功{perror("malloc fail");return NULL;}NewNode->data = x;//赋值NewNode->next = NULL;//置空NewNode->prev = NULL;return NewNode;
}

链表的尾插 (在为尾插接口中直接调用创建节点的函数)

//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = ListCreatNode(x);//先创建一个新节点LTNode* tail = phead->prev;newNode->prev = tail;newNode->next = phead;tail->next = newNode;phead->prev = newNode;
}

2.6 链表的尾删

注意各个节点的指向!

//链表的尾删
void LTPopBack(LTNode* phead)
{//尾删的前提是双向链表不为空assert(phead && phead->next != phead);LTNode* tail = phead->prev;phead->prev = tail->prev;tail->prev->next=phead;free(tail);tail = NULL;
}

2.7 链表的头插

//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = ListCreatNode(x);//先创建一个新节点newNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}

2.8 链表的头删

//链表的头删
void LTPopFront(LTNode* phead)
{//头删的前提是双向链表不为空assert(phead && phead->next != phead);LTNode* start = phead->next;phead->next = start->next;start->next->prev = phead;free(start);start= NULL;
}

2.8 链表的查找

返回值是该指向该数据节点的结构体指针,如没有找到,直接返回空!

//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = NULL;//结束条件是当pcur不等于篇pheadwhile (pcur != phead){if (pcur->data == x){return pcur;}next = pcur->next;pcur = next;}return NULL;
}

2.9 pos位置插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = ListCreatNode(x);//先创建一个新节点newNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}

2.10 pos位置删除数据

//删除pos位置节点
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

3、完整代码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* prev;//前驱指针LTDataType data;struct ListNode* next;//后驱指针
}LTNode;//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit();//链表销毁
void LTDestroy(LTNode* phead);//链表的打印
void LTPrint(LTNode* phead);//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x);//链表的尾删
void LTPopBack(LTNode* phead);//链表的头插
void LTPushFront(LTNode* phead, LTDataType x);//链表的头删
void LTPopFront(LTNode* phead);//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除pos位置节点
void LTErase(LTNode* pos);

List.c

#include"List.h"//链表的初始化
//void LTInit(LTNode** pphead);带参数的初始化
LTNode* LTInit()
{//初始化时创建一个带哨兵卫的头结点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc fail!\n");return NULL;}phead->next = phead->prev = phead;phead->data = -1;return phead;
}//链表销毁
void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur=phead->next;LTNode* next = NULL;//结束条件是当pcur不等于篇pheadwhile (pcur!=phead){next = pcur->next;free(pcur);pcur = next;}
}//链表的打印
void LTPrint(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = NULL;//结束条件是当pcur不等于篇pheadwhile (pcur != phead){next = pcur->next;printf("%d->", pcur->data);pcur = next;}printf("\n");
}//新节点的创建
LTNode* ListCreatNode(LTDataType x)
{LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));//开辟空间if (NewNode == NULL)//判断空间是否开辟成功{perror("malloc fail");return NULL;}NewNode->data = x;//赋值NewNode->next = NULL;//置空NewNode->prev = NULL;return NewNode;
}//链表的尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = ListCreatNode(x);//先创建一个新节点LTNode* tail = phead->prev;newNode->prev = tail;newNode->next = phead;tail->next = newNode;phead->prev = newNode;
}//链表的尾删
void LTPopBack(LTNode* phead)
{//尾删的前提是双向链表不为空assert(phead && phead->next != phead);LTNode* tail = phead->prev;phead->prev = tail->prev;tail->prev->next=phead;free(tail);tail = NULL;
}//链表的头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newNode = ListCreatNode(x);//先创建一个新节点newNode->next = phead->next;newNode->prev = phead;phead->next->prev = newNode;phead->next = newNode;
}//链表的头删
void LTPopFront(LTNode* phead)
{//头删的前提是双向链表不为空assert(phead && phead->next != phead);LTNode* start = phead->next;phead->next = start->next;start->next->prev = phead;free(start);start= NULL;
}//在双向链表中查找数据
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = NULL;//结束条件是当pcur不等于篇pheadwhile (pcur != phead){if (pcur->data == x){return pcur;}next = pcur->next;pcur = next;}return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newNode = ListCreatNode(x);//先创建一个新节点newNode->next = pos->next;newNode->prev = pos;pos->next->prev = newNode;pos->next = newNode;
}//删除pos位置节点
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

Test.c(本人在实现双向链表时的测试代码) 

#define _CRT_SECURE_NO_WARNINGS#include"LIst.h"void TestList1()
{LTNode* plist;plist = LTInit();//初始化链表LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushFront(plist, 4);LTPushFront(plist, 4);/*LTPopFront(plist);LTPopFront(plist);*/LTNode* pos=LTFind(plist, 2);printf("删除pos位置之前\n");LTPrint(plist);LTErase(pos);printf("删除pos位置之后\n");LTPrint(plist);//LTInsert(pos, 5);//LTPopBack(plist);//LTPopBack(plist);//LTPopBack(plist);LTDestroy(plist);//动态开辟的头结点需要手动释放free(plist);plist = NULL;
}int main()
{TestList1();return 0;
}

4、 完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

相关文章:

【数据结构与算法】之双向链表及其实现!

​ 个人主页&#xff1a;秋风起&#xff0c;再归来~ 数据结构与算法 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 目录 1、双向链表的结构及概念 2、双向链表的实现 2.1 要实现的接口…...

记一次奇妙的某个edu渗透测试

前话&#xff1a; 对登录方法的轻视造成一系列的漏洞出现&#xff0c;对接口确实鉴权造成大量的信息泄露。从小程序到web端网址的奇妙的测试就此开始。&#xff08;文章厚码&#xff0c;请见谅&#xff09; 1. 寻找到目标站点的小程序 进入登录发现只需要姓名加学工号就能成功…...

设计模式学习笔记 - 设计模式与范式 -总结:1.回顾23中设计模式的原理、背后的思想、应用场景等

1.创建型设计模式 创建型设计模式包括&#xff1a;单例模式、工厂模式、建造者模式、原型模式。它主要解决对象的创建问题&#xff0c;封装复杂的创建过程&#xff0c;解耦对象的创建代码和使用代码。 1.单例模式 单例模式用来创建全局唯一的对象。一个类只允许创建一个对象…...

22 文件系统

了解了被打开的文件&#xff0c;肯定还有没被打开的文件&#xff0c;就是磁盘上的文件。先从磁盘开始认识 磁盘 概念 内存是掉电易失存储介质&#xff0c;磁盘是永久性存储介质 磁盘的种类有SSD&#xff0c;U盘&#xff0c;flash卡&#xff0c;光盘&#xff0c;磁带。磁盘是…...

OVITO-2.9版本

关注 M r . m a t e r i a l , \color{Violet} \rm Mr.material\ , Mr.material , 更 \color{red}{更} 更 多 \color{blue}{多} 多 精 \color{orange}{精} 精 彩 \color{green}{彩} 彩&#xff01; 主要专栏内容包括&#xff1a; †《LAMMPS小技巧》&#xff1a; ‾ \textbf…...

【Java开发指南 | 第一篇】类、对象基础概念及Java特征

读者可订阅专栏&#xff1a;Java开发指南 |【CSDN秋说】 文章目录 类、对象基础概念Java特征 Java 是一种面向对象的编程语言&#xff0c;它主要通过类和对象来组织和管理代码。 类、对象基础概念 类&#xff1a;类是一个模板&#xff0c;它描述一类对象的行为和状态。例如水…...

Neo4j 图形数据库中有哪些构建块?

Neo4j 图形数据库具有以下构建块 - 节点属性关系标签数据浏览器 节点 节点是 Graph 的基本单位。 它包含具有键值对的属性&#xff0c;如下图所示。 NEmployee 节点 在这里&#xff0c;节点 Name "Employee" &#xff0c;它包含一组属性作为键值对。 属性 属性是…...

002 springboot整合mybatis-plus

文章目录 TestMybatisGenerate.javapom.xmlapplication.yamlReceiveAddressMapper.xmlreceive_address.sqlReceiveAddress.javaReceiveAddressMapper.javaIReceiveAddressServiceReceiveAddressServiceImpl.javaReceiveAddressController.javaTestAddressService.javaSpringboo…...

代码随想录训练营第三十五期|第天16|二叉树part03|104.二叉树的最大深度 ● 111.二叉树的最小深度● 222.完全二叉树的节点个数

104. 二叉树的最大深度 - 力扣&#xff08;LeetCode&#xff09; 递归&#xff0c;可以前序遍历&#xff0c;也可以后序遍历 前序遍历是backtracking 下面是后序遍历的代码&#xff1a; /*** Definition for a binary tree node.* public class TreeNode {* int val;* …...

Mac版2024 CleanMyMac X 4.15.2 核心功能详解 cleanmymac这个软件怎么样?cleanmymac到底好不好用?

近些年伴随着苹果生态的蓬勃发展&#xff0c;越来越多的用户开始尝试接触Mac电脑。然而很多人上手Mac后会发现&#xff0c;它的使用逻辑与Windows存在很多不同&#xff0c;而且随着使用时间的增加&#xff0c;一些奇奇怪怪的文件也会占据有限的磁盘空间&#xff0c;进而影响使用…...

【华为OD机试】执行任务赚积分【C卷|100分】

题目描述 现有N个任务需要处理&#xff0c;同一时间只能处理一个任务&#xff0c;处理每个任务所需要的时间固定为1。 每个任务都有最晚处理时间限制和积分值&#xff0c;在最晚处理时间点之前处理完成任务才可获得对应的积分奖励。 可用于处理任务的时间有限&#xff0c;请问在…...

mybatis分页实现总结

1.mybatis拦截器相关知识 1.作用 mybatis的拦截器是mybatis提供的一个拓展机制&#xff0c;允许用户在使用时根据各自的需求对sql执行的各个阶段进行干预。比较常见的如对执行的sql进行监控&#xff0c;排查sql的执行时间&#xff0c;对sql进行拦截拼接需要的场景&#xff0c…...

Vue3——html-doc-js(html导出为word的js库)

一、下载 官方地址 html-doc-js - npm npm install html-doc-js 二、使用方法 // 使用页面中引入 import exportWord from html-doc-js// 配置项以及实现下载方法 const wrap document.getElementById(test)const config {document:document, //默认当前文档的document…...

第19天:信息打点-小程序应用解包反编译动态调试抓包静态分析源码架构

第十九天 本课意义 1.如何获取到目标小程序信息 2.如何从小程序中提取资产信息 一、Web&备案信息&单位名称中发现小程序 1.国内主流小程序平台 微信 百度 支付宝 抖音头条 2.小程序结构 1.主体结构 小程序包含一个描述整体程序的app和多个描述各自页面的page …...

外观模式:简化复杂系统的统一接口

在面向对象的软件开发中&#xff0c;外观模式是一种常用的结构型设计模式&#xff0c;旨在为复杂的系统提供一个简化的接口。通过创建一个统一的高级接口&#xff0c;这个模式帮助客户端通过一个简单的方式与复杂的子系统交互。本文将详细介绍外观模式的定义、实现、应用场景以…...

PHP数组去重

public function array_unique_key($arr,$key) {$tmp_arrarray();foreach($arr as $k > $v){if(in_array($v[$key],$tmp_arr)){ //判断是否重复unset($arr[$k]); //重复则删除}else{$tmp_arr[]$v[$key]; //将值存储在临时数组中}}return $arr; } public function array…...

论软件系统的架构风格,使用三段论 写一篇系统架构师论文

软件系统的架构风格是指在软件系统设计与开发过程中&#xff0c;采用的一组相互协调的设计原则、模式和实践。这些风格不仅影响着系统的技术实现&#xff0c;还关乎到系统的可维护性、可扩展性和可靠性等关键质量属性。通过三段论的结构&#xff0c;本文旨在探讨软件系统架构风…...

深度挖掘响应式模式的潜力,从而精准优化AI与机器学习项目的运行效能,引领技术革新潮流

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 &#x1f525; 转载自热榜文章&#xff1a;探索设计模式的魅力&#xff1a;深度挖掘响应式模式的…...

企业级网络安全:入侵防御实时阻止,守护您的业务安全

随着互联网技术的快速发展&#xff0c;企业级网络安全问题日益凸显。在这个数字化时代&#xff0c;企业的业务安全不仅关系到企业的形象和声誉&#xff0c;还直接影响到企业的生存和发展。因此&#xff0c;加强企业级网络安全&#xff0c;预防和抵御各种网络攻击已成为企业的重…...

(一)Java八股——Redis

1 Redis缓存 1.1 什么是缓存穿透 ? 怎么解决 ?&#xff08;穿透&#xff09; ​ 缓存穿透是指查询一个一定不存在的数据&#xff0c;如果从存储层查不到数据则不写入缓存&#xff0c;这将导致这个不存在的数据每次请求都要到 DB 去查询&#xff0c;可能导致 DB 挂掉。这种情…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...