线性表的链式存储结构以及顺序表和链表的比较

2.2线性表的链式存储结构

**链式存储结构：**结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。

线性表的链式表示又称为非顺序映像或链式映像

这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。

  • 如何表示空表？

    • 无头结点时，头指针为空时表示空表。

    • 有头结点时，当头结点的指针域为空时表示空表。

  • 头结点的数据域内装的是什么？

    头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值。

1.单链表

1.1单链表的定义和表示

例如，存储学生学号、姓名、成绩的单链表结点类型定义如下：

typedef struct student {
	char num[8];
	char name[8];
	int score;
	struct student* next;
}Node,*LinkList;

为了统一链表的操作，通常这样定义：

typedef struct {
	char num[8];
	char name[8];
	int score;
}ElemType;
typedef struct Lnode {
	ElemType data;
	struct Lnode* next;
}Lnode,*LinkList;

变量定义：

LinkList L;
LNode *p,*s;

重要操作：

p=L;//p指向头结点
s=L->next;//s指向首元结点
p=p->next;//p指向下一结点
1.2单链表的初始化（带头结点）

即构造一个空表。

【算法步骤】：

  1. 生成新结点作头结点，用头指针L指向头结点。
  2. 将头结点的指针域置空。
bool InitList_L(LinkList& L) {
	L = new Lnode;//或L=（LinkList）malloc（sizeof（Lnode））;
	L->next = NULL;
	return true;
}
1.3判断链表是否为空

空表：链表中无元素，称为空链表（头指针和头结点仍然在）

**【算法思路】**判断头结点指针域是否为空

1.4单链表的销毁

链表销毁后不存在

**【算法思路】**从头指针开始，依次释放所有结点

结束条件：L==NULL 循环条件：L!=NULL

bool DestoryList(LinkList& L) {
	Lnode* p;
	while (L) {
		p = L;
		L = L->next;
		delete p;
	}
	return true;
}
1.5清空链表

链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）

**【算法思路】**依次释放所有结点，并将头结点指针域设置为空

结束条件：p==NULL 循环条件：p！=NULL

bool ClearList(LinkList& L) {
	Lnode* p, * q;
	p = L->next;
	while (p) {   //没到表尾
		q = p->next;
		delete p;
		p = q;
	}
	L->next = NULL;//头结点指针域为空
	return true;
}
1.6求单链表的表长

**【算法思路】**从首元结点开始，依次计数所有结点

int ListLength(LinkList L) {
	Lnode* p;
	p = L->next; //p指向第一个结点
	int i = 0;
	while (p) {
		i++;
		p = p->next;
	}
	return i;
}
1.7单链表取值

取单链表中第i个元素的内容

【算法思路】 从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此链表不是随机存取结构。

【算法步骤】：

  1. 从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值为p=L->next。
  2. j做计数器，累计当前扫描过的结点数，j初值为1。
  3. 当p指向扫描到的下一结点时，计数器j加1。
  4. 当j==i时，p所指的结点就是要找的第i个结点。
bool GetElem(LinkList L, int i, int& e) {//获取线性表中的某个数据元素的内容，通过变量e返回
	Lnode* p;
	p = L->next;
	int j = 1;
	while (j < i && p) {//向后扫描，直到p指向第i个元素或p为空
		p = p->next;
		++j;
	}
	if (!p || j > i) return false;
	e = p->data;
	return true;
}
1.8单链表的按值查找

按值查找——根据指定数据获取该数据所在的位置（该数据的地址）。

【算法步骤】：

  1. 从第一个结点起，依次和e相比较。
  2. 如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址。
  3. 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或者“NULL‘’。
Lnode* LocateElem(LinkList L, int e) {
	//在线性表L中查找值为e的数据元素
	//找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
	Lnode* p;
	p = L->next;
	while (p && p->data != e) {
		p = p->next;
	}
	return p;
}

按值查找——根据指定数据获取该数据位置序号（是第几个数据元素）

1.9单链表的插入

在第i个结点前插入值为e的新结点。

【算法步骤】：

  1. 首先找到i-1的存储位置p；

  2. 生成一个数据域为e的新结点s。

  3. 插入新结点：①新结点的指针域指向结点i

    ​ ②节点i-1的指针域指向新结点

    ①s->next (i结点的地址) =p->next;

    ②p->next=s;

