数据结构入门 — 顺序表详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构入门 — 顺序表详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

数据结构入门 — 顺序表详解
博客主页链接：https://blog.csdn.net/m0_74014525
关注博主，后期持续更新系列文章
文章末尾有源码
*****感谢观看，希望对你有所帮助*****

一、顺序表

1. 顺序表是什么

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

2. 优缺点

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

二、概念及结构

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

1. 静态顺序表

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

在静态顺序表中，数据元素按照顺序依次存放，每个元素都占用相同的存储空间，而且元素在内存中的地址也是连续的。
数据结构入门 — 顺序表详解,数据结构,数据结构,开发语言,c++,c语言,算法

2. 动态顺序表

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

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

数据结构入门 — 顺序表详解,数据结构,数据结构,开发语言,c++,c语言,算法

三、顺序表接口实现（代码演示）

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 代码仓库

总结

顺序表是一种线性表，它的重点是：

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