【双向链表】
双向链表
- 带头双向循环链表的实现
- 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张由小到大连续递增的扑…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
