【数据结构】顺序表和链表——顺序表（包含丰富算法题）

1. 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 顺序表

2.1 概念与结构

概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。

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

2.2 分类

2.2.1 静态顺序表

概念：使用定长数组存储元素

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

2.2.2 动态顺序表

概念：使用动态开辟的连续空间存储元素

2.3 动态顺序表的实现

SeqList.h

#define INIT_CAPACITY 4
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList
{
	SLDataType * a;
	int size; // 有效数据个数
	int capacity; // 空间容量
}SL;

//初始化和销毁
void SLInit(SL * ps);
void SLDestroy(SL * ps);
void SLPrint(SL * ps);
//扩容
void SLCheckCapacity(SL * ps);

//头部插⼊删除 / 尾部插⼊删除
void SLPushBack(SL * ps, SLDataType x);
void SLPopBack(SL * ps);
void SLPushFront(SL * ps, SLDataType x);
void SLPopFront(SL * ps);

//指定位置之前插⼊/删除数据
void SLInsert(SL * ps, int pos, SLDataType x);
void SLErase(SL * ps, int pos);
int SLFind(SL* ps, SLDataType x);

[!NOTE] 💡 代码小提示 编写代码过程中要勤测试，写一部分测试一部分，避免写出大量代码后再测试而导致出现问题，问题定位无从下手。

2.4 顺序表算法题

2.4.1 移除元素

https://leetcode.cn/problems/remove-element/description/

2.4.2 删除有序数组中的重复项

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

2.4.3 合并两个有序数组

https://leetcode.cn/problems/merge-sorted-array/description/

2.5 顺序表问题与思考

• 中间/头部的插入删除，时间复杂度为

• 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
• 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200。

我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？