408-ds

听到了大家的保研消息，感慨万分，要是大二能卷绩点，要是大三能打个A类比赛，也没这么多要是，可惜了

45’

C1 绪论

数据结构的基本概念

• 数据的逻辑结构

  • 集合
  • 线性结构
  • 树形结构
  • 图状结构or网状

• 数据的存储结构

  • 顺序存储
  • 链式存储
  • 索引存储
  • 散列存储

• 举例：如果逻辑线性，存储可以是顺序，也可以链式

• 课后习题

  • 链式存储节点内存储单元地址连续
  • 读题他妈读干净点，读仔细点
  • 区分逻辑结构和存储结构

算法和算法评价

• 算法特性

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

• 好算法

  • 确定性
  • 可读性
  • 健壮性
  • 效率与低存储需求

• 度量算法

  • 时间复杂度
    • 用一条语句在算法中被重复的次数来计算
    • 所有语句频度之和为T(n)
  • 空间复杂度
    • 辅助空间大小

• 课后习题：

  • 小题就TM看看复杂度，还行，大题可能结合你写的算法问吧
  • 比如1+2+3 （每次加一个数字），加到n的复杂度
  • 就是计算第几次加=n，然后根据量级判断

C2 线性表

线性表的定义和基本操作

• 相同数据类型的有限序列

• 直接前驱、直接后继

• 线性表是逻辑结构

• 基本操作 (408考试也不能直接用，白打)

  • 初始化表
    • InitList(&L)
  • 求表长
    • Length(L)
  • 按值查找操作
    • LocateElem(L,e)
  • 按位查找操作
    • GetElem(L,i)
  • 插入操作
    • ListInsert(&L,i,e)
  • 删除操作
    • ListDelete(&L,i,&e)
  • 输出操作
    • PrintList(L)
  • 判空操作
    • Empty(L)
  • 销毁操作
    • Destory(&L)

• 课后习题

  • 不会就是低能

线性表的顺序表示

• 线性表的顺序表示叫顺序表
• 逻辑顺序与物理顺序相同（相邻）
• 线性表中的元素位序是1开始，数组下标0开始
• 可以静态分配，也可以动态分配
• 动态分配语句

L.data = new Elemtype[InitSize]; 

• 移动节点平均次数
  • 插入 n/2
  • 删除 （n-1）/2
  • 查找 （n+1）/2
  • 时间复杂度都是O(n)
• 课后算法题 ⭐️
  • abcdefg
    • 循环左移动P位 ，整体思想，AB
  • 求两个序列合并之后的中位数
    • 多讨论情况，分析两个列的中位数大小
    • 我感觉可以直接伪合并有序表
  • 求出一个数列中出现最多的数及其次数（求主元素）
    • 主元素出现的次数肯定大于等于一半次
    • 找出出现最多的，然后判断他是不是满足主元素的条件
    • 找第一个为flag，第二个相同+1，不同-1，到0时下一个为新flag
    • 再来一次验flag
  • 找出数组中未出现过的最小正整数
    • 空间换时间，扫描一遍A，然后标记B[A]
    • B从0开始找到第一个没标记的（==0）则为答案
  • 找出距离最小的三元组
    • A—-B—-C =2AC
    • 因为ABC有序，因此都从最小的开始找，计算距离
    • 计算完距离让里面值最小的一个的指针后移继续判断
    • 记录此时的三元组ijk
    • 统计次数、统计位数、覆盖填写不刷新
• 常用函数：Reverse、Abs、Min

线性表的链式表示

• 单链表

  • 数据域和指针域
  • 引入头节点让链表操作一致，有元素时插入删除和没元素时插入删除一致
  • 无论链表是否为空，head都指向头节点 ，head必定非空

• 基本操作

  • 头插建立
  • 尾插建立
  • 按序号查找节点值
  • 按序号查找节点
  • 插入节点
  • 删除节点
  • 求表长

• 双链表

  • 有prior和next，能直接找到前趋后继
  • 插入要改四个指针
  • 删除改俩就行，记得free掉节点（另外两个指针自动GG）

