首页 > 其他分享 >【数据结构】第二章——线性表(2)

【数据结构】第二章——线性表(2)

时间:2023-12-21 19:02:28浏览次数:42  
标签:初始化 顺序 线性表 int 元素 Sqlist 第二章 数据结构 表长

线性表的顺序表示

【数据结构】第二章——线性表(2)_顺序表

导言

大家好,很高兴又和各位见面啦!!!在上一个篇章中,我们简单了解了一下线性表的基础知识以及一下重要的术语。在今天的篇章中我们将来开始正式介绍线性表的顺序存储——又称顺序表。我们将会在本章介绍什么是顺序表,对于顺序表的操作我们又应该如何实现。接下来,我们就来开始今天的内容吧!!!

1、顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻

在上一个篇章中我们有提到数组是一种线性表,我们在数组篇章中有介绍过,数组元素在内存上是由低地址到高地址进行连续存放的,所以数组元素不仅满足逻辑上相邻,也满足在物理位置上相邻,因此数组就是一种顺序表

通常在高级程序语言中,我们会使用数组来描述线性表的顺序存储结构。假设线性表L存储的起始位置为LOC(A),每个元素占用内存空间大小为sizeof(ElemType),则表L所对应的顺序存储如下图所示:

【数据结构】第二章——线性表(2)_初始化_02

顺序表的元素在物理位置上相邻体现在以下两点:

  1. 两个相邻元素的地址之间相差的大小刚好就是一个元素所占内存空间的大小
  2. 从第二个元素开始,其它的每个元素和首元素的地址之间相差的大小刚好是元素的位序减1与元素所占内存空间大小的乘积,也就是对应的数组下标×元素所占看内存空间大小

因此,顺序表中的任意一个数据元素都是可以进行随机存取的,所以线性表的顺序存储结构是一种随机存取的存储结构

下面我们通过C语言来实现一个顺序表;

2. 顺序表的实现

我们想要实现一个顺序表是可以通过两种方式来实现:

  • 确定了顺序表的最大长度时,可以采取静态分配的方式实现顺序表;
  • 顺序表的最大长度会发生变化时,可以采取动态分配的方式实现顺序表;

接下来我们来详细介绍这两种实现方式;

2.1 静态分配

在已知最大长度时,我们可以通过定义一个静态数组来实现一个顺序表。具体的实现格式如下所示:

//顺序表的静态实现方式
#define MaxSize//通过#define定义一个标识符常量作为顺序表的最大表长
//通过定义一个结构体作为顺序表
typedef struct Sqlist
{
	Elemtype date[MaxSize];
	//Elemtype——数组元素的数据类型
	//date[MaxSize]——静态数组存放数据元素
	int length;//顺序表的当前表长
}Sqlist;//Sq:sequence——顺序,序列
//Sqlist——顺序表,顺序表的名字,这里根据实际情况进行自定义

从这个格式中我们可以看到,要实现一个静态顺序表,我们需要先确定顺序表的最大表长、顺序表的当前表长以及顺序表数据元素的数据类型。这些内容缺一不可,下面我们就来尝试着创建一个整型的顺序表;

2.1.1 整型顺序表的创建

//整型顺序表的静态实现
#define MaxSize 10//最大表长为10
typedef struct
{
	int date[MaxSize];//通过整型数组存取整型数据元素
	int length;//当前表长
}int_Sqlist;//顺序表命名为整型顺序表
int main()
{
	int_Sqlist L;//创建一个顺序表
	return 0;
}

这里我们创建了一个整型数据类型的顺序表,顺序表的最大长度为10,也就是,顺序表中最多只能存放10个元素。

2.1.2 顺序表的初始化

在创建好顺序表后,我们还需要对顺序表进行初始化,如下所示:

//初始化顺序表
void InitList(int_Sqlist* L)
{
	for (int i = 0; i < MaxSize; i++)
		//通过元素下表访问表中的各个元素
		L->date[i] = 0;//当前表中各元素初始化为0
	L->length = 0;//当前表长为0
}
int main()
{
	int_Sqlist L;//创建一个顺序表
	InitList(&L);//通过传址传参实现对顺序表中各个元素的修改
	return 0;
}

通过定义一个初始化函数,我们就能完成对表中的各个元素进行初始化,以及表长的初始化。此时我是因为今天不对其他操作进行演示,所以当前表长我是将其初始化为0。此时我们是可以不用对表中的元素进行初始化的,因为当前表长为0时,表示的是此时表中不存在任何元素。

2.1.3 顺序表的打印

在完成初始化之后,我们还可以将顺序表中的全部元素打印出来,如下所示:

//打印顺序表中的各个元素
void PrintList(int_Sqlist L)
{
	for (int i = 0; i < MaxSize; i++)
		printf("L.date[%d] = %d\n", i, L.date[i]);
}
int main()
{
	int_Sqlist L;//创建一个顺序表
	InitList(&L);//通过传址传参实现对顺序表中各个元素的修改
	PrintList(L);//通过传值传参实现对顺序表中的各个元素进行打印
	return 0;
}

这里我们需要注意一个问题,此时顺序表的当前表长为0,我们通过现在的打印方式是属于违规打印的,正常复合要求的打印方式应该是:

//打印顺序表中的各个元素
void PrintList(int_Sqlist L)
{
	//for (int i = 0; i < L.length; i++)//通过当前表长来打印表中的各个元素
	for (int i = 0; i < MaxSize; i++)//通过最大表长打印表中的元素属于违规打印
		printf("L.date[%d] = %d\n", i, L.date[i]);
}
int main()
{
	int_Sqlist L;//创建一个顺序表
	InitList(&L);//通过传址传参实现对顺序表中各个元素的修改
	PrintList(L);//通过传值传参实现对顺序表中的各个元素进行打印
	return 0;
}

当前表长为0,就表示此时的顺序表中未存放任何元素,所以没有元素打印,但是我们可以先尝试着违规打印一次,看看初始化的效果:

【数据结构】第二章——线性表(2)_顺序表_03

可以看到,此时我们很好的进行了表中各元素的初始化与打印。当然因为我们正常打印是通过当前表长进行打印的,所以对表中各元素的初始化可以省略,只对当前表长进行初始化就行。不过为了避免不必要的麻烦,建议大家还是在初始化时对表中各个元素也完成初始化。

2.2 动态分配

当我们在创建顺序表时,顺序表的最大表长在后续的操作中可能会出现修改的情况,如果此时我们继续通过静态分配来创建顺序表时,当表中的元素个数超过最大表长时,就会导致数组越界,从而导致程序崩溃。为了更好的处理这种表长会变化的情况,我们可以通过malloc/calloc/realloc/free这些来创建一个动态顺序表。具体的实现格式如下:

//顺序表的动态实现方式
#define InitSize//通过#define定义一个标识符作为动态顺序表的初始表长
typedef struct Sqlist
{
	ElemType* date;
	//ElemType——数据元素的数据类型
	//ElemType*——指针类型
	//date——指针变量,通过指针来指向顺序表
	int MaxSize, length;
	//MaxSize——动态顺序表的最大表长
	//length——动态顺序表的当前表长
}Sqlist;//动态顺序表的名字

在通过动态分配的方式实现顺序表时,我们需要确定的元素与静态实现的方式稍有不同。在动态分配的实现中,我们需要确定:初始的表长,指向数据元素的指针,顺序表的最大表长,顺序表的当前表长以及数据元素的数据类型

当然,这里的最大表长是会在后续的操作中不断变化的,所以这里我们是以整型变量的方式来确定最大表长,如果通过#define来定义的话,此时定义的是一个不可被修改的常量,这时就无法完成对最大表长的修改了。

