线性表
线性表(linear list)是 n 个具有相同特性的数据元素的有限序列。作为一种在实际中广泛使用的数据结构,常见的线性表包括顺序表、链表、栈、队列和字符串等。
从逻辑结构上看,线性表是连续的直线;但在物理存储上并不一定连续,通常以数组或链式结构形式存储。
顺序表
概念与结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组来实现。
- 逻辑结构:线性
- 物理结构:线性(连续存储)
顺序表和数组的区别
顺序表的底层结构是数组,它是对数组的封装,实现了常用的增删改查等接口。
数组 ⊆ 线性表
分类
静态顺序表
概念上使用定长数组存储元素。

静态顺序表的缺陷在于空间分配固定:给少了不够用,给多了造成浪费。不过在竞赛场景中,经常使用静态申请数组的方式。
动态顺序表
动态顺序表按需申请内存,不会造成空间浪费。

动态顺序表模拟实现
下面我们通过 C++ 代码来模拟一个动态顺序表的核心功能。
定义动态顺序表结构
首先定义数据类型和结构体:
// 头文件中
typedef int SLTDataType;
typedef struct SeqList {
SLTDataType* arr; // 存储数据的指针
int size; // 有效数据个数
int capacity; // 当前空间大小
} SL;
顺序表初始化
初始化时,将指针置空,大小和容量设为 0。
void SLInit(SL* ps) {
ps->arr = NULL;
ps->size = ps->capacity = 0;
}


