【玩转408数据结构】线性表——线性表的顺序表示(顺序表)

知识回顾

        通过前文,我们了解到线性表是具有相同数据类型的有限个数据元素序列;并且,线性表只是一种逻辑结构,其不同存储形式所展现出的也略有不同,那么今天我们来了解一下线性表的顺序存储——顺序表。

顺序表的定义

        顺序表指的是将逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现。所以顺序表的特点就是其逻辑顺序与其物理顺序相同。

        我们不妨将设线性表L存储的起始位置为LOC(A),那么其顺序表L相对应的顺序存储如图所示:(这里sizeof是计算括号内数据元素所占用存储空间的大小)

        通过图我们也不难观察出其顺序表的特点。这里每个数据元素的存储位置都与线性表的起始位置相差该数据元素的位序个(n个)数据元素内存大小。所以我们的顺序存储结构是随机存取的存储结构。在接下来高级程序设计语言的实现中,我们决定使用数组来实现该内容(不过需要注意的是,线性表中元素的位序是从1开始的而数组中的元素下标是从0开始的)。

元素类型初始化

静态分配 

        既然我们了解了顺序表,那么接下来我们就要尝试着去实现顺序表。首先,我们需要思考的是 我们应该怎么定义出顺序表中每个元素的类型呢?这并不是一个困难的问题,由于顺序表的特点,我们这里可以使用一个数组去存放顺序表中元素;不过仅仅使用数组是不行的,因为我们很难去判断我们顺序表存储了多少个元素(顺序表的长度);那么这时,我们就需要一个附加的值(length)去记录我们顺序表的当前长度,由于我们需要两个值同时存在,这里就需要用到我们之前C语言学习时的一个关键字(struct)了。通过我们的思考,我们就可以尝试写出顺序表中的顺序存储类型了。

#define MaxSize 50 


typedef struct {
	int data[MaxSize];	//	定义元素 
	int length;		//表示当前长度 
}SqList;

        于是我们不难写出上述的代码(需要注意的是,此时data[]为int类型,这里的int可以根据我们存储元素的类型去进行更改)这里我们使用数组去存储顺序表中的元素,使用length去记录当前的长度。

        可以,使用该方法(静态分配)去分配时会出现一种问题,由于我们数组的大小和空间是固定的,我们在分配数组时,若数组的空间开的过大会导致其内存的浪费;若空间开的过小,又有可能导致空间占满,进而导致存入新数据时产生溢出、程序崩溃;这也就是我们进行静态分配的缺点。

 

思考:第三步的Length设为0,可不可以省略?  这当然是不可以的,如果我们没有对Length的值进行初始化,那么这个值在分配的时候将是随机的,这样就会导致长度计算的错误;当然写过一些代码的小伙伴可能会疑惑,我们平时也是没有初始化,他的值一直是0呀,这里主要是由于编译器的原因,我们使用的编译器自动的将其设为0了,但在考试中为了严谨性,还是建议将Length值进行初始化的。

        既然静态分配有那么多缺点,那么我们能不能使用一个更好些的办法,去尽可能的避免这些问题呢?答案当然是可以的,这里我们可以采用动态分配。 

 

动态分配

         在动态分配中,存储数组的空间实在程序执行的过程中通过动态存储分配语句分配的,一旦该数组的空间占满,就另外开辟出一块更大的存储空间,用来替换掉之前的存储空间,这样可以有效的解决上面的问题。

#define InitSize 50     //顺序表初始长度


typedef struct {
	int *data;	//	指向动态分配数组的指针 
	int MaxSize,length;		//分别表示最大容量和当前长度
}SqList;

        在进行动态的申请和释放空间时,我们可以利用下面这些关键字:

C —— malloc、free 函数

        L.data = (ElemType *) malloc (sizeof(ElemType) *InitSize) ;

C++ —— new、delete 函数

        L.data = new ElemType (InitSize) ;

 

顺序表特点:

  1. 随机存储,我们可以通过首地址和元素序号在时间复杂度为O(1)内找到指定的元素。
  2. 其存储密度高,每个节点只需存储数据元素。
  3. 顺序表逻辑上相邻的元素物理上也相邻,所以插入和删除就需要移动大量的元素。