• 循环链表（应该是默认带头）

  • 循环单链表
  • 循环双链表

• 静态链表

  • 借助数组存储，存放数据和下一个元素下标
  • -1为结尾

• 顺序表和链表的比较

  • 存取/读写方式
    • 顺序随机，链表顺序
  • 逻辑结构和物理结构
    • 顺序表逻辑物理相同
    • 链表不一定，节点内相邻
  • 查找、插入和删除操作
    • 根据有序无序结合最后一章自己判断
  • 空间分配
    • 静态不能扩充，过大浪费
    • 动态可扩充但要移动
    • 链表灵活多了捏

• 如何选存储结构

  • 基于存储
    • 难以估计规模长度就链表
    • 链表存储密度低
  • 基于运算
    • 插入删除多的时候链表
  • 基于环境
    • 顺序表容易实现（任何高级语言都有数组）
    • 链表基于指针，前者容易
    • 频繁插入删除的线性表（动态性强）适合链式

• 课后算法题 ⭐️

  • 找到单链表倒数第K个位置的元素
    • 双指针，同步移动，扫描
  • 找单链表表示的两个字符串的公共后缀起始地址
    • 双指针，先让让的妥协短的到比较后面的对其位
  • 删除绝对值相同的后续元素
    • 空间换时间，有就删
  • a1 a2 a3 a4 a5 ……an 变成 a1 an a2 an-1 a3 an-2 ……
    • 同步走双指针v1v2，找到中间，逆后半段
    • 然后合并

• 蟀操作

  • 俩指针同步走
  • 俩指针一个v 一个2v 找中间（两个都先走一步，再看走不走第二步，帅啊！！！！！！）

C3 栈、队列、数组

栈

• 只允许在一端进行插入或者删除的线性表

• 栈顶允许插入删除

• 栈底固定

• 空栈无元素

• 卡特兰数Cn 2n/（n+1）

• 操作

  • 初始化空栈
  • 进/出栈
  • 读栈顶元素
  • 销毁栈
  • 判空

• 栈的状态判断

  • 栈空 top为-1
  • 栈满 top为maxsize-1
  • 栈长 l=top+1

• 顺序栈

• 共享栈（两头）

• 链栈

• 综合题

  • 字符单链表判断构成的字符串是否中心对称
    • 前一半元素进栈，退出时比较接下来的
  • 判断进退栈操作顺序的合理性

队列

• 也是操作受限制的线性表FIFO

• 队头/首 Front 允许删除的

• 队尾 Rear 允许插入的

• 操作

  • 初始化队伍
  • 队列判空
  • 入队
  • 出队
  • 读队头元素

• 队列的顺序存储

  • 假溢出

• 循环队列

  • front指向对头元素
  • rear指向对尾巴元素的后一个（空节点）
  • 牺牲一个节点判断满的情况

• 判断条件

  • 判空 front == rear
  • 判满 （rear+1）%max==front
  • 元素数量 （rear-front+max）
  • 画一个圆 front 从1开始 放元素 rear指向没元素的后一个
  • 0 1 2 3 4 5 （6个空位 maxsize=6 但最多放5个元素 牺牲一个单元）

• 链队列

• 双端队列

  • 两端都可以入队出队
  • 带入验证问题

• 课后习题

  • 考虑最适合的东西，不仅要考虑操作，还要考虑恢复
  • 选择操作最简单的符合条件的即可

• 综合应用题

  • 设计队列
    • 进出都是O（1）
    • 不能释放

栈和队列的应用 ⭐️

• 括号匹配中的应用

  • 是否合法计算序列

• 求值中的应用

  • 后缀表达式（结合树思考）
  • ABCD-x+EF/-
  • 相当A+Bx（C-D）-E/F
  • 后序遍历二叉树

• 递归调用中的应用

  • Fib

• 层次遍历

  • 出1入多 队列

• 计算机系统中的应用

  • 打印缓冲区

• 课后习题

  • 栈可以进制转换
  • 中缀表达式（正常）转后缀表达式

数组和特殊矩阵

• 对称阵

