数据结构篇其三---链表分类和双向链表

前言

数据结构篇其二实现了一个简单的单链表,链表的概念,单链表具体实现已经说明,如下:
单链表
事实上,前面的单链表本质上是无头单向不循环链表。此篇说明的双向链表可以说完全反过来了了。无论是之前的单链表还是双向链表,本质都是链表家族的两位成员。
主题一:链表分类
详细说说链表的特征,以及这些特征组合的链表种类。
主题二:双向链表的实现
像上次实现单链表一样,这次也试着独立实现双向链表吧。
学习收获:十分钟手搓一个链表

为什么学习双向链表?
因为虽然字面上双向链表好像还难一点,结构虽然复杂,但是实现起来特别简单。应用场景有显著的优势。

链表的分类

  • 单向与双向

链表的单向与双向:这说明节点与节点之间的联系。单向链表节点的指针一路往后。双向链表节点指针指前指后。
单向与双向

可见,从定义上,双向链表天生应该有两个指针,所以在单链表的基础上,我们可以推出双向链表的定义。

//双向链表的定义
typedef int LTDataType;
typedef struct ListNode {LTDataType data;//数据域struct ListNode* prev;//前驱指针struct ListNode* next;//后继指针
}ListNode;

链表双向和单向决定了它节点指针的数量

  • 带头与不带头

为了方便对链表进行操作,我们会在链表的第一个节点前附带一个头节点(哨兵位),注意头节点不是第一个节点,第一个节点存储的是有效数据。
头节点的数据域不存储有效的数据,指针域next指向第一个节点,若是双向的话,则前驱指针指向尾结点。
需注意这个时候头指针就指向头节点,而不是第一个节点了。
单链表带哨兵位

  • 循环非循环

若链表的尾结点指向头节点而不是NULL,则链表闭合形成了一个环,可以循环了,就称为循环链表。反之,则为不循环链表。
循环与非循环

  1. 以上就是链表的三大特征,每种特征又分两种情况。组合起来一共8种,所以链表种类一共8种。
  2. 下面介绍双向链表,来熟悉一下双向,带头,循环的链表吧。

双向链表的实现

下面实现这些函数

// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode * plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);

前面已经给出了双向链表的定义。但下图只体现了双向,循环和带头还要我们具体实现。

typedef int LTDataType;
typedef struct ListNode {LTDataType data;//数据域struct ListNode* prev;//前驱指针struct ListNode* next;//后继指针
}ListNode;

开局一个头指针,能这样做吗?


int main() {ListNode* plist = NULL;return 0;
}

这个是带头的链表,起码有头节点吧,所以先创建一个头节点。
其次,这个是循环链表,头节点的前驱指针和后继指针应该都指向自己吧。
头节点

节点创建

ListNode* ListCreate(LTDataType x) {ListNode* phead = (ListNode*)malloc(sizeof(ListNode));//判断动态空间是否开辟失败。if (phead == NULL) {perror("malloc fail");exit(-1);}phead->data = x;//头节点数据随便赋值phead->next = phead;//前驱,后继指针指向自己phead->prev = phead;return phead;
}

双向链表初始化

ListNode* ListInit() {return ListCreate(-1);//头节点的数据域随便给值。
}

还没有元素啊,那就先插入节点吧

双向链表的尾插

如何实现尾插呢?

  1. 保证每个节点的两个指针有明确的指向。

  2. 尾插操作的节点有三个,头节点,尾结点,新节点。

  3. 按照上面图片的步骤写代码。

  4. 后面请自行画图分析,多创建临时变量,良好的命名习惯。写完一个函数去测试一下。

void ListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = ListCreate(x);//创建新节点ListNode* tail = phead->prev;//记录尾结点//执行尾插操作phead->prev = newnode;newnode->next = phead;tail->next = newnode;newnode->prev = tail;
}

打印函数

void ListPrint(ListNode* phead) {assert(phead);ListNode* pcur = phead->next;printf("head->");while (pcur!= phead) {printf("%d->", pcur->data);pcur = pcur->next;}pcur = NULL;printf("return\n");
}

