数据结构 - 管理学院 ¶

C 语言概述 ¶

• 指针
  • int a, s[10]; int *p = &a; int *q = s;
    • & 取地址，* 访问地址得到值（-> 访问错误地址 -> 段错误）
    • s 为数组，可以用作指针，指向数组首元素地址
• 结构体

  struct Student {
      char name[20];
      int age;
      float score;
  };
  struct Student stu1;
  struct Student stu2 = {"Alice", 20, 95.5}; // 直接初始化
  struct Student *p = &stu1;
  

  • 访问字段：stu1.age == (*p).age == p->age
    • (*p). 完全等价于 p->
  • C 语言中要写全 struct Student，C++ 中可以省略 struct
  • C 语言中可以 typedef struct Student { ... } Student; 来省略 struct
    • typedef 任意一大长串类型 A; 之后就可以用 A 来表示那串类型
  • typedef struct Student *StudentPtr; StudentPtr 就是指向 Student 结构体的指针类型
• 动态申请内存
  • 区别于数组的静态分配 int arr[10];
  • malloc 分配：int *p = (int *)malloc(10 * sizeof(int));
    • malloc 里为分配空间的字节数，返回的是 void * 类型，所以需要在前面强制转换一下
    • 如果 malloc 返回了 NULL（即 0），则表示分配失败（系统内存不足）
    • 分配结构体：StudentPtr p = (StudentPtr)malloc(sizeof(struct Student));
  • free 释放：free(p);
    • 释放 malloc 分配的内存，防止内存泄漏

绪论 ¶

• 数据结构定义：TODO / 自己看 PPT 概念
• 算法：
  • 五个特征：输入、输出、有穷性、确定性、可行性
  • 时间复杂度 -> 衡量执行输入规模 n 的算法所执行的语句条数是什么量级的
    • 例如执行一个算法需要运行 2n^2 + 4n + 4 条重复语句，则量级为 n^2，时间复杂度为 \(O(n^2)\)
    • 只需要考虑输入规模 n（或者可能有多个规模），常数和低阶项都忽略
    • 纯粹的循环只需要考虑最内层循环执行了多少次，就是时间复杂度
    • 有递归等情况可能会出现对数复杂度

线性表 ¶

• 线性表：n 个相同类型的数据元素构成的优先序列
  • 存储结构有顺序存储和链式存储
• 存储一元多项式：
  • 例如 \(P(x) = 10 + 5x - 4x^2 + 3x^3 + 2x^4\)，可以表示为 [10, 5, -4, 3, 2]，索引表示指数
  • 稀疏多项式：\(P(x) = 8x + 22x^7 - 9x^8\) 可以表示为 [(8, 1), (22, 7), (-9, 8)]，只存非零系数和对应指数节省空间
• 存储线性表（顺序存储、链式存储）：
  • 顺序存储（顺序表）：就是数组（或者 malloc 分配的连续空间，相当于动态数组）
    • 逻辑结构与存储结构一致
    • 优点：随机存取（通过索引直接访问）效率高，空间利用率高
      • 这里的空间利用率指的是没有指针域等额外开销
    • 缺点：插入、删除效率低（需要移动大量元素），浪费空间
  • 链式存储（链表）
    • 不要求逻辑上相邻的元素在物理上也相邻（能通过指针链接就够了）
    • 插入和删除方便，但不能随机存取（只能顺序存取）
    • 分类：
      • 单链表：每个节点只有一个指针域，指向下一个节点
      • 双链表：每个节点有两个指针域，分别指向前驱和后继节点
      • 循环链表：最后一个节点指向头节点，形成环状结构

链表 ¶

typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域（链域）
} Node, *List;

• Node n; 定义一个节点，List L; 和 Node *p; 定义一个指向节点的指针
• 一般用指向链表的头节点的指针表示这个链表，有两种情况
  • 带哨兵节点（PPT 里直接叫头结点）：
    • 头结点一定存在，L 一定不是 NULL
    • 头结点的数据域 L->data 不存数据，不表示链表中的结点
    • 头结点的指针域 L->next 指向链表中存储数据的第一个结点
      • 对于空链表，L->next == NULL
  • 不带哨兵节点（PPT 里叫不带头结点）：
    • L 直接指向链表中存储数据的第一个结点（L->data 就是第一个数据）
    • 对于空链表，L == NULL

