数据结构C语言版笔记如何高效掌握核心要点？-C语言-盈思创科技

《数据结构（C语言版）》核心知识点笔记

导论：为什么要学习数据结构？

数据结构是计算机存储、组织数据的方式，选择合适的数据结构，可以让算法的效率更高，C语言以其接近硬件、指针操作灵活的特点,是实现数据结构的绝佳语言。

核心思想：

数据: 描述客观事物的符号,是计算机操作的对象。
数据元素: 数据的基本单位,在程序中通常作为一个整体考虑。
数据项: 组成数据元素的、有独立含义的最小单位。
数据对象: 性质相同的数据元素的集合,是数据的一个子集。
数据结构: 相互之间存在一种或多种特定关系的数据元素的集合，包括三个要素：逻辑结构、存储结构、数据的运算。

第一章线性表

线性表是最简单、最基本的数据结构。

1 逻辑结构

元素之间是“一对一”的关系，即除了第一个和最后一个元素外,其他元素都有且仅有一个直接前驱和一个直接后继。

2 存储结构

A. 顺序存储 - 顺序表

定义： 用一段地址连续的存储单元依次存储线性表中的数据元素。
C语言实现： 通常使用数组。
核心特点：
- 优点：
  1. 随机访问：可以通过首地址和元素下标在 O(1) 时间内找到任意元素。
  2. 存储密度高,无需额外空间存储元素间的逻辑关系。
- 缺点：
  1. 大小固定： 预先分配的数组空间可能不够（溢出）或造成浪费。
  2. 插入/删除效率低： 在中间或头部插入/删除元素需要移动大量元素，时间复杂度为 O(n)。
C语言实现要点（动态数组）：
- 使用指针 int *data; 来指向动态分配的内存。
- 使用 int length; 记录当前元素个数。
- 使用 int capacity; 记录当前数组的总容量。
- 关键操作：
  - 初始化： malloc 分配初始空间。
  - 扩容： 当 length == capacity 时，使用 realloc 重新分配更大的内存（通常是原容量的2倍）,并将旧数据拷贝过去。
  - 插入：
    1. 检查是否需要扩容。
    2. 检查插入位置 i 是否合法 (0 <= i <= length)。
    3. 将 i 位置及之后的所有元素后移一位。
    4. 将新元素放入 i 位置。
    5. length++。
  - 删除：
    1. 检查删除位置 i 是否合法 (0 <= i < length)。
    2. 将 i 位置之后的所有元素前移一位。
    3. length--。

B. 链式存储 - 链表

定义： 用一组任意的存储单元存储线性表中的元素，这组存储单元可以是连续的，也可以是不连续的，每个元素包含两部分：数据域 和 指针域。
核心特点：
- 优点：
  1. 大小动态： 可以按需分配内存,没有容量限制。
  2. 插入/删除效率高： 只需修改相关节点的指针即可，时间复杂度为 O(1)（在已知操作位置的情况下）。
- 缺点：
  1. 不能随机访问： 访问第 i 个元素必须从头节点开始遍历，时间复杂度为 O(n)。
  2. 存储密度低： 每个节点都需要额外的空间存储指针。
C语言实现要点：
- 定义节点结构体：
```
typedef struct Node {
    int data;           // 数据域，可以是任意类型
    struct Node *next;  // 指针域，指向下一个节点
} Node;
```
- 链表类型：
  1. 单链表： 每个节点只包含一个指向下一个节点的指针。
  2. 双链表： 每个节点包含 *prev 和 *next 两个指针，可以双向遍历。
```
typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;
```
  3. 循环链表： 尾节点的 next 指针指向头节点（单循环）或头节点的前驱（双循环）。
  4. 静态链表： 使用数组实现，数组元素包含数据和指向数组下标的指针,用于不支持指针的语言或环境。
关键操作（以单链表为例）：
- 遍历： 从头节点 head 开始，使用 p = p->next 直到 p == NULL。
- 头插法：
  1. 创建新节点 new_node。
  2. new_node->next = head;
  3. head = new_node;
- 尾插法： 需要一个 tail 指针始终指向尾节点,以提高效率。
- 在节点 p 后插入：
  1. 创建新节点 s。
  2. s->next = p->next;
  3. p->next = s;
- 删除节点 p 的后继：
  1. q = p->next;
  2. p->next = q->next;
  3. free(q); // 释放内存！

第二章栈与队列

它们是两种特殊的线性表,其操作受限。

1 栈