//在L中第i个元素之前插入数据元素e
bool ListInsert(LinkList& L, int e, int i) {
	Lnode* p;
	p = L;
	int j = 0;
	while (p && j < i - 1) {//寻找第i-1个结点，p指向i-1结点
		p = p->next;
		++j;
	}
	if (!p || j > i - 1) return false;//i大于表长+1或者小于1，插入位置非法
	Lnode* s = new Lnode;//生成新结点s，将结点s的数据域置为e
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}
1.10单链表的删除

删除第i个结点

图解：单链表删除，不遍历链表也能做（时间复杂度O(1)）_承香墨影的博客-CSDN博客

【算法步骤】：

  1. 首先找到i-1的存储位置p，保存要删除的i的值。

  2. 令p->next指向i+1。

    p->next = p->next->next

  3. 释放结点i的空间。

bool ListDelete(LinkList& L, int i, int& e) {
	Lnode* p;
	p = L;
	int j = 0;
	while (p->next && j < i - 1) {//寻找第i个结点，并令p指向其前驱
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1) return false;//删除位置不合理
	Lnode* q;
	q = p->next;//临时保存被删结点的地址以备释放
	p->next = q->next;//改变删除结点前驱结点的指针域
	e = q->data;
	delete q;
	return true;
}
1.11单链表的查找、插入、删除算法时间效率分析
  1. 查找：
    • 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)。
  2. 插入和删除：
    • 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。
    • 但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O（n）。
1.12单链表的建立

建立单链表：头插法——元素插入在链表头部，也叫前插法。

【算法步骤】：

  1. 从一个空表开始，重复读入数据；
  2. 生成新结点，将读入数据存放到新结点的数据域中；
  3. 从最后一个结点开始，依次将各节点插入到链表的前端。

例如，建立链表L（a，b，c，d，e）

void CreateList_H(LinkList& L, int n) {
	L = new Lnode;
	L->next = NULL;//先建立一个带头结点的单链表
	for (int i = n; i > 0; --i) {
		Lnode* p = new Lnode;
		scanf("%d", & p->data);//输入元素值
		p->next = L->next;//插入到表头
		L->next = p;
	}
}

算法的时间复杂度O(n)

建立单链表：尾插法——元素插入在链表尾部，也叫后插法。

【算法步骤】：

  1. 从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
  2. 初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。
void CreateList_F(LinkList& L, int n) {
	L = new Lnode;
	L->next = NULL;
	Lnode* r;
	r = L;//尾指针r指向头结点
	for (int i; i < n; i++) {
		Lnode* p;
		scanf("%d", &p->data);
		p->next = NULL;
		r->next = p;
		r = p;//r指向新的尾结点
	}
}

2.循环链表

循环链表：是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）。

Go 数据结构和算法篇（一）：链表 - 极客书房

优点：从表中的任一结点出发均可找到表中其他结点。

：

​ 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或P->next是否为空，而是判断它们是否等于头指针。

循环条件：

p!=NULL            --->      p!=L
p->next!=NULL      --->      p->next!=L
   单链表                       单循环链表

表的操作常常是在表的首尾位置上进行。（用尾指针操作更方便）

带尾指针循环链表的合并（将Tb合并在Ta之后）

  1. p存表头结点 p=Ta->next
  2. Tb表头连接到Ta表尾 Ta->next=Tb->next->next
  3. 释放Tb表头结点 delete Tb->next
  4. 修改指针 Tb->next=p
LinkList Connect(LinkList Ta, LinkList Tb) {
	Lnode* p;//假设Ta、Tb都是非空的单循环链表
	p = Ta->next;//①p存表头结点
	Ta->next = Tb->next->next;//②Tb表头连接Ta表尾
	delete Tb->next;//③释放Tb表头结点
	Tb->next = p;//④修改指针
	return Tb;
}

3.双向链表

双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表。

双向链表的结构可定义如下：

typedef struct DuLNode {
	int data;
	struct DuLNode* prior, * next;
}DuLNode,*DuLinkList;