双链表的头插

void ListPushFront(ListNode* phead,LTDataType x) {assert(phead);ListNode* newnode = ListCreate(x);ListNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;}

双向链表的尾删

//尾删函数
void ListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tailprev = tail->prev;phead->prev = tailprev;tailprev->next = phead;if(phead->prev!=phead)//判断是否为空表,哨兵位不能释放了。free(tail);tail = NULL;}

双向链表的头删

/头删函数
void ListPopFront(ListNode* phead) {assert(phead);ListNode* first = phead->next;ListNode* second = first->next;phead->next = first->next;second->prev = phead;if (phead != first)//哨兵位不能释放{free(first);}first = NULL;second = NULL;
}

双向链表的销毁

void ListDestory(ListNode** pphead) {assert(pphead);assert(*pphead);ListNode* pcur = (*pphead)->next;ListNode* next = pcur->next;while (pcur != *pphead){free(pcur);pcur = next;next = next->next;}free(pcur);pcur = NULL;next = NULL;*pphead = NULL;}

双向链表补充

// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

双向链表查找指定数据

ListNode* ListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;//找到了返回当前节点的地址}pcur=pcur->next;}return NULL;//双链表跑完一遍都没找到,返回空。
}

在pos节点之前插入新节点

//在pos之前插入
void ListInsert(ListNode* pos, LTDataType x) {assert(pos);ListNode* newnode = ListCreate(x);ListNode* prev = pos->prev;newnode->next = pos;pos->prev = newnode;prev->next = newnode;newnode->prev = prev;pos = NULL;prev = NULL;newnode = NULL;
}

删除位置为pos的节点

void ListErase(ListNode* pos) {assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);prev->next = next;next->prev = prev;pos = NULL;prev = NULL;next = NULL;
}

十分钟实现一个链表

  1. 实现什么类型的链表?
  2. 需要写什么函数?

双向链表;
实现函数,增删查改,还有来链表的初始化,销毁。


#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
typedef struct ListNode {LTDataType data;struct ListNode* next;struct ListNode* prev;
}LT;LT* LTInit(void) {LT* newnode = (LT*)malloc(sizeof(LT));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->next = newnode;newnode->prev = newnode;return newnode;
}LT LTDestory(LT** pphead) {assert(pphead);assert(*pphead);LT* pcur = (*pphead)->next;LT* next = pcur->next;while (pcur != *pphead) {free(pcur);pcur = next;next = next->next;}free(pcur);*pphead = NULL;}//在pos之前插入新节点
void LTInsert(LT* pos, LTDataType x) {assert(pos);LT* prev = pos->prev;LT * newnode = (LT*)malloc(sizeof(LT));if (newnode == NULL) {perror("malloc fail");exit(-1);}newnode->data = x;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}void LTErase(LT* pos) {assert(pos);LT* prev = pos->prev;LT* next = pos->next;free(pos);prev->next = next;next->prev = prev;
}void LTPushBack(LT* phead,LTDataType x) {LTInsert(phead, x);
}void LTPushFront(LT* phead, LTDataType x) {LTInsert(phead->next, x);
}void LTPopBack(LT* phead) {LTErase(phead->prev);
}void LTPopFront(LT* phead) {LTErase(phead->next);
}LT* LTFind(LT* phead, LTDataType x) {LT* pcur = phead->next;while (pcur != phead) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;return;
}LT* LTMidfy( LT* pos,LTDataType x) {pos->data = x;
}

双向链表完结。链表完结!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/330998.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ElasticSearch - 删除已经设置的认证密码(7.x)

文章目录 Pre版本号 7.x操作步骤检查当前Elasticsearch安全配置停止Elasticsearch服务修改Elasticsearch配置文件删除密码重启Elasticsearch服务验证配置 小结 Pre Elasticsearch - Configuring security in Elasticsearch 开启用户名和密码访问 版本号 7.x ES7.x 操作步骤 …