void initList(List *L) {
    *L = (List)malloc(sizeof(Node)); // 分配头结点
    (*L)->next = NULL;               // 头结点指针域置空
}
void insertAfter(Node *p, int value) { // 在节点 p 之后插入新节点
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = p->next; // 新节点的下一个结点为原来 p 的下一个节点
    p->next = newNode;       // p 的下一个结点指向新节点
}
void deleteAfter(Node *p) { // 删除节点 p 之后的节点
    if (p->next != NULL) {
        Node *temp = p->next; // 要删除的节点
        p->next = temp->next; // p 的下一个结点指向要删除节点的下一个节点
        free(temp);           // 释放被删除节点的内存
    }
}
void traverseList(List L) { // 遍历链表
    Node *p = L->next; // 从头结点的下一个节点开始
    while (p != NULL) {
        printf("%d ", p->data); // 访问节点数据
        p = p->next;
    }
}

void initList(List *L) {
    *L = NULL; // 初始化为空链表
}
void insertAfter(Node *p, int value); // 同带头结点
void deleteAfter(Node *p); // 同带头结点
void insertAtHead(List *L, int value) { // 在链表头部插入新节点
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = *L; // 新节点的下一个结点为原来的头节点
    *L = newNode;       // 头指针指向新节点
}
void deleteAtHead(List *L) { // 删除链表头部节点
    if (*L != NULL) {
        Node *temp = *L;   // 要删除的节点
        *L = temp->next;   // 头指针指向下一个节点
        free(temp);        // 释放被删除节点的内存
    }
}
void traverseList(List L) { // 遍历链表
    Node *p = L; // 从头节点开始
    while (p != NULL) {
        printf("%d ", p->data); // 访问节点数据
        p = p->next;
    }
}

最大的差别就是在插入结点时，如果目前是空表，则对于不带头结点的链表，需要特别判断一下，进行 insertAtHead 的操作（因为空表的 L == NULL）

• 头插法与尾插法
  • 头插法：每次插入元素都插入到链表的头部（靠近头结点的位置）
    • 结果是链表中元素的顺序与插入顺序相反
    • 插入简单，只需要在头结点后面插入即可（带头结点），或创建新的结点作为头结点（不带头结点）
  • 尾插法：每次插入元素都插入到链表的尾部
    • 需要遍历链表找到最后一个结点，插入到其后面
    • 或者维护一个尾指针，时刻指向链表的最后一个结点，插入时可以直接插入到尾指针后面
• 循环链表
  • 最后一个结点的指针域指向头结点，形成环状结构
• 双向链表
  • 两个指针域，分别指向前驱和后继结点
  • 插入和删除时需要同时更新前驱和后继两个结点的指针域（画图辅助理解）

栈和队列 ¶

栈 ¶

• 特殊的线性表（只能在表尾插入删除）
• 存储结构：顺序栈（利用数组 / 动态数组存储，更常见）和链栈（利用链表存储）
• 先进后出、后进先出
• 顺序栈实现上是利用一个数组 a 和一个栈顶指针 top 来实现的，有两种情况：
  • a[top] 表示栈顶元素
    • top 初始化为 -1，即 top == -1 表示空栈
    • 入栈：top++; a[top] = value; 或 a[++top] = value;
    • 出栈：value = a[top]; top--; 即 value = a[top--];
    • 栈满条件：top == maxSize - 1，即如果只能存 4 个元素，则 top == 3 时栈满
    • 元素个数：top + 1
  • a[top-1] 表示栈顶元素
    • top 初始化为 0，即 top == 0 表示空栈
    • 入栈：a[top] = value; top++; 或 a[top++] = value;
    • 出栈：top--; value = a[top]; 即 value = a[--top];
    • 栈满条件：top == maxSize，即如果只能存 4 个元素，则 top == 4 时栈满
    • 元素个数：top
  • 对于程序填空、函数题，也需要根据现有代码判断属于哪种
    • PPT 上默认给的是第二种（空栈时 top == 0，栈顶元素为 a[top-1]）
• 链栈：一般不设置头结点，首个结点即表示栈顶，操作都在链表头部进行

队列 ¶

• 特殊的线性表（只能在表的一端删除，在表的另一端插入）
• 存储结构：顺序 / 链式
• 先进先出
• 顺序队列
  • 用两个指针 front 和 rear 分别指向队头和队尾
  • 队头元素为 a[front]，队尾元素为 a[rear-1]
  • 不循环：
    • 初始时 front = rear = 0，表示空队列
    • 入队：a[rear] = value; rear++;
    • 出队：value = a[front]; front++;
    • 元素个数：rear - front
    • 不循环则存在假溢出问题，即 front 和 rear 都向后移动，导致数组前部空间浪费
  • 循环队列：
    • 入队：a[rear] = value; rear = (rear + 1) % maxSize;
    • 出队：value = a[front]; front = (front + 1) % maxSize;
    • 队空条件：front == rear
    • 队满条件：(rear + 1) % maxSize == front
      • 浪费一个存储空间以区分队空和队满，即剩下一个空间就不再存了，不然就区分不了满和空了
    • 元素个数：(rear - front + maxSize) % maxSize