Go 数据结构和算法篇（一）：链表 - 极客书房

双向循环链表：

  • 让头结点的前驱指针指向链表的最后一个结点。
  • 让最后一个结点的后继指针指向头结点。

Go 数据结构和算法篇（一）：链表 - 极客书房

双向链表结构的对称性（设指针p指向某一结点）：

p->prior->next = p = p->next->prior

在双向链表中有些操作（如：ListLength、GetElem等），因仅涉及一个方向的指针，故它们的算法与线性链表的相同。但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为O(n)。

3.1双向链表的插入

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-61aHZJTH-1689762984853)(D:\学习\学习笔记\Typora-img\image-20230719160350565.png)]

1. s->prior=p->prior;
2. p->prior->next=s;
3. s->next=p;
4. p->prior=s;

bool ListInsert_Dul(DuLinkList& L, int i, int e) {
	//在带头结点的双向循环链表L中第i个位置之前插入元素e
	DuLNode* p = new DuLNode;
	if (!(p = GetElemP_Du(L, i)))return false;
	DuLNode* s = new DuLNode;
	s->data = e;
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
	return true;
}
3.2双向链表的删除

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CAADak1q-1689762984853)(D:\学习\学习笔记\Typora-img\image-20230719162511270.png)]

1. p->prior->next=p->next;
2. p->next->prior=p->prior;

bool ListDelete_Dul(DuLinkList& L, int i, int& e) {
	DuLNode* p = new DuLNode;
	if (!(p = GetElemP_Dul(L, i))) return false;
	DuLNode* e;
	e = p->data;
	p->prior->next = p->next;
	p->next->prior = p->prior;
	delete(p);
	return true;
}

4.单链表、循环链表和双向链表的时间效率比较

查找表头节点查找表尾结点查找结点*p的前驱结点
带头结点的单链表LL->next时间复杂度O(1)从L->next依次向后遍历时间复杂度O(n)通过p->next无法找到其前驱
带头结点仅设头指针L的循环单链表L->next时间复杂度O(1)从L->next依次向后遍历时间复杂度O(n)通过p->next可以找到其前驱时间复杂度O(n)
带头结点仅设尾指针R的循环单链表R->next时间复杂度O(1)R时间复杂度O(1)通过p->next可以找到其前驱时间复杂度O(n)
带头结点的双向循环链表LL->next时间复杂度O(1)L->prior时间复杂度O(1)p->prior时间复杂度O(1)

2.3顺序表和链表的比较

链式存储结构的优点：

  • 结点空间可以动态申请和释放；
  • 数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。

链式存储结构的缺点：

  • 存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。（存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比。）
  • 链式存储结构是非随机存取结构，对任一结点的操作都要从头指针依指针链查找到该节点，这增加了算法的复杂度。

顺序表适用情况：

  1. 表长变化不大，且能事先确定变化的范围。
  2. 很少进行插入或删除操作，经常按元素位置序号访问数据元素。

链表适用情况：

  1. 长度变化较大。
  2. 频繁进行插入或删除操作。

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

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

相关文章

Python机器学习、数据统计分析在医疗中的应用

Python机器学习、数据统计分析在医疗中的应用

Python机器学习在医疗诊断领域的应用 随着人工智能技术的不断发展&#xff0c;机器学习已经在医疗领域的诊断治疗、预防等方面展现出强大的潜力。Python 作为一种广泛应用于机器学习的语言&#xff0c;在医疗领域也已经被广泛使用。本文将探讨 Python 机器学习在医疗领域的应用…
阅读更多...
apache ozone详细介绍

apache ozone详细介绍

Ozone是哪路神 Apache Ozone https://github.com/apache/ozone Ozone是Apache软件基金会下的一个项目&#xff0c;其定位是&#xff1a;一个用户大数据分析和云原生应用、具有高扩展性、强一致性的分布式Key-Value对象存储。 HDFS是业界默认的大数据存储系统&#xff0c;在业…
阅读更多...
零钱兑换 II（力扣）动态规划 JAVA

零钱兑换 II（力扣）动态规划 JAVA

给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例…
阅读更多...
git下载源码及环境搭建之前端（三）

