首页 > 其他分享 >数据结构入门 — 顺序表详解

数据结构入门 — 顺序表详解

时间:2023-11-10 13:05:48浏览次数:53  
标签:顺序 入门 元素 pos assert pc 详解 数据结构 size


前言

数据结构入门 — 顺序表详解
关注博主,后期持续更新系列文章
文章末尾有源码
*****感谢观看,希望对你有所帮助*****



文章目录

  • 前言
  • 一、顺序表
  • 1. 顺序表是什么
  • 2. 优缺点
  • 二、概念及结构
  • 1. 静态顺序表
  • 2. 动态顺序表
  • 三、顺序表接口实现(代码演示)
  • 1. 动态存储结构
  • 2. 顺序表打印
  • 3. 顺序表初始化
  • 4. 检查空间大小
  • 5. 增删查改接口
  • 6. 顺序表销毁
  • 四、所有文件代码
  • 1. Gitee链接
  • 总结



一、顺序表

1. 顺序表是什么

顺序表是连续存储的 顺序表是一种线性表的数据结构,它的数据元素按照一定次序依次存储在计算机存储器中,使用连续的存储空间来存储。顺序表中每个数据元素的位置都有一个序号,这个序号也称为元素在顺序表中的下标。顺序表的特点是:元素的逻辑顺序与物理顺序相同,支持随机访问,插入和删除元素的时间复杂度为O(n),查找元素的时间复杂度为O(1)。

2. 优缺点

优点 优点是访问速度快,因为它的元素在内存中是连续存储的,可以直接通过下标访问,而且不需要额外的空间来存储指向下一个节点的指针。
缺点 缺点是插入和删除元素的时间复杂度为O(n),因为需要移动其他元素的位置,而且不利于动态扩展容量。


二、概念及结构

元素的类型、元素的个数、数组的大小和数组的指针 顺序表的实现需要预留一段连续的存储空间来存储所有的元素,目前常见的实现方式是使用数组来实现顺序表。数组的地址是连续的,因此可以通过数组下标进行快速访问元素。为了实现顺序表,需要定义一个数据结构,包含元素的类型、元素的个数、数组的大小和数组的指针等信息。

1. 静态顺序表

静态顺序表是一种使用连续存储空间实现的线性表结构,其特点是在创建表时就需要预先分配好固定长度的存储空间,表长也就固定了下来,不能动态扩展或缩小。

在静态顺序表中,数据元素按照顺序依次存放,每个元素都占用相同的存储空间,而且元素在内存中的地址也是连续的。

数据结构入门 — 顺序表详解_c语言

2. 动态顺序表

动态顺序表是一种线性表的实现方式,它在静态顺序表的基础上,将存储空间由固定长度改为动态分配。

当动态顺序表中存放的元素个数达到当前存储空间的上限时,可以重新申请更大的空间来存放更多的元素,因此动态顺序表的长度是可变的。动态顺序表的实现通常采用数组形式,通过realloc函数来动态分配空间。

数据结构入门 — 顺序表详解_数据结构_02


三、顺序表接口实现(代码演示)

1. 动态存储结构

即定义顺序表的结构。由动态开辟的数组、有效数据个数和容量空间的大小组成

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* a;  // 指向动态开辟的数组
	int size;		// 有效数据个数
	int capacity;	// 容量空间的大小
}SL;

2. 顺序表打印

使用循环,将顺序表遍历一遍,进行打印

//打印顺序表
void SLPrint(SL* pc)
{
	assert(pc);
	int i = 0;
	for (i = 0; i < pc->size; i++)
	{
		printf("%d ", pc->a[i]);
	}
	printf("\n");
}

3. 顺序表初始化

在顺便表初始化时,先用malloc开辟4个空间,如果开启失败报错并返回

//初始化顺序表
void SLInit(SL *pc)
{
	assert(pc);
	//开启内存  
	pc->a=(SLDataType*)malloc(sizeof(SLDataType) * 4);
	//检查是否开辟成功
	if (pc->a==NULL)
	{
		perror("SLInit");
		//return;
		exit(-1);
	}
	pc->capacity = 4;
	pc->size = 0;
}

4. 检查空间大小

检查空间,当顺序表内的数据等于初始化开辟的空间时,再开辟4个空间(用realloc开辟乘2的空间)

//检查内存容量
void SLCheckCapacity(SL* pc)
{
	assert(pc);
	if (pc->size == pc->capacity)
	{
		SLDataType*tem = (SLDataType*)realloc(pc->a, sizeof(SLDataType)*2*pc->capacity);  //要乘以2
		if (tem == NULL)
		{
			perror("SLCheckCapacity");
			exit(-1);
		}
		pc->a = tem;
		pc->capacity *= 2;
	}
}

