🤖 Assistant

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 📦 第二章 线性表

## 📚 基本概念
### 📌 什么是线性表？
🔹 **定义**：线性表是由 **n个数据元素**（结点）组成的 **有限序列**，元素类型相同，且具有 **逻辑上的顺序关系**  
🔹 **特点**：  
  - 唯一的`第一个元素`（无直接前驱）和`最后一个元素`（无直接后继）  
  - 其他元素有且仅有一个**直接前驱**和一个**直接后继**  
🔹 **示例**：  
  ![](https://cdn.jsdelivr.net/gh/kevinwho/pic@main/20230610160510.png)

---

## 📚 顺序存储结构（顺序表）
### 📌 定义与特点
```c
#define MAXSIZE 100  
typedef struct {  
    ElemType data[MAXSIZE];  
    int length;  
} SqList;

🔸 核心原理：用连续存储单元存放线性表元素
🔸 特性：

  • 支持随机访问（时间复杂度 O(1)）
  • 插入/删除平均移动 n/2 个元素（时间复杂度 O(n)）

📌 静态分配 vs 动态分配

类型 特点 适用场景
静态分配 数组大小固定 数据量已知且稳定
动态分配 可扩容（realloc） 数据量变化较大

📚 链式存储结构（链表）

📌 单链表结构

1
2
3
4
typedef struct LNode {  
    ElemType data;  
    struct LNode* next;  
} LNode, *LinkList;

🔹 核心要点：

  • 节点 = 数据域 + 指针域
  • 头指针 vs 头结点：
    • 头结点：为统一操作而添加的虚拟节点（data域无意义）
    • 带头结点的链表操作更统一

📌 循环链表

循环链表示意图
🔹 尾结点指针指向头结点
🔹 判空条件：尾结点->next == head

📌 双向链表

1
2
3
4
typedef struct DuLNode {  
    ElemType data;  
    struct DuLNode *prior, *next;  
} DuLNode, *DuLinkList;

🔹 特性：支持双向遍历
🔹 插入/删除需同时修改前后指针

📊 顺序表 vs 链表对比

操作\结构 顺序表 链表
存取元素 O(1) O(n)
插入/删除 O(n)（需移动元素） O(1)（仅修改指针）
空间分配 预先静态分配 动态实时分配
适用场景 查询多，增删少 频繁增删

🛠️ 应用场景

  1. 顺序表：高频随机访问（如数据库索引）
  2. 单链表：浏览器历史记录（支持后退）
  3. 双向链表：LRU缓存淘汰算法
  4. 循环链表：约瑟夫问题（Josephus problem）

🎨 思维导图总结

1
2
3
4
5
6
7
8
9
10
graph TD
    A[线性表] --> B[顺序表]
    A --> C[链表]
    B --> D[静态分配]
    B --> E[动态分配]
    C --> F[单链表]
    C --> G[循环链表]
    C --> H[双向链表]
    F --> I[带头结点]
    F --> J[不带头结点]