数据结构中的顺序表。首先阐述了线性表的逻辑与物理结构区别，引出顺序表的概念及其与数组的关系。内容涵盖静态与动态顺序表的分类，重点讲解了动态顺序表的初始化、销毁、增容机制以及头尾插删操作。随后提供了完整的 C 语言代码实现，包括头文件、源文件和测试文件，展示了顺序表的核心接口如 PushBack、PushFront、Erase、Find 等。最后分析了顺序表的优缺点，指出其插入删除时间复杂度为 O(N)，且增容过程存在空间浪费和性能消耗的问题。
线性表（linear list）是 n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就是说连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
物理结构上不一定连续，逻辑结构上连续是什么意思呢？我们拿顺序表和链表举例就可以明白
概念：顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。
这看起来不就是数组么？那么顺序表和数组又有什么区别呢？ 实质上：顺序表的底层就是数组，而顺序表对数组进行了封装，可以完成增删查改等操作…… 形象来说数组是苍蝇馆子，而顺序表则是米其林餐厅，同一种原料，但装饰是不同的。
使用静态顺序表有个缺陷：
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
如果我们使用动态顺序表，那么就需要定义一个空间容量，当空间不够时可以动态增容。 重命名 int 为 SLDataType，这样做的好处是如果我们存储的是字符形的顺序表，则只需要在重命名中将 int 形改成 char 形即可，而不需要在每一处涉及整形数组中的地方修改，方便了许多。
初始化时此顺序表并没有插入任何数据，因此需要将 size 和 capacity 都置为 0。
知道了顺序表的初始化，那么相对应的销毁也可以实现。
当要像顺序表的尾部插入数据时，将数据插入 size 中，同时让 size++。
那如果空间不够的时候呢？是否又可以拿数据进行尾插呢？肯定是不可以的，插入的数据会越界。 因此需要增容以继续插入新的数据。
什么情况下进行增容呢？ 当 size == capacity 的时候表示不能再插入数据，这时就要增容。 现在又面临一个问题，增容需要增多少倍合适呢？ 增容过小后面就需要多次增容 (导致性能低下等问题)， 增容过大又容易造成空间的浪费， 较为合适的情况是增加 1 倍或两倍(需从数学角度解释)。
为什么这块新开辟好的空间不直接让 ps->arr 接收呢？ 目的是防止 realloc 失败，成为 NULL 指针。
同样进行头插的时候也可能会面临空间不足的情况，因此我们可以考虑通过调用函数的方法把申请空间 (增容) 封装成一个函数，需要使用到的情况下直接调用这个函数。
让 ps->size–则完成了尾删。
头删的操作其实与头插的操作类似，需要注意的是ps->arr[0]=ps->arr[1], ps->arr[1]=ps->arr[2]……这样的顺序，如果是 ps->arr[ps->size-2]=ps->arr[ps->size-1], ps->arr[ps->size-3]=ps->arr[ps->size-2], 则会把原来数据覆盖掉。
插入完成后让 ps->size++
和指定位置插入数据的方法是类似的
删除数据
查找数据
在项目工程当中，其实并不是在一个源文件中写下所有代码，而是创建测试文件，源文件 (定义)，头文件 (声明) 完成代码功能实现。
SeqList.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
// 顺序表-->底层就是数组
// 但是提供了很多现成的方法，开箱即用，是很厉害的新的数据结构
// 顺序表是线性表的一种
// 物理结构 逻辑结构
// 顺序表 连续 连续
// 线性表 不一定连续 连续
// 静态顺序表
// struct SeqList
// {
// int arr[100]; //定长数组
// int size; //有效数据个数
// };
typedef int SLDataType;
// 动态顺序表
typedef struct SeqList {
SLDataType* arr;
int size; //有效数据个数
int capacity; //空间大小
} SL;
// 顺序表的初始化
void SLInit(SL* ps);
// 顺序表的销毁
void SLDestroy(SL* ps);
// 顺序表的打印
void SLPrint(SL s);
// 头部插入删除/尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
// 尾删
void SLPopBack(SL* ps);
// 头删
void SLPopFront(SL* ps);
// 指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x);
// 指定位置删除数据
void SLErase(SL* ps, int pos);
// 查找指定位置的数据
int SLFind(SL* ps, SLDataType x);
SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
// 顺序表的初始化
void SLInit(SL* ps) {
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
// 顺序表的销毁
void SLDestroy(SL* ps) {
if (ps->arr) {
free(ps->arr);
}
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
// 检测空间是否不足
void CheckCapacity(SL* ps) {
if (ps->capacity == ps->size) {
// 申请空间
// malloc calloc realloc int arr[10] -->增容 realloc
// 三目表达式
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));
// 要申请多大空间
if (tmp == NULL) {
perror("realloc");
exit(1); // 退出程序
}
// 空间申请成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
// 尾插
void SLPushBack(SL* ps, SLDataType x) {
assert(ps);
// ps->arr[ps->size] = x;
// ps->size++;
// 插入之前先看数据够不够
CheckCapacity(ps);
ps->arr[ps->size++] = x;
}
// 头插
void SLPushFront(SL* ps, SLDataType x) {
assert(ps);
CheckCapacity(ps);
for (int i = ps->size; i > 0; i--) {
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}
// 顺序表的打印
void SLPrint(SL s) {
for (int i = 0; i < s.size; i++) {
printf("%d ", s.arr[i]);
}
printf("\n");
}
// 尾删
void SLPopBack(SL* ps) {
assert(ps);
assert(ps->size);
--ps->size;
}
// 头删
void SLPopFront(SL* ps) {
assert(ps);
assert(ps->size);
for (int i = 0; i < ps->size - 1; i++) {
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
// 指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x) {
assert(ps);
assert(pos >= 0 && pos <= ps->size);
// 查看空间够不够
CheckCapacity(ps);
// 让 pos 后的位置往后挪动一位
for (int i = ps->size; i > pos; i--) {
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[pos] = x;
ps->size++;
}
// 指定位置删除数据
void SLErase(SL* ps, int pos) {
assert(ps);
assert(pos >= 0 && pos <= ps->size);
for (int i = pos; i < ps->size - 1; i++) {
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
// 查找指定位置的数据
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;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SLTest01() {
SL sl;
SLInit(&sl);
SLPushBack(&sl, 1);
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
SLPushBack(&sl, 5);
SLPushFront(&sl, 6);
SLPrint(sl);
SLPopBack(&sl);
SLPrint(sl);
SLPopFront(&sl);
SLPrint(sl);
SLInsert(&sl, 2, 5);
SLPrint(sl);
SLErase(&sl, 2);
SLPrint(sl);
int find = SLFind(&sl, 4);
if (find < 0) {
printf("没有找到!\n");
} else {
printf("找到了！下标为%d\n", find);
}
SLDestroy(&sl);
}
int main() {
SLTest01();
return 0;
}
其实这个顺序表的实现并不是很完美，它还是有诸多问题需要顾虑