• 三对角矩阵

• 三角矩阵

• 稀疏矩阵

  • 压缩存储 三元组
  • 十字链表

• 没啥好说的课后习题

C4 串

• 掌握KMP算法以及next数组的推理过程

串的定义和实现

• 不考
• 字符数组

串的模式匹配

• 简单的模式匹配算法（暴力匹配算法）

  • 匹配的不对则模式串（子串）倒退回起始位置
  • 然后主串的位置后退一个

• KMP算法 ⭐️

  • 减少了不必比较的次数
  • 如果已经匹配相等的前缀序列中有某个后缀正是子串的前缀
  • 那么就可以直接通过滑动模式串
  • 做出部分匹配值的表 Partial Match（PM）
  • 1 2 3 4 5
  • a b c a c
  • 0 0 0 1 0
  • a b a a b c a b a
  • 0 0 1 1 2 0 1 2 3 （PM）（这个过程肉眼看）
  • -1 0 0 1 1 2 0 1 2 （next 0 开始）（后移）
  • 0 1 1 2 2 3 1 2 3（next 1 开始）（ +1 ）
  • 移动位数 = 已经匹配的字符数 - 对应的部分匹配值
  • 直接移动到合适的位置
  • 实际的KMP算法中，为了让公式更加简洁简单，如果串的位序是1开始，则next数组整体+1，如果位序0开始那么next数组位序不需要整体+1

• KMP算法的进一步优化 应该不考感觉

  • nextval比的是字母 填写的是位序
  • nextval第一个位置必定是0

• 综合应用题 KMP不考算法题 白了个白

  • 为了不丢失可能的匹配，右移动距离应该最小，j-k就是右移动距，k取大
  • k最大也就是意味着最大的匹配前后缀 PM
  • 除了第一个字符或者有缀的情况外，主串不会素

C5 树和二叉树

5.1 树的概念

• 节点 n>=0 的有限集
• 多选择、也可能算法题
• 树的定义是递归的
• 树的度 孩子个数
• 双亲 兄弟
• 叶子节点、非叶节点
• 深度
• 层次
• 树的高度：最大深度
• 有序树、无序树、路径长度….
• 基本性质： ⭐️
  • 树的所有结点数 = 每个结点度之和（总分支数）+1
  • 度为m的第i层最多有m^( i-1 )
  • 高度为h的m叉树最多有 xxx个结点（等比数列求和）
  • 有n个结点的m叉树的最小高度：等比数列+不等式
  • 总节点数n = n0（度为0的结点）+n1+……
• 课后习题：
  • 总节点数n = n0（度为0的结点）+n1+……
  • 其他题目根据实际情况做就行

5.2 二叉树的概念

• 满二叉树（每一层都满了）

• 完全二叉树（一层一层的完全）

• 二叉树的性质：

  • n0= n2 + 1 ( n = n0 + n1 + n2 ; n = n1 + 2n2 )
  • k 层最多2^(k-1)结点
  • 高度为h 最多2^h-1
  • 完全二叉
    • 求双亲编号 /2下取整
    • 求左孩子2倍 右边孩子2n+1
    • 层次高为log2n向下取整+1（log2 n+1 上取整也行）

• 二叉树的存储结构

  • 顺序存储结构
  • 链式存储结构

• 课后习题

  • 怪题（124个叶子的完全二叉树 最多几个结点）
    • 用巧法解出来以后查看是否可以再加一个
  • 注意题干中（任意 所有 至少 等等条件）

5.3 二叉树的遍历和线索二叉树

• 遍历 ⭐️

  • 先序遍历
  • 中序遍历
  • 后序遍历
  • 层序遍历：队列
  • 先中可以确定；中后可以确定；层中可以；
  • 先后、层先、层后不一定可以；

• 线索二叉树

  • ltag/rtag 0：指向左右孩子；1：指向前/后驱
  • 中序可以带个头节点来方便统一

• 课后习题：

  • 后序可以找路径
  • 线索二叉树是物理结构。。？
  • n个结点的线索二叉树上的线索数：2n
  • 不是每个结点都可以通过线索直接找到前驱和后继
  • 线索化后 后序线索二叉树不能通过后序线索求后序后继
  • 只有后序线索树遍历的时候需要栈的支持

