数据结构 - PPT内容详细总结与注释

约 3978 个字 105 行代码 预计阅读时间 21 分钟

第一章 绪论

1.1 程序、数据结构与算法

• 程序的基本概念:

  • 一个计算机程序主要描述两样东西：数据结构 和 算法。
  • 数据结构 (Data Structure)：描述问题中的数据对象以及它们之间的关系。
  • 算法 (Algorithm)：对这些数据进行操作和处理的规则。
  • 经典公式：\(程序 = 数据结构 + 算法\)。

  [注释]: 这个公式是计算机科学领域的名言，由图灵奖得主尼古拉斯·沃斯（Niklaus Wirth）提出。它精辟地指出了程序设计的核心：先要规划好数据如何组织和存储，然后设计出处理这些数据的步骤。

1.2 数据的存储结构

数据的逻辑结构（如线性关系、树形关系）最终要存储在计算机内存里，这就是存储结构，也叫物理结构。

• 数据元素的映象:
  • 数据元素本身最终会用一串二进制位 (bit) 来表示。例如，整数 321 表示为 (101000001)₂。
• 关系的映象:
  • 顺序映象 (Sequential Mapping)：用内存地址的相对位置来表示数据元素之间的逻辑关系。比如，A元素后面紧跟着B元素，那么在内存里，存储B的地址就在存储A的地址后面。
    • 优点: 访问速度快（直接计算地址）。
    • 缺点: 插入和删除操作可能需要移动大量元素，效率低。
  • 链式映象 (Linked Mapping)：在每个数据元素中增加一个指针 (pointer)，这个指针用于存放下一个元素的内存地址。
    • 优点: 插入和删除操作非常高效，只需修改指针即可。
    • 缺点: 增加了额外的指针存储开销，且访问特定元素时必须从头开始遍历。

1.3 抽象数据类型 (ADT)

• 定义 (Abstract Data Type): 指一个数学模型以及定义在该模型上的一组操作。
• 两大特征:
  1. 数据抽象 (Data Abstraction)：强调数据对象本质的特征和功能，隐藏其内部细节。
  2. 数据封装 (Data Encapsulation)：将外部特性和内部实现分离，用户只能通过预定义的接口（操作）来访问数据，不能直接触碰内部实现。

• 三元组表示: ADT可用 (D, S, P) 三元组表示。

  • D: 数据对象 (Data Object)。
  • S: D上的关系集 (Structure)。
  • P: 对D的基本操作集 (Primitive Operations)。

  [注释]: 可以把ADT理解为一个“黑盒子”。比如一个“栈”ADT，我们只关心它有Push（推入）和Pop（弹出）操作，遵循“后进先出”的规则。至于这个栈内部是用数组还是链表实现的，我们不关心，这就是抽象和封装。

1.4 算法及其衡量

• 算法 (Algorithm): 为解决某类问题而规定的一个有限长的操作序列。
• 算法的五个重要特性:
  1. 有穷性: 算法必须在执行有限步骤后终止。
  2. 确定性: 算法的每一步都有确切的含义，无二义性。
  3. 可行性: 算法的每一步都可以通过执行有限次数的基本运算来完成。
  4. 有输入: 算法有零个或多个输入。
  5. 有输出: 算法有一个或多个输出。
• 算法效率的衡量:
  • 事前分析估算法: 不用运行程序，而是分析算法的时间复杂度来评估效率。这是最常用和科学的方法。
  • 时间复杂度 (Time Complexity)：估算算法执行时间随问题规模n增长的变化趋势。记作 \(T(n) = O(f(n))\)。
    • O 的含义: 表示“同阶”，即增长率相同。例如，\(O(n^2)\) 表示算法的执行时间与问题规模n的平方成正比。
  • 空间复杂度 (Space Complexity)：估算算法运行时额外需要的辅助存储空间。如果所需空间是常数级的，称为原地工作。

---

第二章 线性表

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

