顺序表的简单介绍

前提须知：

数据结构：

什么是数据结构？

数据结构特点：

为什么需要数据结构：

顺序表：

线性表：

与数组区别：

静态顺序表与动态顺序表：

二者之间的区别：

编译器的实现：(以下使用头文件和源文件的书写方式)

初始化：

头文件：

源文件：

销毁开辟空间：

头文件：

源文件：

尾插：（在上述代码的基础上进行尾插操作）

尾插要考虑的因素：

头文件：

回答问题：

1）空间是否足够：

2）空间足够如何进行尾插：

如何扩容？

怎么扩容？

那如何申请空间呢？

注意事项：

头插：（在上诉代码的基础上进行尾插操作）

头插的所需要进行思考的问题：

头文件：

回答问题：

怎么将原先的数据往后移，腾出第一个空间的位置：

尾删：（在上诉的基础上进行尾删操作）

头文件：

需要注意的问题：

头删：（在上诉代码的基础上进行头删）

头文件：

前提须知：

数据结构：

什么是数据结构？

答：数据结构是计算机存储、组织数据的⽅式，举例：数组是最简单的一种数据结构。

数据结构特点：

能够存储数据（如顺序表、链表等结构）
存储的数据能够⽅便查找

为什么需要数据结构：

最基础的数据结构能够提供的操作已经不能完全满⾜复杂算法实现。
假设数据量⾮常庞⼤，频繁的获取数组有效数据个数会影响程序执⾏效率。
数据的多样性，以数组为例，数组只能满足同一种类型的数据，不能满足其他类型的数据。

顺序表：

在顺序表之前，我们要先明白什么是线性表。

线性表：

线性表是一种总称，指的是具有相同特性的一类数据结构的统称。

线性表特点：

线性表在逻辑上是线性结构，也就说是连续的一条直线。
但是在物理结构上并不一定是连续的线性表在物理上存储时，通常以数组和链式结构的形式存储。
逻辑结构：人为想象的。
物理结构：内存存储上，不一定是连续的，连续的举例是数组，数组地址是连续的。

而顺序表是线性表的一种，相当于苹果是水果的一种，且因为顺序表的底层结构是数组，所以顺序表在逻辑结构上是线性的，在物理结构上也是线性的。

与数组区别：

先前讲诉过，数组是同种类型数据的集合。

而且数组分为两种，定长数组和动态数组，定长数组是一开始就设定了数组大小，动态数组是数组的大小不确定，详情看柔性数组。

柔性数组_明日香的博客-CSDN博客

而顺序表的底层结构是数组，对数组的封装，实现了常用的增删改查等接口，这是顺序表与数组的区别。

同时也可以通过数组的分类将顺序表分为两种，静态顺序表和动态顺序表。

静态顺序表与动态顺序表：

静态顺序表和动态顺序表的声明结构，其实顺序表的声明结构就是一种结构体。

结构体的简单介绍（1）_明日香的博客-CSDN博客

//静态顺序表struct SeqList
{int a[100];//定长数组int size; //有效个数}

int a[100]表示这个顺序表的大小是100个int类型的字节数大小，也可以说是400个字节大小。
而int size 表明了该顺序表中放入了多少有效的数据。
struct是结构体的关键字，表明了顺序表的声明结构其实就是结构体。

//动态顺序表struct SeqList
{int* a;int size;//有效数据的个数int capacity;//空间大小
}

int*a 指向的是一个数组空间的首个元素地址，间接表明了顺序表的底层结构是数组。
int capacity 指向的是开辟空间的大小，也就是顺序表空间的大小，因为是动态的，所以需要开辟空间。
在使用的过程中，可以将a直接当成数组名使用，这是允许的。

二者之间的区别：

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费。

编译器的实现：(以下使用头文件和源文件的书写方式)

注意：顺序表是一种声明，所以应该在头文件中输写。

以动态顺序表为例子。

在图中，typedef 将int 类型和顺序表进行了重新命名。

int 类型定义命名的意义是为了方便以后进行类型的更改，这是顺序表和数组的区别之一。

而顺序表 struct SeqList重命名为SL 为了以后方便书写。

初始化：

创建一个void 类型的函数SLInit 该函数的参数是SL*类型的，形参是ps

头文件：

源文件：

结构体的赋值，详情：结构体的简单介绍（1）_明日香的博客-CSDN博客

将顺序表的空间大小和有效数字初始化为0，将顺序表的指针指向NULL

因为局部变量的关系，以及传值调用中，形参的改变不会影响实参的因素，所以我们这里使用传址调用。

C语言实参与形参传值调用与传址调用-CSDN博客

销毁开辟空间：

销毁开辟的空间，在销毁之前我们必须判断这个空间是否存在，或者说是否开辟，如果存在，则需要使用free释放空间，free的本质是将开辟的空间交还给内存。

free详情：malloc与free_明日香的博客-CSDN博客

头文件：

源文件：

尾插：（在上述代码的基础上进行尾插操作）

在尾部插入数据。

如图所示，在下标为6的位置上插入数据，这种就是尾插。

尾插要考虑的因素：

空间是否足够的问题？
足够应该如何进行尾插？
如若空间不够应该如何扩容的问题？
扩容时需要注意什么？
需要扩容多少空间合适？

头文件：

回答问题：

1）空间是否足够：

在动态顺序表中，capacity是表示顺序表的空间的大小，size是表示顺序表中的有效数据的个数，所以当capacity==size的时候，就可以说明顺序表的空间是否满了。

顺带一提，capacity表示的是空间大小，而size表示的是有效数据的个数，所以当二者相同时，二者均可以代表顺序表这个数组的数组大小，而不相同时，反倒是size可以代表顺序表这个数组的数组大小，而顺序表这个数组的最大下标则就是size-1

使用if进行判断二者是否相等，如若相等，准备进行空间的扩容，若不相等则直接进行尾插。

2）空间足够如何进行尾插：

因为空间足够使用，所以在顺序表这个数组中插入数据即可。

且，因为size无论在何时都表明了数组的大小，而size-1表明了当前顺序表这个数组的最大下标，所以在顺序表这个数组中，若要插入数据，直接在size这个位置中插入数据即可。

当然，在最后别忘了将有效数据个数+1，这是为了进行多次的尾插所必要的代码，且直接插入是基于capacity 够的情况下，所以capacity不需要进行改动。

如何扩容？怎么扩容？需要扩大多少空间合适？

如何扩容？

使用realloc函数进行扩容，realloc函数详情：realloc-CSDN博客

怎么扩容？

每次插入一个数据就申请一个空间？插入100个数据申请一百个空间？
但是如果频繁的扩容，会降低程序的性能。

那如何申请空间呢？

答：一般以2倍或者1.5倍进行扩容，比如一开始申请4个空间，当插入第五个数据的时候，扩容成八个空间，插入第九个数据的时候，扩容成16个空间，以此类推··················

图中的代码类比，realloc函数的调整空间大小，基于realloc函数的特性，如若调整空间大小失败，那么这个空间则会丢失，所以直接赋予ps->a有可能造成原空间地址失效，所以需要使用tmp进行中间赋值，然后判断，判断成功后在赋予ps->a

扩容：

ps->a表示需要扩容空间的起始地址
ps->capacity*2*sizeof(SLDataType)，前者表示当前的空间大小，sizeof表示计算当前顺序表的字节大小，*2表示我们的扩容方法。
（需要注意的是，空间大小是有类型的，所以空间大小不能代表字节数的多少）