git下载源码及环境搭建之前端（三）

学习目标&#xff1a; vue 新项目的 前端环境搭建 vue 项目在 使用 Visual Studio Code 开发前端项目环境的搭建及 相关文件的配置 操作步骤&#xff1a; 前端&#xff1a; 下图所示为开发时前端所用的编辑器 注意&#xff1a;在配置时 有时候 localhost 可能 不太好用&…
阅读更多...
AN OVERVIEW OF LANGUAGE MODELS RECENT DEVELOPMENTS AND OUTLOOK

AN OVERVIEW OF LANGUAGE MODELS RECENT DEVELOPMENTS AND OUTLOOK

LLM系列相关文章&#xff0c;针对《AN OVERVIEW OF LANGUAGE MODELS: RECENT DEVELOPMENTS AND OUTLOOK》的翻译。 语言模型综述&#xff1a;近年来的发展与展望 摘要1 引言2 语言模型的类型2.1 结构化LM2.2 双向LM2.3 置换LM 3 语言单元3.1 字符3.2 单词和子单词3.2.1 基于统…
阅读更多...
JVM——类加载和垃圾回收

JVM——类加载和垃圾回收

目录 前言 JVM简介 JVM内存区域划分 JVM的类加载机制 1.加载 双亲委派模型 2.验证 验证选项 3.准备 4.解析 5.初始化 触发类加载 JVM的垃圾回收策略 GC 一&#xff1a;找 谁是垃圾 1.引用计数 2.可达性分析 &#xff08;这个方案是Java采取的方案&#x…
阅读更多...
金融数据库的战场，太平洋保险和OceanBase打了场胜仗

金融数据库的战场，太平洋保险和OceanBase打了场胜仗

点击关注 文丨刘雨琦 “数据库的国产替代&#xff0c;必须经过严格的考虑&#xff0c;保证不会出错&#xff0c;所以大多数企业的领导层选择按兵不动或者简单扩容。因为不换就不会错&#xff0c;选了很久如果选错&#xff0c;还可能会出现重大事故。” 某银行数据库技术人员…
阅读更多...
【Vue】day02-Vue基础入门

【Vue】day02-Vue基础入门

目录 day02 一、今日学习目标 1.指令补充 2.computed计算属性 3.watch侦听器 4.综合案例 &#xff08;演示&#xff09; 二、指令修饰符 1.什么是指令修饰符&#xff1f; 2.按键修饰符 3.v-model修饰符 4.事件修饰符 三、v-bind对样式控制的增强-操作class 1.语法…
阅读更多...
AI时代图像安全“黑科技”如何助力人工智能与科技发展？

AI时代图像安全“黑科技”如何助力人工智能与科技发展？

〇、前言 7月7日下午&#xff0c;2023世界人工智能大会&#xff08;WAIC&#xff09;“聚焦大模型时代AIGC新浪潮—可信AI”论坛在上海世博中心红厅举行。人工智能等技术前沿领域的著名专家与学者、投资人和领军创业者汇聚一堂&#xff0c;共同探索中国科技创新的驱动力量。 在…
阅读更多...
【Git】Git 拉取的快速方法（含项目示例）

【Git】Git 拉取的快速方法（含项目示例）

文章目录 一、问题的提出二、问题的尝试解决 一、问题的提出 在我们之前的拉取中&#xff0c;速度可能比较慢&#xff0c;例如&#xff0c;我们要拉取CLIP的项目。 (ldm) rootI1385efcc2300601b29:/hy-tmp/latent-diffusion# pip install githttps://github.com/openai/CLIP.…
阅读更多...
JavaWeb课程设计项目实战(02)——搭建开发环境

JavaWeb课程设计项目实战(02)——搭建开发环境

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 友情提示 1、 假若你的设备已有可用的Java开发基础环境&#xff0c;则无需重新搭建 2、 假若你需重新搭建Java开发&#xff0c;请务必彻底卸载之前的环境 3、 请尽量保证与…
阅读更多...
吴恩达ML2022-用于手写数字识别的神经网络

吴恩达ML2022-用于手写数字识别的神经网络