2.1 线性表的定义与特征

• 定义: 一个数据元素的有序集合。
• 基本特征:
  1. 存在唯一的“第一元素”和“最后元素”。
  2. 除第一个元素外，每个元素都有唯一的前驱。
  3. 除最后一个元素外，每个元素都有唯一的后继。

2.2 线性表的顺序实现 (顺序表)

使用一段地址连续的存储单元依次存储线性表的数据元素。

• 地址计算: 假设第一个元素的地址是 LOC(a₁)，每个元素占 C 个存储单元，则第 i 个元素的地址为： \(LOC(a_i) = LOC(a_1) + (i-1) \times C\)

  [注释]: 这个公式是顺序表的精髓，它使得我们可以通过下标随机访问任意一个元素，时间复杂度为 \(O(1)\)。LOC(a₁) 也被称为基地址。

2.3 线性表的链式实现 (链表)

用一组地址任意的存储单元存放数据元素，通过指针将它们链接起来。

• 结点 (Node): 包含两部分。
  1. 数据域: 存储数据元素本身。
  2. 指针域: 存储后继结点的地址。

• 单链表 (Singly Linked List):

  • 插入操作: 在第 i-1 个结点 p 之后插入新结点 s。

    /*
     * 功能: 在单链表的p结点后插入s结点
     * LinkList 是指向LNode的指针类型
     * LNode 是结点结构体，包含 data 和 next 域
     * p 是指向第 i-1 个结点的指针
     * s 是已创建好的新结点
     */
    // 1. 将新结点s的后继指针指向原本p的后继结点 (即原来的第i个结点)
    s->next = p->next;
    // 2. 将p结点的后继指针指向新结点s
    p->next = s;
    

    [注释]: 这两步的顺序绝对不能颠倒！如果先执行 p->next = s;，那么原来第i个结点的地址就丢失了，链表就断了。 * 双向链表 (Doubly Linked List): * 结点有两个指针域：prior 指向前驱，next 指向后继。 * 插入操作: 在结点p后插入新结点s。

    /*
     * 功能: 在双向链表的p结点后插入s结点
     * p 是一个已存在于链表中的结点指针
     * s 是已创建好的新结点指针
     */
    // 1. 新结点s的后继指向p的原后继
    s->next = p->next;
    // 2. 如果p的原后继存在，则将其前驱指向s
    if (p->next != NULL) {
        p->next->prior = s;
    }
    // 3. p的后继指向s
    p->next = s;
    // 4. s的前驱指向p
    s->prior = p;
    

    * 删除操作: 删除p结点的后继结点。

    /*
     * 功能: 删除双向链表中p结点的后继结点
     * 假设p的后继结点是q
     */
    LinkList q = p->next; // q是待删除结点
    // 1. p的后继指向q的后继 (即p->next->next)
    p->next = q->next;
    // 2. 如果q的后继不为空，则将其前驱指向p
    if (q->next != NULL) {
        q->next->prior = p;
    }
    // 3. 释放q结点的内存
    free(q);
    

• 改进的链表结构: PPT中提到，为了提高效率，可以为链表类型增加表头指针、表尾指针和表长等信息。

  typedef struct LNode {
      ElemType data;
      struct LNode *next;
  } LNode, *LinkList;
  
  typedef struct {
      LinkList head;      // 指向头结点的指针
      LinkList tail;      // 指向最后一个结点的指针
      int len;            // 链表长度
  } EnhancedLinkList;
  

  [注释]: 增加了tail指针后，在表尾插入元素的时间复杂度从 \(O(n)\) 降为 \(O(1)\)。增加了len后，获取链表长度的时间复杂度从 \(O(n)\) 降为 \(O(1)\)。这是典型的空间换时间。

---

第三章 栈和队列

栈和队列是两种操作受限的特殊线性表。

3.1 栈 (Stack)