5. 增删查改接口

以增删查改顺序依次编排头插:
头插,即在顺序表头部进行插入数值,在SLCheckCapacity检查空间是否充足后,进行插入数值

//头插
void SLPushFront(SL* pc,SLDataType x)
{
	assert(pc);
	SLCheckCapacity(pc);
	int end = pc->size - 1;
	while (end >=0)
	{
		pc->a[end + 1] = pc->a[end];
		--end;
	}
	pc->a[0] = x;
	pc->size++;
}

尾插:
尾插,即找到顺序表的尾,下标为pc->size的位置插入数值

//尾插
void SLPushBack(SL* pc, SLDataType x)
{
	assert(pc);
	SLCheckCapacity(pc);
	pc->a[pc->size] = x;
	pc->size++;
}

头删:
头删,将后面的数值依次向前覆盖。覆盖时要注意顺序,将在前的先覆盖,防止数组丢失,然后将顺序表的size(数据个数减一)

//头删
void SLPopFront(SL* pc)
{
	assert(pc);
	int start = 1;
	while (start < pc->size)
	{
		pc->a[start] = pc->a[start + 1];
		++start;
	}
	pc->size--;
}

尾删:
尾删,即将有效数据减一,直接将pc所指向的size减一

//尾删
void SLPopBack(SL* pc)
{
	assert(pc->size > 0);

	pc->size--;
}

查找:
查找方法有很多种,这里使用暴力查找,将顺序表遍历一遍,找到要找的元素并返回下标