• 综合大题

  • n个不同元素进栈 出栈个数C n 2n / (n+1)
  • 求一棵树的WPL 带权路径长度 给出树根结点指针
    • 可以层序遍历，也可以先序遍历
    • 如果是在函数内部定义的，那么这个变量只初始化一次，即使再次调用这个函数，这个static变量也不会再次被初始化，于是，这个变量的取值就会一直保存着，我们再次调用该函数时，仍是保存的上一次函数调用时保存的结果。（static int）
    • 先序遍历就多一个参数叫deep 每次把deep当成参数一起传进去 传deep+1
    • 层序遍历，遍历到每层最后一个结点就加深度
    • 区别于先序每一次探测都要增加深度，层序只需要在每一层最后一个元素的时候deep+1
  • 给出二叉表达式树，求中缀表达式，带括号
    • 修改中序遍历
    • 空结点就直接返回
    • 叶子结点就输出操作数
    • 如果不是叶子那证明还要继续遍历，深度大于1就加括号，然后左边继续中序
    • 然后再输出那个非叶结点的数据（操作符）
    • 然后再遍历右边的东西，
    • 深度大于1继续加括号（）括号对应
    • 分析
      • 非叶子是操作
      • 叶子是数据
      • 有深度就要有括号
      • 要明白 一个操作 一定涵盖了一个左边的括号和右边的括号
      • 且左括号（，要把那个结点的左子树的所有操作涵盖
      • 同样右括号也是这样
      • 解答完毕，好题目
    • 感觉本章节内容要考的话，主要就是考在基础的遍历方式上进行一些修改
    • 先匹配一个大致能完成工作的算法
    • 然后分析目标和已有算法能得出的东西
    • 再进行修改

5.4 树、森林

• 树的存储结构

  • 双亲表示法：一个结构体数组，分别存放着自己的data和自己的parent
  • 孩子表示法：每个结点的孩子单链表起来，几个结点几个链表
  • 孩子兄弟表示法：左边指针指向第一个孩子，右边指针指向了其兄弟姐妹

• 树、森林与二叉树的转换

  • 树和二叉树的对应：孩子兄弟
  • 左孩子右兄弟

• 树和森林的遍历 ⭐️

  • 树的先根遍历 对应 二叉树先序序列 对应 森林的先序遍历
  • 树的后根遍历 对应 二叉树中序序列 对应 森林的中序遍历
  • 记忆法：树才有根，先根先先，后根中中

• 课后习题

  • 举例子
  • 二叉树左指针为空 -》树中叶子结点
  • 二叉树右指针为空 -》树中没兄弟的结点

• 综合题：

  • 非叶结点都有K个孩子，正则K叉树
  • 多从数列的角度以及特殊情况的角度考虑

5.5 树和二叉树的应用

• 哈夫曼树

  • WPL 带权路径长度
  • 哈夫曼树的构造
  • 哈夫曼编码（可变长度编码）
  • WPL必然相同且最优

• 并查集

  • 双亲表示法
  • 可用于实现克鲁斯卡尔（是否一棵树）
  • 可用于判断无向图连通性
  • 时间复杂度一般是最坏情况下的时间复杂度

• 综合应用题

  • 6个有序表 ABCDEF 10、35、40、50、60、200个数据元素
    • 表中升序，5次22合并，6表合一，最坏情况总次数达最小
    • m长与n长的表合并 最多比较次数是m+n-1
  • 模拟验证前缀问题
    • 模拟

C6 图

6.1 图的基本概念

• 顶点集 V 边集 E

• 图不可以是空图

• 有向图

• 无向图

• 简单图

  • 无重复遍，无自身边就
  • 否则为多重图

• 完全图

  • 无向图与有向图的完全，没啥好说的，自己算边数吧

• 子图

  • 边为子集，点为子集
  • 生成子图要继承所有点
  • 不能有边没点