从ES到ClickHouse,Bonree ONE平台更轻更快!

本文字数&#xff1a;8052&#xff1b;估计阅读时间&#xff1a;21 分钟 作者&#xff1a;博睿数据 李骅宸&#xff08;太道&#xff09;& 娄志强&#xff08;冬青&#xff09; 本文在公众号【ClickHouseInc】首发 本系列第一篇内容&#xff1a; 100%降本增效&#xff01;…

01-02.Vue的常用指令(二)

01-02.Vue的常用指令&#xff08;二&#xff09; 前言v-model&#xff1a;双向数据绑定v-model举例&#xff1a;实现简易计算器Vue中通过属性绑定为元素设置class 类样式引入方式一&#xff1a;数组写法二&#xff1a;在数组中使用三元表达式写法三&#xff1a;在数组中使用 对…

redis--redis Cluster

简介 解决了redis单机写入的瓶颈问题&#xff0c;即单机的redis写入性能受限于单机的内存大小、并发数量、网卡速率等因素无中心架构的redis cluster机制&#xff0c;在无中心的redis集群当中&#xff0c;其每个节点保存当前节点数据和整个集群状态,每个节点都和其他所有节点连…

数组和指针的联系(C语言)

数组和指针是两种不同的数据类型&#xff0c;数组是一种构造类型&#xff0c;用于存储一组相同类型的变量&#xff1b;而指针是一种特殊类型&#xff0c;专门用来存放数据的地址。数组名除了sizeof(数组名)和&数组名表示整个数组外&#xff0c;其他情况下都表示的是首元素的…

百度集团:AI重构,走到哪了?

内有自家公关一号“自曝”狼性文化&#xff0c;主动制造舆论危机。 外有&#xff0c;OpenAI、谷歌、字节、华为等大模型劲敌扎堆迭代新产品&#xff0c; 强敌环伺。 今天我们要说的是早就从BAT掉队的——百度。 最近&#xff0c;在武汉Aapollo Day 2024上&#xff0c;百度发布了…

增强ev代码签名证书2300

代码签名证书是软件开发者们确保软件完整性和安全性的重要工具之一。在各种类型的代码签名证书中&#xff0c;增强EV代码签名证书拥有许多独特的功能而受到企业开发者的欢迎&#xff0c;今天就随SSL盾小编了解增强EV代码签名证书的申请条件以及申请流程。 1.增强型EV代码签名证…

npm介绍、常用命令详解以及什么是全局目录

目录 npm介绍、常用命令详解以及什么是全局目录一、介绍npm的主要功能npm仓库npm的配置npm的版本控制 二、命令1. npm init: 初始化一个新的Node.js项目&#xff0c;创建package.json文件。package.json是一个描述项目信息和依赖关系的文件。2. npm install <package_name&g…

Linux 内核之 mmap 内存映射的原理及源码解析

文章目录 前言一、简介1. mmap 是什么&#xff1f;2. Linux 进程虚拟内存空间 二、mmap 内存映射1. mmap 内存映射的实现过程2. mmap 内存映射流程2.1 mmap 系统调用函数2.2 ksys_mmap_pgoff 函数2.3 vm_mmap_pgoff 函数2.4 do_mmap_pgoff 函数2.5 do_mmap 函数2.6 get_unmappe…

ElasticSearch操作之重置密码脚本

ElasticSearch操作之重置密码脚本 #!/bin/bash # 使用样例 ./ES密码重置.sh 旧密码 新密码# 输入旧密码 es_old_password$1# 设置新的密码变量 es_password$2# 正确响应 es_reponse{"acknowledged":true}# 检查Elasticsearch是否在运行 if pgrep -f elasticsearch &g…

DNF手游攻略:角色培养与技能搭配!游戏辅助!

角色培养和技能搭配是《地下城与勇士》中提升战斗力的关键环节。每个职业都有独特的技能和发展路线&#xff0c;合理的属性加点和技能搭配可以最大化角色的潜力&#xff0c;帮助玩家在各种战斗中立于不败之地。接下来&#xff0c;我们将探讨如何有效地培养角色并搭配技能。 角色…

