数据结构
时间：2026-03-07 
mindmap
  root((数据结构))
    绪论
    线性表
    栈和队列
    串
    数组和广义表
    树和二叉树
    图
    动态存储管理
    查找
    内部排序
    外部排序
    文件

第六章 树和二叉树

  • 完全二叉树是除了最后一层，其他层节点都达到最大值
  • 任意一个森林都可以转换为一个二叉树
  • 有子节点的是分支节点，没子节点的是叶节点
  • TODO 链式树
  • 哈曼编码，Weighted Path Length最小二叉树
  • n阶B树，多路平衡查找树
    1. 每个结点最多n-1个关键字
    2. 每个结点最多n个孩子
    3. 非根结点至少n/2个孩子
    4. 非根结点至少1个关键字

第七章 图

  • 各顶点的度均大于等于2的无向图必有回路
  • TODO 拓扑排序
  • TODO BFS算法

第九章 查找

归并查找

  • n个最小元素归并查找的每块最少元素:
    $$\sqrt{n}$$

散列表

  • 线性探测法
  • 二次探测法/平方探测法

第十章 内部排序

最好 最坏 逻辑 特性
插入排序 $$n$$ $$n^2$$ 插入到排序好的序列内 基本有序最快
冒泡排序 $$n$$ $$n^2$$ 相邻交换 交换最多
快速排序 $$\log_2 n$$ $$n^2$$ 平均最快
简单选择排序 $$n^2$$ $$n^2$$ 遍历找最小跟第一个交换 交换最少
希尔排序 gap=n/2
基数排序 个十百
归并排序 合并有序数组