• 连通、连通图和连通分量

  • 无向图有边就是连通，任意2点都连通：连通图，否则非连通图
  • 极大连通子图称为连通分量
  • 可能没有连通分量，因为不是连通图

• 强连通图、强连通分量

  • 有向图 两点有来回路径，强连通
  • 有向图的极大强连通子图称为强连通分量

• 生成树、生成森林

  • 连通图的生成树是包含全部顶点的极小连通子图

• 顶点的度、出度、入度

  • 自己算

• 边的权和网

  • 带权图称为网

• 路径、路径长度和回路

  • 路径是顶点序列，边数为路径长度
  • n点 大于n-1边 铁有环

• 简单路径、简单回路

• 距离

• 有向树

  • 一个点入度为0 其他点入度都是1

• 课后习题：

  • n个顶点 最少几条边 无论怎么分配都连通？ n-1点的完全图+1
  • n个顶点 最少几条边 一定有环 n-1 组合数学 一个点先和其他n-1连 然后再多一个

6.2 图的存储以及基本操作

• 邻接矩阵：利于稠密图 ⭐️

  • 空间复杂度n^2
  • 可以直接01
  • 也可表示权
  • 无向图必定唯一且对称，只需要存储上下三角
  • 有向图横着是出度，竖着是入度

• 邻接表法：利于稀疏图 ⭐️

  • 无向图 V + 2E
  • 有向图 V + E

• 邻接多重表：存无向图 感觉不考

• 十字链表：存有向图

• 课后习题：

  • 感觉都不难

• 综合题：

  • 沃舍尔算法
  • 浩宇考的算法

6.3 图的遍历 ⭐️

• 广搜 BFS 队列

  • Dijkstra 单源最短路径算法
  • Prim 最小生成树算法
  • 操作：
    • BFSTraverse
    • 初始化标记数组、辅助队列
    • 从0号开始遍历 即使用BFS函数
    • BFS函数：
      • 访问初始点v
      • v入队
      • while 队列非空
        • 出队
        • 访问其所有的临界点
        • 未访问的入队列
  • 俩函数各一次
  • 还可以求单源最短路径（权1）
  • 广度优先生成树
    • 邻接矩阵唯一 树唯一
    • 邻接表存储表示不唯一 树不唯一
  • 复杂度
    • 矩阵 V^2
    • 表 V+E

• 深搜 DFS 栈

  • DFSTraverse：
    • 初始化标记数组、辅助队列
    • 从0号开始遍历 即使用DFS函数
    • DFS函数：
      • 访问本点
      • dfs其所有的邻接点
  • 递归动作栈 空间V
  • 复杂度
    • 矩阵 V^2
    • 邻接表 V+E

• 课后习题

  • 直接秒
  • 看清有向无向图
    • 对应搜索的序列不同

6.4 图的应用

• 最小生成树 ⭐️

  • Prim算法（适合边稠密）
    • 每次选已知集合距离最近的点（边）
    • 避开环
    • 复杂度：V^2
    • 记忆点：Point 与point有关
  • Kruskal算法（适合边稀疏、顶点多）
    • 每次选边集合中最小的边
    • 避开环（属于不同的连通分量）
    • 复杂度 E log E

• 最短路径

  • Dijkstra算法（单源最短路径问题）
    • 一共n个点
    • 那就要进行n-1轮
    • 每一轮确定到一个的最短路
  • Floyd-Warshall算法（各顶点之间的最短路径问题）
    • 几阶矩阵 复杂度 V^3
    • 矩阵乘法就行
    • 允许负权边，不允许负回路

• 拓扑排序

  • AOV网络
  • 找入度为0的，然后减少那些其指向的结点的入度
  • 入度数组
  • 用逆邻接表更快

• 关键路径

  • AOE网络 边代表活动的网络 权值代表活动的开销
  • ve(i)：事件Vk的最早发生时间：到本结点最长的一条路 max （列数为点数）
  • vl(i)：事件Vk的最迟发生时间：逆拓扑最小 min（列数为点数）
  • e(i)：活动Ai的最早开始时间：本活动（边）的起始点的最早发生时间（列数为边数）
  • l(i)：活动Ai的最迟开始时间：本活动（边）的终点的最迟发生时间-边长（列数为边数）
  • l(i)-e(i)：数列中0的就是关键活动

