【C语言】实现双向链表
目录
(一)头文件
(二) 功能实现
(1)初始化
(2)打印链表
(3) 头插与头删
(4)尾插与尾删
(5)指定位置之后插入
(6)删除指定位置的数据
(7)链表的销毁
正文开始:
在实际应用中,常用的双向链表是双向带头循环链表,本文考虑到实际应用,目的也是实现双向带头循环链表。
(一)头文件
命名"List.h"
本文不加解释的给出头文件,按照头文件来实现双向链表的基本功能:包括打印链表,链表的初始化,头插与头删,尾插与尾删,在指定位置之后插入数据,删除指定位置的数据,链表的销毁等共九个功能。
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //链表的数据类型 typedef int LTtype; //双向链表的节点 typedef struct ListNode {LTtype data;struct ListNode* prev;struct ListNode* next; }LTNode;//双向链表带有哨兵位,插入数据之前先插入哨兵位 //初始化》传入头节点 void LTInit(LTNode** pphead);//初始化2>返回头节点 LTNode* LtInit0();//销毁链表 void LTDestory(LTNode** pphead);//尾插 void LTtail_push(LTNode* phead,LTtype x);//头插 //是在头节点之后插入,在头节点之前插入等价于尾插 void LThead_push(LTNode* phead,LTtype x);//打印便于调试 void Print(LTNode* phead);//头删 void LTpophead(LTNode* phead);//尾删 void LTpoptail(LTNode* phead);//查找 //为了找到pos位置 LTNode* LTfind(LTNode* phead, LTtype x);//在pos之后插入数据 void LTinsert(LTNode* pos, LTtype x);//删除pos处的数据 void LTerase(LTNode* pos);
(二) 功能实现
带头相对于不带头有诸多优势:
带头与不带头链表:
带头链表是指在链表的开头增加一个额外的节点,该节点不存储具体的数据,仅用于辅助操作链表。带头链表的带头节点可以简化链表的操作,提高代码的可读性和可维护性。
意义:
带头节点可以避免链表为空的特殊情况处理。在没有带头节点的链表中,如果链表为空,添加、删除等操作都需要额外的处理逻辑。而带头节点的链表中,带头节点一直存在,无论链表是否为空,操作逻辑都是一致的,可以减少代码的复杂性。
局限:
造成额外的空间浪费。
(1)初始化
初始化有两种方法,具体实现如下:
传址初始化
初始化传递链表的地址(二级指针【通过传址,将形参与实参建立联系】),初始化要插入头指针哨兵位(不保存有效的数据),便于简化代码逻辑。
//双向链表带有哨兵位,插入数据之前先插入哨兵位 void LTInit(LTNode** pphead) {*pphead = (LTNode*)malloc(sizeof(LTNode));if (*pphead == NULL){perror("malloc");exit(1);}(*pphead)->data = -1;(*pphead)->next = (*pphead)->prev = *pphead; }
接受返回值初始化
在函数内申请头节点,最后返回到主函数内:
//初始化2>返回头节点 LTNode* LtInit0() {LTNode* phead = (LTNode*)malloc(sizeof(LTNode));if (phead == NULL){perror("malloc");exit(1);}phead->data = -1;phead->next = phead->prev = phead;return phead; }
(2)打印链表
以便于调试,理解代码;
与打印单链表一样,不同的是:while的跳出条件是 pcur != phead;
//打印链表 void Print(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n"); }
(3) 头插与头删
插入操作需要申请新节点:
//获取新节点 LTNode* LTbuynewnode(LTtype x) {LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = newnode->prev = NULL;return newnode; }
头插与头删
头插,是在头节点之后插入,在头节点之前插入等价于尾插;
先对新节点进行操作,因为新节点与原节点没有联系,不会因为对指针进行操作而丢失节点,造成数据丢失和内存泄漏;
我们可以直接得到phead,因此先让phead的下一个节点的前驱指针指向newnode,再改变phead的next指针;
(如果反过来,先改变phead的next指向newnode,此时newnode后面的节点就找不到了。)//头插,是在头节点之后插入,在头节点之前插入等价于尾插 void LThead_push(LTNode* phead, LTtype x) {assert(phead);LTNode* newnode = LTbuynewnode(x);//先对新节点进行操作newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;}
头删
断言传过来的指针不为空,链表不为空,通过assert实现;
通过创建del指针(要被删除的节点),保存旧头节点;
通过创建next指针,保存旧头节点的next节点;
这样命名后进行头删,逻辑清晰,不易出错;
//头删 void LTpophead(LTNode* phead) {assert(phead);assert(phead->next != phead);LTNode* del = phead->next;//被删除的节点LTNode* next = del->next;//del的后置节点phead->next = next;next->prev = phead;free(del);del = NULL; }
(4)尾插与尾删
尾插
与头插的逻辑完全相同
//尾插 void LTtail_push(LTNode* phead, LTtype x) {assert(phead);LTNode* newnode = LTbuynewnode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode; }
尾删
与头删的逻辑完全相同
//尾删 void LTpoptail(LTNode* phead) {assert(phead);assert(phead->next != phead);LTNode* del = phead->prev;//被删除的节点LTNode* prev = del->prev;//del的前置节点prev->next = phead;phead->prev = prev;free(del);del = NULL; }
(5)指定位置之后插入
查找
查找数据值为x的节点,找到返回此节点,找不到返回NULL;
//查找 LTNode* LTfind(LTNode* phead,LTtype x) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL; }
在指定位置之后插入数据
根据find找到的pos位置,申请新节点,插入到pos之后
//在pos位置之后插入数据 void LTinsert(LTNode* pos,LTtype x) {assert(pos);LTNode* newnode = LTbuynewnode(x);newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode; }
(6)删除指定位置的数据
删除指定位置的数据,需要的指针有pos的前驱节点,pos节点。
//删除pos处的数据 void LTerase(LTNode* pos) {assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL; }
(7)链表的销毁
链表的销毁共有两种方法:
传址销毁
//销毁链表 void LTDestory(LTNode** pphead) {assert(pphead);//哨兵位不为空assert(*pphead);LTNode* pcur = (*pphead)->next;while (pcur != *pphead){LTNode* next = pcur->next;free(pcur);pcur = next;}//释放哨兵位free(pphead);//此时可以改变哨兵位的pphead = NULL;}
传值销毁
一级指针phead传递的是值,不是phead的地址,所以在函数中改变phead并不会改变phead的实际值
函数返回后,仍需要手动phead = NULL;//推荐使用一级,为了保持接口的一致性 void LTDestory0(LTNode* phead) {assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;//无效的置空,当做是习惯 } //一级指针phead传递的是值,不是phead的地址,所以在函数中改变phead并不会改变phead的实际值 //函数返回后,仍需要手动phead = NULL;
完~
未经作者同意禁止转载
相关文章:

【C语言】实现双向链表
目录 (一)头文件 (二) 功能实现 (1)初始化 (2)打印链表 (3) 头插与头删 (4)尾插与尾删 (5)指定位置之后…...

Python操作MySQL基础
除了使用图形化工具以外,我们也可以使用编程语言来执行SQL从而操作数据库。在Python中,使用第三方库: pymysql来完成对MySQL数据库的操作。 安装第三方库pymysql 使用命令行,进入cmd,输入命令pip install pymysql. 创建到MySQL的数据库连接…...

【数学建模】【2024年】【第40届】【MCM/ICM】【E题 财产保险的可持续性】【解题思路】
一、题目 (一) 赛题原文 2024 ICM Problem E: Sustainability of Property Insurance Extreme-weather events are becoming a crisis for property owners and insurers. The world has endured “more than $1 trillion in damages from more than …...

SpringCloud--Eureka注册中心服务搭建注册以及服务发现
注意springboot以及springcloud版本,可能有莫名其妙的错误,这里使用的是springboot-2.6.13,springcloud-2021.0.5 一,Eureka-Server搭建: 1.创建项目:引入依赖 <dependency><groupId>org.sp…...

ansible shell模块 可以用来使用shell 命令 支持管道符 shell 模块和 command 模块的区别
这里写目录标题 说明shell模块用法shell 模块和 command 模块的区别 说明 shell模块可以在远程主机上调用shell解释器运行命令,支持shell的各种功能,例如管道等 shell模块用法 ansible slave -m shell -a cat /etc/passwd | grep root # 可以使用管道…...
qss的使用
参考:qss样式表笔记大全(二):可设置样式的窗口部件列表(上)(持续更新示例)_51CTO博客_qss样式...

archlinux 使用 electron-ssr 代理 socks5
提前下载好 pacman 包 https://github.com/shadowsocksrr/electron-ssr/releases/download/v0.2.7/electron-ssr-0.2.7.pacman 首先要有 yay 和 aur 源,这个可以参考我之前的博客 虚拟机内使用 archinstall 安装 arch linux 2024.01.01 安装依赖 yay 安装的&#…...
macos安装local模式spark
文章目录 配置说明安装hadoop安装Spark测试安装成功 配置说明 Scala - 3.18 Spark - 3.5.0 Hadoop - 3.3.6 安装hadoop 从这里下载相应版本的hadoop下载后解压,配置系统环境变量 > sudo vim /etc/profile添加以下两行 export HADOOP_HOME/Users/collinsliu/…...