顺序表的基本操作实现

顺序表的插入

顺序表的插入操作:

        ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e。

         我们的实现思路主要就是,首先,判断输入的第i个位置是否合法;若不合法则插入失败,若合法则将第i个元素及其后面的元素依次向后移动一个位置,然后腾出一个空位置插入新元素e,顺序表的长度增加1,及插入成功。 

//插入 
bool ListInsert(SqList &L, int i, int e){	//传入顺序表 以及从第i个位置插入一个值e 
	if(i<1 || i>L.length+1) //注:这里的i是表中的第几个元素,并非其数组下标
		return false ;
	
	if(L.length >= MaxSize)	//表满 无法插入
		return false ;
		
	 //后移
	 for(int j=L.length; j>=i; j--){	//此时j表示的是位数  
	 	L.data[j] = L.data[j-1];
	 } 
	 /*
	 for(int j=L.length-1; j>=i-1; j--){	j表示的为数组下标 
	 	L.data[j+1] = L.data[j];
	 }
	 */	
	 
	L.data[i-1] = e ;
	L.length++;
	return true ;  
}

思考:为什么代码中if语句中用length+1,而for语句中只用length呢?通过对代码的观察我们不难发现,这里if语句和for语句中的元素代表的含义并不相同,if语句中代表的是顺序表元素的位序而for语句中代表的是数组下标。

时间复杂度分析

        最好情况:直接在表尾插入元素( i=n+1 ),元素直接后移即可,时间复杂度为O(1)。

        最坏情况:在表头插入元素( i=1 ),元素需要后移n次,时间复杂度为O(n)。

        平均情况:假设p_{i}为在第 i 个位置上插入一个结点的概率,则在一个长度为n的线性表中插入一个结点时,需要移动节点的平均次数为:

\sum_{i=1}^{n+1}p_{i}(n-i+1) = \sum_{i=1}^{n+1}\frac{1}{n+1}(n-i+1) = \frac{n}{2}

        因此,顺序表插入算法的时间复杂度为O(n)。 

顺序表的删除

 顺序表的删除操作:

        ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。

        删除元素我们主要的实现思路就是,我们在删除第i个位置之后,需要将其后面的位置全部向前移动一位,这样就可以完成删除操作了。 

//删除
bool ListDelete(SqList &L, int i, int &e){
	if(i<1 || i>L.length+1)
		return false ;
	
	e = L.data[i-1] ;	//第i个元素 在数组的i-1
	
	for(int j=i; j<L.length; j++){
		L.data[j-1] = L.data[j] ;
	} 
	
	L.length = L.length-1 ;
	return true ;
	
} 
时间复杂度分析

        最好情况:直接在表尾删除元素( i=n+1 ),元素删除即可,时间复杂度为O(1)。

        最坏情况:在表头删除元素( i=1 ),元素需要前移n次,时间复杂度为O(n)。

        平均情况:假设p_{i}为在第 i 个位置上删除一个结点的概率,则在一个长度为n的线性表中删除一个结点时,需要移动节点的平均次数为:

\sum_{i=1}^{n}p_{i}(n-i) = \sum_{i=1}^{n}\frac{1}{n}(n-i) = \frac{n-1}{2}

        因此,顺序表插入算法的时间复杂度为O(n)。 

        

        由此可见,插入操作删除操作的时间主要消耗在移动元素上,而移动元素的个数与我们插入或者删除元素的位置有关,不同的插入删除位置所移动的元素个数是不同的。

顺序表的查找

按位查找

        GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

         对于按位查找,由于我们的数组下标可以很好的表示出元素的顺序,这里我们就可以直接利用数组下标与元素位序的映射关系去完成返回第i个元素的值操作。

//查找第i个位置的元素值
int GetElem(SqList L, int i) {
	return L.data[i-1];	//数组下标从0开始 
} 
时间复杂度分析

        由于是直接返回数组值的,所以不需要什么中间的计算,其时间复杂度是稳定的 O(1) 。

