【数据结构】顺序表专题详解（带图解析）

•🌙说在前面

亲爱的读者们大家好！💖💖💖，我们又见面了，我们有关C语言部分的语法在上一篇文章就告一段落了，紧接着我将会给大家更新一些有关数据结构的基础知识，帮助大家更好的理解和学习数据结构，希望大家可以有所收获。

今天这篇文章所讲解的是有关顺序表的知识，包括了顺序表的增加、删除、查找、插入元素等一系列操作，感谢大家支持！

在数据结构的学习中，画图是必不可少的，所以在数据结构的部分我将会尽可能用图画的方式让大家直观的感受到它的原理，其实只要思路到位，代码部分就是信手拈来~

初阶数据结构的部分将会用C语言进行实现~

💘💘💘数据结构的学习离不开刷题，这里🌷给大家推荐两个很好的学习刷题网站——力扣、牛客网，各种题目应有尽有，大家可以在上面挑选合适难度的题进行训练

👇👇👇

各位友友们！🎉🎉🎉点击这里进入牛客网🎉🎉🎉

👇👇👇

🎉🎉🎉这里是力扣🎉🎉🎉

博主主页传送门：愿天垂怜的博客

🍋知识点一：什么是数据结构

数据结构是由"数据"和"结构"两词组合而来。

• 🌰1.什么是数据？

常见的数值1、2、3、4......、教务系统里保存的用户信息（姓名、性别、年龄、学历等等）、网页上肉眼可以看到的相关信息（文字、图片、视频等等），这些都是数据。

• 🌰2.什么是结构？

当我们想要使用大量同一类型的数据时，通过定义大量的独立的变量，可读性非常差，而且非常不方便，这时我们可以借助数组这样的数据结构将大量的数据组织在一起。结构也可以理解为组织数据的方式。

生活中也有这样的例子：

🔥想要找到草原上名叫"小白"的样很难

🔥但是从羊圈里找到1号羊就很简单，羊圈这样的结构有效将羊群组织起来

概念：数据结构是计算机在内存中存储和组织数据的方式。

数据结构关注如何以最有效的方式组织和存储数据，以便在计算机程序中进行操作和处理。

• 🌰3.为什么需要数据结构？

如图所示，不借助排队的方式来管理客户，会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理，程序中如果不对数据进行管理，可能会导致数据丢失、操作困难、野指针等情况。用过数据结构，能够有效将数据组织和管理在一起。按照我们的方式任意方式对数据进行增、删、查、改等操作。

• 🌰4.常见的数据结构分类

数据结构一般根据组织形式，分为：线性数据结构和非线性数据结构。

线性的数据结构有：数组、链表、栈和队列等。

非线性的数据结构有：树、散列表、堆、图。

最基础的数据结构 - 数组

那我们已经有了数组，为什么还要学习其他的数据结构呢？

假定数组有10个空间，已经使用了5个，向数组中插入数据步骤：

求数组的长度，求数组的有效数据个数，向下标为数据有效个数的位置插入数据（注意：这里是否要判断数组是否满了，满了还能继续插入吗？）......

假设数据量非常庞大，频繁的获取数组有效个数会影响程序执行效率。

结论：最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。

🍋知识点二：顺序表

• 🌰1.顺序表的概念及结构

🔥线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串......

线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不一定是连续的，

比如：

蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合。

那如何理解逻辑结构和物理结构的连续？

以链表为例，上面每个节点分别存储了数据和指向下一个节点的地址，不难发现这些节点的地址是各不相同的，并不是像数组一样在内存中连续存放；但是由于每个节点存储了指向下一个节点的地址，所以通过一个节点我们可以找到下一个节点，由此每个节点之间都产生了联系，从上面的图中我们发现，这种联系是连续的，所以我们称链表在物理结构上不连续，在逻辑结构上连续。

• 🌰2.顺序表的分类

