【双向链表】
双向链表
- 带头双向循环链表的实现
- 1. 函数的声明
- 2. 函数的实现
- 3. 主函数测试
带头双向循环链表的实现
今天我们来实现一下带头双向循环链表,顾名思义,带头就是有哨兵位,哨兵位不是链表的头,它是连接头节点的一个节点,方便操作链表而已;双向就是一个节点可以找到下一个节点,也可以找到上一个节点,所以每个节点应该有两个结构体指针;循环就是没有空指针,哨兵位的上一个节点是尾,尾的下一个节点是哨兵位;如下图为带头双向循环链表:

1. 函数的声明
以下是函数的声明部分,我们主要实现双向链表的增删查改功能;
#pragma once#include <stdio.h>#include <stdlib.h>#include <assert.h>#include <stdbool.h>//类型的命名typedef int LTDataType;//定义节点typedef struct ListNode{struct ListNode* prev;struct ListNode* next;LTDataType data;}LTNode;//初始化链表LTNode* ListInit();//打印链表void ListPrint(LTNode* phead);//判断是否是空链表bool IsEmpty(LTNode* phead);//尾插、头插、头删、尾删void ListPushBack(LTNode* phead, LTDataType x);void ListPushFront(LTNode* phead, LTDataType x);void ListPopFront(LTNode* phead);void ListPopBack(LTNode* phead);//查找LTNode* LTFindPos(LTNode* phead, LTDataType x);//在pos位置之前插入void LTInsertPos(LTNode* pos, LTDataType x);//删除pos位置void LTErasePos(LTNode* pos);//销毁void LTDestroy(LTNode* phead);
2. 函数的实现
为了防止创建新的节点的时候重复出现,我们将创建节点写成一个函数:
LTNode* BuyListNode(int x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));assert(newnode);newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}
初始化节点,只需要一个哨兵位,它的next和prev都指向自己;
LTNode* ListInit(){LTNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;}
打印链表的函数:
void ListPrint(LTNode* phead){assert(phead);LTNode* cur = phead->next;printf("guard<==>");while (cur != phead){printf("%d<==>",cur->data);cur = cur->next;}printf("\n");}
由于头删尾删的时候不能是空链表,带头的链表的空链表相当于只有一个哨兵位,所以头删尾删的时候链表中不能只剩下哨兵位;
bool IsEmpty(LTNode* phead){assert(phead);return phead->next == phead;}
尾插函数:
void ListPushBack(LTNode* phead,LTDataType x){assert(phead);LTNode* newnode = BuyListNode(x);LTNode* tail = phead->prev;newnode->next = phead;tail->next = newnode;newnode->prev = tail;phead->prev = newnode;}
头插函数:
void ListPushFront(LTNode* phead, LTDataType x){assert(phead);LTNode* newnode = BuyListNode(x);LTNode* next = phead->next;newnode->next = next;newnode->prev = phead;next->prev = newnode;phead->next = newnode;}
头删函数:
void ListPopFront(LTNode* phead){assert(phead);assert(!IsEmpty(phead));LTNode* del = phead->next;LTNode* next = del->next;phead->next = next;next->prev = phead;free(del);}
尾删函数:
void ListPopBack(LTNode* phead){assert(phead);assert(!IsEmpty(phead));LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;tailprev->next = phead;phead->prev = tailprev;free(tail);}
查找某个节点的函数,返回找到的节点,否则返回空;
LTNode* LTFindPos(LTNode* phead, LTDataType x){assert(phead);LTNode* cur = phead->next;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}
在pos位置之前插入的插入函数:
void LTInsertPos(LTNode* pos, LTDataType x){assert(pos);LTNode* newnode = BuyListNode(x);LTNode* ptr = pos->prev;ptr->next = newnode;newnode->next = pos;pos->prev = newnode;newnode->prev = ptr;}
删除pos位置的函数:
void LTErasePos(LTNode* pos){assert(pos);assert(!IsEmpty(pos));LTNode* ptr = pos->prev;LTNode* next = pos->next;ptr->next = next;next->prev = ptr;free(pos);}
销毁链表的函数:
void LTDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}
3. 主函数测试
#include "List.h"int main(){LTNode* phead = ListInit();ListPushBack(phead, 1);ListPushBack(phead, 2);ListPushBack(phead, 3);ListPushBack(phead, 4);ListPushFront(phead, 10);ListPopBack(phead);ListPopFront(phead);LTNode* pos = LTFindPos(phead, 3);LTInsertPos(pos, 20);LTErasePos(pos);ListPrint(phead);LTDestroy(phead);return 0;}
以上就是带头双向循环链表的基本实现,感兴趣的伙伴可以自行尝试噢!!!
相关文章:
【双向链表】
双向链表 带头双向循环链表的实现1. 函数的声明2. 函数的实现3. 主函数测试 带头双向循环链表的实现 今天我们来实现一下带头双向循环链表,顾名思义,带头就是有哨兵位,哨兵位不是链表的头,它是连接头节点的一个节点,方…...
POSTGRESQL NEON - Serverless 式的POSTGRESQL 数据库的独特技能 分支数据
开头还是介绍一下群,如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题,有需求都可以加群群内有各大数据库行业大咖,CTO,可以解决你的问题。加群请联系 liuaustin3 ,在新加的朋友会分到2群(共…...
数据分布——长尾分布的处理
前言 长尾分布在分类任务中会提到这个名,这是因为长尾分布这个现象问题会导致在训练过程中会出现出错率高的问题,影响了实验结果。 这里要说的是,长尾分布是一种现象,有的地方说是一种理论或定律,我感觉这样说不太确切࿰…...
集合导题、刷题、考试全套完整流程,专业强大的功能,提高刷题学习效率和企业的培训效率
土著刷题微信小程序v1.15,主要是迭代了考试模块的进阶功能,对考试模块进行了一次升级改造。 由于在v1.15开发期间,收到了违规内容整改的通告,为了遵守相关法律法规,让小程序能够平稳安全地运营下去,我们特此…...
【机器学习】采样方法
文章目录 采样方法11.1 简介11.2 常见采样方法11.2.1 均匀分布采样11.2.2 逆变换采样11.2.3 拒绝采样11.2.4 重要采样11.2.5 Metropolis方法11.2.6 Metropolis-Hasting 算法11.2.7 吉布斯采样 采样方法 11.1 简介 什么是采样 从一个分布中生成一批服从该分布的样本,…...
Seata TCC 模式理论学习、生产级使用示例搭建及注意事项 | Spring Cloud55
一、前言 通过以下系列章节: docker-compose 实现Seata Server高可用部署 | Spring Cloud 51 Seata AT 模式理论学习、事务隔离及部分源码解析 | Spring Cloud 52 Spring Boot集成Seata利用AT模式分布式事务示例 | Spring Cloud 53 Seata XA 模式理论学习、使用…...
一文详解:Vue3中使用Vue Router
目录 安装和配置Vue Router安装Vue Router配置Vue Router Vue Router的基本概念Vue Router 的配置项介绍routes中的配置项介绍 路由跳转使用 router-link组件使用router.push函数 路由传参动态路由嵌套路由命名路由路由守卫全局路由守卫路由独享守卫 路由懒加载使用import()方式…...
C++开发—远程控制
C开发—远程控制 一,准备二,安装版本控制工具1,安装gitforwindows2,安装乌龟git1,安装乌龟git应用2,安装乌龟git对应的语言包 3,设置Visual Studio的git插件4,创建git项目 三&#x…...
【Python基础】Python数据容器(集合)
文章目录 数据容器:set(集合)集合的定义集合的常用操作-修改(1)添加新元素(2)移除元素(3)从集合中随机取出元素(4)清空集合(5)取出 两个集合的差集(6)消除 两个集合的差集(7)两个集合 合并(8)统计集合元素数量len()(9)集合的遍历 集合的特点 …...
高通 Camera HAL3:集成camxoverridesettings.txt到整机版本
camxoverridesettings.txt 是高通提供给开发者临时进行CAMX、CHI-CDK功能调试的一种方式,通过配置各种变量值然后写入到该文件,能控制Log打印、参数配置、数据dump等多种功能 这个文件需要集成在设备目录的vendor/etc/camera/里 因为camxoverridesetti…...
PHP面试题大全
一 、PHP基础部分 1、PHP语言的一大优势是跨平台,什么是跨平台? PHP的运行环境最优搭配为ApacheMySQLPHP,此运行环境可以在不同操作系统(例如windows、Linux等)上配置,不受操作系统的限制,所以…...
Linux发送接收邮件
目录 一、实验 1.linux用户发送给linux中的其它用户 2.linux用户发送给外网用户 一、实验 1.linux用户发送给linux中的其它用户 (1)使用命令 yum install -y sendmail 安装sendmail软件 (2)使用yum install -y mailx 安装 mail…...
SpringBoot-【回顾】
第一个SpringBoot程序 自动装配原理 Springboot的自动装配实际上就是为了从Spring.factories文件中获取到对应的需要进行自动装配的类,并生成相应的Bean对象,然后将它们交给Spring容器来帮我们进行管理 启动器:以starter为标记 EnableAuto…...
Python模拟试卷2023(1)
模拟试卷(1) 一、简答题 (共8题,100分) 1、已知有列表lst[54,36,75,28,50],请完成一下操作: 1、在列表尾部插入元素42 2、在元素28前面插入66 3、删除并输出28 4、将列表按降序排序 5、清空整个列表 lst[54,3…...
常量接口 vs 常量类 vs 枚举区别
把常量定义在接口里与类里都能通过编译,那2者到底有什么区别呢? 那个更合理? 常量接口 public interface ConstInterfaceA {public static final String CONST_A "aa";public static final String CONST_C "cc"; } 存在…...
第二章 模态命题:必然、可能
第二章 模态命题:必然、可能 第一节 模态命题-句式转换-逻辑转换 题-模态命题-句式转换-逻辑转换:①不一定不可能;②不一定可能不未必。 1.唐代韩愈在《师说》中指出:“孔子曰:三人行,则必有我师。是故…...
Selenium 必了解—如何测试REST API
目录 前言: Web UI测试存在的问题: REST API测试: 依赖包 程序示例: 1-获取联系人 2-GET Request: 3-POST Request: 4- 编辑请求 5- 删除请求 前言: Selenium WebDriver 可以用于测试 Web 应用的…...
pytorch安装老版本
比如1.7.1, cuda 10.1 pip install torch1.7.1cu101 -f https://download.pytorch.org/whl/torch_stable.html官网查看有哪些可以装的: https://download.pytorch.org/whl/torch_stable.html...
怎么自学电脑编程
首要之首:不要急于选择一种语言 新手们有一个常见的错误就是犹豫于判断哪种编程语言是做好的、最该先学的。 我们有很多的选择,但你不能说那种语言最好。 我们应该理解:说到底,什么语言并不重要。 重要的是理解数据结构、控制逻辑…...
【华为OD统一考试B卷 | 100分】斗地主之顺子(C++ Java JavaScript Python)
文章目录 题目描述输入描述输出描述用例C++JavajavaScriptpython题目描述 在斗地主扑克牌游戏中, 扑克牌由小到大的顺序为:3,4,5,6,7,8,9,10,J,Q,K,A,2,玩家可以出的扑克牌阵型有:单张、对子、顺子、飞机、炸弹等。 其中顺子的出牌规则为:由至少5张由小到大连续递增的扑…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)
目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 编辑编辑 UDP的特征 socke函数 bind函数 recvfrom函数(接收函数) sendto函数(发送函数) 五、网络编程之 UDP 用…...