逻辑结构： 线性表。
操作特性： 后进先出，只能在表尾（栈顶）进行插入和删除操作。
C语言实现：
- 顺序栈： 使用数组实现，用一个 top 变量（或 top 指针）标记栈顶元素的位置。
- 链栈： 使用链表实现，通常在链表的头部进行插入和删除,效率更高。
核心应用：
- 函数调用栈
- 表达式求值（后缀表达式）
- 括号匹配
- 浏览器的前进/后退

2 队列

逻辑结构： 线性表。
操作特性： 先进先出，在队尾插入元素,在队头删除元素。
C语言实现：
- 顺序队列（循环队列）： 为了避免假溢出（头尾指针相遇但队列未满），将数组逻辑上看成一个环，需要区分队空 (front == rear) 和队满 ((rear + 1) % MAXSIZE == front) 的条件。
- 链队列： 使用链表实现，通常需要头指针 front 和尾指针 rear。
核心应用：
- 广度优先搜索
- 操作系统中的进程调度
- 打印任务队列

第三章树

非线性数据结构，元素之间是“一对多”的关系。

1 树的基本概念

根节点： 没有前驱的节点。
叶子节点： 没有后继的节点。
度：一个节点拥有的子树数量。
树的度： 树中所有节点的度的最大值。
深度/高度： 树中节点的最大层次。

2 二叉树

定义： 度不超过2的树，每个节点最多有两个子节点，分别称为左孩子和右孩子。
特殊二叉树：
- 满二叉树： 每一层都达到最大节点数。
- 完全二叉树： 对一棵二叉树，从上到下，从左到右编号，如果所有节点编号都与满二叉树对应位置一致,则为完全二叉树。
性质：
1. 第 i 层最多有 2^(i-1) 个节点。
2. 深度为 k 的二叉树最多有 2^k - 1 个节点。
3. 任意一棵二叉树，度为0的节点数（n0）总比度为2的节点数（n2）多1，即 n0 = n2 + 1。

3 二叉树的存储结构

顺序存储： 仅适用于完全二叉树，使用数组，父节点和孩子节点的下标有固定关系：
- 父节点下标 i，左孩子下标 2*i + 1，右孩子下标 2*i + 2。

链式存储：

二叉链表： 最常用。

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

4 二叉树的遍历

遍历是二叉树最核心的操作,有四种方式。

递归实现（核心思想）：
1. 先序遍历： 根 -> 左 -> 右
2. 中序遍历： 左 -> 根 -> 右
3. 后序遍历： 左 -> 右 -> 根
4. 层序遍历： 从上到下，从左到右（通常使用队列实现）。
非递归实现（面试重点）：
- 先序遍历： 使用栈。
  1. 将根节点入栈。
  2. 循环：栈不为空，则出栈一个节点并访问，然后将其右孩子入栈，再将其左孩子入栈（因为栈是后进先出，所以先右后左）。
- 中序遍历： 使用栈。
  1. 从根节点开始,一路向左将所有节点入栈。
  2. 循环：栈不为空,则出栈一个节点并访问。
  3. 转向出栈节点的右子树,重复步骤1。
- 后序遍历： 使用栈（较复杂），或者“双栈法”或“标记法”。

5 线索二叉树

利用二叉链表中空的 lchild 和 rchild 指针，指向前驱和后继,提高遍历效率。

6 树与森林

树的存储： 双亲表示法、孩子表示法、孩子兄弟表示法（最常用，可以方便地转换为二叉树）。
森林与二叉树的转换： 孩子兄弟表示法是转换的桥梁。

7 哈夫曼树

带权路径长度最小的二叉树，常用于哈夫曼编码,进行数据压缩。

第四章图

非线性数据结构，元素之间是“多对多”的关系。

1 图的基本概念

顶点: 图中的数据元素。
边: 顶点之间的连线。
有向图/无向图
带权图/网
路径、路径长度、连通图、生成树

2 图的存储结构

邻接矩阵：
- C语言实现： 使用一个二维数组 int G[V][V];。
- 特点：
  - 适合稠密图（边数接近 n^2）。
  - 直观，易于实现，判断两点间是否有边非常快（O(1)）。
  - 空间复杂度为 O(V^2),空间消耗大。
邻接表：
- C语言实现： 使用“数组 + 链表”结构，数组 AdjList[V] 存储每个顶点的头指针，每个头指针指向一个链表,链表中的节点表示与该顶点相邻的其他顶点。
- 特点：
  - 适合稀疏图（边数远小于 n^2）。
  - 空间复杂度为 O(V+E),节省空间。
  - 查找一个顶点的所有邻接点很快。

