数据结构——考研笔记（三）线性表之单链表

文章目录

      • 2.3 单链表
        • 2.3.1 知识总览
        • 2.3.2 什么是单链表
        • 2.3.3 不带头结点的单链表
        • 2.3.4 带头结点的单链表
        • 2.3.5 不带头结点 VS 带头结点
        • 2.3.6 知识回顾与重要考点
        • 2.3.7 单链表的插入和删除
          • 2.3.7.1 按位序插入（带头结点）
          • 2.3.7.2 按位序插入（不带头结点）
          • 2.3.7.3 指定结点的后插操作
          • 2.3.7.4 指定结点的前插操作
          • 2.3.7.5 按位序删除（带头结点）
          • 2.3.7.6 知识回顾与重要考点
        • 2.3.8 单链表的查找
          • 2.3.8.1 按位查找
          • 2.3.8.2 按值查找
          • 2.3.8.3 知识回顾与重要考点
        • 2.3.9 单链表的建立
          • 2.3.9.1 尾插法
          • 2.3.9.2 头插法

2.3 单链表

2.3.1 知识总览

image-20240715163504480

2.3.2 什么是单链表

image-20240715163622432

  • 顺序表：

    • 优点：可随机存取，存储密度高
    • 缺点：要求大片连续空间，改变容量不方便

  • 单链表：

    • 优点：不要求大片连续空间，改变容量方便
    • 缺点：不可随机存取，要消耗一定空间存放指针

  • 用代码实现单链表

image-20240715164545122

typedef struct LNode{			//定义单链表结点类型
    ElemType data;		//每个节点存放一个数据元素
    struct LNode* next;  //指针指向下一个节点
}LNode,*LinkList;
2.3.3 不带头结点的单链表
#include <stdlib.h>

typedef struct LNode {	//定义单链表结点类型
	int data;			//每个节点存放一个数据元素
	struct LNode* next; //指针指向下一个节点
}LNode,*LinkList;

//初始化一个空的单链表
bool InitList(LinkList& L) {
	L = NULL;	//空表，暂时还没有任何结点
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L == NULL)
		return true;
	else
		return false;
}

void test() {
	LinkList L;	//声明一个指向单链表的指针
	//初始化一个空表
	InitList(L);
	//……后续代码……
}
2.3.4 带头结点的单链表

image-20240715171402035

#include <stdlib.h>

typedef struct LNode {	//定义单链表结点类型
	int data;			//每个节点存放一个数据元素
	struct LNode* next; //指针指向下一个节点
}LNode, * LinkList;

//初始化一个空的单链表
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));	//分配一个头节点
	if (L == NULL)			//内存不足，分配失败
		return false;
	L->next = NULL;			//头结点之后暂时还没有节点
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L->next == NULL)
		return true;
	else
		return false;
}

void test() {
	LinkList L;	//声明一个指向单链表的指针
	//初始化一个空表
	InitList(L);
	//……后续代码……
}
2.3.5 不带头结点 VS 带头结点

image-20240715171704621

  • 不带头结点：写代码更麻烦对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑对空表和非空表的处理需要用到不同的代码逻辑
  • 带头结点：写代码更方便。
2.3.6 知识回顾与重要考点

image-20240715171817961

2.3.7 单链表的插入和删除

image-20240715172017835

2.3.7.1 按位序插入（带头结点）
  • ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

image-20240715172337653

  • 代码展示

image-20240715174709999

#include <stdlib.h>

typedef struct LNode {	//定义单链表结点类型
	int data;			//每个节点存放一个数据元素
	struct LNode* next; //指针指向下一个节点
}LNode, * LinkList;

//初始化一个空的单链表
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));	//分配一个头节点
	if (L == NULL)			//内存不足，分配失败
		return false;
	L->next = NULL;			//头结点之后暂时还没有节点
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L == NULL)
		return true;
	else
		return false;
}

//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1)
		return false;
	LNode* p;	//指针p指向当前扫描到的结点
	int j = 0;	//当前p指向的是第几个结点
	p = L;		//L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1) {	//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)	//i值不合法
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;	//将结点s连到p之后
	return true;	//插入成功
}

void main() {
	LinkList L;	//声明一个指向单链表的指针
	//初始化一个空表
	InitList(L);
	//……后续代码……
}
2.3.7.2 按位序插入（不带头结点）

image-20240715175632081

  • 代码展示
#include <stdlib.h>

typedef struct LNode {	//定义单链表结点类型
	int data;			//每个节点存放一个数据元素
	struct LNode* next; //指针指向下一个节点
}LNode, * LinkList;

//初始化一个空的单链表
bool InitList(LinkList& L) {
	L = (LNode*)malloc(sizeof(LNode));	//分配一个头节点
	if (L == NULL)			//内存不足，分配失败
		return false;
	L->next = NULL;			//头结点之后暂时还没有节点
	return true;
}

