数据结构第二课 | 顺序表（详解）

前言：Hello！大家好，我是@每天都要敲代码，上次我们讲了数据结构第一课时间复杂度和空间复杂度；不明白的小伙伴可以学习一遍时间复杂度和空间复杂度传送门；今天让我们开始一起学习数据结构第二课啦-----线性表；在学习线性表之前，我们要先弄清楚它的概念，下面让我们一起来看看吧！

概念：

线性表：线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛
使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串....
解释：线性表在逻辑上是线性结构，也就是连续的一条直线。但是在物理结构上并不一定是
连续的，线性表在物理上存储时，通常以【数组】和【链式结构】(链表)的形式存储
 数组空间是连续的，链表空间是不连续的。

顺序表实现：顺序表是用一段【物理地址连续】的存储单元【依次存储数据元素】的线性结构，一般情况下采用数组存储。在数组上完成数据的增删改查。
顺序表一般可以分为：
                   1.静态顺序表：适应定长数组存储。
                   2.动态顺序表：使用动态开辟的数组存储

目录

静态顺序表：

动态顺序表：

1.先创建顺序表：struct SqList

2.进行初始化：SqListInit

3.打印函数：SqListPrint

4.尾插函数：SqListPushBack

扩容函数：SqListExpasion

5.头插函数：SqListPushFront

6.尾删函数 SqListPopBack

7.头删函数 SqListPopFront

8.修改：SqListModify 

 查找：SqListFind

9.任意位置插入：SqListInsert

10.任意位置删除：SqListDelete

11.销毁：SqListDestory

所有具体代码：

补充题目1： 原地移除元素

补充题目2：合并两个有序数组

总结： 

---

    静态链表的形式很简单，但是容量的大小其实是写死了，不太实用；我们先写出静态链表感受一下吧：

静态顺序表：

     我们先对顺序表进行初始化，那么传参怎么办呢？传值还是传址？它要改变原来的数据，当然是传址啦；初始化有两种方法，自己选择一种适合自己使用就可以；

    第二步我们就把相对简单的打印函数写出来了；

    第三步我们就进行尾插，在插入的时候我们就发现了静态顺序表的弊端，我们首先要进行判满，满了就不能插了，只能手动进行扩容，扩小了造成来回扩容，很麻烦；扩大了又会造成浪费，那么该怎么办？我们不妨写成动态顺序表的形式；所以下面的函数接口我就不在写了；直接写成动态顺序表的形式吧！！！

动态顺序表：

      对于动态顺序表我们就把常用的接口函数都写出来吧，虽然稍微有点复杂，不要怕，我们一个一个接口函数来解决：

1.先创建顺序表：struct SqList

   包括存储数据的数组arr，用malloc创建出来、有效数据的个数sz、容量capacity；下面一起来实现吧:

2.进行初始化：SqListInit

    我们同样也需要传址！！！在写初始化接口函数之前，我们首先要思考，要初始化什么？怎么初始化？

第一种初始化方式：首先我们要肯定要用malloc先动态申请空间，申请空间的大小就是上面定义的宏常量INIT_MAX的大小；值得注意的是malloc开辟空间是以字节为单位开辟的；之后还是把sz的大小初始化为0，容量capacity的大小初始化为INIT_MAX的大小。

第二种初始化方式：当然你也可以像航哥一样，才开始把ps->arr=NULL，ps->sz=0，  ps->capacity = 0；我们插入的时候直接realloc进行扩容；这里就需要老铁对malloc和realloc有一定的了解了，我们思考一下，当realloc初始传一个空指针，是不是相当于malloc的作用呢？不妨自己去尝试一下吧！并且写成这种形式，我们在直接用reallo直接扩容之前，要把capacity初始化一个值，不然（倍数*capacity=0）就永远为0了；我们一般扩容为原来的两倍。

下面两种方式的扩容都给出来，选择自己习惯的就好；我是比较偏向第一种方式，所以读这篇博客还是按照第一种初始化方式去理解：