• 链式队列：
  • 其实就是正常链表，再额外维护一个 rear 指针指向链表尾部

树和二叉树 ¶

• 树包括根节点（root），0 个或多个非空子树 \(T_1,\cdots, T_k\) 与根通过一条边连接
• 术语：
  • 结点的度：结点的子树个数（下面接了几个结点）
  • 树的度：树中所有结点的度的最大值
  • 分支结点：度不为 0 的结点（内部的结点）
  • 叶子结点：度为 0 的结点（没有子树的结点，终端结点）
  • 孩子：某结点的直接下级结点
  • 父亲：某结点的直接上级结点（PPT 叫双亲）
  • 兄弟：同一个父亲的孩子结点互为兄弟
  • 堂兄弟：父亲是兄弟的结点互为堂兄弟
  • 结点的祖先：从根结点到该结点路径上的所有结点
  • 结点的子孙：以该结点为根的子树中的所有结点
  • 结点的层次：根结点为第 1 层，其它结点的层次为其父结点层次加 1
  • 树的深度 / 高度：树中结点的最大层次
  • 有序树：每个结点的子树不能随意排列，有固定顺序
  • 森林：若干棵互不相交的树的集合
• 二叉树
  • 每个结点最多有两个儿子
  • 满二叉树：每一层都不能再加结点了，深度为 \(k\) 且有 \(2^k - 1\) 个结点
  • 完全二叉树：除了最底层外，每一层结点数都达到最大值，且最底层结点都集中在该层最左边
  • 性质：
    • 第 \(i\) 层的节点数最多为 \(2^{i-1}\)
    • 深度为 \(k\) 的二叉树最多有 \(2^k - 1\) 个节点
    • \(n_0\) 表示叶节点数，\(n_2\) 表示度为 2 的节点数，则 \(n_0 = n_2 + 1\)
    • 有 \(n\) 个节点的二叉树的深度为 \(\lfloor \log_2(n) \rfloor + 1\)
    • 对完全二叉树的结点从上到下、从左到右编号（1 开始），则对于编号为 \(i\) 的结点：
      • 左孩子编号为 \(2i\)（如果存在的话）
      • 右孩子编号为 \(2i + 1\)（如果存在的话）
      • 父节点编号为 \(\lfloor i/2 \rfloor\)
• 二叉树的表示
  • 顺序表示：通过数组来表示（不是完全二叉树则会浪费空间）
    • 根为 tree[1]
    • 节点 tree[i] 的左儿子为 tree[2i]，右儿子为 tree[2i+1]
    • 完全二叉树的数组中元素全部分布在 1 ~ n 中
  • 链式表示：每个结点包含数据域、左孩子指针和右孩子指针

    typedef struct Node {
        int data;                   // 数据域
        struct Node *left;      // 左孩子指针
        struct Node *right;     // 右孩子指针
        // struct Node *parent;  // 可选，指向父节点的指针
    } Node, *Tree;
    