3 图的遍历

深度优先搜索：
- 思想： 尽可能深地搜索图的分支,类似树的先序遍历。
- 实现： 使用递归或栈，需要 visited 数组标记已访问节点。
广度优先搜索：
- 思想： 先访问所有直接邻接点,再逐层访问邻接点的邻接点。
- 实现： 使用队列，需要 visited 数组标记已访问节点。

4 图的应用

最小生成树：
- Prim 算法： 从一个顶点开始，逐步选择与当前树连接的最小权边，适合稠密图（邻接矩阵）。
- Kruskal 算法： 按边的权值从小到大选择，且不构成回路，适合稀疏图（邻接表）。
最短路径：
- Dijkstra 算法： 求单源最短路径,不能处理负权边。
- Floyd 算法： 求任意两点间最短路径，可以处理负权边（但不能有负权回路）。
拓扑排序：
- 应用： 用于解决工程的先后顺序问题（如课程安排、编译依赖）。
- 思想： 每次选择一个入度为0的顶点输出，并删除其所有出边，直到所有顶点输出或剩余顶点入度均不为0（存在环）。
- 实现： 使用队列,统计每个顶点的入度。
关键路径：
- 应用： 用于找出工程中的关键活动（影响整个工期的活动）。
- 思想： 在AOE网（Activity On Edge Network）上，计算每个事件的最早发生时间和最晚发生时间,差值为0的活动即为关键活动。

第五章查找

在数据集合中寻找特定元素。

1 静态查找

顺序查找： 从表头开始逐个比较，简单，但效率低（O(n)）。
折半查找：
- 前提： 查找表必须有序，且为顺序存储。
- 思想： 每次将查找区间折半,比较中间元素。
- 效率： O(log n)。

2 动态查找

二叉排序树:
- 定义： 左子树所有节点值 < 根节点值 < 右子树所有节点值。
- 操作：
  - 查找：类似折半查找。
  - 插入：找到空位插入。
  - 删除：情况较复杂（叶子节点、单孩子节点、双孩子节点）。
- 缺点： 可能退化成单链表，查找效率降为 O(n)，可以通过平衡二叉树解决。
平衡二叉树:
- 定义： 任意节点的左右子树高度差（平衡因子）的绝对值不超过1。
- 代表： AVL树。
- 核心操作： 在插入和删除后，通过旋转（左旋、右旋、左右旋、右左旋）来恢复平衡。
B树 / B+树：
- 定义： 多路平衡查找树,专门为磁盘等外部存储设备设计。
- 特点： 每个节点可以有很多孩子，大大减少了树的深度，从而减少了磁盘I/O次数。
- B+树： B树的变种，所有数据记录都存储在叶子节点，非叶子节点只作为索引,数据库索引的常用结构。

3 哈希表

核心思想： 在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得 f(key) = address，这个对应关系 f 称为哈希函数。
C语言实现要点：
- 哈希函数： 将关键字映射到哈希表地址，常用方法：直接定址法、除留余数法（key % TableSize）、数字分析法、平方取中法等。
- 冲突处理： 两个不同的关键字通过哈希函数得到相同的地址，解决方法：
  1. 开放定址法：
    - 线性探测：f(key) = (f(key) + d) % m，d 为1, 2, 3, ...
    - 二次探测：d = 1^2, -1^2, 2^2, -2^2, ...
    - 伪随机探测。
  2. 链地址法： 将所有哈希地址相同的元素链接成一个单链表，这是C语言中最常用的方法，通常结合数组+链表实现。
性能分析： 一个好的哈希表，其平均查找时间接近 O(1)。

第六章排序

将一组无序的数据序列调整为有序序列。

1 插入排序

直接插入排序： 将待排序元素插入到已排序序列的适当位置，简单，但效率低（O(n^2)）。
希尔排序： 对直接插入排序的改进，将序列按某个增量 d 分成若干子序列，对子序列进行插入排序，然后逐步减小增量 d，直到 d=1，时间复杂度约为 O(n^(3/2))。

2 交换排序

冒泡排序： 每次比较相邻元素，如果顺序错误就交换，简单，效率低（O(n^2)）。
快速排序：
- 核心思想： 分治法。
1. 选基准： 从序列中选一个元素作为基准。
2. 分区： 将序列分为两部分，左边部分都小于基准,右边部分都大于基准。
3. 递归： 对左右两个子序列重复上述过程。
- 效率： 平均 O(n log n)，最坏情况（序列已有序或逆序）会退化到 O(n^2)。