2.2.1 整型顺序表的创建

下面我们通过动态分配的方式来创建一个整型顺序表,如下所示:

#define InitSize 5//初始表长为5
typedef struct
{
	int* date;//通过指针指向顺序表
	int MaxSize, length;//定义顺序表的最大表长和当前表长
}Int_Sqlist;//顺序表命名为整型顺序表
int main()
{
	Int_Sqlist L;//创建一个整型顺序表L
	return 0;
}

现在我们已经创建好了一个整型顺序表L,接下来我们就要对顺序表进行初始化了;

2.2.2 顺序表的初始化

与静态分配不同的是,动态分配在初始化时,我们要对顺序表进行动态内存的空间申请,格式如下:

//动态内存申请格式
L->date = (ElemType*)malloc(InitSize * sizeof(ElemType));
//L——创建的顺序表
//date——指向顺序表的指针
//ElemType*——指向顺序表的指针的数据类型
//malloc——分配内存块的函数
//InitSize——初始表长
//sizeof(ElemType)——每个元素所占内存空间大小

因此我们在动态分配时的初始化如下所示:

//初始化顺序表
void InitList(Int_Sqlist* L)
{
	//进行动态内存空间申请
	L->date = (int*)malloc(InitSize * sizeof(int));
	L->length = 0;//当前表长初始化为0
	L->MaxSize = InitSize;//最大表长初始化为初始表长
}
int main()
{
	Int_Sqlist L;//创建一个整型顺序表L
	InitList(&L);//初始化顺序表
	return 0;
}

此时我们就在内存空间中申请了5个连续的整型空间给顺序表进行使用;

2.2.3 修改顺序表的长度

当我们在完成初始化后,如果我们想要修改此时的表长,我们可以通过malloc/calloc进行空间的重新申请,也可以直接通过realloc直接对表长进行修改,如下所示:

//修改表长
void IncreaseSize(Int_Sqlist* L, int len)
{
	//通过realloc修改表长
	L->date = (int*)realloc(L->date, L->MaxSize + len);
	---------------------------------------------------
	//通过malloc/calloc修改表长
	//创建整型指针p指向顺序表原先的空间
	int* p = L->date;
	//通过malloc向内存申请新的空间
	L->date = (int*)malloc((L->MaxSize + len) * sizeof(int));
	//将原先空间中的元素复制到新的空间中
	for (int i = 0; i < L->length; i++)
		L->date[i] = p[i];
	//释放原先申请的空间
	free(p);
}
int main()
{
	Int_Sqlist L;//创建一个整型顺序表L
	InitList(&L);//初始化顺序表
	IncreaseSize(&L, 5);//修改表长
	//正数代表增加表长
	//负数代表减少表长
	return 0;
}
  • 当我们直接通过realloc对表长进行修改时,我们是不需要创建临时的指针变量的;
  • 当我们通过malloc或者calloc来修改表长时,我们需要按照以下的步骤完成修改:
  • 我们需要通过临时的指针变量来指向原先的空间,并通过malloc或者calloc申请新的空间;
  • 在申请完新的空间后,我们再通过临时指针将原先空间的内容复制到新的空间中;
  • 最后将原先的空间通过free给释放掉。

结语

现在咱们对顺序表的静态分配和动态分配与表长的修改就介绍完了,希望这篇内容能帮助大家更加容易理解顺序表的创建与表长的修改过程。

对于动态内存管理相关的内容,后面我会给大家进行详细的介绍,现在还不了解动态内存管理的朋友不要着急,我们先阶段只需要了解顺序表的两种创建方式就可以了。

在下一篇中,我会详细介绍顺序表的其它操作,大家记得关注哦!!!最后感谢各位的翻阅,咱们下一篇再见!!!

标签:初始化,顺序,线性表,int,元素,Sqlist,第二章,数据结构,表长
From: https://blog.51cto.com/u_16231477/8926108

