# 1. 线性表的定义和基本操作
# 识记概念
- 线性表：有限个相同类型数据元素的有序序列（如学生名单）。
- 表长：线性表中元素的个数（空表长度为0）。
- 表头元素：序列中的第一个元素（如队列的首元素）。
- 表尾元素：序列中的最后一个元素（如队列的末元素）。
- 直接前驱/后继：若元素
B紧接在A之后，则A是B的直接前驱，B是A的直接后继。 - 有序表/无序表：元素是否按特定规则排列（如升序为有序表，随机排列为无序表）。
# 领会核心
- 抽象数据类型定义：定义线性表的逻辑特征（如插入、删除等操作），与存储无关。
- 元素逻辑关系：元素之间是一对一的线性关系，除首尾外每个元素有且仅有一个直接前驱和后继。
- 位置含义：元素在线性表中的逻辑顺序（如第1个、第2个元素）。
- 特点：
- 有限性（元素个数有限）
- 同一性（元素类型相同）
- 有序性（元素有明确先后顺序）
# 简单应用
- 操作结果的逻辑表示：
- 插入元素
X到位置i后，原i位置元素及后续元素后移一位。 - 删除位置
i的元素后，后续元素前移一位。
- 插入元素
# 2. 线性表的顺序存储及实现
# 识记概念
- 顺序表：用连续内存空间存储线性表元素（如数组实现）。
- 位置：元素在内存中的物理地址与其逻辑顺序一致。
# 领会核心
- 顺序存储思想：元素在内存中连续存放，通过下标直接访问。
- 随机访问：通过下标直接定位元素（如
arr[3]），时间复杂度O(1)。 - 关键概念：
- 表空：长度为0（
length=0）。 - 表满：元素数量达到存储空间上限。
- 长度：当前存储的元素个数。
- 表空：长度为0（
# 简单应用
- 下标地址计算：
- 第
i个元素的地址 = 首地址 + (i-1)*元素大小（假设从1开始计数）。
- 第
- 基本操作实现：
- 插入：需移动
i后的元素，时间复杂度O(n)。 - 删除：需移动
i后的元素，时间复杂度O(n)。 - 查找：通过下标直接访问，时间复杂度O(1)。
- 插入：需移动
# 综合应用
- 例：设计顺序表实现“动态数组”，支持动态扩容（如Java的ArrayList）。
# 3. 线性表的链式存储及实现
# 识记概念
- 单链表：每个结点包含数据域和指针域（指向下一个结点）。
- 头结点：链表首部附加的结点，简化插入/删除操作。
- 首结点/表尾结点：链表第一个实际元素为首结点，最后一个结点为表尾结点。
- 头指针：指向链表第一个结点的指针（可能指向头结点或首结点）。
- 循环链表：表尾结点指针指向头结点（单向循环）或前驱结点（双向循环）。
# 领会核心
- 链式存储思想：元素分散存储，通过指针链接。
- 头结点作用：统一处理插入/删除操作（无需单独处理首结点）。
- 顺序访问：需从头结点开始逐个遍历（时间复杂度O(n)）。
# 简单应用
- 基本操作实现：
- 插入：修改相邻结点的指针，时间复杂度O(1)（已知位置时）。
- 删除：同上，时间复杂度O(1)（已知位置时）。
- 查找：需遍历链表，时间复杂度O(n)。
- 结构性开销：每个结点需额外存储指针（如单链表每个结点多占4/8字节）。
# 综合应用
- 例：实现“约瑟夫环”问题，使用循环单链表模拟人员出列顺序。
# 总结对比
| 特性 | 顺序表 | 链表 |
|---|---|---|
| 存储方式 | 连续内存，支持随机访问 | 分散内存，需顺序访问 |
| 插入/删除 | 需移动元素，O(n) | 修改指针，O(1)（已知位置） |
| 空间开销 | 无额外指针，紧凑 | 需存储指针，结构性开销大 |
| 适用场景 | 频繁查询，少修改（如静态数据） | 频繁插入/删除（如动态数据） |
-----------------------------分割--------------------------------
# 扩展链表的插入和删除，指针如何操作
以下是链表插入和删除操作的详细指针操作步骤，结合实际场景和引用资料进行说明：
# 一、单链表插入操作
# 1. 插入到指定位置（非头非尾）
步骤：
- 创建新节点：分配内存并填充数据。
- 定位前驱节点：遍历链表找到目标位置的前一个节点
prev。 - 调整指针：
- 新节点的
next指向prev->next（即原后继节点）。 prev->next指向新节点。
- 新节点的
// 伪代码（C语言风格）
new_node->next = prev->next; // 新节点指向原后继
prev->next = new_node; // 前驱指向新节点
时间复杂度：O(n)（需遍历查找位置）。
# 2. 头插法（插入到链表头部）
步骤：
- 创建新节点。
- 直接调整头指针：
- 新节点的
next指向原头节点。 - 头指针指向新节点。
- 新节点的
new_node->next = head; // 新节点指向原头节点
head = new_node; // 更新头指针
时间复杂度：O(1)（无需遍历）。
# 3. 尾插法（插入到链表尾部）
步骤：
- 创建新节点。
- 遍历到尾节点：找到最后一个节点（
current->next == NULL）。 - 调整尾节点指针：
- 尾节点的
next指向新节点。
- 尾节点的
current->next = new_node; // 尾节点指向新节点
优化：若维护尾指针，可直接定位，时间复杂度O(1)。
# 二、单链表删除操作
# 1. 删除指定节点（非头非尾）
步骤：
- 定位前驱节点：找到待删除节点的前驱节点
prev。 - 调整指针：
prev->next指向待删除节点的后继节点。
- 释放内存：删除原节点。
prev->next = curr->next; // 前驱直接指向后继
free(curr); // 释放当前节点
时间复杂度：O(n)（需遍历查找前驱）。
# 2. 删除头节点
步骤：
- 临时保存头节点：
temp = head。 - 更新头指针：
head = head->next。 - 释放原头节点：
free(temp)。
temp = head;
head = head->next; // 头指针后移
free(temp); // 释放原头节点
时间复杂度：O(1)。
# 3. 使用二级指针简化删除（Linus技巧）
核心思想：通过二级指针直接修改节点指针，无需特殊处理头节点。
void delete_node(Node **head, int value) {
Node **curr = head; // 二级指针指向头指针
while (*curr) {
if ((*curr)->data == value) {
Node *temp = *curr;
*curr = (*curr)->next; // 修改前驱节点的指针
free(temp);
break;
}
curr = &(*curr)->next; // 移动到下一个指针的地址
}
}
优势：统一处理头节点和其他节点，代码更简洁。