• 二叉树的遍历

  • 先序遍历（根 - 左 - 右）
  • 中序遍历（左 - 根 - 右）
  • 后序遍历（左 - 右 - 根）
  • 层次遍历（按层从上到下、从左到右）

  • 递归实现：

    先序遍历中序遍历后序遍历

    void preOrder(Tree T) {
        if (T != NULL) {
            printf("%d ", T->data); // 访问根节点
            preOrder(T->left);      // 遍历左子树
            preOrder(T->right);     // 遍历右子树
        }
    }
    

    void inOrder(Tree T) {
        if (T != NULL) {
            inOrder(T->left);      // 遍历左子树
            printf("%d ", T->data); // 访问根节点
            inOrder(T->right);     // 遍历右子树
        }
    }
    

    void postOrder(Tree T) {
        if (T != NULL) {
            postOrder(T->left);      // 遍历左子树
            postOrder(T->right);     // 遍历右子树
            printf("%d ", T->data); // 访问根节点
        }
    }
    

  • 迭代实现（较复杂）：

    先序遍历中序遍历后序遍历层次遍历

    void preOrderIter(Tree T) {
        if (T == NULL) return;
        Stack s; // 假设已经定义好了栈
        initStack(&s);
        push(&s, T);
        while (!isEmpty(&s)) {
            Tree node = pop(&s);
            printf("%d ", node->data); // 访问节点
            if (node->right) push(&s, node->right); // 先右后左入栈
            if (node->left) push(&s, node->left);
        }
    }
    

    void inOrderIter(Tree T) {
        Stack s; // 假设已经定义好了栈
        initStack(&s);
        Tree current = T;
        while (current != NULL || !isEmpty(&s)) {
            while (current != NULL) {
                push(&s, current);
                current = current->left; // 一直往左走
            }
            current = pop(&s);
            printf("%d ", current->data); // 访问节点
            current = current->right; // 转向右子树
        }
    }
    

    void postOrderIter(Tree T) {
        Stack s1, s2; // 使用两个栈
        initStack(&s1);
        initStack(&s2);
        if (T != NULL) push(&s1, T);
        while (!isEmpty(&s1)) {
            Tree node = pop(&s1);
            push(&s2, node); // 先将节点压入第二个栈
            if (node->left) push(&s1, node->left); // 先左后右入栈
            if (node->right) push(&s1, node->right);
        }
        while (!isEmpty(&s2)) {
            Tree node = pop(&s2);
            printf("%d ", node->data); // 访问节点
        }
    }
    

    void levelOrder(Tree T) {
        if (T == NULL) return;
        Queue q; // 假设已经定义好了队列
        initQueue(&q);
        enqueue(&q, T);
        while (!isEmpty(&q)) {
            Tree node = dequeue(&q);
            printf("%d ", node->data); // 访问节点
            if (node->left) enqueue(&q, node->left);
            if (node->right) enqueue(&q, node->right);
        }
    }
    

  • 利用递归实现更多功能

    • 主要就是几个步骤：
      1. 递归终止条件
      2. 处理当前节点
      3. 递归处理左子树（递归调用，执行相同逻辑）
      4. 递归处理右子树（递归调用，执行相同逻辑）
    • 例如计算二叉树的高度：

      int treeHeight(Tree T) {
          if (T == NULL) return 0; // 终止条件：空树
          int leftHeight = treeHeight(T->left);   // 递归处理左子树
          int rightHeight = treeHeight(T->right); // 递归处理右子树
          return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; // 当前节点高度为左右子树高度最大值加 1
      }
      

• 线索二叉树

  • 如果一个节点的左儿子为空，那么它的左指针指向它的中序遍历前驱节点
  • 如果一个节点的右儿子为空，那么它的右指针指向它的中序遍历后继节点
  • 一定有一个 head node，左儿子为根，右儿子为自身
• 树的表示
  • 列表表示
    • 子节点个数未知，不易表示
  • FirstChild-NextSibling 表示法
    • 记录第一个子节点和下一个兄弟节点
    • 因为一棵树的儿子顺序不定，所以一棵树的表示方式不唯一

      typedef struct Node {
          int Element;
          struct Node* FirstChild;
          struct Node* NextSibling;
      } Node *Tree;
      

• 树与二叉树的转换
  • 用 FirstChild-NextSibling 表示法表示的一棵树，就可以视为一棵二叉树（左子树为 FirstChild，右子树为 NextSibling）
  • 树按这个规则转成二叉树后，根结点一定只有左子树（因为根结点没有兄弟节点）
• 森林与二叉树转换
  • 每棵树对应的二叉树的根结点都只有左子树
  • 把多棵树的二叉树根结点通过右子树连接起来，就形成了一棵二叉树
  • 根结点的右子树表示了森林中另一棵树
• 树的遍历
  • 先根遍历：访问根结点、然后依次先根遍历每棵子树
    • 等价于先序遍历对应的二叉树
  • 后根遍历：依次后根遍历每棵子树、然后访问根结点
    • 等价于中序遍历对应的二叉树
• 哈夫曼树
  • 一棵树上，叶子结点表示若干个符号及其权值（频率），树的带权路径长度最小
    • 利用路径表示叶子结点代表的符号的编码，从根开始，向左走表示 0，向右走表示 1
  • 构造哈夫曼树的贪心算法
    1. 初始化：将每个符号及其权值看作一棵单节点树
    2. 重复以下步骤直到只剩下一棵树：
       • 从森林中选出两棵根结点权值最小的树作为左右子树，构造一棵新树，其根节点的权值为两棵子树权值之和
       • 将新树加入森林，删除原来的两棵子树

图 ¶

有限的边集 \(E=E(G)\) 和点集 \(V=V(G)\) 构成的非空有限集 \(G=(V,E)\) 即为图