//判断单链表是否为空
bool Empty(LinkList L) {
	if (L == NULL)
		return true;
	else
		return false;
}

//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1)
		return false;
	if (i = 1) {	//插入第1个结点的操作与其它结点的操作不同
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;		//头指针指向新节点
		return true;
	}
	LNode* p;	//指针p指向当前扫描到的结点
	int j = 1;	//当前p指向的是第几个结点
	p = L;		//L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1) {	//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)	//i值不合法
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;	//将结点s连到p之后
	return true;	//插入成功
}

void main() {
	LinkList L;	//声明一个指向单链表的指针
	//初始化一个空表
	InitList(L);
	//……后续代码……
}
2.3.7.3 指定结点的后插操作

image-20240715180832621

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode* p, int e) {
	if (p == NULL)
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL)	//内存分配失败
		return false;
	s->data = e;	//用结点s保存数据元素e
	s->next = p->next;
	p->next = s;	//将结点s连到p之后
	return true;
}
2.3.7.4 指定结点的前插操作

image-20240715181828300

  • 代码展示
//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode* p, int e) {
	if (p == NULL)		//内存分配失败
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->next = p->next;
	p->next = s;		//新结点s连到p之后
	s->data = p->data;	//将p中元素复制到s中
	p->data = e;		//p中元素覆盖为e
	return true;
}
2.3.7.5 按位序删除（带头结点）
  • ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

image-20240715183805791

  • 代码展示
//删除表中第i个元素
bool ListDelete(LinkList& L, int i, int& e) {
	if (i < 1)
		return false;
	LNode* p;		//指针p指向当前扫描到的结点
	int j = 0;		//当前p指向的是第几个结点
	p = L;			//L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1) {	//循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)	//i值不合法
		return false;
	if (p->next == NULL)	//第i-1个结点之后无其他结点
		return false;
	LNode* q = p->next;		//令q指向被删除结点
	e = q->data;			//用e返回元素的值
	p->next = q->next;		//将*q结点从链中“断开”
	free(q);				//释放结点的存储空间
	return true;			//删除成功
}
2.3.7.6 知识回顾与重要考点

image-20240715190156270

2.3.8 单链表的查找

image-20240715190606364

  • GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
  • LocalteElem(L,e)：按值查找。在表L中查找具有给定关键字值的元素。
2.3.8.1 按位查找
  • 代码展示
//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
	if (i < 0)
		return false;
	LNode* p;		//指针p指向当前扫描到的结点
	int j = 0;		//当前p指向的是第几个结点
	p = L;			//L指向头节点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i) {	//循环找到第i个结点
		p = p->next;
		j++;
	}
	return p;
}
2.3.8.2 按值查找
  • 代码展示
//按值查找，找到数据域==e的结点
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next;
	//从第1个结点开始查找数据域为e的结点
	while (p != NULL && p->data != e)
		p = p->next;
	return p;	//找到后返回该结点指针，否则返回NULL
}
2.3.8.3 知识回顾与重要考点

image-20240715192241414

2.3.9 单链表的建立

image-20240715192343150

如果给你很多个数据元素（ElemType），要把它们存到一个单链表里边，怎么办呢？

step1：初始化一个单链表

step2：每次取一个数据元素，插入到表尾/表头

2.3.9.1 尾插法
  • 代码展示
