【数据结构】—顺序表专题

😊 笔者主页：ristarry
📖 数据结构专栏：数据结构
💾 本篇代码:顺序表专题
✨ 纸上谈来终觉浅，觉知此事要躬行

计算机的学习好似登山，你敲下的每一段代码，掌握的每一个算法，完成的每一次复习，都将化作登山路上坚实的脚印。
最初你不知道前方等待着你的是什么，但是如果你坚持向上攀登，你看到的东西将越来越清晰，终将一览众山小。

希望我能与各位一同在顶峰见证黎明破晓的时刻。

文章目录

• 1. 线性表
• 2. 顺序表
• • 2.1 顺序表的物理结构:
  • 2.2 顺序表的分类
  • • 2.2.3 静态顺序表
    • 2.2.3 动态顺序表
• 3. 动态顺序表的实现
• • 3.1 初始化
  • 3.2 销毁
  • 3.1 检查容量
  • 3.2 插入方式
  • • 3.2.1 尾插
    • 3.2.2 头插
    • 3.2.3 指定位置之前插入
  • 3.3 删除数据
  • • 3.3.1 尾删
    • 3.3.2 头删
    • 3.3.3 指定位置删除
• 3.4 查找数据

1. 线性表

线性表是一种十分基础的数据结构，它是n个具有相同特性的元素的有限序列。
线性表主要分为：顺序表、链表、栈、队列、字符串…

既然它叫做线性表，那么顾名思义，表上的数据都应该是线性排列的，而这种线性的表现就是一一对应的前后顺序关系，我们就拿数组来举例：下标为0的元素后面一定对应了下标为1的元素，这就是一种对应关系。

线性表在逻辑结构上一定是连续的，也就是一定会有明确的前后关系，但是在物理结构上不一定是连续的，关于这一点我们会在后面进行讲解。

---

2. 顺序表

概念：顺序表的底层是数组，但是在数组的基础之上，加入了增删查改等接口。

数组和顺序表的关系就像是路边苍蝇小馆中的酸辣土豆丝，来到米其林后将工艺变得复杂，摇身一变成了法式酸香丝绒土豆脆条，附加的东西变多了但是本质并没有改变。

2.1 顺序表的物理结构:

这就是我所说的物理结构和逻辑结构都是连续的，逻辑结构连续是因为在数组中有这种前后对应的关系，下标为0的元素后面就一定对应着下标为1的元素。而物理结构连续指的是数组中每个元素的地址全都相邻，在如图的整型数组中，每个元素的地址正好对应了一个整型的大小。

在之后我们会讲到的链表中，每个元素的地址是混乱分布的，因此无法构成物理结构上的连续，但是每一个元素又通过指针指向了下一个元素，形成了一一对应的关系，因此能够形成逻辑结构。

2.2 顺序表的分类

顺序表分为静态顺序表和动态顺序表。我们依次来进行讲解。

2.2.3 静态顺序表

语法形式如下：

typedefintSLDataType;#defineN7typedefstructSeqList{SLDataType a[N];//定长数组intsize;//有效数据个数}SL;

在静态顺序表中最为显著的特征就是这个定长数组了，它的元素个数是通过定义常数来确定的，这正是“静态“的体现。

但是我们来设想一下这样一种情况，你独自开发了一款软件，你使用了静态顺序表去存放用户数据，最开始用户人少，你将N定义为1000,然后你的软件突然火了，用户人数越来越多，你每次都要手动去把你的N定义为更大的值，你还不能一次性给N定义太大（比如直接赋值十个亿），你用户没有那么多，空间又浪费了。

因此我们会发现静态顺序表的局限性太大了，太小不够，太大浪费，考虑到这些因素，动态顺序表也就诞生了，本篇我们主要讲解的就是动态顺序表。

2.2.3 动态顺序表

语法形式如下：