术语 ¶

• 无向图：边没有方向；有向图：边有方向（有向图的边又称弧，无箭头的一端是弧尾，有箭头的一端是弧头）
• 完全图：任意两个不同顶点间都有一条边相连的图
  • 对于无向图，含有 n 个顶点的完全图有 \(n(n-1)/2\) 条边
  • 对于有向图，含有 n 个顶点的完全图有 \(n(n-1)\) 条弧（需要互相指向对方）
• 权值图：边（弧）带有权值的图，带权图又称网（有向无向都算）
• 子图：选原来图里的一部分点，再选一部分边构成的图
• 邻接点：对于无向图，若存在边 \((u,v)\)，则称 \(u\) 和 \(v\) 互为邻接点；对于有向图，若存在弧 \(<u,v>\)，则称 \(u\) 邻接到 \(v\)，\(v\) 邻接自 \(u\)
• 无向图的度：
  • 无向图结点的度：与该结点邻接的边的条数
• 有向图的度：
  • 入度：以该结点为弧头的弧的条数（箭头指向该结点的弧的数量）
  • 出度：以该结点为弧尾的弧的条数（箭头从该结点出发的弧的数量）
  • 有向图结点的度：入度与出度之和
• 路径：一个顶点到另一个顶点所经过的顶点序列
  • 简单路径：顶点不重复出现的路径
  • 路径长度：路径上边的条数
• 回路 / 环：起点和终点相同的路径
  • 简单回路 / 环：除起点和终点外，其他顶点均不重复出现的回路
• 无向图的连通性：
  • 如果 u 到 v 存在路径，则称 u 和 v 连通
  • 如果图中任意两个顶点均连通，则称该无向图为连通图
  • 无向图的极大联通子图称为该图的联通分量
    • 可以理解为可以互相连接的“一团”就是一个联通分量
    • 相当于森林里每棵树为一个联通分量
• 有向图的连通性：
  • 强连通：如果 u 到 v 存在路径，且 v 到 u 也存在路径，则称 u 和 v 强连通
  • 如果图中任意两个顶点均强连通，则称该有向图为强连通图
    • 即使 u 到 v 有路径，但 v 到 u 没有路径，则也不强连通
  • 有向图的极大强连通子图称为该图的强连通分量
• 生成树：包含图中所有 n 个顶点，有 n-1 条边的无回路子图
  • 对于连通图，至少存在一棵生成树
  • 最小生成树：生成树中边权值之和最小的生成树
  • 对生成树添加一个新边一定会形成一个回路
• 有向树：有一个顶点的入度为 0，其余顶点的入度均为 1（一棵树，每个结点指向自己的子节点）
• 生成森林：包含图中所有顶点，只有足以构成若干棵不相交的有向树的弧

图的存储结构 ¶

• 邻接矩阵：
  • 如果存在一条从 \(v_i\) 到 \(v_j\) 的边，则 \(a_{ij}=1\)，否则 \(a_{ij}=0\)
  • 对于非稠密图来说非常浪费空间
  • 构建带有 n 个结点，m 条边的邻接矩阵的时间复杂度为 \(O(\max(n^2,m*n))\)（PPT 给的）
    • 至少有 \(O(n^2)\) 来初始化矩阵
    • 这里 \(m*n\) 是因为对于每条边，需要 \(O(n)\) 的复杂度来找到对应的行列下标（即输入的边的信息是结点的值，而不是结点的下标）
• 邻接表（链式存储）：
  • 对于每个节点，存储一个链表来记录所有和它相临的节点
  • 对于无向图会将每个边存储两次
  • 对于有向图无法遍历入度，需要额外存储一个逆邻接表（存储每个节点的入边）
  • 构建一个邻接表的时间复杂度为 \(O(m*n)\)（PPT 给的）
• 其他存储结构：看 PPT（我觉得并不重要）
• 带权图：
  • 邻接矩阵：\(a_{ij}\) 存储边 \((v_i, v_j)\) 的权重
  • 邻接表：每个链表节点存储边的权重

图的遍历 ¶

• 深度优先搜索：

  • 尽可能按路径深入，直到访问过终点了再回溯

  void dfs(Graph G, int v) {
      visit[v] = 1; // 访问结点
      for (each neighbor w of v) {
          if (!visit[w]) {
              dfs(G, w); // 递归访问邻接结点
          }
      }
  }
  int main() {
      memset(visit, 0, sizeof(visit)); // 初始化访问数组为全 0
      for (each vertex v in G) {
          if (!visit[v]) {
              dfs(G, v); // 对每个未访问结点进行 DFS
          }
      }
  }
  

