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

【双向链表】

双向链表

  • 带头双向循环链表的实现
    • 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. 主函数测试 带头双向循环链表的实现 今天我们来实现一下带头双向循环链表&#xff0c;顾名思义&#xff0c;带头就是有哨兵位&#xff0c;哨兵位不是链表的头&#xff0c;它是连接头节点的一个节点&#xff0c;方…...

POSTGRESQL NEON - Serverless 式的POSTGRESQL 数据库的独特技能 分支数据

开头还是介绍一下群&#xff0c;如果感兴趣polardb ,mongodb ,mysql ,postgresql ,redis 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请联系 liuaustin3 &#xff0c;在新加的朋友会分到2群&#xff08;共…...

数据分布——长尾分布的处理

前言 长尾分布在分类任务中会提到这个名,这是因为长尾分布这个现象问题会导致在训练过程中会出现出错率高的问题&#xff0c;影响了实验结果。 这里要说的是&#xff0c;长尾分布是一种现象&#xff0c;有的地方说是一种理论或定律&#xff0c;我感觉这样说不太确切&#xff0…...

集合导题、刷题、考试全套完整流程,专业强大的功能,提高刷题学习效率和企业的培训效率

土著刷题微信小程序v1.15&#xff0c;主要是迭代了考试模块的进阶功能&#xff0c;对考试模块进行了一次升级改造。 由于在v1.15开发期间&#xff0c;收到了违规内容整改的通告&#xff0c;为了遵守相关法律法规&#xff0c;让小程序能够平稳安全地运营下去&#xff0c;我们特此…...

【机器学习】采样方法

文章目录 采样方法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 简介 什么是采样 从一个分布中生成一批服从该分布的样本&#xff0c…...

Seata TCC 模式理论学习、生产级使用示例搭建及注意事项 | Spring Cloud55

一、前言 通过以下系列章节&#xff1a; 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开发—远程控制 一&#xff0c;准备二&#xff0c;安装版本控制工具1&#xff0c;安装gitforwindows2&#xff0c;安装乌龟git1&#xff0c;安装乌龟git应用2&#xff0c;安装乌龟git对应的语言包 3&#xff0c;设置Visual Studio的git插件4&#xff0c;创建git项目 三&#x…...

【Python基础】Python数据容器(集合)

文章目录 数据容器&#xff1a;set&#xff08;集合&#xff09;集合的定义集合的常用操作-修改(1)添加新元素(2)移除元素(3)从集合中随机取出元素(4)清空集合(5)取出 两个集合的差集(6)消除 两个集合的差集(7)两个集合 合并(8)统计集合元素数量len()(9)集合的遍历 集合的特点 …...

高通 Camera HAL3:集成camxoverridesettings.txt到整机版本

camxoverridesettings.txt 是高通提供给开发者临时进行CAMX、CHI-CDK功能调试的一种方式&#xff0c;通过配置各种变量值然后写入到该文件&#xff0c;能控制Log打印、参数配置、数据dump等多种功能 这个文件需要集成在设备目录的vendor/etc/camera/里 因为camxoverridesetti…...

PHP面试题大全

一 、PHP基础部分 1、PHP语言的一大优势是跨平台&#xff0c;什么是跨平台&#xff1f; PHP的运行环境最优搭配为ApacheMySQLPHP&#xff0c;此运行环境可以在不同操作系统&#xff08;例如windows、Linux等&#xff09;上配置&#xff0c;不受操作系统的限制&#xff0c;所以…...

Linux发送接收邮件

目录 一、实验 1.linux用户发送给linux中的其它用户 2.linux用户发送给外网用户 一、实验 1.linux用户发送给linux中的其它用户 &#xff08;1&#xff09;使用命令 yum install -y sendmail 安装sendmail软件 &#xff08;2&#xff09;使用yum install -y mailx 安装 mail…...

SpringBoot-【回顾】

第一个SpringBoot程序 自动装配原理 Springboot的自动装配实际上就是为了从Spring.factories文件中获取到对应的需要进行自动装配的类&#xff0c;并生成相应的Bean对象&#xff0c;然后将它们交给Spring容器来帮我们进行管理 启动器&#xff1a;以starter为标记 EnableAuto…...

Python模拟试卷2023(1)

模拟试卷(1) 一、简答题 &#xff08;共8题&#xff0c;100分&#xff09; 1、已知有列表lst[54,36,75,28,50]&#xff0c;请完成一下操作&#xff1a; 1、在列表尾部插入元素42 2、在元素28前面插入66 3、删除并输出28 4、将列表按降序排序 5、清空整个列表 lst[54,3…...

常量接口 vs 常量类 vs 枚举区别

把常量定义在接口里与类里都能通过编译&#xff0c;那2者到底有什么区别呢&#xff1f; 那个更合理&#xff1f; 常量接口 public interface ConstInterfaceA {public static final String CONST_A "aa";public static final String CONST_C "cc"; } 存在…...

第二章 模态命题:必然、可能

第二章 模态命题&#xff1a;必然、可能 第一节 模态命题-句式转换-逻辑转换 题-模态命题-句式转换-逻辑转换&#xff1a;①不一定不可能&#xff1b;②不一定可能不未必。 1.唐代韩愈在《师说》中指出&#xff1a;“孔子曰&#xff1a;三人行&#xff0c;则必有我师。是故…...

Selenium 必了解—如何测试REST API

目录 前言&#xff1a; Web UI测试存在的问题&#xff1a; REST API测试&#xff1a; 依赖包 程序示例&#xff1a; 1-获取联系人 2-GET Request&#xff1a; 3-POST Request: 4- 编辑请求 5- 删除请求 前言&#xff1a; Selenium WebDriver 可以用于测试 Web 应用的…...

pytorch安装老版本

比如1.7.1&#xff0c; cuda 10.1 pip install torch1.7.1cu101 -f https://download.pytorch.org/whl/torch_stable.html官网查看有哪些可以装的&#xff1a; https://download.pytorch.org/whl/torch_stable.html...

怎么自学电脑编程

首要之首&#xff1a;不要急于选择一种语言 新手们有一个常见的错误就是犹豫于判断哪种编程语言是做好的、最该先学的。 我们有很多的选择&#xff0c;但你不能说那种语言最好。 我们应该理解&#xff1a;说到底&#xff0c;什么语言并不重要。 重要的是理解数据结构、控制逻辑…...

【华为OD统一考试B卷 | 100分】斗地主之顺子(C++ Java JavaScript Python)

文章目录 题目描述输入描述输出描述用例C++JavajavaScriptpython题目描述 在斗地主扑克牌游戏中, 扑克牌由小到大的顺序为:3,4,5,6,7,8,9,10,J,Q,K,A,2,玩家可以出的扑克牌阵型有:单张、对子、顺子、飞机、炸弹等。 其中顺子的出牌规则为:由至少5张由小到大连续递增的扑…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

【机器视觉】单目测距——运动结构恢复

ps&#xff1a;图是随便找的&#xff0c;为了凑个封面 前言 在前面对光流法进行进一步改进&#xff0c;希望将2D光流推广至3D场景流时&#xff0c;发现2D转3D过程中存在尺度歧义问题&#xff0c;需要补全摄像头拍摄图像中缺失的深度信息&#xff0c;否则解空间不收敛&#xf…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...