第一种方式初始化：

 第二种方式初始化和扩容：

3.打印函数：SqListPrint

 同样我们先把相对简单的打印函数写出来，以后需要直接调用这个函数就行：

4.尾插函数：SqListPushBack

扩容函数：SqListExpasion

    在尾插之前我们需要先判断是否需要扩容，看ps->sz == ps->capacity；满足我们就需要扩容，而且在哪里插入都需要先判断是否需要扩容；我们不妨封装成一个函数，下面在使用直接调用就行，避免代码冗余；尾插我们在直接插入就行了，不需要数据的移动，很简单：

 是否扩容成功呢？我们定义的初始capacity=4，我们不如来多输入几个数来测试一下：

 能正常打印出来，说明我们已经扩容成功了！！！

5.头插函数：SqListPushFront

     同样在头插之前我们需要先判断是否需要扩容；头插就不像尾插那么简单直接在后面插入数据；头插需要往后移元素，把下标为0的位置留给新插入的数据；那么怎么移动呢？当然是从后面开始移动啦！从前面数据会被覆盖！！！

 头插两个数据11、12看运行结果：

 正常打印，说明头插成功。

6.尾删函数 SqListPopBack

对于尾删也很简单，直接让ps->sz--访问不到最后一个元素就可以了：

 下面我们尾删两个数试试：

发现9、10已经打印不出来了，尾删成功。

7.头删函数 SqListPopFront

   对于头删，也要先判断是否为空表；我们同样也要移动元素，从最前面开始，把数据一个个往前移；然后在把ps->sz--就可以啦：这里可以再回过头来去看一下头插函数里面的移动元素和这里头删函数移动元素的区别，对比着学习！！！

 下面头删两个元素，打印试试看：

正常删除头两个元素12和11，头删除成功。

8.修改：SqListModify 

 查找：SqListFind

    在修改数据之前，我们肯定要先进行查找，根据数据的下标进行修改操作，所以不妨先封装一个查找的函数SqListFind；根据这个查找函数找下标，然后在传参进行修改：

 我们不妨修改一个元素试试，比如：把3改为300：

从这里可以看出，完全是没问题的。 

9.任意位置插入：SqListInsert

在任意位置插入；你可以有两种理解，

一种直接给你下标pos，就把数据插入到pos里；比如：我们直接给出下标pos=1的位置插入，这时我们插入之前就要判断pos下标是不是越界；直接用assert(pos<ps->sz)断言就可以。

另外一种理解你可以根据给出的具体数据，调用SqListFind查找函数返回的下标pos，来进行插入；这时返回的下标除了找不到是-1，其它的肯定返回的是合法的值，所以不用越界判断也是可以的。

这里我们只实现第一种理解：

 我们不妨在下标为0的元素前面插入100；看运行结果：

从这里可以看出，完全是没问题的。 

10.任意位置删除：SqListDelete

   同样删除也是和任意位置插入一样，有两种理解；我们还是只实现第一种理解，我们随意给定一个下标就可以删除这个下标的元素：

 我们不妨删除下标为1的数据；看运行结果：

 从这里可以看出，完全是没问题的，1被删除了。 

11.销毁：SqListDestory

所有具体代码：

补充题目1： 原地移除元素

补充题目2：合并两个有序数组

    这两道题目是航哥数据结构补充的两道题目；我们在以前的博客里已经做过这两道题目，这里就不在说了，感兴趣的小伙伴，不妨看看我的另外两篇博客，专门详解了这两道题目：传送门1<原地移除元素>     传送门2<合并两个有序数组>

总结： 

       当然你可以模仿通讯录那样写一个详细的菜单，这里就留给老铁们自己动手写一写！今天的数据结构之顺序表就学完了，希望对您有所收获；等你完全一口气能写出这个顺序表，不妨就尝试把这个当成小项目来写；创建SqList.h：用来存放函数的声明、头文件的引用、结构体的定义、常量的定义等放在这里面；创建SqList.c来写具体函数的实现；创建tect.c来写主函数、以及各个函数的调用等。