1 用到的包 导入在这个分配过程中需要的所有包。 Numpy 是使用 Python 进行科学计算的基本软件包。Matplotlib 是在 Python 中绘制图形的流行库。tensorflow是一种流行的机器学习平台。 import numpy as np import tensorflow as tf from tensorflow.keras.models import Se…
阅读更多...
文心一言 VS 讯飞星火 VS chatgpt （59）-- 算法导论6.4 3题

文心一言 VS 讯飞星火 VS chatgpt （59）-- 算法导论6.4 3题

文心一言 VS 讯飞星火 VS chatgpt &#xff08;59&#xff09;-- 算法导论6.4 3题 三、对于一个按升序排列的包含 n 个元素的有序数组 A 来说&#xff0c;HEAPSORT 的时间复杂度是多少?如果 A 是降序呢? 文心一言&#xff1a; 对于一个按升序排列的包含 n 个元素的有序数组…
阅读更多...
windows下mingw 编译boost-1.78.0

windows下mingw 编译boost-1.78.0

1.mingw环境设置 添加C:\cygwin64\bin 到环境变量&#xff0c;cmd运行检查是否安装成功 打开cmd&#xff0c;验证&#xff1a; 2.boost下载&编译 下载&#xff1a;Boost Downloads 如果基于msvc编译器编译&#xff0c;可直接下载安装库&#xff1a;Boost C Libraries -…
阅读更多...
Hugging News #0717: 开源大模型榜单更新、音频 Transformers 课程完成发布！

Hugging News #0717: 开源大模型榜单更新、音频 Transformers 课程完成发布！

每一周&#xff0c;我们的同事都会向社区的成员们发布一些关于 Hugging Face 相关的更新&#xff0c;包括我们的产品和平台更新、社区活动、学习资源和内容更新、开源库和模型更新等&#xff0c;我们将其称之为「Hugging News」。本期 Hugging News 有哪些有趣的消息&#xff0…
阅读更多...
R语言的水文、水环境模型优化技术及快速率定方法与多模型案例实践

R语言的水文、水环境模型优化技术及快速率定方法与多模型案例实践

在水利、环境、生态、机械以及航天等领域中&#xff0c;数学模型已经成为一种常用的技术手段。同时&#xff0c;为了提高模型的性能&#xff0c;减小模型误用带来的风险&#xff1b;模型的优化技术也被广泛用于模型的使用过程。模型参数的快速优化技术不但涉及到优化本身而且涉…
阅读更多...
TCP的三次握手过程

TCP的三次握手过程

TCP 是面向连接的协议&#xff0c;所以使用 TCP 前必须先建立连接&#xff0c;而建立连接是通过三次握手来进行的。三次握手的过程如下图&#xff1a; 刚开始客户端处于 closed 的状态&#xff0c;服务端处于 listen 状态。 第一次握手&#xff1a;客户端给服务端发一个 SYN 报…
阅读更多...
Flask

Flask

简介 django是个大而全的框架&#xff0c;flask是一个轻量级的框架django内部为我们提供了非常多的组件&#xff1a;orm/session/cookie/admin/form/modelform/路由/视图/模板/中间件/分页/auth/contenttype/缓存/信号/多数据库连接flask框架本身没有太多的功能&#xff0c;路由…
阅读更多...
【MQTT】Esp32数据上传采集：最新mqtt插件（支持掉线、真机调试错误等问题）

【MQTT】Esp32数据上传采集：最新mqtt插件（支持掉线、真机调试错误等问题）

前言 这是我在Dcloud发布的插件-最完整Mqtt示例代码&#xff08;解决掉线、真机调试错误等问题&#xff09;&#xff0c;经过整改优化和替换Mqtt的js文件使一些市场上出现的问题得以解决&#xff0c;至于跨端出问题&#xff0c;可能原因有很多&#xff0c;例如&#xff0c;合法…
阅读更多...
Python 字典 get()函数使用详解，字典获取值

Python 字典 get()函数使用详解，字典获取值

「作者主页」&#xff1a;士别三日wyx 「作者简介」&#xff1a;CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」&#xff1a;小白零基础《Python入门到精通》 get函数使用详解 1、设置默认返回值2、嵌套字典取值3、get() 和 dict[key] 的区别…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站