顺序表操作（动态+静态版本），思路清晰易懂

在上一篇文章我们了解到，数据结构就是对数据的高效处理方式的学习，那么我们开始由浅入深的来正式学习数据结构这门课程。

本篇介绍的是静态顺序表的实现思路，和动态的并无大异，动态顺序表的代码也给出了。

前言介绍

先来介绍一下数据中最为简单的一种数据结构——线性表
听名字相比大家应该就能猜出它的一些性质了。

线性表：一个或多个数据元素的有限序列

首先它是有限的，若数据有多个的话，那么第一个元素无前驱，最后一个元素无后继，其他的所有元素都有一个直接前驱和直接后驱元素。如下图所示：

线性表又分为两种，一种是顺序存储的，还有一种是链式存储的。
本文章就先来介绍顺序存储的线性表。
关于顺序存储的线性表，和大家所学过的高级语言中的数组很相似，它们都是在内存中有一段连续的存储空间。

有人可能会问，那既然都有数组了，为什么数据结构这们课中，为什么还要引入顺序表这个概念呢？

原因很简单，数组能处理的数据是非常局限的，比如int类型的数组只能存放和处理int类型的数据，当我们需要对不同数据进行同样的操作的时候就需要重新分配内存空间，这很麻烦，而且学习顺序表对后面的链表的学习是有很大的帮助的，而我们常用的也是链表的数据结构。

那么我们不如将对数据的一些基本操作，分装成一个个的函数，当我需要使用的时候，就直接调用对应的操作函数即可，放我们需要改变要处理的数据类型时，我们只需要对头文件中的类型进行修改即可，这大大方便了对数据的操作和管理。

我们回想一下，当我们要对一个已满的数组进行写入数据的时候，这个操作是不被允许的，这是我们只能使用动态内存函数malloc等开辟新的内存来达到我们的目的。那么数组就可以被分成两种情况，静态内存的数组和动态内存的数组（内存不够就malloc）

所以顺序表也分成两种情况，动态的顺序表和静态的顺序表
为了照顾新手，所以我在下面所讲解的思路是静态的顺序表，关于动态的顺序表，相信大家学完本篇文章就能看的懂动态的顺序表代码了，所以我这里直接给出动态顺序表的gitee代码链接

动态顺序表的链接

动态顺序表代码

在文章的最后也会给出静态的代码链接哦。

SeqList的创建和初始化

SeqList是顺序表的名称。

SeqList的创建

#pragma once

#include 

typedef int SLData;//SLData的类型根据实际情况而定，这里是int

typedef struct SeqList
{
	SLData* a;//数据存储的内存地址
	size_t size;//要插入数据的下标--也是数据的个数
	size_t capacity;//顺序表的容量
}SL;
1
2
3
4
5
6
7
8
9
10
11
12

之所以使用结构体，是为了方便我们管理该顺序表，和对该顺序表进行操作。
这里我解释一下size和capacity变量的作用，之后便不再赘述。
size表示的是元素的个数，初始值为0，当我们要插入一个元素时，size正好也是我们 要插入位置的下标，之后size++变为1，此时元素个数为1，而1也是我们要插入下一个元素位置的下标。

注意，顺序表不能像数组那样可以无视位置进行写入数据，顺序表对的数据的写入只能是在尾部或头部或者在中间进行插入。而我们初始一个数组之后，可以在0的位置写入数据之后，直接跳到最后一个位置进行写入，这是两者不同的地方之一。

这也就意为着，我们在使用静态的顺序表的时候，就要在一开始为它初始化好合理的大小（动态版本的就能解决此问题）。

capacity表示的是这个顺序表的大小，当size==capacity时，表示顺序表已满（类似于数组已满），此时再进行仍和的插入操作都会失败，所以我们在实现后续的插入操作的时候，都要先检查一下容量是否已满，这一点尤为重要。

SeqList的初始化
我们将顺序表的创建和其他操作函数的声明集中放在SeqList.h的头文件中，把初始化和各个操作函数的实现集中放在SeqList.c的源文件中，另外新建test.c用于测试各个函数的功能是否正常。