• 特点: 后进先出 (Last In, First Out - LIFO)。
• 操作: 只允许在表的一端（称为栈顶）进行插入（入栈/压栈 Push）和删除（出栈/弹栈 Pop）。
• 顺序栈实现:

  #define STACK_INIT_SIZE 100  // 初始分配量
  #define STACKINCREMENT 10    // 存储空间分配增量
  
  typedef struct {
      SElemType *base;    // 栈底指针，在栈构造前和销毁后为NULL
      SElemType *top;     // 栈顶指针，始终指向栈顶元素的下一个位置
      int stacksize;      // 当前已分配的存储空间，以元素为单位
  } SqStack;
  

  > [注释]: top == base 表示栈空。top - base 是栈中元素的个数。当 top - base == stacksize 时，表示栈满，需要增加存储空间。

3.2 队列 (Queue)

• 特点: 先进先出 (First In, First Out - FIFO)。
• 操作: 在表的一端（队尾）进行插入（入队 Enqueue），在另一端（队头）进行删除（出队 Dequeue）。

3.3 栈的应用：表达式求值

• 表达式表示法:
  • 中缀表达式 (Infix): 操作符在操作数中间，如 a + b。这是人类习惯的写法，但有括号和优先级问题，不适合计算机处理。
  • 前缀表达式 (Prefix / 波兰式): 操作符在操作数前面，如 + a b。
  • 后缀表达式 (Postfix / 逆波兰式): 操作符在操作数后面，如 a b +。
• 后缀表达式的优点:
  • 没有括号，运算顺序唯一确定。只需从左到右扫描，遇到数字则入栈，遇到运算符则从栈中弹出两个数字进行运算，结果再入栈。