顺序表底层就是数组，它是对数组的封装，在数组的基础上增加了增删查改的方法。

🔥静态顺序表

概念：使用定长数组存储元素

#define N 100
struct SeqList
{
	int arr[N];//定长数组
	int size;//顺序表当前有效的数据个数
};

定义结构体SeqList，在结构体中有一数组，其长度N必须是确定的，在数组中有效的数据个数为size，这样定义出的顺序表称为静态顺序表。

🔥动态顺序表

struct SeqList
{
	int* arr;
	int size;//有效的数据个数
	int capacity;//空间大小
};

定义结构体SeqList，在结构体中有一数组，其长度capacity是不确定的，在数组中有效的数据个数为size，这样定义出的顺序表称为动态顺序表。

📌那是静态顺序表更好还是动态顺序表更好呢？

答案是，动态顺序表

原因有二：

🎉对于静态顺序表，由于其长度是确定的，如果数组大小给小了，空间不够用，如果给大了，造成空间浪费。

🎉对于动态顺序表，由于其长度不确定，我们可以按需申请所需要的大小，对其进行增容和减容。

所以在顺序表中我们一般都使用动态顺序表。

注意：

在数据结构中，由于频繁利用结构体类型，在定义结构体时通常用以下形式同时对结构体类型进行重定义：

typedef struct SeqList
{
	int* arr;
	int size;
	int capacity;
}SL;

同时，由于顺序表的元素不一定只是int型，也可以是别的类型，如果后期要修改数据类型，一个一个改比较麻烦，通常用typedef重定义如下：

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size;
	int capacity;
}SL;

• 🌰3.顺序表的初始化

实现顺序表的增删查改功能，我们使用的都是动态顺序表。

C语言实现初始化顺序表的代码如下：

void SLInit(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

初始化需要将arr置为NULL，同时需要将数组的有效长度和空间大小设置为0。

📌为什么这里用传址调用而不用传值调用？

形参只是实参的一份临时拷贝，对形参的修改并不会影响实参。若传递结构体变量，是不会改变结构体变量本身的值的，如果我们需要在函数中改变一个变量的值，则需要传递这个值的地址，所以需要传址调用。

• 🌰4.判断是否需要申请空间

在初始化动态顺序表后我们就需要对其开开辟空间，或在程序判断出顺序表内存空间已满后要进行顺序表空间的扩容处理，所以最好可以封装一个函数，达到既可以判断最大空间与当前成员的关系（即判断满没满），又能在将顺序表扩容。

void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		SLDataType NewCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* temp = (SLDataType*)realloc(ps->arr, NewCapacity * sizeof(SLDataType));
		if (temp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		else
		{
			ps->arr = temp;
			ps->capacity = NewCapacity;
		}
	}
}

注意我们一般情况下扩容为原来大小的两倍左右，但是我们也要考虑到空间大小为0的情况，比如我们刚初始化完的顺序表，那此时的空间大小我们直接设置成4个字节，所以我们创建了一个SLDataType类型的Newcapacity，表示扩容后的大小，如果原空间大小为0就为4，否则就为原来大小的两倍，然后用realloc函数进行增容，增容失败就显示错误信息并且退出，增容成功就将增容后的新地址赋值给顺序表中的数组，同时空间的大小也更新为新的NewCapacity。

• 🌰5.顺序表元素的打印

C语言实现顺序表元素的打印：

void SLPrint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

打印元素就非常简单了，一个for循环直接搞定。由于在打印元素的过程中没有对原结构体进行修改，所以可以不需要传地址，直接传值就好。

• 🌰6.顺序表头部插入元素

例如一顺序表含有2、3、4、5、6，希望在2的前面，也就是最开始的地方添加一个数据1，就是在顺序表的头部插入元素

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

在对顺序表进行插入元素，都应该先检查ps是否为空，以及ps->arr是否需要扩容，然后使用for循环，让顺序表中的每个元素都向后移动一位，然后再将第一个元素置为我们所想要插入的数据x，就可以了。