机器学习算法之支持向量机(SVM)
SVM恐怕大家即使不熟悉,也听说过这个大名吧,这一节我们就介绍这相爱相杀一段内容。 前言:在介绍一个新内容之SVM前,我们不觉映入眼帘的问题是为什么要引入SVM?吃的香,睡的着的情况下,肯定不会是…...

线性判别分析(LDA)
一、说明 LDA 是一种监督降维和分类技术。其主要目的是查找最能分隔数据集中两个或多个类的特征的线性组合。LDA 的主要目标是找到一个较低维度的子空间,该子空间可以最大限度地区分不同类别,同时保留与歧视相关的信息。 LDA 是受监督的,这意…...
Vue 前置导航
Vue 前置导航(Vue Front Navigation)是一种在 Vue.js 框架中实现导航功能的常见方式。它通常用于构建单页应用程序(Single Page Application),通过在页面顶部或侧边栏显示导航菜单,使用户能够轻松切换到不同…...
串行通信,并行通信,波特率,全双工,半双工,单工等通信概念
串行通信: 只使用一根线来进行数据发送或者是接收,串行通信传输数据是一位一位进行传输 并行通信: 使用多跟线进行数据的发送和接收,并行通信可以一次传输多个数据位 波特率: 每秒传输数据的位数,决定…...

鸿蒙系统进一步学习(一):学习资料总结,少走弯路
随着鸿蒙Next的计划越来越近,笔者之前的鸿蒙系统扫盲系列中,有很多朋友给我留言,不同的角度的问了一些问题,我明显感觉到一点,那就是许多人参与鸿蒙开发,但是又不知道从哪里下手,因为资料太多&a…...
异步复位同步释放原则
复位信号有一个非常重要的原则,叫作异步复位同步释放原则。异步复位指一个寄存器的复位信号随时可以复位,不必考虑该寄存器的时钟信号正处在哪个相位上。同步释放是指一个寄存器的复位信号从复位态回到释放态的时机,必须与该寄存器的时钟信号…...

M1 Mac使用SquareLine-Studio进行LVGL开发
背景 使用Gui-Guider开发遇到一些问题,比如组件不全。使用LVGL官方的设计软件开发 延续上一篇使用的基本环境。 LVGL项目 新建项目 选择Arduino的项目,设定好分辨率及颜色。 设计UI 导出代码 Export -> Create Template Project 导出文件如图…...

web3知识体系汇总
web3.0知识体系 1.行业发展 2. web3的特点: 1、统一身份认证系统 2、数据确权与授权 3、隐私保护与抗审查 4、去中心化运行 Web3.0思维技术思维✖金融思维✖社群思维✖产业思维”,才能从容理解未来Web3.0时代的大趋势。 3.技术栈 Web3.jsSolidit…...

服务器与电脑的区别?
目录 一、什么是服务器 二、什么是电脑 三、服务器和电脑的区别 一、什么是服务器 服务器是指一种专门提供计算和存储资源、运行特定软件服务的物理或虚拟计算机。服务器主要用于接受和处理来自客户端(如个人电脑、手机等)的请求,并向客户…...
结束 代码随想录 链表章节(下一张
环形链表II 首先,先判断有没有环,像物理相对速度一样 只要 相对速度为1 那么快指针绝对会在环里追上慢指针,最后x 和z 的距离其实最后两个index总会相遇,相遇的点就是入口 class Solution { public:ListNode *detectCycle(List…...
re:从0开始的CSS学习之路 6. 字体相关属性
1. 字体相关属性 font-size 字体大小 font-family 字体的系列(字体簇) 可以设置多个字体,每个字体之间以逗号隔开 设置多个字体的目的是为了用户尽可能的支持字体 网页字体的五大类: serif 衬线字体 sans-serif 非衬线字体 monos…...

FPGA(基于xilinx)中PCIe介绍以及IP核XDMA的使用
Xilinx中PCIe简介以及IP核XDMA的使用 例如:第一章 PCIe简介以及IP核的使用 文章目录 Xilinx中PCIe简介以及IP核XDMA的使用一、PCIe总线概述1.PCIe 总线架构2.PCIe 不同版本的性能指标及带宽计算3.PCIe 接口信号 二、XDMA1.XDMA 与其它 PCIe IP 的区别2.XDMA简介 三…...
【Linux】shell脚本忽略错误继续执行
在 shell 脚本中,可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行,可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令,并忽略错误 rm somefile…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版分享
平时用 iPhone 的时候,难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵,或者买了二手 iPhone 却被原来的 iCloud 账号锁住,这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...