• 广度优先搜索：

  • 按层次逐层访问节点，先访问完一层再访问下一层

  void bfs(Graph G, int v) {
      Queue q;
      initQueue(&q);
      visit[v] = 1; // 访问结点
      enqueue(&q, v);
      while (!isEmpty(&q)) {
          int u = dequeue(&q);
          for (each neighbor w of u) {
              if (!visit[w]) {
                  visit[w] = 1; // 访问邻接结点
                  enqueue(&q, w);
              }
          }
      }
  }
  int main() {
      memset(visit, 0, sizeof(visit)); // 初始化访问数组为全 0
      for (each vertex v in G) {
          if (!visit[v]) {
              bfs(G, v); // 对每个未访问结点进行 BFS
          }
      }
  }
  

最小生成树 ¶

• 最小生成树（minimum spanning tree）是给定一个连通图，找一个总边权最小的生成树
  • 生成树为图的一个子图，包含所有点，且任意两点之间有且仅有一条边
• 连通图一定存在一个最小生成树
• Prim 算法

  T = 最小权边
  for i = 1..n-2
      e = 与 T 中的点相连且加入 T 后不会形成环的最小权边
      将 e 加入 T
  T 即为最小生成树
  

• Kruskal 算法

  T = 空图
  for i = 1..n-1
      e = 加入 T 中不会形成环的最小权边
      将 e 加入 T
  T 即为最小生成树
  

• 两个算法类似，都是贪心，区别是 Prim 是从一个点开始不断扩展，Kruskal 是不断挑权最小的边加入

最短路径 ¶

• 单源最短路：给定一个有向图和一个源点，求从源点到图中每个点的最短路径
• 无权图的单源最短路：BFS 即可
• 带权图的单源最短路：Dijkstra 算法
  1. 初始化 dis[s] = 0，其他 dis[v] = ∞
  2. 取全局 dis[x] 最小的、且未访问过的 x，将 x 标记为已访问
  3. 扫描 x 的所有出边 (x, y)
     • 若 dis[y] > dis[x] + weight(x, y)，则更新 dis[y] = dis[x] + weight(x, y)

有向无环图及应用 ¶

• 有向无环图（Directed Acyclic Graph，DAG）
  • 一种特殊的有向图，不包含有向回路
  • 可以进行拓扑排序
• 拓扑排序
  • 如果存在一条从 \(i\) 到 \(j\) 的路径，则称 \(i\) 是 \(j\) 的前驱（predecessor），\(j\) 是 \(i\) 的后继（successor）
  • 如果存在一条边 \(<i, j>\)，则称 \(i\) 是 \(j\) 的直接（immediate）前驱，\(j\) 是 \(i\) 的直接后继
  • 拓扑排序（topological order）是一个图的点集的线性序列，满足：
    • 对于任意一对点 \(i, j\)，如果 \(i\) 是 \(j\) 的前驱，则序列中 \(i\) 在 \(j\) 的前面
  • 算法流程：
    • 查找入度为 0 的结点入栈
    • 栈非空时，重复以下步骤：
      • 弹出栈顶结点，输出该结点到拓扑序列
      • 查找该结点的所有出边，将其指向的所有结点的入度减 1
      • 将入度变为 0 的结点入栈
    • 栈变空了，若输出的结点数等于图中结点数，则排序成功，否则图中有环，无法进行拓扑排序
• AOV 图（Activity on Vertex）
  • 用有向图表示项目中各个活动之间的先后关系
  • 结点表示活动，边表示活动之间的依赖关系
  • 拓扑排序可以用来确定活动的执行顺序
• AOE 网（Activity on Edge）
  • 用有向图表示项目中各个活动之间的先后关系（必须前驱活动完成后才能开始后继活动）
  • 边表示活动，结点表示事件（活动的开始或结束），边的权值表示活动的持续时间
  • 关键路径：从源点到汇点的路径长度最长的路径
  • 事件 \(v_j\) 的最早发生时间：从源点到 \(v_j\) 的最长路径长度 \(ve(j)\)
  • 事件 \(v_j\) 的最迟发生时间：在不推迟整个工程完成的前提下，事件 \(v_j\) 最迟必须发生的时间，记为 \(vl(j)\)
    • 活动 \(<v_i, v_j>\) 的最早开始时间为 \(e(i,j) = ve(i)\)
    • 活动 \(<v_i, v_j>\) 的最迟开始时间为 \(l(i,j) = vl(j) - C_{i,j}\)

