数据结构（03）——线性表（顺序存储和链式存储）
Hi！探索者们😉，欢迎踏入 408 数据结构的奇妙秘境🌿！
我是 ankleless📚，和你并肩的寻宝人～ 这是我的探险手札🗺️，里面记着链表森林的岔路陷阱🕸️、栈与队列城堡的机关密码🔐、二叉树山脉的攀登技巧🚶♀️，还有哈希表迷宫的快捷密道🌀，盼着能帮你避开数据结构的暗礁险滩🌊。
愿我们在算法峡谷🌄各自披荆斩棘，在复杂度峰顶🥇击掌相庆，共观数据流转的星河璀璨🌠！冲呀！🚀
1. 线性表
1.1 线性表的定义
线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n = 0时，线性表是一个空表。若用L命名线性表，则其一般表示为：
L = （a1,a2,a3,.......an-1,an）
式中，a1是唯一的“第一个”数据元素，又称表头元素；an是唯一的“最后一个”数据元素，又称表尾元素，除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继（“直接前驱”和“前驱”、“直接后继”和“后继”通常被视为同义词）。以上就是线性表的逻辑特性，这种线性有序的逻辑结构正式线性表名字的由来。
总结：
表中元素的个数有限；
表中元素具有逻辑上的顺序性，表中元素有其先后次序；
表中元素都是数据元素，每个元素都是单个元素；
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间；
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。
注：线性表是一种逻辑结构（线性结构），表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。
1.2 线性表的基本操作
一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。复杂的问题是由一个个小问题堆积而成的，要具有繁化简的思想。
//线性表的基本操作
InitList(&L);//初始化表。构建一个空的线性表
Length(L);//求表长，返回线性表L的长度，即L中数据元素的个数
LocateElem(L, e);//按值查找操作。在表L中查找具有给定关键字值的元素
GetElem(L, i);//按位查找操作，获取表L中位置i上的元素的值
ListInsert(&L, i, e);//插入操作，在表L中的位置i上插入指定元素e
ListDelete(&L, i, &e);//删除操作，删除表L中位置i上的元素e，并返回删除元素的值
PrintList(L);//输出操作，按前后顺序输出线性表L的所有元素值
Empty(L);//判空操作，若L为空表，则返回true，否则返回false
DestroyList(&L);//销毁操作，销毁线性表，并释放线性表L所占用的内存空间
//上述基本操作的命名增强了可读性，这也是变量命名的一些技巧参考基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同；
符号“&”表示C++语言中的引用调用，在C语言中采用指针也可以达到同样的效果。
注：基本操作中使用到指针或引用调用的地方，都是需要对线性表内数据进行变化操作（改变L的元素、表长等）
2. 顺序表
顺序表是用一段 连续的存储单元 依次存储数据元素的线性结构，可理解为 “加强版数组”，支持随机访问，适合频繁查询、少增删场景。
2.1 顺序表的定义
顺序表本质是结构体，包含 “存储数据的数组 + 记录有效元素个数的长度”，C 语言示例：
// 顺序表结构体定义（假设存储 int 类型，可按需改）
#define MAX_SIZE 100 // 顺序表最大容量
typedef struct {int data[MAX_SIZE]; // 数组存储数据int length; // 当前有效元素个数
} SeqList;data：连续数组，存数据本体；length：标记已有元素数量，方便操作（比如插入时找位置、判断是否满了）。
2.2 顺序表基本操作的实现
2.2.1 顺序表的创建
“创建” 即定义并初始化一个空顺序表，C 语言里可直接声明变量 + 手动清 0，或写函数封装：
// 函数方式创建空顺序表
SeqList createSeqList() {SeqList L;L.length = 0; // 初始无元素// 数组默认可能有脏数据，可循环清 0（简单场景也可跳过，按需处理）for (int i = 0; i < MAX_SIZE; i++) {L.data[i] = 0;}return L;
}// 调用示例
int main() {SeqList list = createSeqList();printf("创建的顺序表长度：%d\n", list.length); // 输出 0return 0;
}逻辑：初始化 length 为 0，保证后续增删能正确统计元素数量；清数组是为了避免内存里残留的随机值干扰。
2.2.2 顺序表的初始化
和 “创建” 类似，有时会把初始化单独拆成函数（尤其是需要动态分配内存的场景，不过这里用静态数组简化），核心是重置 length 和数据：
// 初始化顺序表（复用已有的顺序表变量）
void initSeqList(SeqList *L) { // 用指针修改传入的顺序表L->length = 0;for (int i = 0; i < MAX_SIZE; i++) {L->data[i] = 0;}
}// 调用示例
int main() {SeqList list;initSeqList(&list); // 传地址，让函数内部能修改printf("初始化后长度：%d\n", list.length); // 输出 0return 0;
}为什么用指针 *L？因为要修改主函数里 list 的值，值传递（直接传 list）只能改副本，指针 / 引用才能真正改原变量 → 这就是开头说的 “需要改数据时用指针 / 引用” 的典型场景！
2.2.3 插入操作
目标：在顺序表第 pos 个位置（从 1 开始数）插入新元素 value，插入后元素后移，length 加 1。
难点：需要先判断 “顺序表是否满了”“插入位置是否合法”，再批量移动元素。
// 插入操作：pos 是插入的位置（1~length+1），value 是要插入的值
int insertSeqList(SeqList *L, int pos, int value) {// 1. 检查顺序表是否已满if (L->length == MAX_SIZE) {printf("顺序表满了，无法插入！\n");return 0; // 插入失败}// 2. 检查插入位置是否合法（pos 范围：1 ~ length+1）if (pos < 1 || pos > L->length + 1) {printf("插入位置 %d 不合法！\n", pos);return 0; // 插入失败}// 3. 元素后移：从最后一个元素开始，往后挪一位，给新元素腾位置for (int i = L->length; i >= pos; i--) { L->data[i] = L->data[i - 1]; // 比如 pos=3，data[2]→data[3]，依此类推}// 4. 插入新元素 + 更新长度L->data[pos - 1] = value; // 数组下标从 0 开始，所以 pos-1L->length++;return 1; // 插入成功
}// 调用示例
int main() {SeqList list;initSeqList(&list);// 插入几个元素试试insertSeqList(&list, 1, 10); // 位置 1 插入 10insertSeqList(&list, 2, 20); // 位置 2 插入 20// 输出看看：应该是 [10,20]，长度 2for (int i = 0; i < list.length; i++) {printf("%d ", list.data[i]); }return 0;
}关键逻辑：
- 后移从
length开始往前遍历，避免 “先挪前面的，后面的被覆盖”；pos是用户视角的 “第几个位置”（1 起始），所以数组下标要减 1；- 插入成功后
length必须 +1，否则后续操作会错位。
2.2.4 删除操作
目标：删除第 pos 个位置的元素，后面元素前移，length 减 1
// 删除操作：pos 是要删除的位置（1~length）
int deleteSeqList(SeqList *L, int pos) {// 1. 检查顺序表是否为空if (L->length == 0) {printf("顺序表为空，无法删除！\n");return 0;}// 2. 检查位置是否合法（pos 范围：1 ~ length）if (pos < 1 || pos > L->length) {printf("删除位置 %d 不合法！\n", pos);return 0;}// 3. 元素前移：从 pos 位置开始，后面的元素往前补for (int i = pos; i < L->length; i++) {L->data[i - 1] = L->data[i]; // 比如 pos=2，data[2]→data[1]}// 4. 更新长度（逻辑删除，实际数组可能有残留值，但 length 控制访问）L->length--;return 1;
}// 调用示例（基于之前插入的 list）
int main() {SeqList list;initSeqList(&list);insertSeqList(&list, 1, 10);insertSeqList(&list, 2, 20);// 删除位置 2 的元素（值为 20）deleteSeqList(&list, 2); // 输出：应该只剩 [10]，长度 1for (int i = 0; i < list.length; i++) {printf("%d ", list.data[i]); }return 0;
}关键逻辑：
- 前移从
pos开始往后遍历，把后面的元素往前 “挤”，覆盖要删除的位置；length--后，后续操作不会访问到已删除的元素（虽然数组里可能还有旧值，但逻辑上被截断了）。
2.2.5 查找操作
目标：按值查找元素位置，或按位置查找值（这里演示 “按值找下标”，按位置找值很简单，直接 data[pos-1] 即可）。
// 按值查找：返回第一个匹配值的下标（从 0 开始），没找到返回 -1
int findByValueSeqList(SeqList L, int value) { for (int i = 0; i < L.length; i++) {if (L.data[i] == value) {return i; // 找到，返回下标}}return -1; // 没找到
}// 调用示例
int main() {SeqList list;initSeqList(&list);insertSeqList(&list, 1, 10);insertSeqList(&list, 2, 20);int index = findByValueSeqList(list, 20);if (index != -1) {printf("值 20 的下标是：%d\n", index); // 输出 1} else {printf("没找到~");}return 0;
}为什么用值传递 SeqList L？因为查找操作 不修改 顺序表数据，用值传递也能工作；如果要改数据（比如插入、删除），才必须用指针 / 引用！
3. 链表
链表是用 零散的节点 存储数据，每个节点存 “数据 + 指向下一节点的指针”，无需连续内存，适合频繁增删场景（不用像顺序表那样批量移动元素）。
3.1 单链表
单链表节点只有一个指针指向下一个节点，结构简单，是链表基础。
3.1.1 单链表的定义
单链表节点 + 链表结构（用头指针标记起点），C 语言示例：
// 单链表节点结构体
typedef struct Node {int data; // 数据域：存具体值struct Node *next; // 指针域：存下一个节点的地址
} Node;// 单链表：用头指针表示，指向第一个节点（空链表则为 NULL）
typedef struct {Node *head; // 头指针
} LinkList;data：存当前节点的值；next：存下一个节点的地址，串联整个链表；head：链表的 “入口”，通过它能找到所有节点。
3.1.2 单链表的初始化
目标：创建一个 空链表（头指针指向 NULL，没有节点）。
// 初始化单链表（创建空链表）
void initLinkList(LinkList *L) {L->head = NULL; // 头指针置空，链表无节点
}// 调用示例
int main() {LinkList list;initLinkList(&list);// 此时 list.head == NULL，是空链表return 0;
}为什么用指针 *L？因为要修改 list.head 的值（让它指向 NULL），必须传地址，否则函数里改的是副本，主函数里 list.head 不会变 → again，需要改数据时用指针 / 引用！
3.1.3 单链表--求表长
目标：遍历链表，统计节点个数（空链表返回 0）。
// 求单链表长度（节点个数）
int getLengthLinkList(LinkList L) { // 不用改数据，值传递也够int count = 0;Node *p = L.head; // 指针 p 从头节点开始遍历while (p != NULL) { // 只要 p 没走到链表末尾（NULL）count++;p = p->next; // 跳到下一个节点}return count;
}// 调用示例（后续插入节点后用，现在先演示逻辑）
int main() {LinkList list;initLinkList(&list);// 此时是空链表，长度 0printf("链表长度：%d\n", getLengthLinkList(list)); return 0;
}遍历逻辑：用 p 当 “游标”，从头节点出发，每次跳 p->next，直到 p 变成 NULL（链表末尾），循环次数就是节点数。
3.1.4 单链表--按序查找
目标：找第 pos 个位置的节点（从 1 开始数），返回节点指针（找不到返回 NULL）。
// 按序查找：pos 是位置（1~length），返回节点指针
Node* findByPosLinkList(LinkList L, int pos) {// 1. 处理非法位置（pos 必须 ≥1，且不超过链表长度）if (pos < 1) {printf("位置 %d 不合法！\n", pos);return NULL;}// 2. 遍历找位置Node *p = L.head;int count = 1; // 当前遍历到第几个节点（从 1 开始）while (p != NULL && count < pos) { p = p->next;count++;}// 3. 判断是否找到（p 为 NULL 说明没到 pos 就走完了）if (p == NULL) {printf("位置 %d 超出链表长度！\n", pos);return NULL;}return p; // 找到，返回节点指针
}// 调用示例（后续插入节点后用，先理解逻辑）
// 假设链表有 3 个节点：10→20→30，找 pos=2 → 应返回存 20 的节点关键逻辑：
- 用
count记录当前遍历到第几个节点，走到count == pos时停下；- 如果
p提前变成 NULL，说明链表长度不够，返回 NULL。
3.1.5 单链表--按值查找
目标：找第一个值等于 value 的节点，返回指针（找不到返回 NULL）。
// 按值查找：返回第一个值匹配的节点指针
Node* findByValueLinkList(LinkList L, int value) {Node *p = L.head;while (p != NULL) {if (p->data == value) {return p; // 找到，返回节点}p = p->next; // 没找到，继续下一个}return NULL; // 遍历完没找到
}// 调用示例（后续插入节点后用）
// 假设链表节点值是 10→20→30，找 value=20 → 返回存 20 的节点逻辑：和顺序表的按值查找类似，遍历每个节点对比 data，找到就返回，否则继续。
3.1.6 单链表--插入结点
目标：在第 pos 个位置插入新节点（分 “头插”“中间 / 尾插”，逻辑统一处理）。
步骤：
- 找到第
pos-1个节点（插入位置的前驱节点）； - 新节点的
next指向原pos节点； - 前驱节点的
next指向新节点。// 插入节点：pos 是位置（1~length+1），value 是新节点的值 int insertNodeLinkList(LinkList *L, int pos, int value) {// 1. 处理 pos=1 的特殊情况（头插）if (pos == 1) {Node *newNode = (Node*)malloc(sizeof(Node)); // 分配新节点内存if (newNode == NULL) {printf("内存分配失败！\n");return 0;}newNode->data = value;newNode->next = L->head; // 新节点 next 指向原头节点L->head = newNode; // 头指针指向新节点return 1;}// 2. 找 pos-1 位置的前驱节点Node *pre = findByPosLinkList(*L, pos - 1); // 注意传 *L（值传递）if (pre == NULL) {return 0; // 找不到前驱，插入失败}// 3. 分配新节点并插入Node *newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败！\n");return 0;}newNode->data = value;newNode->next = pre->next; // 新节点 next 指向原 pos 节点pre->next = newNode; // 前驱节点 next 指向新节点return 1; }// 调用示例 int main() {LinkList list;initLinkList(&list);// 插入几个节点：insertNodeLinkList(&list, 1, 10); //
3.1.7 单链表--删除操作
目标：删除第 pos 个位置的节点，需处理 “删头节点”“删中间 / 尾节点” 两种情况，核心是 找到前驱节点，跳过待删节点并释放内存。
// 单链表节点结构体（复用之前的定义）
typedef struct Node {int data; // 数据域struct Node *next; // 指针域：指向下一个节点
} Node;// 单链表结构体（复用之前的定义）
typedef struct {Node *head; // 头指针，指向第一个节点
} LinkList;// 删除操作：pos 是要删除的位置（1 ~ 链表长度）
int deleteNodeLinkList(LinkList *L, int pos) {// 1. 处理空链表if (L->head == NULL) {printf("链表为空，无法删除！\n");return 0;}Node *p = NULL; // 用来存待删除的节点// 2. 处理删除头节点（pos = 1）if (pos == 1) {p = L->head; // 标记头节点L->head = L->head->next; // 头指针指向下一个节点} else {// 3. 找 pos-1 位置的前驱节点Node *pre = findByPosLinkList(*L, pos - 1); // 调用之前实现的按序查找if (pre == NULL || pre->next == NULL) {printf("位置 %d 不合法，删除失败！\n", pos);return 0;}p = pre->next; // 标记待删除节点pre->next = p->next; // 前驱节点跳过待删节点}// 4. 释放待删除节点的内存（避免内存泄漏）free(p);p = NULL;return 1;
}// 辅助函数：按位置查找节点（复用之前的 findByPosLinkList）
Node* findByPosLinkList(LinkList L, int pos) {if (pos < 1) {printf("位置 %d 不合法！\n", pos);return NULL;}Node *p = L.head;int count = 1;while (p != NULL && count < pos) {p = p->next;count++;}if (p == NULL) {printf("位置 %d 超出链表长度！\n", pos);}return p;
}3.1.8 头插法建立单链表
目标：每次把新节点插在 链表头部（头指针位置），适合需要 逆序输入 的场景（比如输入 1 2 3，链表是 3 → 2 → 1）。
// 头插法建表：输入 n 个数据，返回创建好的链表
LinkList createListByHeadInsert() {LinkList L;L.head = NULL; // 初始化空链表int n, value;printf("请输入链表长度 n：");scanf("%d", &n);for (int i = 0; i < n; i++) {printf("请输入第 %d 个数据：", i + 1);scanf("%d", &value);// 1. 分配新节点Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = value;// 2. 头插逻辑：新节点 next 指向原头节点newNode->next = L.head;// 3. 头指针指向新节点（新节点成为新的头）L.head = newNode;}return L;
}3.1.9 尾插法建立单链表
目标：每次把新节点插在 链表尾部，适合需要 顺序输入 的场景（输入 1 2 3，链表就是 1 → 2 → 3）。
// 尾插法建表：输入 n 个数据，返回创建好的链表
LinkList createListByTailInsert() {LinkList L;L.head = NULL; // 初始化空链表Node *tail = NULL; // 尾指针，始终指向最后一个节点int n, value;printf("请输入链表长度 n：");scanf("%d", &n);for (int i = 0; i < n; i++) {printf("请输入第 %d 个数据：", i + 1);scanf("%d", &value);// 1. 分配新节点Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = NULL; // 新节点是尾部，next 置空// 2. 尾插逻辑if (L.head == NULL) {// 链表为空时，头指针和尾指针都指向新节点L.head = newNode;tail = newNode;} else {// 链表非空时，尾节点 next 指向新节点，更新尾指针tail->next = newNode;tail = newNode;}}return L;
}持续更新修正内容中~