C7 查找

查找的基本概念

• 查找成功和失败的平均查找长度
• 用于查找的数据集合称为查找表（同一类型的数据元素）
• 静态查找表
• 动态查找表涉及动态插入删除
• 关键字唯一标识该元素

顺序查找和折半查找

• 一般线性表的顺序查找
  • 烧饼减少判断
  • 成功(n+1)/2
  • 失败n+1
• 有序表的顺序查找
  • 成功(n+1)/2
  • 失败n/2+n/(n+1)
  • (1+2+….+n+n)/(n+1)
• 折半查找
  • mid = ( low + high ) / 2 while开始就干这个
  • 每一次mid与元素进行比较 移动high 和low 到mid的左右位置
  • 大小题考察概率都不低
  • 不能基于链表
  • 外部结点
  • 判定树的画法
• 分块查找
  • 也叫索引顺序查找
    • 可以顺序或者折半查找索引表
  • 快内无序
  • 块间有序
  • 索引包含本块最大的关键字
  • 最好根号n块
  • 支持链式存储，方便动态插入删除
• 课后习题：
  • 判定树的左右取决于上下取整问题
  • 哪边取整哪边少
  • 排序树的性能要取决于树的形状
  • 比较几次的题目就画树

树型查找 ⭐️

• 二叉排序树 BST

  • 定义
    • 左<根<右 中序就可以得到递增序列
  • 查找
    • 模拟走左右
  • 插入
    • 硬插
  • 构造
    • 从头开始插入
  • 删除
    • 被删除的是叶子，直接删
    • 被删除的结点只有左or右子树，子树代替根
    • 有左右两棵树
      • 直接前驱or直接后继代替，然后继续删除那个前驱or后继
      • 前驱：左子树最右下（最大）
      • 后继：右子树最左下（最小）
  • 如果有序表是动态查找表，应该用二叉排序树作为其逻辑结构

• 平衡二叉树 AVL （ASL是平均查找长度）

  • 平衡因子：左高-右高 绝对值<1
  • 保持平衡的目的是为了查找效率
  • 平衡树最少有的结点数量 nk = nk-1 + nk-2 + 1
  • 插入：调整最小不平衡子树（向上检查）
    • LL：在A的左孩子的左子树插入导致不平衡
      • 右单旋转
    • RR：A 右 右
      • 左单旋转
    • LR：A 左 右
      • 先左后右 （部分左 整体右）
    • RL：A 右 左
      • 先右后左
  • 删除
    • 按照二叉排序树删除节点
    • 向上查找问题节点 没问题就完结撒花
    • 找到最小不平衡子树个头最高的儿孙
      • 根据孙子相对于爷爷的问题进行修改
    • 调整
    • 查看不平衡向上传导的问题

• 红黑树 ⭐️

  • AVL容易遭受破坏
  • 平衡二叉树以查为主
  • 频繁插入删除就红黑
  • 定义、性质、插入
  • 定义
    • 左孩子 右孩子 颜色 父亲指针 值
    • 红黑树的叶子结点一般叫失败节点 NIL
    • 左根右、根叶黑、不红红、黑路同
      • BST
      • 根和叶子都是黑的
      • 相邻不红
      • 一个节点到任何一个叶子都是同样的黑色（不算自己）（黑高）
  • 查找复杂 logn
  • 插入：与AWL异曲同工
    • 查找、先确定插入位置
    • 新节点是根就染黑，否则染红
    • 破坏了就调整，要看新节点的叔叔的脸色
      • 黑叔叔：旋转+染色（看相对于爷）
        • LL：右单、父换爷+父爷染色
        • RR：左单、父换爷+父爷染色
        • LR：左右双旋、儿换爷+染色
        • RL：右左双旋、儿换爷+染色
      • 红叔叔：染色+变新
        • 叔父爷换色，爷变新结点

B树和B+树 ⭐️