按值查找

        LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值的元素。 

        对于按值查找,我们可以使用循坏,去遍历一遍我们的顺序表,这样就可以找到需要返回的值了;如果遍历一遍之后仍没有发现需要查找的值,那么就返回false,证明查找失败。

//查找
//查找第一个是e的元素 返回其位序 
int LocateElem(SqList &L, int e){
	
	for(int i=0; i<L.length; i++){	//i为数组下标 
		if(L.data[i] == e)
			return i+1 ;
	}
	
	return 0; 
}
时间复杂度分析

        最好情况:查找的元素在表头,只需要查找一次即可,时间复杂度为O(1)。

        最坏情况:查找的元素不存在或者在表尾,需要查找n次,时间复杂度为O(n)。

        平均情况:假设p_{i}为查找元素在第 i 个位置上结点的概率,则在一个长度为n的线性表中查找一个结点时,需要比较节点的平均次数为:

\sum_{i=1}^{n}p_{i}i = \sum_{i=1}^{n}\frac{1}{n}i = \frac{n+1}{2}

        因此,顺序表按值查找算法的时间复杂度为O(n)。 

        

        到这里,顺序表的功能也基本完成了,当然对于这些操作,我们动态分配和静态分配的操作代码相差并不大,只是动态分配时需要多出一个增加数组长度的函数,这里在下面的完整代码展示中会体现出来,本文就不做过多描述。

顺序表完整代码

静态分配代码 

//2.2 顺序表 
#include<bits/stdc++.h>
#define MaxSize 50 

using namespace std;

typedef struct {
	int data[MaxSize];	//	定义元素 
	int length;		//表示当前长度 
}SqList;

int ex = -1 ;

//插入 
bool ListInsert(SqList &L, int i, int e){	//传入顺序表 以及从第i个位置插入一个值e 
	if(i<1 || i>L.length+1) //注:这里的i是表中的第几个元素,并非其数组下标
		return false ;
	
	if(L.length >= MaxSize)	//表满 无法插入
		return false ;
		
	 //后移
	 for(int j=L.length; j>=i; j--){	//此时j表示的是位数  
	 	L.data[j] = L.data[j-1];
	 } 
	 /*
	 for(int j=L.length-1; j>=i-1; j--){	j表示的为数组下标 
	 	L.data[j+1] = L.data[j];
	 }
	 */	
	 
	L.data[i-1] = e ;
	L.length++;
	return true ;  
}

//删除
bool ListDelete(SqList &L, int i, int &e){
	if(i<1 || i>L.length+1)
		return false ;
	
	e = L.data[i-1] ;	//第i个元素 在数组的i-1
	
	for(int j=i; j<L.length; j++){	
		L.data[j-1] = L.data[j] ;
	} 
	
	L.length = L.length-1 ;
	return true ;
	
} 

//查找
//查找第一个是e的元素 返回其位序 
int LocateElem(SqList &L, int e){
	
	for(int i=0; i<L.length; i++){	//i为数组下标 
		if(L.data[i] == e)
			return i+1 ;
	}
	
	return 0; 
}

//查找第i个位置的元素值
int GetElem(SqList L, int i) {
	return L.data[i-1];	//数组下标从0开始 
} 

int main(){
	
	SqList L ;
	for(int i=0; i<=5; i++){
		L.data[i] = i+1 ;
	}
	
	L.length = 6 ;
	
	for(int i=0; i<=L.length-1; i++)	cout << L.data[i] << "  " ;
	cout << endl;
	
	ListInsert(L, 3, 3) ;
	for(int i=0; i<=L.length-1; i++)	cout << L.data[i] << "  " ;
	cout << endl;
	
	ListDelete(L, 3, ex) ;
	cout << ex << endl ;
	for(int i=0; i<=L.length-1; i++)	cout << L.data[i] << "  " ;
	cout << endl;
	
	cout << GetElem(L, 3) << endl ; 
	cout << LocateElem(L, 3) << endl;
	
	return 0;
}

 

动态分配代码