• 中缀转后缀算法 (使用栈):
  1. 初始化一个运算符栈。
  2. 从左到右扫描中缀表达式。
  3. 遇到操作数，直接输出到后缀表达式。
  4. 遇到运算符：
     • 若栈为空或栈顶是左括号 (，直接入栈。
     • 若优先级高于栈顶运算符，直接入栈。
     • 否则，将栈顶运算符弹出并输出，重复此过程，直到当前运算符可以入栈。
  5. 遇到左括号 (，直接入栈。
  6. 遇到右括号 )，将栈顶运算符依次弹出并输出，直到遇到左括号为止，括号不输出。
  7. 扫描完毕后，将栈中剩余运算符全部弹出并输出。

---

第四章 串

• 串 (String): 由零个或多个字符组成的有限序列。
• 与线性表的区别: 串的逻辑结构与线性表类似，但操作对象通常是整个串或子串，而不是单个元素。
• 模式匹配 (Pattern Matching): 在一个主串中查找一个子串（模式串）的位置。

  • KMP算法: 一种高效的模式匹配算法。

    • 核心思想: 当匹配过程中发生不匹配时，主串的指针 i 不回溯，而是通过一个预先计算好的 next 数组，将模式串的指针 j 移动到合适的位置，然后继续比较。
    • 时间复杂度: \(O(n+m)\)，其中n是主串长度，m是模式串长度。
    • next数组: next[j] 的值表示当模式串的第 j 个字符与主串失配时，模式串指针 j 应该回溯到的位置。这个值只与模式串自身结构有关。

    [注释]: next数组的计算是KMP算法的难点。它的本质是寻找模式串中每个子串的“最长公共前后缀”的长度。例如，模式串 abaabcac，next数组为 [0, 1, 1, 2, 2, 3, 1, 2]。

---

第五章 数组和广义表

5.1 稀疏矩阵

• 定义: 非零元素个数远远少于矩阵总元素个数的矩阵。通常认为稀疏因子 \(\delta \le 0.05\) 的为稀疏矩阵。
• 压缩存储 (三元组顺序表): 只存储非零元素。每个非零元素用一个三元组 (行号, 列号, 值) 来表示。

  #define MAXSIZE 12500 // 假设矩阵中非零元个数的最大值为12500
  
  // 三元组类型定义
  typedef struct {
      int i, j;           // 该非零元的行下标和列下标
      ElemType e;         // 该非零元的值
  } Triple;
  
  // 稀疏矩阵类型定义
  typedef struct {
      Triple data[MAXSIZE + 1]; // 非零元三元组表，data[0]未用
      int mu, nu, tu;           // 矩阵的行数、列数和非零元个数
  } TSMatrix;
  

5.2 广义表

• 定义: 广义表是n(\(n \ge 0\))个表元素组成的有限序列，其中表元素可以是原子（单个数据）或子表（另一个广义表）。广义表是递归定义的。
• 示例:
  • A = () 空表
  • B = (a, (b, c)) 包含一个原子和一个子表
  • C = (a, C) 递归表
• 存储结构 (头尾链表表示法): 这是一种非常经典的表示方法，结点有两种类型：原子结点和表结点。

  // 结点类型枚举：0代表原子，1代表子表
  typedef enum {ATOM, LIST} ElemTag;
  
  typedef struct GLNode {
      ElemTag tag; // 标志域，用于区分原子结点和表结点
  
      // 联合体 (union) 用于存储不同类型的数据
      union {
          AtomType atom; // 当tag为ATOM时，存储原子值
          // 当tag为LIST时，ptr是一个结构体指针
          struct {
              struct GLNode *hp; // 指向表头的指针
              struct GLNode *tp; // 指向表尾的指针
          } ptr;
      };
  } *GList;
  

  > [注释]: union 是C语言中一个节省空间的技巧，所有成员共享同一块内存。hp (head pointer) 指向广义表的第一个元素（可能是原子或子表）。tp (tail pointer) 指向由剩下元素构成的子表。例如，对于 L=(a, (b,c), d)，head(L) 是原子 a，tail(L) 是广义表 ((b,c), d)。

---

第六章 树和二叉树

6.1 树的基本概念

• 树 (Tree): n(\(n \ge 0\))个结点的有限集。它是一种非线性结构。
• 术语:
  • 根 (Root): 没有前驱的结点。
  • 叶子 (Leaf): 没有后继（度为0）的结点。
  • 结点的度 (Degree): 结点拥有的子树个数。
  • 树的度: 树中所有结点的度的最大值。
  • 深度 (Depth): 树中结点的最大层次。

6.2 二叉树

• 定义: 每个结点最多有两棵子树（左子树和右子树），且子树有左右之分，次序不能颠倒。
• 特殊二叉树:
  • 满二叉树: 深度为k且有 \(2^k-1\) 个结点的二叉树。
  • 完全二叉树: 深度为k，前k-1层是满的，第k层结点从左到右连续排列。

• 遍历 (Traversal):

  • 先序遍历 (Pre-order): 根 -> 左 -> 右
  • 中序遍历 (In-order): 左 -> 根 -> 右
  • 后序遍历 (Post-order): 左 -> 右 -> 根

  [注释]: 如果只知道一种遍历序列（如先序），是无法唯一确定一棵二叉树的。但如果知道先序和中序，或后序和中序，就可以唯一确定一棵二叉树。

• 由表达式创建二叉树: PPT中提到了用栈来辅助从表达式创建二叉树的方法。

  // 创建子树的核心C语言函数
  // 假设有两个栈，一个存运算符，一个存指向树结点的指针(PTR)
  void CrtSubtree(BiTree *T, char c) {
      // 1. 创建新结点，存放当前运算符
      *T = (BiTNode*)malloc(sizeof(BiTNode));
      if (!(*T)) exit(OVERFLOW); // 内存分配失败
      (*T)->data = c;
  
      // 2. 从指针栈中弹出两个子树根结点，作为新结点的右孩子和左孩子
      BiTree rc, lc;
      Pop(PTR, &rc); // 弹出右孩子
      Pop(PTR, &lc); // 弹出左孩子
  
      (*T)->rchild = rc;
      (*T)->lchild = lc;
  
      // 3. 将新创建的子树的根结点压入指针栈
      Push(PTR, *T);
  }
  

6.3 赫夫曼树 (Huffman Tree)

• 定义: 带权路径长度 (WPL) 最小的二叉树，也叫最优二叉树。
• 构造算法 (赫夫曼算法):
  1. 将n个权值看作n棵只有根结点的二叉树，构成一个森林F。
  2. 在F中选取权值最小的两棵树，作为左右子树构造一棵新的二叉树，新树的根结点权值为其左右子树根结点权值之和。
  3. 从F中删除那两棵树，并将新树加入F。
  4. 重复2、3步，直到F中只剩下一棵树为止。这棵树就是赫夫曼树。
• 赫夫曼编码:
  • 一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀。
  • 应用: 常用于数据压缩，权值越大的字符（出现频率越高），编码越短。

---

第七章 图

7.1 图的基本概念

• 定义: 图由顶点集(V) 和 边集(E) 构成，表示为 \(G = (V, E)\)。
• 术语:
  • 无向图: 边没有方向。
  • 有向图: 边有方向（称为弧）。
  • 度: 与顶点相关联的边的数目。有向图中分为入度和出度。
  • 连通图: 图中任意两个顶点之间都存在路径。
  • 最小生成树 (MST): 对于一个带权的连通图，包含图中全部n个顶点，有n-1条边，且边的权值之和最小的子图。

7.2 图的存储结构

• 邻接矩阵 (Adjacency Matrix): 用一个二维数组 A 存储。\(A[i][j]=1\) (或权值) 表示顶点 i 和 j 之间有边，否则为0 (或 \(\infty\))。
  • 优点: 判断两个顶点间是否有边很方便 (\(O(1)\))。
  • 缺点: 对于稀疏图，空间浪费严重。
• 邻接表 (Adjacency List): 为每个顶点建立一个单链表，存储所有与该顶点相邻的顶点。
  • 优点: 节省空间，特别适合稀疏图。
  • 缺点: 判断两顶点间是否有边需要遍历链表。

7.3 图的遍历

• 深度优先搜索 (DFS): 类似于树的先序遍历，尽可能深地搜索图的分支。常使用栈或递归实现。
• 广度优先搜索 (BFS): 类似于树的层次遍历，从一个顶点开始，逐层向外访问。常使用队列实现。
  • 应用: 求解单源最短路径问题（对于无权图）。

7.4 最小生成树算法

• 普里姆算法 (Prim's Algorithm):
  • 思想: 从一个顶点开始，不断将离当前生成树最近的顶点和边加入进来，直到所有顶点都被包含。是一种“加点”的策略。
  • 时间复杂度: \(O(n^2)\) (使用邻接矩阵)，适合稠密图。
• 克鲁斯卡尔算法 (Kruskal/Kruscal's Algorithm):
  • 思想: 按边的权值从小到大的顺序考察，如果一条边连接的两个顶点不属于同一个连通分量（即加入这条边不会形成环），就选择它。是一种“加边”的策略。
  • 时间复杂度: \(O(e \log e)\) (e是边数)，适合稀疏图。

7.5 拓扑排序

• 应用: 用于有向无环图 (DAG)，得到一个顶点的线性序列。
• 算法:
  1. 在图中找到一个入度为0的顶点并输出。
  2. 从图中删除该顶点及其所有出边。
  3. 重复1、2步，直到所有顶点都被输出。如果图中还有顶点但找不到入度为0的，说明图中有环。

---

第九章 查找

9.1 查找表

• 静态查找表: 只做查找操作。
• 动态查找表: 除查找外，还可能进行插入和删除操作。

9.2 静态查找

• 顺序查找: 时间复杂度 \(O(n)\)。
• 折半查找 (二分查找):
  • 前提: 表必须是有序的。
  • 时间复杂度: \(O(\log n)\)。
• 次优查找树: PPT中提到的构造方法是一种启发式算法，用于在查找概率不均等的情况下，构造一棵平均查找长度较小的判定树。

9.3 动态查找

• 二叉排序树 (BST / Binary Search Tree):
  • 性质: 左子树所有结点的值 < 根结点的值 < 右子树所有结点的值。
  • 缺点: 在极端情况下（如插入一个有序序列），会退化成链表，查找效率降为 \(O(n)\)。
• 平衡二叉树 (AVL Tree):
  • 定义: 它首先是一棵二叉排序树，并且其任意结点的左、右子树的深度差的绝对值不超过1。
  • 目的: 解决BST退化问题，使树高保持在 \(O(\log n)\) 级别，从而保证查找、插入、删除操作的时间复杂度都是 \(O(\log n)\)。
  • 平衡操作: 当插入或删除导致不平衡时，通过旋转操作（左旋、右旋）来恢复平衡。

---

第十、十一章 排序

10.1 插入排序

• 直接插入排序: 将一个记录插入到已经排好序的有序表中。时间复杂度 \(O(n^2)\)。
• 希尔排序 (Shell Sort):
  • 也称缩小增量排序，是直接插入排序的改进版。
  • 思想: 先将整个序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
  • 时间复杂度: 不稳定，优于 \(O(n^2)\)，与增量序列的选择有关。

10.2 交换排序

• 起泡排序 (冒泡排序): 反复遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。时间复杂度 \(O(n^2)\)。
• 快速排序 (Quick Sort):
  • 思想: 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序（分治法）。
  • 核心: 一次划分 (Partition) 操作，选取一个“枢轴”(Pivot)元素，将小于它的放左边，大于它的放右边。
  • 时间复杂度: 平均为 \(O(n \log n)\)，最坏为 \(O(n^2)\)。是实践中应用最广泛的排序算法之一。

10.3 选择排序

• 简单选择排序: 每次在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。时间复杂度 \(O(n^2)\)。
• 堆排序 (Heap Sort):
  • 思想: 将待排序序列构造成一个大顶堆（或小顶堆），此时，整个序列的最大值（或最小值）就是堆顶的根结点。将其与末尾元素交换，然后将剩余n-1个元素重新调整成堆，如此反复执行。
  • 堆的定义: 一个完全二叉树，且满足 \(r_i \le r_{2i}\) 和 \(r_i \le r_{2i+1}\) (小顶堆) 或 \(r_i \ge r_{2i}\) 和 \(r_i \ge r_{2i+1}\) (大顶堆)。
  • 时间复杂度: \(O(n \log n)\)。

10.4 归并排序

• 思想: 也是分治法的典型应用。将序列递归地分成两半，直到每个子序列只有一个元素，然后再将这些有序的子序列两两合并。
• 时间复杂度: \(O(n \log n)\)。
• 缺点: 需要 \(O(n)\) 的额外空间。

10.5 基数排序

• 思想: 不是基于比较的排序。它将整数按位数切割成不同的数字，然后按每个位数分别比较。是一种“分配-收集”的过程。
• 时间复杂度: \(O(d(n+r))\)，d是位数，r是基数。当d较小时，效率很高。

10.6 排序算法总结

• 时间复杂度:
  • \(O(n^2)\): 直接插入、冒泡、简单选择。
  • \(O(n \log n)\): 快速排序、堆排序、归并排序。
  • \(O(n^{1+ \epsilon})\): 希尔排序。
  • \(O(n)\): 基数排序 (特定条件下)。

• 稳定性:

  • 稳定: 冒泡、直接插入、归并、基数排序。（相等的元素排序后相对位置不变）
  • 不稳定: 简单选择、快速排序、希尔、堆排序。

  [注释]: 稳定性在某些应用中很重要。例如，要对一个学生列表按成绩排序，如果成绩相同，希望保持原来的学号顺序，这时就必须用稳定的排序算法。