顺序表-线性表
一、线性表的基本概念
线性表的定义
- 线性表(linear list)是相同类型的n(n>=0)个数据元素的有限序列。一般表示为 L = (a1 , a2 , ..., ai, ai+1 , ..., an)
- n是表的长度，当 n=0时，称为空表。
- a1 是表头元素， an 是表尾元素。
- 表头元素没有前驱，其余的任意元素都有唯一的前驱元素，表尾元素没有后继，其余的任意元素都有唯一的后继元素。
- 线性表的定义就是数据的逻辑结构(第一章2.2)，数据运算的定义针对逻辑结构的，运算的实现要针对线性表选择的存储结构，选择顺序存储来实现线性表就是顺序表，选择链式存储实现线性表就是链表。
二、线性表的两种实现方式
用顺序存储的方式实现线性表就是顺序表，用链式存储的方式实现线性表就是链表。
1.顺序存储（顺序表）：
把逻辑上相邻的数据元素存放在一段连续物理存储单元中，数据元素之间的逻辑关系可以由物理存储关系体现。
2.链式存储（链表）：
逻辑上相邻的数据元素存储在任意的一组物理存储单元中，数据元素之间的逻辑关系用指针来表示。
线性表L = ("张三", "李四", "王五","赵六")分别用顺序存储和链式存储展示如下：
3.举例：贪吃蛇
移动本质是数据的头部插入数据，尾部删除数据。
踩到点后的本质是头部插入数据，尾部不删除数据。
顺序表是在创建的时候创建好空间，贪吃蛇执行时需要移动数据。（时间复杂度O(N)）;
链表可以任意位置申请空间再指向表头即可。（O(1)）;
三、C++引用补充
1.引用的定义
类型& 引用别名 = 引用变量;（引用时必须初始化）
2.引用的特性
- 引用在定义时必须初始化
- 一个变量可以有多个引用
- 引用一旦引用一个实体，再不能引用其他实体
3引用的做参数
- 函数调用传值传参：将实参的值复制一份给形参，函数内对形参的修改不会影响实参。
- 函数调用指针传参：传递实参的地址（指针），通过指针间接访问和修改实参。
- 指针传参和引用传参除了通过形参修改实参的作用，对于大对象传参还有减少拷贝提高效率的作用。
- 指针和传参和引用传参在功能上是重叠的，一些场景用引用程序要简化方便一些。
四、顺序表
1.1静态顺序表
静态顺序表就是用固定大小的静态数组来存储数据。优点是实现简单，缺点是适用场景局限，只适用于确定知道自己最多存放多少数据的场景，否则空间申请少了不够用，申请多了浪费。
1.2动态顺序表
动态顺序表就是用⼀个堆上动态申请的数组来存储数据，如果空间不够了可以做扩容处理。优点适
用场景多，不确定自己要存放多少数据的场景也很适合，缺点是实现相对复杂一些。后续我们主要
实现动态顺序表，因为动态顺序表可以掌握，静态顺序表就是手拿把掐。
代码在：
SqList · Epiphany_ran/opencode - 码云 - 开源中国
2.1初始化
- 顺序表的结构体变量创建好后，系统会以随机值对其进行填充，所以在使用前须先进行初始化，步骤如下：
a. 使用malloc申请一个默认大小动态数组空间，比如默认大小为4，这个空间一般不要太大，因为太大了，用不了就浪费了，反正如果不够，后续可以扩容。
b. 申请成功后，将有效元素个数初始化为0，因为初始化阶段，顺序表中还未存放任何有效元素。
c. 将capacity设置为所申请空间的实际大小。
2.2销毁
- 由于顺序表中的空间是用malloc从堆上动态申请的，使用完后必须释放，否则会内存泄漏。具体步骤如下：
a. 检测顺序表 s 的空间是否被销毁。
b. 如果未销毁，使用 free 将其释放掉，并将 arr 设置 NULL，size 和 capacity 设置为0。
c. 其次要注意的free本质并不是真的把空间销毁掉，free的本质是把这段空间的使用权还给操作系统，操作系统后续还可以把这段空间分配给别人。
2.3插入
- 顺序表经过初始化之后，才可以进行元素插入操作。插入函数原型为void SqListInsert(SqList* ps, int i, SqDataType x) , 即在顺序表的第i个位置之前插入新元素x，如果 i 的位置非法，则不进行插入；插入具体步骤如下：
a. 参数检测。主要检测位序i是否满族 0 <= i <= s.size ，满足则着插入，否则无法插入。
b. 检测是否需要扩容，如果顺序表中存满了则需要先扩容之后才能插入。
c. 插入元素x。将 i 及其之后的所有元素整体往后移动一个位置，然后将 x 填充到待插入位置。
d. 插入成功后，给有效元素个数加1
- 我们这里扩容使用C的库函数 void* realloc (void* ptr, size_t size) 实现，ptr是旧空间的指针，size是需要的新空间的字节数，realloc函数有以下几种情况：
a. 原地扩容：如果当前数组后面有足够的空间没有分配给别人，realloc则会将后面空间分配给我
们，返回的地址跟ptr一样。
b. 异地扩容：如果当前数组后面没有足够的空间(这些空间已经分配给别人了)，realloc则会尝试
找一块 size 大小的新空间，如果没有找到则代表扩容失败了，返回NULL；找到了则会把ptr
空间的数据拷贝到新空间，然后释放ptr指向的旧空间，然后返回新空间的地址。
2.4 删除
- 删除函数原型： SqDataType SqListDelete(SqList* ps, int i)
- 删除函数的功能是删除顺序表中第 i 个位置上的元素，删除的元素通过返回值带出，注意i必须在0 ≤ i < s.size ，否则无法删除。具体操作如下：
a. 参数检测，主要检测位序i是否满足 0 <= i < s.size ，满足则删除，否则无法删除。
b. 将 i 位置之后所有元素整体往前搬移一个位置。
c. 删除成功，将有效元素个数减1。
2.5查找
- 顺序表有两种查找操作，位序查找和按值查找。
- 位序查找函数原型： SqDataType GetElem(SqList* ps, int i) 第i个位置元素随机访问，在i满足 0 <= i < s.size 时(不满足则报错)，直接返回顺序表第i个元素即可。
- 按值查找函数原型： int LocateElem(SqList* ps, SqDataType x) 从前往后逐个查找，找到第一个相等的就返回其下标，否则返回-1。
2.6复杂度分析
插入的时间复杂度
a. 最好情况：位序 i = n + 1 在表尾插入，插入时无需扩容，无需移动元素，时间复杂度为 O(1)
b. 最坏情况：位序 i = 1在表头插入，此时需要将所有元素整体往后移动1步，即移动语句需要执行n次，再叠加需要扩容，异地扩容的最大的消耗是要拷贝n个元素，那么时间复杂度为O(n)
c. 平均情况：假设在任意位置前插入元素的概率Pi相等，则Pi = 1 / n+1，则在长度为 n 的线性表中插入一个元素时所需移动元素的平均次数为：
那么时间复杂度为 O(n)。
删除的时间复杂度
a. 最好情况：位序 i = n 在表尾删除，删除时无需移动元素，时间复杂度为 O(1)
b. 最坏情况：位序 i = 1 在表头删除，此时需要将i位置后面的元素依次往前挪动覆盖，即挪动n-1个数据，时间复杂度为O(n)
c. 平均情况：假设在任意位置删除元素的概率 相等，则 Pi = 1 / n ，则在长度为 n 的线性表中删除个一元素时所需移动元素的平均次数为：
那么时间复杂度为 O(n)。
下标查找的时间复杂度
因为顺序表中的数组物理存储上是连续的，通过首地址常数次就是可以算出任意i位置的地址，所以时间复杂度均是 O(1)。
按值查找的时间复杂度
a. 最好情况：查找的元素就在表头，此时比较 1 次即可找到，时间复杂度为 O(1)
b. 最坏情况：查找的元素在表尾或不存在时，则需要比较 n 次，时间复杂度为 O(n)
c. 平均情况：假设查找任意位置元素的概率Pi相等，则 Pi = 1 / n，则在长度为n的线性表中查找一个值的比较平均比较次数为：
那么时间复杂度为O(n)。