//2.2 顺序表 
#include<bits/stdc++.h>
#define InitSize 50     //顺序表初始长度

using namespace std;

typedef struct {
	int *data;	//	指向动态分配数组的指针 
	int MaxSize,length;		//分别表示最大容量和当前长度
}SqList;

int ex = -1 ;

//初始化
void InitList(SqList &L) {
	L.data = (int *)malloc(sizeof(int));
	L.length = 0;
	L.MaxSize = InitSize;
} 

//动态增长数组
void IncreaseSize(SqList &L, int len) {	//len为需要增加长度 
	int *p = L.data;	//p记录之前数组地址 方便后期释放 
	L.data = (int *)malloc(sizeof(int) * (L.MaxSize+len)) ;	//申请一片新的区域 
	
	for(int i=0; i<L.length; i++) {
		L.data[i] = p[i];	//将值复制到新的区域 
	}
	
	L.MaxSize = L.MaxSize+len;	//更新最大的容量 
	free(p);	//释放之前动态申请的空间 
} 

//插入 
bool ListInsert(SqList &L, int i, int e){	//传入顺序表 以及从第i个位置插入一个值e 
	if(i<1 || i>L.length+1) //注:这里的i是表中的第几个元素,并非其数组下标
		return false ;
	
	if(L.length >= L.MaxSize)	//表满 无法插入
		return false ;
		
	 //后移
	 for(int j=L.length; j>=i; j--){	//此时j表示的是位数  
	 	L.data[j] = L.data[j-1];
	 } 
	 /*
	 for(int j=L.length-1; j>=i-1; j--){	j表示的为数组下标 
	 	L.data[j+1] = L.data[j];
	 }
	 */	
	 
	L.data[i-1] = e ;
	L.length++;
	return true ;  
}

//删除
bool ListDelete(SqList &L, int i, int &e){
	if(i<1 || i>L.length+1)
		return false ;
	
	e = L.data[i-1] ;	//第i个元素 在数组的i-1
	
	for(int j=i; j<L.length; j++){	
		L.data[j-1] = L.data[j] ;
	} 
	
	L.length = L.length-1 ;
	return true ;
	
} 

//查找
//查找第一个是e的元素 返回其位序 
int LocateElem(SqList &L, int e){
	
	for(int i=0; i<L.length; i++){	//i为数组下标 
		if(L.data[i] == e)
			return i+1 ;
	}
	
	return 0; 
}

//查找第i个位置的元素值
int GetElem(SqList L, int i) {
	return L.data[i-1];	//数组下标从0开始 
} 

int main(){
	
	SqList L ;
	InitList(L) ;
	IncreaseSize(L, 10); 
	
	for(int i=0; i<=5; i++){
		L.data[i] = i+1 ;
	}
	
	L.length = 6 ;
	
	for(int i=0; i<=L.length-1; i++)	cout << L.data[i] << "  " ;
	cout << endl;
	
	ListInsert(L, 3, 3) ;
	for(int i=0; i<=L.length-1; i++)	cout << L.data[i] << "  " ;
	cout << endl;
	
	ListDelete(L, 3, ex) ;
	cout << ex << endl ;
	for(int i=0; i<=L.length-1; i++)	cout << L.data[i] << "  " ;
	cout << endl;
	
	cout << GetElem(L, 3) << endl ; 
	cout << LocateElem(L, 3) << endl;
	
	return 0;
}

        两个完整代码的内容大同小异,主要就是在顺序表定义初始化时会产生些许不同,我们主要理解其产生逻辑即可,其代码的运行结果图如下:

         由代码可知,我们对其顺序表初始化为(1,2,3,4,5,6)就是我们第一行所展示的数字;之后我们在第三个位置插入3,所以第二行展示的就是插入后的结果;第三行则是输出我们在删除时需要删除的位置,紧接着我们将第三个位置的数字删除,所以第四行显示的是其删除后的结果;最后两行就是输出的为第三个位置和查找值为3的元素在第几个位置并输出。

        顺序表的内容到这里也就结束了,我们在下面尽量可以独立的去实现一下代码,这样可以更好的帮助我们理清其内部的逻辑。

 

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

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