• B树 （多路平衡查找树）

  • 性质 插入 删除
  • m叉查找树
    • 每个节点最多有m颗子树
    • 最多m-1关键字
    • 根如果不是终端节点，那么至少两颗子树
    • 除了根以外的所有非叶子至少m/2 上取整个子树
    • 节点内有序，有失败结点NIL（其实节点内数据多可以折半）
    • 所有数据都在自己的节点
  • 所有结点子树高度相同
    • 所有叶子都在同一层
  • 计算高度不包括失败结点
    • 最小高度，填满，h>=log m (n+1)
    • 最大高度，每一层结点尽可能少，h <= log m/2 (n+1)/2 + 1
    • log m (n+1) <= h <= log m/2 (n+1)/2 + 1
  • 插入
    • 先插满根、然后分裂，提出中间的位置
    • 一定先插入最底层
    • 插入的最关键，是学会分裂
  • 删除
    • 删除的结点若非终端，用直接前驱or直接后继替代
      • 直接前驱，左侧指针最右
      • 直接后继，右侧指针最左
      • 转化成对终端节点的删除
    • 看兄弟够不够借
    • 兄弟也不够
      • 合并
      • 和左右兄弟以及双亲节点中相关的关键字合并
      • 可能导致双亲节点减少，向上合并

• B+树

  • 性质
    • 每个分支最多m个子树
    • 根最少2子树，其他最少m/2上取余个子树
    • 关键字和子树个数相等
    • 包含指向记录的指针
    • 可以多路查找，也可以顺序查找
    • 一定要走到最下层
    • 关键字会重复
  • 很像分块查找
  • 所有的数据都在叶子结点
  • 放的是最大元素
  • 并不是n个关键词，对应n+1个分支
  • 对应的是n个分支，n个块，关键词存放里面最大的块
  • 最下层块之间也有指针

• B+ VS B

  • 分叉对应
  • 分支上下限，关键字上下限
  • 结点重复问题
  • B+非叶只是索引，不包含存储地址
  • B包含存储地址

散列表（Hash Table）

• 数据元素的关键字和存储地址直接相关

• 建立关键字和存储地址的联系

• 散列函数 哈希函数

• 散列函数的构造

  • 除留余数法 素数P
    • 均匀
  • 直接定址法
    • 空位
  • 数字分析法
    • 选数字编码分布均匀的数码位作为散列函数
    • 手机后4位
  • 平方取中法
    • 平方以后中间取几位
  • 空间换时间 直接2的多少次

• 处理冲突的方法

  • 开放定址法
    • 散列表长度是4m+3素数
    • 线性探测法
      • 发生冲突、往后探测相邻的下一个单元看是否为空
      • 哈希函数值域选择13 0-12
      • 和冲突函数处理函数值域不一样可能 0- 15
      • 查找空也算一次查找
      • 删除标记，逻辑删除，假删
    • 平方探测法
      • 1 -1 4 -4 9 -9
    • 双散列法
  • 拉链法

C8 排序

8.1 排序的定义

• 定义

8.2 插入排序

• 直接插入排序：找一个、放前面（顺序找插入位置）
• 折半插入排序：折半找插入位置
• 希尔排序：增量、间隔

8.3 交换排序

• 冒泡排序
• 快速排序

8.4 选择排序

• 简单选择排序
  • 从后面选一个最小
• 堆排序：
  • 初始：多次向上调整子树，一次向下
  • 调整好后删除，最后一个元素放上来然后一次向下调整

8.5 归并排序和基数排序（桶排序）

• 归并排序
  • 分路
• 基数排序
  • 桶

8.6 各种内部排序算法的比较和应用 ⭐️

• 比较
• 应用

8.7 外部排序

• 概念

• 方法

• 多路平衡归并与败者树

• 置换-选择排序

• 最佳归并树

  • x叉 n(x-1)>结点数量的最小n为一共需要的结点数量
  • 做差得到结果

• 口诀：

  • 间希快堆（JXKD）不稳定
  • 快logn 2归n 基r
  • 快排平均最坏不同