typedefintSLDataType;typedefstructSeqList{SLDataType*arr;intsize;//有效空间个数intcapacity;//总容量大小}SL;

在说明动态顺序表为什么“动态”之前让我先介绍一下这个代码中的各个部分。

1. 先看到typedef int SLDataType;这句话的意思是将int类型重命名为SLDataType，我们都知道顺序表不可能全部存放同一种类型的数据，可能你今天想放整型数据，明天就像放字符型数据了，到时候要修改时只需要将int换成char就行了。
2. SLDataType* arr，数组，顺序表的主体，大家都了解。
3. int size;有效空间个数，就是你的顺序表中已经存放了多少个数据了。
4. int capacity;总容量大小，等价于顺序表中数组所能够容纳的最大元素个数，capacity减去size就是顺序表中还能容纳的元素个数。
5. SL给结构体类型重新取的名字。
   
   

3. 动态顺序表的实现

3.1 初始化

不论是我们现在学习数据结构，还是以后学习c++中的类和对象，初始化和销毁都是必不可少的一个流程。

初始化的意义如下：

1. 消除随机垃圾值，使变量处于合法状态。
2. 防止未定义的行为。
3. 让对象建立完整可用的状态。

//初始化voidSLInit(SL*ps){ps->arr=NULL;ps->size=ps->capacity=0;}

3.2 销毁

这一步非常关键!!!
因为现阶段特别容易忘记。

销毁的意义：
使对象的生命周期结束，将它占用的内存资源归还给系统，

//销毁voidSLDestroy(SL*ps){if(ps->arr)free(ps->arr);ps->arr=NULL;ps->size=ps->capacity=0;}

3.1 检查容量

代码：

voidSLCheckCapacity(SL*ps){if(ps->size==ps->capacity){//若容量为0,给一个初始值为4,否则乘2intNewCapacity=ps->capacity==0?4:2*ps->capacity;SLDataType*tmp=(SLDataType*)realloc(ps->arr,NewCapacity*sizeof(SLDataType));if(tmp==NULL){perror("realloc fail!");exit(1);}ps->arr=tmp;ps->capacity=NewCapacity;}}

这就是我之前提到的动态顺序表“动态“的来源，还记得吗，静态顺序表的数组元素个数是宏定义的常数，而动态顺序的元素个数是使用动态内存开辟的函数创建的，通过realloc能够在空间不够时自动开辟适量空间。（不了解realloc的可以点击这里跳转到我的另一篇文章）

现在来讲解一下这个函数：
1.先判断空间是否满了（size是否等于capacity），注意：容量为0时也成立,size = capacity = 0
2. 一上来先去检查顺序表中是否有空间，如果没有空间就给上空间的初始值为4,如果有空间就乘2,扩大一倍。

3.2 插入方式

3.2.1 尾插

顺序表里面一定要存放有数据，那么在我们的动态顺序表中一共有三种数据的存入方式：尾插、头插、指定位置插入。

先说尾插，顾名思义，我们如果将顺序表当作一个数组，那么它就会有首元素和尾元素，将新来的元素插入到尾元素的后面，这就叫做尾插。

尾插实现方式如下：

//尾插voidSLPushBack(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);ps->arr[ps->size++]=x;}

本质就是直接对底层数组进行操作。

3.2.2 头插

与尾插类似，但这次是将新来的元素插入到首元素的前面。

//头插voidSLPushFront(SL*ps,SLDataType x){assert(ps);SLCheckCapacity(ps);for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[0]=x;ps->size++;}

通过一个简单的数组遍历，让所有的数组元素后移一位，将下标为0的位置空出来，再将新元素放入下标为0的位置，头插就完成了。

3.2.3 指定位置之前插入

相较于尾插和头插，指定位置之前插入明显在功能上更加灵活。

//指定位置之前插入voidSLInsert(SL*ps,intpos,SLDataType x){assert(ps);assert(pos>=0&&pos<=ps->size);//检查容量够不够SLCheckCapacity(ps);for(inti=ps->size;i>pos;i--){ps->arr[i]=ps->arr[i-1];}ps->arr[pos]=x;ps->size++;}

可以看到，指定位置之前插入和头插及其类似，或者我们可以这么去看，头插就是指定位置为0的插入方式。

我们只需要将指定位置pos后面的数据都后移一位，然后将新的数据插入空出来的pos的位置就行了。

---

3.3 删除数据

在讲完了插入数据了以后，肯定还要讲讲删除数据，与插入方式对应，删除方式也分为三种：尾删、头删、指定位置删除。

数据的删除方式与插入方式几乎一模一样，只是操作顺序略有差异，不过多讲解了（绝对不是因为我懒哈）。

3.3.1 尾删

//尾删voidSLPopBack(SL*ps){assert(ps);assert(ps->size);ps->size--;}

3.3.2 头删

//头删voidSLPopFront(SL*ps){assert(ps);assert(ps->size);for(inti=1;i<ps->size;i++){ps->arr[i-1]=ps->arr[i];}ps->size--;}

3.3.3 指定位置删除

//指定位置删除voidSLErase(SL*ps,intpos){assert(ps);assert(pos>=0&&pos<ps->size);for(inti=pos;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];}ps->size--;}

3.4 查找数据

//查找 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; }

和大部分的数组查找方式相同，先遍历整个数组，当发现要查找的数据时直接返回。

---