相关文章

  • 【算法】【线性表】移除元素
    1 题目给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。示例1:输......
  • 金牌导航-数据结构优化DP
    数据结构优化DP例题A题解设\(f_{i,j}\)表示以第\(i\)位为结尾,长度为\(j\)的严格单调上升子序列的数量。那么显然有\(f_{i,j}=\sum_{k=1}^{i-1}f_{k,j-1}\times(a_k<a_i)\)然后发现这玩应\(O(n^2m)\)直接寄掉了。考虑优化。发现只有当\(a_k<a_i\)时才会有贡献。......
  • python 数据结构与算法知识图
    1.算法思想:递归、分治(归并排序、二分查找、快速排序)、贪心(贪心策略排序+当前最优)、动态规划(最优子结构+递推式)、回溯(解空间:排列树+子集树、深度搜索+剪枝)、分支限界(解空间:排列树+子集树、广度搜索+剪枝))2.排序算法:(low:冒泡、插入、选择;mid:快排、归并、堆排(完全二叉树),其他:桶排序、基......
  • Databend 源码阅读: Meta-service 数据结构
    作者:张炎泼(XP)DatabendLabs成员,Databend分布式研发负责人https://github.com/drmingdrmer引言Databend是一款开源的云原生数据库,采用Rust语言开发,专为云原生数据仓库的需求而设计。面向云架构:Databend是完全面向云架构的数据库,可以在云环境中灵活部署和扩展简介|......
  • Databend 源码阅读: Meta-service 数据结构
    作者:张炎泼(XP)DatabendLabs成员,Databend分布式研发负责人https://github.com/drmingdrmer引言Databend是一款开源的云原生数据库,采用Rust语言开发,专为云原生数据仓库的需求而设计。面向云架构:Databend是完全面向云架构的数据库,可以在云环境中灵活部署和扩展简介|......
  • 数据结构
    数据结构有:1.数组;2.栈;3.队列;4.链表(单链表、双向链表、循环链表);5.数;6.散列表;7.堆;8.图。一、数组内存连续,可通过元素下标访问。二、栈先进后出三、队列先进先出四、链表物理存储不连续,因为存储了相邻元素的物理地址,所以逻辑上连续。五、树每个节点有零个或多个子节点;没......
  • 【面试官版】【持续更新中】融合滤波算法+数据结构+激光视觉SLAM+C++面试题汇总
    C++部分什么时候需要写虚函数、什么时候需要写纯虚函数?只继承接口为纯虚函数强调覆盖父类重写,或者父类也需要实现一定的功能,为虚函数指针传参和引用传参区别?引用传参本质上是传递原参数地址,指针传参本质还是值传递,生成拷贝指针,拷贝指针和原指针指向的为同一块内存。因此改变......
  • 第二章:SpringMVC的配置文件(web.xml)及访问页面
    一、开发环境二、创建maven工程三、默认方式配置web.xml四、扩展方式配置web.xml五、创建控制器六、配置springMVC配置文件七、访问首页八、访问指定页面九、总结......
  • 数据结构之<图>的介绍
    图(Graph)的概念:在数据结构中,图是由节点(顶点)和边组成的非线性数据结构。图用于表示不同对象之间的关系,其中节点表示对象,边表示对象之间的连接或关系。1.图的基本组成元素:节点(Vertex或Node):表示图中的实体或对象。节点可以有不同的属性和值。在某些情况下,节点也被称为顶点。边(Edge):......
  • 数据结构 —— 线性表、栈、队列
    一、算法复杂度 【2011】设n是描述问题规模的非负整数,下面的程序片段时间复杂度是()x=2;while(x<n/2)x=2*x;AO(log2(n))  BO(n) CO(nlog2(n)) DO(n^2) 答案:A解析:x=2^i=n/2i=log2(n/2) 【2012】求整数n(n>=0)的阶乘的算法......