相关文章

Linux:信号的处理

文章目录 信号处理 本篇总结的是关于信号的处理 信号处理 在之前有这样的观点&#xff1a;信号在合适的时候被处理好&#xff0c;当进程收到信号后&#xff0c;当前进程可能在做优先级更高的事&#xff0c;所以它来不及处理这个信号&#xff0c;那么就会把这个信号暂时保存起…

Apache 神禹(shenyu)源码阅读(一)——Admin向Gateway的数据同步(Admin端)

源码版本&#xff1a;2.6.1 单机源码启动项目 启动教程&#xff1a;社区新人开发者启动及开发防踩坑指南 源码阅读 前言 开了个新坑&#xff0c;也是第一次阅读大型项目源码&#xff0c;写文章记录。 在写文章前&#xff0c;已经跑了 Divide 插件体验了一下&#xff08;体…

SpringCloud-项目引入Nacos

一、安装Nacos服务 首先&#xff0c;我们需要从 Nacos 的官方网站下载发布版本。下载地址&#xff1a;Releases alibaba/nacos GitHub 选择合适的版本并下载&#xff0c;解压缩得到 Nacos 的安装包。 在解压后的 Nacos 目录中&#xff0c;找到 bin 文件夹。 用写字板编辑…

python学习23

前言&#xff1a;相信看到这篇文章的小伙伴都或多或少有一些编程基础&#xff0c;懂得一些linux的基本命令了吧&#xff0c;本篇文章将带领大家服务器如何部署一个使用django框架开发的一个网站进行云服务器端的部署。 文章使用到的的工具 Python&#xff1a;一种编程语言&…

Centos7离线安装MySQL5.7

卸载mariadb rpm -e --nodeps mariadb-libs可以使用rpm -qa|grep mariadb命令检测是否卸载完成。 关闭selinux 将/etc/selinux/config文件中的SELINUX设置为disabled下载MySql的相关rpm包 打开https://dev.mysql.com/downloads/mysql/ 选择Red Hat Enterprise Linux / Oracle L…

Codeforces Round 924 E. Modular Sequence

E. Modular Sequence 题意 对于一个长度为 n n n 的数组 a a a&#xff0c;定义它是 g o o d good good 的当且仅当&#xff1a; a 1 x a_1 x a1​x a i a i − 1 y a_{i} a_{i - 1} y ai​ai−1​y 或 a i a i − 1 m o d y i ≥ 2 a_{i} a_{i - 1} mod \hspace{…

kali最新最简单安装

之前都是用iso镜像文件的 今年好多东西都删库了&#xff0c;所有还是要主要资源的保存 去官网找下载 一般来说都是用虚拟机的 下载完会是一个压缩文件&#xff0c; 解压&#xff0c;然后操作之前需要先下载虚拟机 打开方式用虚拟机打开 kali就按装好了

【Java EE初阶十二】网络编程TCP/IP协议(一)

1. 网络编程 通过网络&#xff0c;让两个主机之间能够进行通信->就这样的通信来完成一定的功能&#xff0c;进行网络编程的时候&#xff0c;需要操作系统给咱们提供一组API&#xff0c;通过这些API来完成编程&#xff1b;API可以认为是应用层和传输层之间交互的路径&#xf…

STM32 cubemx配置DMA+空闲中断接收不定长数据

文章目录 前言一、串口空闲中断二、DMA空闲中断接收不定长数据实现思路三、STM32Cubemx配置DMA空闲中断接收不定长数据四、代码编写总结 前言 本篇文章给大家讲解一下DMA串口空闲中断接收串口不定长数据&#xff0c;之前我们也是讲解过串口接收不定长数据的&#xff0c;那么本…

详细分析Redis中数值乱码的根本原因以及解决方式

目录 前言1. 问题所示2. 原理分析3. 拓展 前言 对于这方面的相关知识推荐阅读&#xff1a; Redis框架从入门到学精&#xff08;全&#xff09;Java关于RedisTemplate的使用分析 附代码java框架 零基础从入门到精通的学习路线 附开源项目面经等&#xff08;超全&#xff09; …