//尾插法
LinkList List_TailInsert(LinkList& L) {	//正向建立单链表
	int x;								
	L = (LinkList)malloc(sizeof(LNode));//建立头结点
	LNode* s, * r = L;					//r为表尾指针
	scanf("%d", &x);					//输入结点的值
	while (x != 9999) {					//输入9999表示结束
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;							//r指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL;						//尾结点指针置空
	return L;
}
2.3.9.2 头插法
  • 代码展示
//头插法
LinkList List_HeadInsert(LinkList& L) {
	LNode* s;
	int x;
	L = (LNode*)malloc(sizeof(LNode));	//建立头结点
	L->next = NULL;						//初始化空链表
	scanf_s("%d", &x);					//输入结点的值
	while (x != 9999) {					//输入9999表示结束
		s = (LNode*)malloc(sizeof(LNode));//创建新结点
		s->data = x;
		s->next = L->next;
		L->next = s;					//将新结点插入表中，L为头指针
		scanf_s("%d", &x);
	}
	return L;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

如何使用 GPT？

如何使用 GPT？

​通过实例&#xff0c;来展示如何最好地使用 GPT。 生成文字 假设你在写一篇文章&#xff0c;需要在结尾加上这样一句&#xff1a;「California’s population is 53 times that of Alaska.」&#xff08;加州的人口是阿拉斯加州的 53 倍&#xff09;。 但现在你不知道这两个…
阅读更多...
Git钩子Hook功能

Git钩子Hook功能

&#x1f4be; Hook 钩子 目录 &#x1f514; 简介&#x1f514; 常见类型&#x1f514; 如何配置&#x1f514; 使用场景&#x1f514; 示例 &#x1f514; 简介 Git Hooks是Git内置的一种机制&#xff0c;允许在特定事件发生时执行自定义脚本。Git Hook可以在客户端和服务器端…
阅读更多...
SpringBoot整合阿里云RocketMQ对接,商业版

SpringBoot整合阿里云RocketMQ对接,商业版

1.需要阿里云开通商业版RocketMQ 普通消息新建普通主题,普通组,延迟消息新建延迟消息主题,延迟消息组 2.结构目录 3.引入依赖 <!--阿里云RocketMq整合--><dependency><groupId>com.aliyun.openservices</groupId><artifactId>ons-client</…
阅读更多...
[论文笔记]构建基于RAG聊天机器人的要素

[论文笔记]构建基于RAG聊天机器人的要素

引言 今天带来一篇构建RAG的论文笔记&#xff1a;FACTS About Building Retrieval Augmented Generation-based Chatbots。 基于生成式人工智能构建企业聊天机器人迅速成为行业中最受关注的应用之一&#xff0c;旨在提高员工生产力。 然而&#xff0c;构建成功的企业聊天机器…
阅读更多...
爬虫-requests和Selenium

爬虫-requests和Selenium

1、了解requests的功能 1.1 使用post和get发送请求 HTTP中常见发送网络请求的方式有两种&#xff0c;GET和POST。GET是从指定的资源请求数据&#xff0c;POST是向指定的资源提交要被处理的数据。 GET的用法&#xff1a; import requestsr requests.get("https://www.…
阅读更多...
随机过程基础：2.Markov (马尔可夫)过程（2）

随机过程基础：2.Markov (马尔可夫)过程（2）

纯生过程和纯灭过程 纯生过程&#xff1a;想象一下一个生物种群&#xff0c;比如一群兔子&#xff0c;在没有天敌的理想环境中&#xff0c;食物充足&#xff0c;疾病不存在。在这样的环境下&#xff0c;兔子的种群只会增加&#xff0c;不会减少。纯生过程模型就是用来描述这种情…
阅读更多...
Android使用ANativeWindow更新surfaceView内容最简Demo

Android使用ANativeWindow更新surfaceView内容最简Demo

SurfaceView简介 SurfaceView对比View的区别 安卓的普通VIew,都依赖于当前Activity的Window的surface&#xff0c;这个surface用于承载view树从底到顶绘制出来的所有内容&#xff0c;因此任何一个view需要更新时&#xff0c;都需要把所有view中底到顶进行更新&#xff0c;即使使…
阅读更多...
人工智能算法工程师(中级)课程12-PyTorch神经网络之LSTM和GRU网络与代码详解1

人工智能算法工程师(中级)课程12-PyTorch神经网络之LSTM和GRU网络与代码详解1

大家好，我是微学AI，今天给大家介绍一下人工智能算法工程师(中级)课程12-PyTorch神经网络之LSTM和GRU网络与代码详解。在深度学习领域，循环神经网络（RNN）因其处理序列数据的能力而备受关注。然而，传统的RNN存在梯度消失和梯度爆炸的问题，这使得它在长序列任务中的表现不尽…
阅读更多...
【Diffusion学习】【生成式AI】淺談圖像生成模型 Diffusion Model 原理

【Diffusion学习】【生成式AI】淺談圖像生成模型 Diffusion Model 原理

文章目录 Diffusion Model 是如何运作的&#xff1f;吃额外的1个数字&#xff1a;stepDenoise 模组内部实际做的事情&#xff1a;预测noise如何训练 Noise Predictor Text-to-ImageDDPM 算法 from&#xff1a; https://www.youtube.com/watch?vazBugJzmz-o&listPLJV_el3uV…
阅读更多...
深入剖析 Android 开源库 EventBus 的源码详解

深入剖析 Android 开源库 EventBus 的源码详解

文章目录 前言一、EventBus 简介EventBus 三要素EventBus 线程模型 二、EventBus 使用1.添加依赖2.EventBus 基本使用2.1 定义事件类2.2 注册 EventBus2.3 EventBus 发起通知 三、EventBus 源码详解1.Subscribe 注解2.注册事件订阅方法2.1 EventBus 实例2.2 EventBus 注册2.2.1…
阅读更多...
无人机之电动系统篇

无人机之电动系统篇

无人机的动能系统为无人机提供了动力&#xff0c;使无人机能够进行飞行活动。电动系统是无人机动力系统的其中一种。电力系统是将化学能转化为电能&#xff0c;再转化为机械能&#xff0c;为无人机飞行提供动力的系统。电力系统有电池、电调、电机和螺旋桨四个部分组成。 电池…
阅读更多...
论文阅读【时间序列】TimeMixer (ICLR2024)

论文阅读【时间序列】TimeMixer (ICLR2024)

【时间序列】TimeMixer (ICLR2024) 原文链接&#xff1a;TIMEMIXER: DECOMPOSABLE MULTISCALE MIXING FOR TIME SERIES FORECASTING 代码仓库&#xff1a;https://github.com/kwuking/TimeMixer 符号定义 符号含义P用于预测的历史序列长度&#xff08;seq_len&#xff09;F预测…
阅读更多...
第七天 SpringBoot与SpringCloud微服务项目交付

第七天 SpringBoot与SpringCloud微服务项目交付

Spring Cloud微服务项目交付 微服务扫盲篇 微服务并没有一个官方的定义&#xff0c;想要直接描述微服务比较困难&#xff0c;我们可以通过对比传统WEB应用&#xff0c;来理解什么是微服务。 单体应用架构 如下是传统打车软件架构图&#xff1a; 这种单体应用比较适合于小项…
阅读更多...
LVS+Keepalive高可用

LVS+Keepalive高可用

1、keepalive 调度器的高可用 vip地址主备之间的切换&#xff0c;主在工作时&#xff0c;vip地址只在主上&#xff0c;vip漂移到备服务器。 在主备的优先级不变的情况下&#xff0c;主恢复工作&#xff0c;vip会飘回到住服务器 1、配优先级 2、配置vip和真实服务器 3、主…
阅读更多...
基于hive数据库的泰坦尼克号幸存者数据分析

基于hive数据库的泰坦尼克号幸存者数据分析

进入 ./beeline -u jdbc:hive2://node2:10000 -n root -p 查询 SHOW TABLES; 删除 DROP TABLE IF EXISTS tidanic; 上传数据 hdfs dfs -put train.csv /user/hive/warehouse/mytrain.db/tidanic 《泰坦尼克号幸存者数据分析》 1、原始数据介绍 泰坦尼克号是当时世界上…
阅读更多...
PyTorch人脸识别

PyTorch人脸识别

新书速览|PyTorch深度学习与企业级项目实战-CSDN博客 一套基本的人脸识别系统主要包含三部分&#xff1a;检测器、识别器和分类器&#xff0c;流程架构如图11-3所示&#xff1a; 图11-5 检测器负责检测图片中的人脸&#xff0c;再将检测出来的人脸感兴趣区域&#xff08;Reg…
阅读更多...
音视频入门基础：H.264专题（13）——FFmpeg源码中通过SPS属性获取视频色彩格式的实现

音视频入门基础：H.264专题（13）——FFmpeg源码中通过SPS属性获取视频色彩格式的实现

一、引言 通过FFmpeg命令可以获取到H.264裸流文件的色彩格式&#xff08;又译作色度采样结构、像素格式&#xff09;&#xff1a; 在vlc中也可以获取到色彩格式&#xff08;vlc底层也使用了FFmpeg进行解码&#xff09;&#xff1a; 这个色彩格式就是之前的文章《音视频入门基础…
阅读更多...
2024年初级注册安全工程师职业资格考试首次开考！

2024年初级注册安全工程师职业资格考试首次开考！

​2024年初级注册安全工程师考试首次开考&#xff08;注&#xff1a;该考试由各省人事考试局组织考试&#xff09;。目前未取得中级注册安全工程师证书的各位同学&#xff0c;可以关注该考试&#xff0c;毕竟初级考证相对较容易&#xff0c;先去考一个。 目前初安开考地区汇总…
阅读更多...
【Diffusion学习】【生成式AI】Stable Diffusion、DALL-E、Imagen 背後共同的套路

【Diffusion学习】【生成式AI】Stable Diffusion、DALL-E、Imagen 背後共同的套路

文章目录 图片生成Framework 需要3个组件&#xff1a;相关论文【Stable Diffusion&#xff0c;DALL-E&#xff0c;Imagen】 具体介绍三个组件1. Text encoder介绍【结论&#xff1a;文字的encoder重要&#xff0c;Diffusion的模型不是很重要&#xff01;】评估指标&#xff1a;…
阅读更多...
大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】

大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】

大数据面试SQL题复习思路一网打尽&#xff01;(文档见评论区)_哔哩哔哩_bilibiliHive SQL 大厂必考常用窗口函数及相关面试题 大数据面试SQL题-笔记01【运算符、条件查询、语法顺序、表连接】大数据面试SQL题-笔记02【...】 目录 01、力扣网-sql题 1、高频SQL50题&#xff08…
阅读更多...
最新文章

Copyright @ 2022~2023