3 选择排序

简单选择排序： 每次在未排序序列中找到最小（或最大）元素，放到已排序序列的末尾，效率 O(n^2)。
堆排序：
- 核心思想： 利用堆这种数据结构。
1. 建堆： 将待排序序列建成一个大顶堆（或小顶堆）。
2. 排序： 交换堆顶元素（最大/最小值）和堆的最后一个元素,然后将剩余元素调整成堆。
- 效率： O(n log n)，且是原地排序,空间复杂度低。

4 归并排序

核心思想： 分治法。
1. 分解： 将序列不断二分,直到每个子序列只有一个元素。
2. 合并： 将两个已排序的子序列合并成一个有序序列。
效率： O(n log n)，但需要额外的 O(n) 空间。

5 基数排序

核心思想： 分配收集,按关键字的不同位值进行排序。
效率： O(d*(n+r))，d 是关键字的位数，r 是基数（如10进制中r=10）,是线性时间排序。

学习建议与技巧

先理解，再编码： 不要一上来就埋头敲代码，先彻底理解每种数据结构的逻辑结构和核心思想，问自己：它为什么这样设计？解决了什么问题？
画图！画图！画图！ 数据结构是可视化的，无论是链表的插入删除、二叉树的遍历还是图的BFS/DFS,亲手画图是最好的理解方式。
掌握C语言指针： 数据结构（尤其是链表、树、图）的实现高度依赖指针，你必须熟练掌握指针的声明、赋值、解引用、结构体指针等操作。
从基础实现开始： 不要一开始就想着实现一个完美的、带所有功能的库，先实现一个最简单的链表或二叉树,只包含最基本的增删查改功能。
对比学习：
- 顺序表 vs 链表：对比它们的优缺点和适用场景。
- 栈 vs 队列：对比它们的操作规则和LIFO/FIFO特性。
- 各种排序算法：对比它们的时间/空间复杂度、稳定性、适用场景。
多写注释： 在写代码时，对关键步骤、指针的变化、边界条件（如链表的头尾、队列的满空）进行详细注释，这有助于理清思路,也方便日后回顾。
调试是关键： 学会使用GDB等调试工具，单步执行代码，观察变量和指针的变化,这是发现逻辑错误的最佳途径。

这份笔记涵盖了数据结构课程的核心内容，祝你学习顺利,在C语言的海洋中乘风破浪！

数据结构C语言版笔记如何高效掌握核心要点？

《数据结构（C语言版）》核心知识点笔记

导论：为什么要学习数据结构？

第一章线性表

1 逻辑结构

2 存储结构

A. 顺序存储 - 顺序表

B. 链式存储 - 链表

第二章栈与队列

1 栈

2 队列

第三章树

1 树的基本概念

2 二叉树

3 二叉树的存储结构

4 二叉树的遍历

5 线索二叉树

6 树与森林

7 哈夫曼树

第四章图

1 图的基本概念

2 图的存储结构

3 图的遍历

4 图的应用

第五章查找

1 静态查找

2 动态查找

3 哈希表

第六章排序

1 插入排序

2 交换排序

3 选择排序

4 归并排序

5 基数排序

学习建议与技巧

相关文章

数据结构C语言版如何高效学习？

数据结构(C语言版)清华大学出版社，如何高效学习？

目录[+]

《数据结构（C语言版）》核心知识点笔记

导论：为什么要学习数据结构？

第一章 线性表

1 逻辑结构

2 存储结构

A. 顺序存储 - 顺序表

B. 链式存储 - 链表

第二章 栈与队列

1 栈

2 队列

第三章 树

1 树的基本概念

2 二叉树

3 二叉树的存储结构

4 二叉树的遍历

5 线索二叉树

6 树与森林

7 哈夫曼树

第四章 图

1 图的基本概念

2 图的存储结构

3 图的遍历

4 图的应用

第五章 查找

1 静态查找

2 动态查找

3 哈希表

第六章 排序

1 插入排序

2 交换排序

3 选择排序

4 归并排序

5 基数排序

学习建议与技巧

相关文章

数据结构C语言版如何高效学习？

数据结构(C语言版)清华大学出版社，如何高效学习？

目录[+]

第一章线性表

第二章栈与队列

第三章树

第四章图

第五章查找

第六章排序