初始化部分，我们就假设顺序表要处理6个数据，所以我们为SLData* a分配6*4个字节的大小空间。

SeqList尾插

在创建和初始化完成之后，我们就来实现第一个操作，在队尾进行插入一个元素。（简称尾插）
这就好比一群人在超市排队付钱，然后新的一个人就得排在队伍的最后。

先检查容量是否已满
若size==capacity，则操作失败，执行exit(-1)
插入新元素
最后size++；

SeqList打印

为了方便我们检查程序的正确性，所以我们紧接着就实现打印函数，来观测我们的上一个函数的实现是否正确。
要想将结果打印出来也很容易，因为我们的size是表示的元素的个数，所以我们只需要用 < size 来作为循环的判断条件即可。

测试结果：

SeqList头插

接着上面那个例子说，然而在现实生活中，终是有些人脸皮很厚，要进行插队，还要插到第一的位置，你说这气不气人！！

当我们在头部进行插入一个元素的时候，此时就需要顺序表中已有的元素全部都向后移动一位，为插队的元素腾出第一的位置。

我们思考一个问题，如果size的大小为0的时候进行头插呢？
这就好比你前面一个人没有，此时你去排队就不能被称作“头插”了而是正儿八经的排队，即尾插。

运行结果

SeqList销毁

当超市的营业时间到了之后，所有的顾客都会被强制要求退出超市，此时的队伍就相当于被销毁了。

当我们不再想要顺序表时，我们希望能直接调用一个函数对它进行销毁，而不是将元素一个个的赶出去，这样效率太慢了。

运行结果

SeqList尾删

既然前面有了尾插和头插，那么相应的就需要有尾删和头删的操作，即从尾部删除一个数据，和从头部删除一个数据。

同样我们也需要考虑size为0的情况，此时如果继续进行删除的话，size就会变成-1，-1是不能作为数组的下标的，所以在下次进行插入的时候，就会出现异常情况，所以我们要对size为0的时候，单独进行处理。

运行结果

SeqList头删

头删任然要考虑size为0的情况。

其次就是，所有的数据要进行前移一位的操作，这样就能直接将第一位的数据覆盖掉，从而达到删除的效果。

然后size–;

运行结果

SeqList的查询

我们不仅仅要对数据插入和删除，有时候更要查看某个数据，这时就需要一个查询顺序表的函数了。
我们输入数据之后，查询函数进行查询，找到了将位置返回，找不到提示一下。

运行结果

SeqList指定位置的插入和删除

最后就是顺序表中比较复杂的部分了，在顺序表的指定位置进行插入和删除。

我们先来思考一下我们应该注意的地方。

首先怎么理解指定位置的概念。因为前面我们已经实现了尾插头插和尾删头删，所以我们在理解指定位置的时候，就要去掉上面已经实现的函数的情况，即避免位置冲突。

试想一下，如果我们指定在头部进行插入，是不是就是头插的功能，在尾部 进行删除是不是就是尾删的功能，所以我们在实现指定位置上的插入和删除的时候，就要考虑一下位置是否合理。

同样在进行插入的时候，还是要检查一下容量是否已满。

插入和删除之后，都需要将数据元素进行移动（前移和后移）。
我们先来看一下，指定位置的插入函数。

运行结果

在指定位置进行删除的操作，步骤和插入函数基本一致，所以我们直接给代码

运行结果

最后我们在每个函数的开头加上assert断言一下，提高我们代码的安全性

至此，有关静态顺序表的介绍就结束了!

两种顺序表的优缺点

说了这么多，我们来回顾一下吧。我给定了一个结构体，结构体中包含存储数据的a和表示元素个数的size，以及顺序表的容量capacity，之后实现了，各种对顺序表的操作，要提醒新手的是，有关顺序表各种操作的实现要根据现实情况而定，但是原理思路是一样的。

既然我们已经实现了静态的顺序表，那么我们来想象一下它的应用场景，什么时候使用静态的，什么时候使用动态的呢？

所有的数据结构都是 根据具体的应用场景选择的。

感谢观看！