//查找数字位置
int SLFind(SL* pc, SLDataType x)
{
	int i = 0;
	for (i = 0; i < pc->size; i++)
	{
		if (pc->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

指定位置插入
这里配合查找函数使用,找到要找的数值的下标,进入下列函数,将pos之后的值依次下向后移动,在pos位置插入数值

// 在pos位置插入x
void SLInsert(SL* pc, int pos, SLDataType x)
{
	assert(pc);
	assert(pos >= 0 && pos <= pc->size);
	SLCheckCapacity(pc);
	int end = pc->size - 1;
	while (end >= pos)

	{

		pc->a[end + 1] = pc->a[end];
		--end;
	}
	pc->a[pos] = x;
	pc->size++;

}

指定位置删除
这里配合查找函数使用,找到要找的数值的下标,进入下列函数,将pos位置后的数值依次向前覆盖

// 删除pos位置的值
void SLErase(SL* pc, int pos)
{
	assert(pc);
	assert(pos >= 0 && pos < pc->size);
	int start = pos+ 1;
	while (start < pc->size)
	{
		pc->a[start - 1] = pc->a[start];
		++start;

	}
	pc->size--;
}

更改指定位置
这里配合查找函数使用,找到要找的数值的下标,进入下列函数,将pos位置的值进行修改

//更改制定位置的数字
void SLModify(SL* pc, int pos, SLDataType x)
{
	assert(pc);
	assert(pos >= 0 && pos < pc->size);
	pc->a[pos] = x;
 }

6. 顺序表销毁

顺序表进行销毁,将开辟的数值空间进行释放,并置为空(NULL)将空间和数据个数置为0 ,这样顺序表就销毁完成

//销毁释放内存
void SLDestroy(SL* pc)
{
	assert(pc);
	free(pc->a);
	pc->a=NULL;
	pc->capacity = 0;
	pc->size=0;
}

四、所有文件代码

1. Gitee链接

***查看所有代码*** 点击右边蓝色文字 DuckBro Gitee 代码仓库


总结

顺序表是一种线性表,它的重点是:

  1. 物理结构:顺序表的数据元素在内存中是连续存放的,即使用一段连续的存储空间来存储线性表的元素。
  2. 逻辑结构:顺序表是一种线性表,它的元素在逻辑上是依次排列的。
  3. 数据操作:顺序表支持基本的数据操作,包括插入、删除、查找等操作。其中,插入和删除操作需要移动大量元素,时间复杂度较高,而查找操作可以通过使用二分查找等算法来提高效率。
  4. 容量管理:顺序表的容量是由数组的长度来决定的。如果数组长度不够,顺序表需要进行扩容操作,如果数组长度过长,会浪费内存空间。
  5. 性能特点:由于顺序表的数据元素在内存中是连续存放的,所以顺序表具有快速的随机访问能力,但插入、删除操作较为耗时。因此,适合于需要随机访问元素,但不频繁进行插入、删除操作的场景。顺序表

如这篇博客对大家有帮助的话,希望 三连 支持一下 !!! 如果有错误感谢大佬的斧正 如有 其他见解发到评论区,一起学习 一起进步。


标签:顺序,入门,元素,pos,assert,pc,详解,数据结构,size
From: https://blog.51cto.com/u_16225555/8296004

相关文章

  • 数据结构入门 — 链表详解_双向链表
    前言数据结构入门—双向链表详解*关注博主,后期持续更新系列文章文章末尾有源码*****感谢观看,希望对你有所帮助*****系列文章第一篇:数据结构入门—链表详解_单链表第二篇:数据结构入门—链表详解_双向链表第三篇:数据结构入门—链表详解_循环链表文章目录前言系列文章什......
  • Pandas入门
    安装库pipinstallpandas#读取.xlspipinstallxlrd#读取.xlsxpipinstallopenpyxl案例1importpandasaspdpath=r"C:\work\test.xlsx"data=pd.read_excel(path)print(data)读取.csv文件importpandasaspddata=pd.read_csv(r"C:\\work......
  • 【视频课】纯新手如何快速掌握深度学习必备的Python基础能力,150分钟助你入门!...
    前言欢迎大家关注有三AI的视频课程系列,我们的视频课程系列共分为5层境界,内容和学习路线图如下:第1层:掌握学习算法必要的预备知识,包括Python编程,深度学习基础,数据使用,框架使用。第2层:掌握CV算法最底层的能力,包括模型设计基础,图像分类,模型分析。第3层:掌握CV算法最核心的方向,包括图像分......
  • 【ROS2机器人入门到实战】生命周期节点
    3.生命周期节点写在前面当前平台文章汇总地址:ROS2机器人从入门到实战获取完整教程及配套资料代码,请关注公众号<鱼香ROS>获取教程配套机器人开发平台:两驱版|四驱版为方便交流,搭建了机器人技术问答社区:地址fishros.org.cn以前在ROS1中,节点的启动顺序无法被控制,这对整个机器人系统......
  • Kafka入门
    Kafka定义Kafka是一个分布式的流处理平台,它具有以下特性:磁盘保存数据伸缩性术语生产者生产者是消息的创造者,可以指定Topic,Partion,Key,Value,并将消息发送到Kafka集群中的Broker。消费者消费者负责从Kafka集群中读取消息。需要设置偏移量一个分区里面,每个消息的偏移......
  • k8s入门学习
    k8s入门https://kubernetes.io/zh-cn/docs/tutorials/hello-minikube/minikube启动集群minikubestart创建实例kubectlcreatedeploymentgin--image=gin_demo:v1会创建相对应的pod和deployment此时服务端口只能内部集群访问端口暴露使用expose将服务端口暴露进行访......
  • 【零基础速领】全套Android零基础入门指南(PDF文档+全套视频),Android Studio安装教程
    Android开发的入门可分成两个大的阶段,第一个语言的学习,第二个Android框架的学习。语言的学习Android开发目前主要有两种语言,java和kotlin,kotlin是目前google官方的首推语言,但个人还是建议先学java,因为至少在未来的几年内,公司的项目肯定是还会有大量的java代码,你至少需要能看懂,能去......
  • Android入门教程 | Fragment 基础概念
    什么是Fragment?Fragment,直译为“碎片”,“片段”。Fragment表示FragmentActivity中的行为或界面的一部分。可以在一个Activity中组合多个片段,从而构建多窗格界面,并在多个Activity中重复使用某个片段。可以将片段视为Activity的模块化组成部分,它具有自己的生命周期,能接收自......
  • Android零基础入门 | 广播机制 Broadcast
    Android应用可以通过广播从系统或其他App接收或发送消息。类似于订阅-发布设计模式。当某些事件发生时,可以发出广播。系统在某些状态改变时会发出广播,例如开机、充电。App也可发送自定义广播。广播可用于应用间的通讯,是IPC的一种方式。广播的种类广播的种类也可以看成是广播的属性......
  • OpenGL 投光物详解
    1.投光物继续上一节的流程,到目前为止,我们介绍的都是点光源。但是现实世界中,光源的类型却要相对复杂一些。大概会有这么几种形式:定向光、点光源、聚光等等。 2.定向光当一个光源处于很远的地方时,来自光源的每条光线就会近似于互相平行。这点很好理解,生活中我们的太阳光,就可以......