大一下复习

数据结构期末复习

二叉树的遍历

牢记递归思想。

// 中序遍历
void mFind(Node* root) {
    if (root == nullptr) {
        return;
    }
    // 先递归遍历左子树
    mFind(root->lc);
    // 访问当前结点
    cout << root->data << " ";
    // 再递归遍历右子树
    mFind(root->rc);
}

树和森林的转换

参考视频

• 树转森林：删除树的根节点，根节点的子树即为森林。
• 森林转树：将森林的第一棵树作为树的根节点，其他树作为根节点的子树依次连接起来。

哈夫曼树（Huffman Tree）

带权路径长度：带权路径长度 = SUM（长度*权值）

1. 选择权值最小的两个节点作为左右子树。
2. 合并这两个节点并更新权值，重复以上步骤，直到只剩一个根节点。

图

• 入度和出度：在有向图中，如果一个人可以向多个人说话（即有多个人可以听他说话），那么他的“出度”就是他说话对象的数量。相对的，“入度”就是有多少人可以向他说话。

• 深度优先搜索：D(Depth)FS（类似树的先序遍历）

  // DFS 深度优先搜索
  // 从节点u开始进行深度优先搜索
  void DFS(int u) {
    // 输出当前访问的节点u
    cout << u << " ";
    // 标记节点u为已访问
    vis[u] = 1;
    // 遍历节点u的邻接表 递归访问所有未被访问的相邻节点
    for (int i = head[u]; i != -1; i = edg[i].next) {
        int v = edg[i].to;
        if (!vis[v]) {
            DFS(v);
        }
    }
  }

• 广度优先搜索：B(Breadth)FS（类似树的层序遍历）
• 拓扑排序：每次选入度为0的点，然后删除这个点和它的出边

最小生成树（Minimum Spanning Tree）

参考视频

• Prim算法：从任一节点开始，每次选择权值最小的边连接一个新节点，直到所有节点都连接。
• Kruskal算法：将所有边按权值从小到大排序，依次选择不形成环的最小权值边，直到所有节点都连接。

最短路径（Shortest Path）

• Dijkstra算法：用于单源最短路径，适合边权为非负的图，从起点开始逐步扩展最短路径，直到所有节点都找到最短路径。
• Floyd-Warshall算法：用于任意两点间最短路径，逐步优化所有点对的路径。

二叉排序树（Binary Search Tree, BST）

BST是一种特殊的二叉树，左子树所有节点的值都小于根节点的值，右子树所有节点的值都大于根节点的值。

• 平衡二叉树、二叉排序树：任意节点左右子树的深度差≤1
• 二叉排序树的调整：参考视频（调整LL,LR,RL,RR）

B树和B+树

• B树：一种自平衡的多路查找树，节点可以有多个子节点，用于数据库和文件系统。
• B+树：B树的变种，所有叶子节点构成一个有序链表，更适合范围查询。

散列表（Hash Table）

散列表是一种数据结构，通过哈希函数将键映射到表中的位置进行存储，实现快速查找、插入和删除。

排序算法

• 插入排序（Insertion Sort）：通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
  下面这些都不稳定
• 希尔排序（Shell Sort）：插入排序的一种改进，分组进行插入排序，逐步减少分组数量，最终整体插入排序。

• 快速排序（Quick Sort）：通过分区将数组分成两部分，递归对两部分排序。

  // 交换两个元素的值(略)
  void swap(int &a, int &b);
  // 分区函数
  int partition(vector<int> &arr, int low, int high) {
    int pivot = arr[high];  // 选择最后一个元素作为枢轴
    int i = low - 1;        // 指向较小元素的索引
    for (int j = low; j < high; ++j) {
        if (arr[j] < pivot) {  // 如果当前元素小于枢轴
            ++i;
            swap(arr[i], arr[j]);  // 交换arr[i]和arr[j]
        }
    }
    swap(arr[i + 1], arr[high]);  // 将枢轴放在正确的位置
    return i + 1;                 // 返回枢轴的索引
  }
  // 快速排序函数
  void quickSort(vector<int> &arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);  // 获取分区索引
        quickSort(arr, low, pi - 1);  // 递归排序左子数组
        quickSort(arr, pi + 1, high); // 递归排序右子数组
    }
  }

• 堆排序（Heap Sort）：利用堆这种数据结构，将数组看成完全二叉树，构建最大堆，然后依次取出堆顶元素进行排序。