Leetcode | 5-21| 每日一题

2769. 找出最大的可达成数字 考点: 暴力 数学式子计算 思维 题解 通过式子推导: 第一想法是二分确定区间在区间内进行查找是否符合条件的, 本题最关键的便是 条件确定 , 第二种方法: 一般是通过数学公式推导的,这种题目我称为数学式编程题 代码 条件判断式 class Solution { …

基于SSM的“医院门诊管理系统”的设计与实现(源码+数据库+文档)

基于SSM的“医院门诊管理系统”的设计与实现&#xff08;源码数据库文档) 开发语言&#xff1a;Java 数据库&#xff1a;MySQL 技术&#xff1a;SSM 工具&#xff1a;IDEA/Ecilpse、Navicat、Maven 系统展示 系统功能模块图 医院门诊管理系统首页页面图 用户登录界面图 管…

【数据结构】------C语言实现二叉树

作者主页&#xff1a;作者主页 数据结构专栏&#xff1a;数据结构 创作时间 &#xff1a;2024年5月20日 一、二叉树的定义 二叉树(Binary Tree) 是由n个结点构成的有限集(n≥0)&#xff0c;n0时为空树&#xff0c;n>0时为非空树。 对于非空树&#xff1a; 有且仅有一个根…

用这8种方法在海外媒体推广发稿平台上获得突破-华媒舍

在今天的数字时代&#xff0c;海外媒体推广发稿平台已经成为了许多机构和个人宣传和推广的有效途径。如何在这些平台上获得突破并吸引更多的关注是一个关键问题。本文将介绍8种方法&#xff0c;帮助您在海外媒体推广发稿平台上实现突破。 1. 确定目标受众 在开始使用海外媒体推…

基于STM32实现数字示波器

目录 引言环境准备数字示波器基础代码示例&#xff1a;实现数字示波器 ADC采样数据处理显示波形用户界面应用场景&#xff1a;信号分析与电子实验问题解决方案与优化收尾与总结 1. 引言 本教程将详细介绍如何在STM32嵌入式系统中使用C语言实现数字示波器&#xff0c;包括如何…

Kali Linux安装Xrdp远程桌面工具结合内网穿透实现远程访问Kali桌面

文章目录 前言1. Kali 安装Xrdp2. 本地远程Kali桌面3. Kali 安装Cpolar 内网穿透4. 配置公网远程地址5. 公网远程Kali桌面连接6. 固定连接公网地址7. 固定地址连接测试 前言 Kali远程桌面的好处在于&#xff0c;它允许用户从远程位置访问Kali系统&#xff0c;而无需直接物理访…

【maven与tomcat配置】如何正确配置maven及tomcat环境变量及运行Java项目 (附图文说明及下载包)

maven及tomcat配置详解 &#x1f354;涉及知识&#x1f964;写在前面&#x1f367;一、maven和tomcat是啥&#xff1f;&#x1f367;二、maven环境变量配置2.1获取maven包2.2创建本地仓库及修改配置A&#xff0e;校验是否安装javaB&#xff0e;创建本地maven存放仓库C&#xff…

【代码随想录】二分查找算法总结篇

目录 前言二分查找例题一例题二例题三例题四 前言 本篇文章记录了代码随想录二分查找算法的总结笔记&#xff0c;下面我们一起来学习吧&#xff01;&#xff01; 二分查找 关于二分查找算法&#xff0c;我在之前的这篇博客里面做了非常多的分析&#xff0c;但是后面做题做着…

【ETAS CP AUTOSAR工具链】ARXML文件详解

本篇文章首先对ARXML这种文件格式做了一个概述&#xff0c;叙述了这种标签语言的基本语法&#xff08;如果您用HTML做过网页&#xff0c;那么这种格式您一定不会陌生&#xff09;&#xff0c;然后对ARXML文件都会包含的一些基本信息做了详细的解读&#xff0c;最后基于使用ISOL…