查找 ¶

• 在表里查找某个关键字等于给定值的记录 / 元素
  • 静态查找表：只有查找
  • 动态查找表：允许增、删、改
• 性能分析（平均查找长度）：\(\text{ASL} = \sum_{i=1}^n P_iC_i\)
  • n 为表中元素个数
  • \(P_i\) 为查找第 i 个元素的概率
  • \(C_i\) 为查找第 i 个元素所需的比较次数
• 顺序表的查找
  • 线性查找（顺序查找）
    • 从表的第一个元素开始，逐个比较，直到找到目标元素或遍历完整个表
    • 等概率查找，且一定找的到的情况下的 ASL 为 \((n+1)/2\)
    • 优点：简单；缺点：效率低，ASL 大
  • 折半查找（二分查找）
    • 要求是顺序存储的有序表
    • 每次将查找范围缩小一半（如果查找的值小于中间元素，则在左半部分继续查找，否则在右半部分继续查找），直到找到目标元素或范围为空
    • 时间复杂度为 \(O(\log_2 n)\)，ASL 约为 \(\log_2 (n+1)-1\)
  • 分块查找
    • 将有序表分成若干块，每块内元素无序，块与块之间有序（前一块中的最大小于后一块中的最小）
      • 还需要一个索引表，存储每块的最大值与块的起始位置
    • 先在块间进行折半查找，找到目标元素所在的块，再在该块内进行线性查找
    • ASL 为折半查找的 ASL + 块内线性查找的 ASL
  • ASL 上来说，二分最优，分块次之，线性最差
  • 表结构上来说，线性查找对任何表都适用，二分要求全部有序，分块要求块间有序

查找树 ¶

查找树（PPT 叫树表）：动态生成的树结构，专门为了查找进行优化

• 二叉排序树（Binary Sort Tree），又叫二叉搜索树、二叉查找树
  • 要求具有以下性质：
    • 若左子树不空，则左子树上所有结点的值均小于根结点的值
    • 若右子树不空，则右子树上所有结点的值均大于根结点的值
    • 左、右子树也分别为二叉排序树
  • 中序遍历 BST 的到的是一个有序序列
  • 查找：

    Node *searchBST(Node *root, int key) {
        if (root == NULL || root->data == key) return root; // 找到或到达叶子节点
        if (key < root->data) return searchBST(root->left, key); // 在左子树查找
        else return searchBST(root->right, key); // 在右子树查找
    }
    

    • 最好情况时间复杂度为 \(O(\log_2 n)\)，最坏情况为 \(O(n)\)（退化成链表）
  • 插入：插入新叶子结点，新结点是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子
  • 删除：（PPT 上描述的巨复杂）
    • 删除叶节点：直接删除即可
    • 删除只有一个儿子的节点：直接删除，然后把儿子接上
    • 删除有两个儿子的节点
      • 将该节点替换为左子树的最大值，或右子树的最小值
      • 递归删除左子树的最大值，或右子树的最小值
• 平衡二叉树（AVL 树）：修复了 BST 中最坏情况下退化为链表的问题，要求：
  • 每个结点的左、右子树的深度差不超过 1
  • 左子树和右子树都是平衡二叉树

哈希表 ¶

• 又叫散列表，是一种通过哈希函数将关键字映射到表中位置的数据结构
  • 因为理想情况是给出关键字就能知道这个元素在哪，而不需要查找
  • 但是关键字的数量可能超过表的大小，因此需要用一个哈希（hash）函数来映射关键字到表的位置
• 术语：
  • 哈希函数（hash function）：将关键字映射到表中位置的函数
  • 哈希（散列）地址：关键字经过哈希函数计算得到的表位置
  • 不同的关键字经过哈希函数计算可能得到相同的哈希地址，称为冲突
  • 有相同哈希地址的关键字称为同义词
  • 装填因子：表中填入的记录数量 / 表的长度（装填因子越小，冲突概率越低）

• 哈希函数构造方法
  • 直接定址：H(key) = a*key + b
    • 一一对应，不会冲突
  • 数字分析法：事先知道可能出现的关键字特征，然后来尽量避免冲突
  • 平方取中法：对关键字进行平方运算，然后取中间几位作为哈希地址
  • 折叠法：将关键字分成若干部分，然后将这些部分相加作为地址
  • 除留余数法：H(key) = key % p，其中 p 为表长（通常取质数）
  • 随机数法：利用关键字生成随机函数值作为地址，常用在关键字长度不等的情况
