当前位置: 首页 > 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张由小到大连续递增的扑…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...