【玩转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-1for(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-1for(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-1for(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的元素在第几个位置并输出。

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

 

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

上个月刚跟男朋友一起买了个三百万的房子,准备明年结婚,这个月他突然被裁了...

职场变动&#xff0c;尤其是裁员&#xff0c;已经成为我们无法忽视的现实。不管你是互联网大佬&#xff0c;还是刚入行的新人&#xff0c;这个问题都可能突如其来&#xff0c;影响到你的生活和计划。 想象一下&#xff0c;你和你的另一半刚刚为了将来的幸福生活&#xff0c;拼尽…

使用 Windows 11/10 上的最佳 PDF 转 Word 转换器释放 PDF 的潜力

毫无疑问&#xff0c;PDF 是最好的文档格式之一&#xff0c;但就像其他格式一样&#xff0c;有时它们确实会带来一些限制。例如&#xff0c;在某些情况下&#xff0c;您可能想要将 PDF 转换为 Word。在这种情况下&#xff0c;您始终可以借助 PDF 到 Word 转换器的帮助。 为了说…

python - 模块使用详解

前言 Python有非常强大的第三方库&#xff0c;也有非常多的内置模块帮助开发人员实现某些功能&#xff0c;无需开发人员自己造轮子。本文介绍Python的模块。 什么是模块 模块简单来说就是一系列功能的集合体&#xff0c;如果将程序的开发比喻成拼图&#xff0c;模块就是各种…

12.atoi函数

文章目录 函数简介函数原型 代码运行 函数简介 函数原型 int atoi(char const *string);函数把字符转化为正数 代码运行 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h>int main() {int ret 0;char str[20] "112233";ret …

Day 43 | 动态规划 1049. 最后一块石头的重量 II 、494. 目标和 、 474.一和零

1049. 最后一块石头的重量 II 题目 文章讲解 视频讲解 思路&#xff1a;dp[j] 表示容量为 j 的背包&#xff0c;最多可以背最大重量为dp[j]。 class Solution {public int lastStoneWeightII(int[] stones) {int sum 0;for (int i 0; i < stones.length; i) {sum stone…

Django模型层part two - 多表关系创建和多表操作

前言 继续上面一篇文章的内容&#xff0c;本文介绍多表操作。使用django ORM可以创建多表关系&#xff0c;并且也支持多张表之间的操作&#xff0c;以创建表关系和查询两部分说明django ORM的多表操作。以作者、图书、出版社和作者信息几张表作为案例进行说明。 创建表关系 …

视觉slam十四讲学习笔记(三)李群与李代数

1. 理解李群与李代数的概念&#xff0c;掌握 SO(3), SE(3) 与对应李代数的表示方式。 2. 理解 BCH 近似的意义。 3. 学会在李代数上的扰动模型。 4. 使用 Sophus 对李代数进行运算。 目录 前言 一、李群李代数基础 1 群 2 李代数的引出 3 李代数的定义 4 李代数 so(3…

Docker笔记-搭建Python环境、安装依赖、打包镜像、导入镜像、编写bash脚本灵活调用

说明 适合无联网的机器及多Python的机器进行部署。 制作docker版Python环境 有网络及有docker的,拉取指定版本的python如: docker pull python:3.7 安装好后进入容器: docker run -it <name> /bin/bash 使用pip安装各种依赖: pip install <name> pip in…

Python访问数据库

目录 SQLite数据库 SQLite数据类型 Python数据类型与SQLite数据类型的映射 使用GUI管理工具管理SQLite数据库 数据库编程的基本操作过程 sqlite3模块API 数据库连接对象Connection 游标对象Cursor 数据库的CRUD操作示例 示例中的数据表 无条件查询 有条件查询 插入…

重学JavaScript高级(十二):async/await-事件循环-面试高频

async/await-事件循环 前面我们学习了生成器和迭代器&#xff0c;那么在本篇文章中&#xff0c;我们主要讲解生成器与Promise的结合使用&#xff0c;从而引出async/await语法&#xff0c;同时会涉及面试中频次最高的一个知识点&#xff1a;事件循环 生成器与异步处理 首先需要…

【Chrono Engine学习总结】4-vehicle-4.1-vehicle的基本概念

由于Chrono的官方教程在一些细节方面解释的并不清楚&#xff0c;自己做了一些尝试&#xff0c;做学习总结。 1、基本介绍 Vehicle Overview Vehicle Mannel Vehicle的官方demo 1.1 Vehicle的构型 一个车辆由许多子系统构成&#xff1a;悬挂、转向、轮子/履带、刹车/油门、动…

搜索专项---最短路模型

文章目录 迷宫问题武士风度的牛抓住那头牛 一、迷宫问题OJ链接 本题思路:只需要记录各个点是有哪个点走过来的&#xff0c;就能递推得出路径。记录前驱假设从 1,1 这个点向下走到了2, 1&#xff0c;则将2,1这个点的前驱记为1,1。这样&#xff0c;将整张地图 bfs 后&#xff0c…

C++进阶(十五)C++的类型转换

&#x1f4d8;北尘_&#xff1a;个人主页 &#x1f30e;个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上&#xff0c;不忘来时的初心 文章目录 一、C语言中的类型转换二、为什么C需要四种类型转换三、C强制类型转换1、static_cast2、reint…

【必看】Onlyfans如何使用搜索功能?Onlyfans如何搜索博主?如何在OnlyFans搜索HongkongDoll

1. 什么是Onlyfans OnlyFans是一种内容订阅服务平台&#xff0c;它成立于2016年。 它允许内容创作者在平台上面分享自己的创作&#xff0c;如图片、视频等等&#xff0c;用户需要支付订阅费用才能查看创作者的内容。此外&#xff0c;用户还可以通过打赏的方式来让创作者为自己…

[Python进阶] 制作动态二维码

11.1 制作动态二维码 二维码&#xff08;QR code&#xff09;是一种二维条形码&#xff08;bar code&#xff09;&#xff0c;它的起源可以追溯到20世纪90年代初。当时&#xff0c;日本的汽车工业开始使用一种被称为QR码的二维条码来追踪汽车零部件的信息。 QR码是Quick Respo…

代码随想录算法训练营Day55|392.判断子序列、115.不同的子序列

目录 392.判断子序列 思路 ​算法实现 115.不同的子序列 思路 算法实现 总结 392.判断子序列 题目链接 文章链接 思路 利用动规五部曲进行分析&#xff1a; 1.确定dp数组及其下标含义&#xff1a; dp[i][j] 表示以下标i-1为结尾的字符串s&#xff0c;和以下标j-1为结尾的…

controlnet的模型下载

controlnet模型有sd15和基于sd15上的fp16版本 fp16版本的模型比较小&#xff0c;但功能效果跟sd15是一样的 controlnet的fp16模型下载地址 https://huggingface.co/comfyanonymous/ControlNet-v1-1_fp16_safetensors/tree/main controlnet的openpose里&#xff0c;有个dw_open…

寒假作业

手写盗版微信登入界面 #include "mainwindow.h" #include "ui_mainwindow.h"MainWindow::MainWindow(QWidget *parent): QMainWindow(parent), ui(new Ui::MainWindow) {ui->setupUi(this);this->resize(421,575);this->setFixedSize(421,575);th…

AI:126-基于深度学习的人体情绪识别与分析

🚀点击这里跳转到本专栏,可查阅专栏顶置最新的指南宝典~ 🎉🎊🎉 你的技术旅程将在这里启航! 从基础到实践,深入学习。无论你是初学者还是经验丰富的老手,对于本专栏案例和项目实践都有参考学习意义。 ✨✨✨ 每一个案例都附带有在本地跑过的关键代码,详细讲解供…