• 🌰7.顺序表尾部插入元素

例如一顺序表含有1、2、3、4、5，希望在5的后面，也就是最后一个元素的后面添加一个数据6，就是在顺序表的尾部插入元素

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	ps->arr[ps->size++] = x;
}

尾插相对于头插就更简单了，直接在末尾添加数据即可，同时有效的数据个数也增加1就可以了。

• 🌰8.顺序表指定位置插入元素

例如一顺序表含有1、2、4、5、6，希望在2和4的中间添加一个数据3，也就是在下标为2（pos=2）的位置插入数据3，这就是指定位置插入元素

void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[pos] = x;
	ps->size++;
}

此时我们再保证ps不为NULL的同时也需要保证元素下标pos的值是大于等于0且小于等于ps->size的，然后将pos之后的元素全部向后移动一位，在向pos位置插入要添加的数据SLDataType x即可。

• 🌰9.顺序表头部删除元素

例如一顺序表含有0、1、2、3、4、5，希望删除最开头的元素0，也就是顺序表的头部，这就是头部删除元素

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

头部删除元素，只需要将出了第一个元素之外的所有元素向前移动一位就行了，这样直接就能将它覆盖。

• 🌰10.顺序表尾部删除元素

例如一顺序表含有1、2、3、4、7，希望删除最末尾的元素7，也就是顺序表的尾部，这就是尾部删除元素

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	ps->size--;
}

尾删就很简单了，直接有效长度-1就可以了，毕竟有效长度之前的才算是有效的顺序表的元素。

• 🌰11.顺序表指定位置删除元素

例如一顺序表含有1、2、3、3、5，希望删除2和第二个3中间的数据3，也就是删除下标为（pos=2）的位置的元素，这就是指定位置删除元素

void SLErase(SL* ps ,int pos) 
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	for (int i = pos; i < ps->size; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

想要删除pos位置的元素，需要将角标pos到ps->size-1的元素全体向前移动一位，将pos位置的元素覆盖即可。

• 🌰12.顺序表的查找

例如有一顺序表1、2、3、4、5、... n-1、n，想在这个顺序表中查找数据x，这就是顺序表的查找

int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}

用for循环遍历数组，在查找的过程中，如果顺序表中确实有数据x，则返回x的下标i，如果没有查找到这个数据，则返回-1，也就是说返回的是-1说明顺序表中没有该元素。

• 🌰13.顺序表的销毁

在利用顺序表成功实现相对应的功能后，需要将顺序表进行销毁

void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
    ps->arr=NULL;
	ps->size = ps->capacity = 0;
}

由于ps->arr申请的是堆上的动态内存，使用完之后我们需要释放这部分内存，释放后还最好将ps->arr置为NULL，以防造成野指针，同时将有效数据个数和空间大小设置为0。

🍋知识点三：顺序表基本操作

顺序表的基本操作就是实现对顺序表元素的增、删、查、改，关于如何实现已经在前面都进行了讲解，也给出了代码，现在希望大家掌握之后通过下面给出的SeqList.h头文件，在SeqList.c文件中分别实现这些功能，并在test.c的main函数中测试：

#pragma once
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;
	int size; //
	int capacity;
}SL;

//初始化和销毁
void SLInit(SL * ps);
void SLDestroy(SL * ps);

//顺序表的打印
void SLPrint(SL * ps);

//判断是否需要申请空间
void SLCheckCapacity(SL * ps);

 //头部插入删除 / 尾部插入删除
void SLPushBack(SL * ps, SLDataType x);
void SLPopBack(SL * ps);
void SLPushFront(SL * ps, SLDataType x);
void SLPopFront(SL * ps);

//指定位置插入/删除数据
void SLInsert(SL * ps, int pos, SLDataType x);
void SLErase(SL * ps, int pos);

//查找元素
int SLFind(SL * ps, SLDataType x);