数据结构：顺序表讲解（1）
目录
前言
本篇文章将讲解顺序表介绍，顺序表分类，顺序表动态顺序表的实现，顺序表算法题，顺序表问题与思考知识的相关内容，其中顺序表介绍、顺序表概念与结构、顺序表分类、动态顺序表的实现、尾插，头插，尾删，头删时间复杂度对比为本章节知识的内容。
一、顺序表介绍
介绍：
在说明顺序表之前，我们要先了解下线性表的概念：
1.线性表
线性表：逻辑结构的统称
线性表是n个具有相同特性的数据元素的有限序列，是一种抽象的逻辑结构，仅描述数据元素之间的“线性”关系（即除首尾元素外，每个元素有唯一前驱和后继）。其核心特征包括：
- 逻辑连续性：元素按顺序排列，形成一条直线。
- 有限性：元素个数确定，非无限集合。
- 通用性：可表示多种实际问题，如学生名单、购物清单、队列等。
常见类型：
- 顺序表：用连续内存存储（如数组）。
- 链表：用非连续节点存储（通过指针/引用链接）。
- 栈/队列：特殊线性表（操作受限）。
- 字符串：元素为字符的线性表。
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
逻辑结构：线性表的本质定义线性表的逻辑结构必须是线性的（元素间“一对一”相邻关系），这是其核心特征。物理结构：逻辑结构的存储实现物理结构（存储方式）可以是线性的，也可以是非线性的，但需保证能体现逻辑上的线性关系：线性物理结构：如数组（顺序存储），元素在内存中连续存放，物理位置直接反映逻辑顺序。非线性物理结构：如链表（链式存储），元素在内存中分散存放，通过指针/引用关联，逻辑顺序通过指针体现（物理上不连续，但逻辑上线性）。
我们可以理解为： 线性表 = 逻辑结构（线性）+ 物理结构（可选线性/非线性存储）
2.顺序表概念与结构
顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。
根据（1）的概念，我们可以得知：顺序表的逻辑结构和物理结构均为线性的。
顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。
根据此定义，我们可以描绘下顺序表：
如图：
既然上文说过：顺序表的底层结构是数组，对数组的封装。
那么二者有何区别：
首先，数组是一种物理存储结构，指用一段连续的内存空间存储相同数据类型元素的集合。其核心作用是存储数据，不自带数据管理功能。顺序表是一种逻辑结构（线性表）的实现方式，底层基于数组，但通过结构体封装，提供了对数据的管理功能（如动态扩容、增删查改接口）。
简单来说：我们可以认为：数组是基础，顺序表是“升级版”。更加方便且好用。数组 ≈ “空饭盒”：仅提供存放食物的空间，需手动装取。顺序表 ≈ “智能饭盒”：自带分区、加热、容量提示功能，方便管理食物。
二、顺序表分类
介绍：
顺序表根据底层数组的特性分为两类，均需通过结构体封装：
分为静态顺序表与动态顺序表。
1.静态顺序表
所谓静态顺序表，实质为使用定长数组来存储元素，他的空间在一开始时就是确定好了的，空间给少了不够⽤，给多了造成空间浪费，上面提到过顺序表通过结构体封装实现，静态顺序表为：（例）
struct A
{
int a[100]; //定长数组
int size; //有效的数据个数
}; （数组类型可不止int的，也可以为其他类型）
结合代码内容，我们可以近似得出图示：
2.动态顺序表
所谓动态顺序表，是一种基于数组实现的线性数据结构，其大小可根据元素数量动态调整（扩容/缩容），克服了静态顺序表容量固定的缺点。
核心特点
- 底层结构：动态分配的数组（通过
malloc/realloc管理内存）。 - 动态性：容量不足时自动扩容（通常按原容量的2倍或1.5倍增长）。
- 随机访问：支持O(1)时间复杂度的元素访问（通过下标）。
- 顺序存储：元素在内存中连续存放。
动态顺序表为：
struct A
{
int* a; // 动态数组
int size; //有效数据个数
int capacity; //空间容量大小
}; （数组类型可不止int的，也可以为其他类型）
结合代码内容，我们可以近似得出图示：
由于静态顺序表使用起来不太方便，空间给少了不够⽤，给多了造成空间浪费，而动态顺序表，是一种基于数组实现的线性数据结构，其大小可根据元素数量动态调整（扩容/缩容），克服了静态顺序表容量固定的缺点，所以我们顺序表方面知识重点讲解动态顺序表部分。
三、动态顺序表的实现
讲解
接下来，我会讲解动态顺序表中会涉及的函数以及他们的代码实现：
#include<stdio.h> #include<stdlib.h> //定义顺序表的结构 typedef int type; typedef struct Seqlist { type* arr;//存储数据 int size;//有效数据个数 int capacity;//空间容量 }SL;核心成员解析：type* arr：动态数组的指针。顺序表的本质是用数组存储数据，通过指针管理内存空间。size：记录当前已使用的元素个数（从0开始计数，size-1是最后一个元素的下标）。capacity：记录数组的总容量。当size == capacity时，需扩容（通过realloc重新分配更大的内存）。
1.初始化： SLinit
void SLinit(SL* h)
void SLinit(SL* h) { h->arr = NULL; h->capacity = h->size = 0; } h->arr = NULL; // 初始时不分配内存，指针置空h->capacity = 0; // 初始容量为0（无可用空间）h->size = 0; // 初始有效数据个数为0（无元素）
初始化部分简单来说就是像数组刚刚创建，没有存值的情况，内部没有内容，数组指针则置为NULL，两位整数，给值0；
在使用时：这样调用函数即可：
一定要采用传址调用的形式，否则会出现一些错误，因为传值调用修改形参并不影响实参，它们的地址终究还是不同的，而传址调用，形参的修改会影响实参，而我们的目的，是通过传址调用，形参的修改影响实参。
2.顺序表的尾插
前文曾说过，顺序表的底层为数组，所以我们可以先想想数组的尾插入是什么样的：
尾差为直接在数组的结尾处插入数据，顺序表也同理：
但首先，我们要考虑一下问题：
- 初始化中，明确的将值放置为NULL ，0值，插入操作该先怎么办。
- 作为动态顺序表,如果当前容量满了，我们该怎么办。
解决办法： 调用扩容函数
void kuo(SL* h);
不太会起函数名哈；
void kuo(SL* h) { if (h->capacity == h->size) { int newcapacity = h->capacity == 0 ? 4 : 2 * h->capacity; type* tmp = (type*)realloc(h->arr, sizeof(type) * newcapacity); if (tmp) { h->arr = tmp; h->capacity = newcapacity; } else { exit(1); } } }解释：
核心目标：当顺序表已满（size == capacity）时，扩大内存空间。
1. 扩容触发条件h->size：当前有效元素个数（已使用空间）。h->capacity：当前总容量（已分配空间）。当两者相等时，说明数组已满，插入新元素会导致越界，必须先扩容。
2. 计算新容量newcapacity
（增容：我们一般成倍数增加，最好是两倍。这样可以有效降低增容的次数，就算可能会存在空间的浪费，但是也不会有太多浪费。）三目运算符逻辑：若初始容量为0（h->capacity == 0，即首次扩容），则新容量设为 4（默认初始值，可自定义，如8）。若已有容量（如4），则新容量设为 原容量的2倍（2 * h->capacity，例如4→8，8→16）。为什么2倍扩容？时间效率：分摊扩容成本。若每次只扩1个空间，频繁插入会导致多次扩容（每次扩容时间复杂度O(n)），总时间复杂度退化到O(n²)；2倍扩容：每次扩容后可支持多次插入，分摊后单次插入的平均时间复杂度为O(1)（均摊分析）。
3. 动态内存分配（realloc）realloc功能：重新分配h->arr指向的内存空间，新大小为sizeof(type) * newcapacity（总字节数 = 单个元素大小 × 新容量）。若h->arr为NULL（首次扩容），realloc等价于malloc（直接分配新空间）。临时指针tmp：避免直接修改h->arr。若realloc失败（内存不足），会返回NULL，此时若直接赋值给h->arr，会导致原内存地址丢失（内存泄漏）。
4. 扩容结果处理成功时：更新顺序表的arr（指向新内存）和capacity（记录新容量）。失败时：realloc返回NULL，此时程序无法继续运行（无空间存储新元素），通过exit(1)退出（1表示异常退出）。
本函数很有用，凡是插入值得函数，都要先调用一下函数的，作为检测。
此时尾插入函数就好写了：
void SLpushback(SL* h, type x)
void SLpushback(SL* h, type x) { kuo(&h); h->arr[h->size++] = x; }函数调用：
3.顺序表的头插
前文曾说过，顺序表的底层为数组，所以我们可以先想想数组的头插入是什么样的：
数组想头部插入一个值，做法是进行数据的移动，将数据整体的向后移动一位，顺序表也是如此，但头插入操作时，也需要考虑下扩容的。
void kuo(SL* h);
void kuo(SL* h) { if (h->capacity == h->size) { int newcapacity = h->capacity == 0 ? 4 : 2 * h->capacity; type* tmp = (type*)realloc(h->arr, sizeof(type) * newcapacity); if (tmp) { h->arr = tmp; h->capacity = newcapacity; } else { exit(1); } } }接下来，写一下头插入函数：
void SLpushfront(SL* h, type x)
void SLpushfront(SL* h, type x) { kuo(h); int i; for (i = h->size; i > 0; i--) { h->arr[i] = h->arr[i - 1]; } h->arr[i] = x; h->size++; }注意：头插，顺序表中的其它元素一定是从后往前的顺序向后移动一位。
4.顺序表的尾删
尾部删除一个值，其实并不难，不需要使用free释放掉或是令h->arr[h->size-1]=0，然后h->size--，我们只要将当前记录节点个数减一即可，这样访问时便访问不到该值，在之后如果插入值，会覆盖掉我们认为删去的值的。
void popback(SL* h);
void popback(SL* h) { h->size--; }我们也可以更谨慎些：
void popback(SL* h) { assert(h && h->size); h->size--; }使用assert(h && h->size)确保：h不为空指针（避免对空指针解引用）；顺序表当前size > 0（避免删除空表，防止size那里出现问题）。
记住要有#include<assert.h> 头文件。
5.顺序表的头删
头删与尾删和头插入、尾部插入的操作相反，既然头插入是整体的像后方移动一位，那我们可以通过（除了头节点）整体的向前方移动一位，来实现头部删除。
void popfront(SL* h)；
void popfront(SL* h) { assert(h && h->size); int i; for (i = 0; i < h->size - 1; i++) { h->arr[i] = h->arr[i + 1]; } h->size--; }通过 for 循环（i 从 0 到 size-2）将数组中 从第2个元素开始的所有元素依次向前移动一位，覆盖头部元素（arr[0]）。移动完成后，h->size-- 减少顺序表长度，原头部元素被删除。
四、尾插，头插，尾删，头删时间复杂度对比：
1.尾插入：
该插入为直接找到位置，直接在位置处插入值，复杂度O(1)。
2.头插入：
该插入为将该位置起的节点整体后移一位，之后在首位置处插入值，经历了一次for循环，复杂度O(n)。
3.尾删：
该删除为直接使节点数减一，复杂度O(1)。
4.头删：
该插入为将该首位置后的节点整体前移一位，之后首位置处值被覆盖，经历了一次for循环，复杂度O(n)。
总结
以上就是今天要讲的内容，本篇文章涉及的知识点为：顺序表介绍、顺序表概念与结构、顺序表分类、动态顺序表的实现、尾插，头插，尾删，头删时间复杂度对比等知识的相关内容，为本章节知识的内容，希望大家能喜欢我的文章，谢谢各位，接下来的内容我会很快更新。