力扣 第 383 场周赛 解题报告 | KMP

力扣 第 383 场周赛 解题报告 | KMP 链接 前言 一个人能走的多远不在于他在顺境时能走的多快&#xff0c;而在于他在逆境时多久能找到曾经的自己。 T1 修改矩阵 思路&#xff1a;模拟 时间复杂度&#xff1a; O ( m n ) O(mn) O(mn) class Solution:def modifiedMatrix(se…

读书笔记之《重塑大脑重塑人生》:大脑强大的可塑性

《重塑大脑重塑人生》作者是诺曼道伊奇&#xff0c;原作名: The Brain That Changes Itself: Stories of Personal Triumph from the Frontiers of Brain Science &#xff0c;于 2015-1-20出版。 诺曼•道伊奇&#xff08;Norman Doidge&#xff09;是医学博士&#xff0c;精…

leetcode题目记录

文章目录 单调栈[127. 单词接龙](https://leetcode.cn/problems/word-ladder/)[139. 单词拆分](https://leetcode.cn/problems/word-break/)[15. 三数之和](https://leetcode.cn/problems/3sum/)[140. 单词拆分 II](https://leetcode.cn/problems/word-break-ii/)[113. 路径总和…

C++ STL string类使用及实现详解

1. string简介 C语言中&#xff0c;可以用字符数组来存储字符串&#xff0c;如&#xff1a; char ch[] "hello world"; C中&#xff0c;可以使用string类对象来存储字符串&#xff0c;使用起来比C语言中的字符数组要方便得多&#xff0c;而且不用考虑容量的问题。…

C#,普洛尼克数(Pronic Number)的算法与源代码

1 普洛尼克数(pronic number) 普洛尼克数(pronic number)&#xff0c;也叫矩形数、欧波朗数(oblong number)&#xff0c;是两个连续非负整数的积&#xff0c;即mn*(n1)。第n个普洛尼克数侪是n个三角形数个两倍。 2 计算结果 3 源程序 using System; namespace Legalsoft.Tru…

c++之说_14|左值引用与右值引用

提起左右值引用我就头疼 左值&#xff1a; 1、在内存中开辟了空间的便叫左值 2、左值不一定可以赋值 如字符串常量 3、左值可以取地址 右值&#xff1a; 1、在内存中没有开辟空间的 2、右值无法取地址 如&#xff1a; 立即数&#xff08;1&#xff0c;2&#xff0c;3…

Unity类银河恶魔城学习记录7-1 P67 Sword Throw Skill State源代码

Alex教程每一P的教程原代码加上我自己的理解初步理解写的注释&#xff0c;可供学习Alex教程的人参考 此代码仅为较上一P有所改变的代码 【Unity教程】从0编程制作类银河恶魔城游戏_哔哩哔哩_bilibili Sword_Skill.cs using System.Collections; using System.Collections.Gen…

nba2k24 韩旭面补

nba2k23-24 韩旭面补 nba2k23-nba2k24通用 韩旭面补 下载地址&#xff1a; https://www.changyouzuhao.cn/9605.html

【原创 附源码】Flutter安卓及iOS海外登录--Tiktok登录最详细流程

最近接触了几个海外登录的平台&#xff0c;踩了很多坑&#xff0c;也总结了很多东西&#xff0c;决定记录下来给路过的兄弟坐个参考&#xff0c;也留着以后留着回顾。更新时间为2024年2月7日&#xff0c;后续集成方式可能会有变动&#xff0c;所以目前的集成流程仅供参考&#…

Flex布局 (上万字)超详细讲解 这篇就够了

一、Flex概述 Flex布局&#xff0c;全称为“Flexible Box Layout”&#xff0c;意为“弹性盒布局”。它是一种现代的CSS布局模式&#xff0c;旨在提供一种更有效的方式来布局、对齐和分配容器中项目之间的空间&#xff0c;即使它们的大小未知或动态变化。 Flex布局的主要特点…