• 处理冲突方法：（为冲突的关键字找一个新的空位存放）
  • 开放定址法：
    • 对冲突的关键字再用新函数确定新地址 H = (H(key) + f(i)) % tableSize
      • 其中 H(key) 为原哈希地址，f(i) 为增量函数，i 为冲突次数
    • 增量函数常用的有：
      • 线性探测再散列：f(i) = i
      • 二次探测再散列：f(i) = 1, -1, 4, -4, 9, -9, ...
      • 随机探测再散列：f(i) 为伪随机数
    • 二次聚集现象：原有的 H(key) 不同，但经过增量函数计算后得到的地址相同，导致冲突（非同义词但冲突了）
  • 链地址法：
    • 每个哈希地址对应一个链表，所有映射到该地址的关键字都存储在该链表中
    • 查找时先计算哈希地址，然后在对应链表中查找
    • 优点：解决冲突简单，删除方便；缺点：需要额外存储指针，浪费空间

排序 ¶

• 排序：将一组数据按关键字非递减 / 非递增顺序重新排列的过程
• 稳定性：
  • 对于一个序列，如果存在两个相等的元素：
    • 排序后它们的相对位置不变，则称这个排序算法是稳定的
    • 排序后它们的相对位置发生了变化，则称这个排序算法是不稳定的
  • 稳定排序：冒泡、归并、插入
  • 不稳定排序：快排、希尔、堆排、选择
• 排序种类：
  • 内部排序：待排序序列全部放在内存中进行排序
  • 外部排序：待排序序列过大，无法全部放入内存中进行排序（不考虑）
• 基本操作：比较关键字大小、移动记录位置
• 各种算法原理：
  • 插入：直接插入排序 -> 希尔排序
  • 交换：冒泡排序 -> 快速排序
  • 选择：选择排序 -> 堆排序
  • 归并：归并排序
• 直接插入排序：
  • 依次将每个元素插入到已排序的有序表中
  • 起始将第一个元素视为有序，然后依次将后续元素移动到合适位置使前面的部分有序
  • 时间复杂度为 \(O(n^2)\)（最好情况 \(O(n)\)），稳定排序
  • 适合初始基本有序的情况
• 希尔排序：（太复杂，我觉得不可能考）
  • 先将整个待排序的记录序列分割成若干子序列分别进行直接插入排序，待整个序列基本有序后，再对全体记录进行一次直接插入排序
  • 通过选择不同的增量序列，可以得到不同的希尔排序算法
  • 时间复杂度介于 \(O(n)\) 和 \(O(n^2)\)（最坏）之间，不稳定排序
• 冒泡排序：
  • 对于序列 a[1..n]，首先比较 a[1] 和 a[2]：
    • a[1] > a[2] 则交换，否则不交换
    • 然后比较 a[2] 和 a[3]，依此类推，直到比较 a[n-1] 和 a[n]
  • 这样一趟下来，最大的元素就“冒泡”到了最后一个位置
  • 重复上述过程，直到所有元素有序
  • 时间复杂度为 \(O(n^2)\)（最好情况 \(O(n)\)），稳定排序
• 快速排序：
  • 选择一个基准元素（pivot），将序列划分为两部分：
    • 左边部分的元素均小于等于基准元素
    • 右边部分的元素均大于等于基准元素
  • 然后递归地对左右两部分进行快速排序
  • 时间复杂度为 \(O(n \log n)\)（最坏情况 \(O(n^2)\)），不稳定排序
• 简单选择排序：
  • 从 a[1..n] 中选出关键字最小的元素，与 a[1] 交换位置
  • 然后从 a[2..n] 中选出关键字最小的元素，与 a[2] 交换位置
  • 重复上述过程，直到所有元素有序
  • 时间复杂度为 \(O(n^2)\)，不稳定排序
• 堆排序：（也太复杂，我觉得应该不会考，没细讲过堆把）
  • 堆是一个完全二叉树，满足堆性质：
    • 对于大根堆，任意节点的值均大于等于其子节点的值
    • 对于小根堆，任意节点的值均小于等于其子节点的值
  • 利用堆来每次取出最大（或最小）元素进行排序
  • 时间复杂度为 \(O(n \log n)\)，不稳定排序
• 归并排序：
  • 将待排序序列递归地划分为两半，直到每个子序列只有一个元素
  • 然后将子序列两两合并，得到有序序列
  • 时间复杂度为 \(O(n \log n)\)，稳定排序
• 比较：
  • 平均时间性能，快速排序最佳
  • 对于基本有序序列或者序列长度较小，直接插入排序表现最好