数据结构详细版本

数据结构详细版本思维导图，数据结构三要素是逻辑结构、存储结构（物理结构）、数据运算，一起来学习数据结构知识吧。

数据结构

• 绪论
  • 概念和术语
    • 数据、数据元素、数据项
    • 数据对象、数据类型
    • 抽象数据类型ADT
      • 数据对象集
      • 数据关系集：可以用集合或边集的表示方法
      • 操作集
  • 数据结构三要素
    • 逻辑结构
      • 线性结构
        • 线性表、栈、队列、串
      • 非线性结构
        • 树形结构
        • 图状结构（网状）
        • 集合
    • 存储结构（物理结构）
      • 数据在计算机中的表示，包括数据元素的表示和关系的表示
      • 顺序存储
        • 逻辑上相邻的元素在物理位置上也相邻 优点是可以随机存储 缺点是可能产生较多的外部碎片
      • 链式存储
        • 逻辑上元素相邻，但物理位置上不一定相邻 优点是没有碎片产生，能充分利用存储单元 缺点是因存储指针而占用额外的存储空间，且只能顺序存取
      • 索引存储
        • 在存储元素信息的同时，还建立附加的索引表 索引表项形式为（关键字，地址） 优点：检索速度快 缺点：索引表占用较多的存储空间；增删数据时需要修改索引表，花费较多时间
      • 散列存储
        • 根据元素的关键字直接计算出该元素的地址 优点：检索、增删速度快 缺点：可能出现元素存储单元冲突
    • 数据运算
      • 包括运算的定义和实现 运算的定义是针对逻辑结构的，指出运算的功能 运算的实现是针对存储结构的，指出运算的具体操作步骤
  • 算法
    • 算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。 设计目标：包括正确性、可读性、健壮性和效率与低存储需求
    • 五个特性
      • 有穷性
        • 一个算法必须保证执行有限步后结束
      • 确定性
        • 算法的每一个步骤必须有确定的意义 即相同的输入只能得到相同的输出
      • 可行性
        • 算法中的所有操作都可以通过已经实现的基本操作进行运算，并在有限次内实现
      • 输入
        • 一个算法有0个或多个输入
      • 输出
        • 一个算法有一个或多个输出
    • 效率的度量
      • 时间复杂度
        • 以算法中基本运算的执行次数（频度）作为时间复杂度T(n)的度量 基本运算一般指最深层循环内的语句，即一个循环内的语句最多会被执行多少次 基本操作的度量是问题规模n的一个函数f(n) 当f(n)与n无关时，T(n)=O(1) 当f(n)与n是线性关系时，T(n)=O(n) 当f(n)与n是二次方关系时,T(n)=O(n^2)...以此类推 一般将最坏的情况作为算法时间复杂的的度量
      • 空间复杂度
        • 使用的辅助空间的大小
• 线性表
  • 线性表是具有相同数据类型的n个数据元素的有限序列 本章重点考查各类算法的实现：链表的查找、插入、删除等
  • 逻辑结构
    • 只有一个表头元素，只有一个表尾元素，其他元素只有一个直接前驱和一个直接后驱
  • 物理结构
    • 顺序存储（顺序表）
      • 在物理存储空间上连续 可随机存取 类型描述： 静态分配 typedef struct{ ElemType data[MaxSize]; // 顺序表的元素 int length; // 顺序表的长度 }SqList; // 类型定义 动态分配 typedef struct{ ElemType *data; // 动态分配数组的指针 int MaxSize, length; // 最大容量和当前个数 }SqList L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize); 或L.data = new ElemType[InitSize];
    • 链式存储（链表）
      • 在物理空间上不需要使用连续的存储单元 只能顺序遍历 由结点构成，每个结点包括存放数据元素的数据域和指向后继结点地址的指针域。 结点类型描述： typedef struct LNode{ ElemType data; // 数据域 struct LNode *next; // 指针域 }LNode;
      • 单链表：只有一个后继指针，只能从头结点顺序向后遍历
      • 双链表：有两个指针域，指向指向前驱和后继结点
      • 循环单链表：尾结点的next指向头结点
      • 循环双链表：头结点的prior指向尾结点，尾节点的next指向头结点
      • 静态链表：实质上是用一位数组来表示一个链表
  • 应用
    • 栈：先进后出FILO
      • 只允许在一段进行插入或删除操作的线性表 从栈顶入栈，从栈顶出栈 考点：出栈序列（个数）的计算；n个不同元素进栈，出栈序列个数为卡特兰数C（2n，n）*（1/n+1）
      • 基本操作
        • InitStack(&S) // 初始化空栈 StackEmpty(s) // 判断栈是否为空 Push(&S,x) // 入栈x Pop(&S,&x) // 出栈x GetTop(S,&x) // 读栈顶元素至x ClearStack(&S) // 销毁栈
      • 顺序栈：采用顺序存储结构
      • 链栈：采用链式存储结构
      • 共享栈：两个栈共享一片连续的存储空间，并且两栈的栈顶分别设在空间的两端
    • 队列：先入先出FIFO
      • 基本操作
      • 顺序队列
        • 循环队列
        • 队空条件和队满条件
      • 链式队列
        • 长度不受限制
      • 双端队列
        • 两端都可以插入和删除的队列
    • 栈的应用
      • 括号匹配：遇左括号入栈，遇右括号匹配出栈
      • 表达式求值
        • 中缀转后缀
          • 根据运算符的栈内（isp）和栈外（icp）优先级来进行栈的变化
          • 表达式最后加上‘#’字符
          • 扫描表达式，遇操作数直接输出
          • 遇运算符
            • 若为‘(’，入栈
            • 若为‘)’，将栈中运算符出栈输出，直到出栈‘(’
            • 若为其他运算符，判断优先级
              • 栈顶操作符isp<栈外操作符icp：入栈
              • 栈顶操作符isp>栈外操作符icp：栈顶运算符出栈输出，继续与下面的栈顶比较
              • 遍历完成后，若栈非空，弹出所有元素
        • 后缀表达式计算
          • 遇操作数，进栈
          • 遇操作符，出栈两个操作数，计算结果进栈
      • 数制转换
      • 递归
        • 将每一层的返回点，局部变量，传入参数进栈保存
    • 队列的应用
      • 解决逐行或逐层的问题
        • 树的层次遍历
          • 根结点入队
          • 根结点出队，左右孩子结点入队
      • 解决主机与外部设备速度不匹配的问题
        • 缓冲区
      • 解决由多用户引起的资源竞争问题
        • 进程的就绪队列
    • 数组
      • 行优先存储
      • 列优先存储
    • 特殊矩阵的压缩存储
      • 对称矩阵
        • Aij = Aji
      • 三角矩阵
      • 三对角矩阵
      • 计算元素在数组中的位置（下标）
      • 稀疏矩阵
        • 仅存储非零元素
        • 三元组方式存储（行标，列标，值）
        • 链式存储
          • 邻接表法
          • 十字链表法
          • 与图的存储结构相同
• 树和二叉树
  • 树的基本概念
    • 定义
      • 只有一个根结点
      • 是一种递归的数据结构
    • 基本术语
      • 结点的度：结点拥有的子树个数
      • 树的度：各结点度的最大值
      • 叶子结点：度为0的结点
      • 结点的层次：从根开始，根结点为第1层，根的孩子为第二层，以此类推
      • 树的高度：树中结点的最大层次
      • 结点的深度：从根结点开始往下逐层累加的
      • 结点的高度：从叶结点开始往上逐层累加的
    • 树的性质
      • 树中的结点数等于所有结点的度数加1
      • 度为m的第i层上至多有m的（i-1）次方个结点
      • 高度为h的m叉数至多有？个结点
      • 具有n个结点的m叉数的最小高度为？
    • 树的存储结构
      • 顺序存储结构
        • 双亲表示法，
          • 一维数组下标代表结点编号，内容为双亲结点在数组中的位置
          • 根节点下标为0，内容为-1
      • 链式存储结构
        • 孩子表示法，即图的邻接表结构
          • 将每个结点的孩子结点都用单链表链接起来
        • 孩子兄弟表示法
          • 又称二叉树表示法，以二叉链表作为树的存储结构
          • 每个结点包括三个部分：结点值，指向第一个孩子的指针，指向下一个兄弟的指针
  • 二叉树
    • 定义：每个结点的度不大于2的树，可以为空
    • 几种特殊的二叉树
      • 满二叉树：除叶子结点外，每个结点的度都为2，所有叶子结点都在同一层
      • 完全二叉树：各个结点的编号与相同高度的满二叉树中相同位置上的结点的编号均相同
    • 性质
      • 非空二叉树上叶子结点数等于双分支结点数加1
      • 二叉树的第i层最多有？个结点
      • 高度为k的二叉树最多有？个结点
      • 结点i的双亲结点的编号为i/2（向下取整）
      • 结点i所在的层次为？
      • 具有n个节点的完全二叉树的高度为？
    • 二叉树的存储结构
      • 顺序存储结构
        • 适合完全二叉树和满二叉树
        • 结点值按编号依次存入一个一维数组中
      • 链式存储结构
        • typedef struct BTNode { Elemtype data; struct BTNode *lchild,*rchild; }BTNode;
        • 结点信息：左指针域+数据域+右指针域
    • 二叉树的遍历算法
      • 根据中&前或中&后或中&层遍历才可以唯一确定一颗二叉树 根据前序和后序可以确定祖先与子孙的关系
      • 先序遍历
        • 1. 访问根结点
        • 2. 先序遍历左子树
        • 3. 先序遍历右子树
      • 中序遍历
        • 1. 中序遍历左子树
        • 2. 访问根结点
        • 3. 中序遍历右子树
      • 后序遍历
        • 1. 后序遍历左子树
        • 2. 后序遍历右子树
        • 3. 访问根结点
      • 层次遍历
        • 1. 根结点入队
        • 2. 根结点出队，左右孩子结点入队
      • 先、中、后序非递归算法
    • 线索二叉树
      • 把二叉树中的空指针（n+1个）利用起来，作为寻找前驱或后继的线索
      • 二叉树线索化后近似于线性结构，分支结构的遍历就转化为了近似于线性结构的遍历
      • 后序线索树查找后序结点任需要栈的支持
      • 结点结构：| ltag | lchild | data | rchild | rtag |
      • 规则
        • 若Itag=0，表示lchild为指针，指向结点的左孩子 若Itag=1，表示lchild为线索，指向结点的直接前驱
        • 若rtag=0，表示rchild为指针，指向结点的右孩子 若rtag=1，表示rchild为线索，指向结点的直接后继
  • 树和森林
    • 树转换为二叉树
      • 左孩子右兄弟，根结点没有右孩子
    • 二叉树转换为树
      • 一层一层，将右孩子全变回兄弟
    • 森林转换成二叉树
      • 先将每棵树转成二叉树
      • 再将第一棵树的根作为转换后的二叉树的根
      • 第二棵树作为根的右子树
      • 第三棵树作为根的右子树的根的右子树。。。
    • 二叉树转换为森林
      • 不停的将根结点有右孩子的二叉树右孩子断开，得到多颗二叉树，再由二叉树变回树
    • 数和森林的遍历
      • 树的遍历
        • 先序遍历：先访问根结点，然后先序遍历每一颗子树
        • 后序遍历：先后序遍历每一颗子树，再访问根结点
      • 森林的遍历
        • 先序遍历：对森林的每一棵树分别进行先序遍历，对应于二叉树的先序遍历
        • 后序遍历：对森林的每一颗树分别进行后序遍历，对应于二叉树的中序遍历
  • 树与二叉树的应用
    • 并查集
      • 通常用树（森林）的双亲表示法作为并查集的结构
      • 每个子集合用一颗树表示，所有集合构成一个森林，森林存在双亲表示数组里
      • 数组元素的下标代表元素名；根结点的下标代表集合名；根结点的双亲结点为负数，数值绝对值代表集合内元素个数
    • 二叉排序树
      • 定义
        • 左子树上所有结点值均小于根结点
        • 右子树上所有结点值均大于根结点
        • 左右子树也是二叉排序树
      • 操作算法
        • 查找
          • 从根结点关键字值开始比较
          • 小于则从左子树中查找；大于则从右子树中查找
          • 循环，若相等，查找成功
        • 插入
          • 关键字小于根结点关键字，插入左子树
          • 关键字大于根结点关键字，插入右子树
          • 插入的新结点一定是叶子结点
        • 构造
        • 删除
          • 被删除结点z是叶子结点：直接删除
          • z只有一颗子树，删除后用子树代替z
          • z有两颗子树，令z的中序直接后继（或直接前驱）代替z，然后再删除该直接后继（或直接前驱）
    • 二叉平衡树AVL
      • 定义
        • 任何结点的左右子树的高度差绝对值不超过1
        • 目的是使二叉排序数的平均查找长度更小
      • 插入
        • 插入过程前半部分与二叉排序树相同
        • 新结点插入后，若失去平衡，需要进行旋转
        • 旋转方式
          • LL（右单旋转）
            • 左孩子的左子树上插入了新结点
          • RR（左单旋转）
            • 右孩子的右子树上插入了新结点
          • LR（先左后右旋转）
            • 左孩子的右子树上插入了新结点
          • RL（先右后左旋转）
            • 右孩子的左子树上插入了新结点
    • 哈夫曼树和哈夫曼编码
      • 哈夫曼树的定义
        • 结点的带权路径长度WPL：从根结点到任意结点的路径长度乘以结点的权值
        • 树的带权路径长度WPL：树中所有叶结点的WPL之和
        • WPL最小的二叉树称为哈夫曼树
      • 哈夫曼树的构造
        • 1. 将所有结点分开放入集合中
        • 2. 构造一个新结点，选取集合中权值最小的两个结点作为新结点的左右孩子，新结点的权值是左右孩子结点权值之和
        • 3. 将新结点加入集合，并从集合中删除选取的两个结点
        • 4. 重复2-3，直到集合中只剩一颗树
      • 哈夫曼编码
        • 从根结点到叶结点的路径上的边标记序列
        • 边标记为0代表转向左孩子
        • 边标记为1代表转向右孩子
        • 可得出所有叶结点的哈夫曼编码
• 图
  • 图的基本概念
    • 图的定义
      • 图G(V,E)由顶点集V和边集E组成
      • V = ｛v1，v2,,,vn｝,一定非空
      • E = ｛(u，v) | u ∈V, v ∈V｝，可以为空
    • 相关概念
      • 有向图，无向图：边是否为有向边
      • 简单图，多重图：两个结点之间的边数是否多于一条
      • 完全图：任意两个顶点之间都存在边
        • 无向完全图有n(n-1)/2条边
        • 有向完全图有n(n-1)条边
      • 路径和长度
        • 路径：相邻顶点构成的序列对，如(D，C)、(C，B)、(B，A)
        • 路径长度：路径上的边数
      • 连通
        • 顶点v到顶点w之间有路径存在，则v、w连通
      • 连通图和连通分量
        • 无向图中任意两个顶点都是连通的，称为连通图
        • 无向图的极大连通子图称为连通分量
        • 若无向图是一个连通图，它的连通分量是它本身
        • 连通图的边数最小为n-1
      • 强连通图和强连通分量
        • 有向图中任意两个顶点都是连通的，称为强连通图
        • 有向图的极大连通子图称为强连通分量
        • 若有向图是一个强连通图，它的强连通分量是它本身
        • 强连通图的边数最小为n
      • 度；入度、出度
        • 度是以一个顶点为端点的边的数目，入度指向该顶点，出度相反
        • 有向图全部顶点的入度之和等于出度之和
        • 无向图全部顶点的度之和等于边数的两倍
  • 存储结构及操作
    • 顺序存储
      • 邻接矩阵
        • 一维数组存顶点信息，二维数组存边信息 存储效率低 无向图的邻接矩阵是对称矩阵，可以矩阵压缩
        • 无向图的邻接矩阵是一个对称矩阵（并且唯一）
        • 设矩阵为A，Aⁿ[i][j]表示从顶点i到j的长度为n的路径的数目
    • 链式存储
      • 邻接表法
        • 减少存储空间 对有向图来说容易查找出度，不容易查找入度
        • 每条边用一个结点表示
        • 因为结点链接顺序是任意的，所以表示不唯一
        • 顶点结点：| data | firstarc |
        • 弧结点：| adjvex | nextacr |
      • 邻接多重表（无向图优化）
        • 顶点结点：| data | firstedge |
          • firstedge：指向第一条依附于该顶点的边
        • 弧结点：| mark | ivex | ilink | jvex | jlink | info |
          • mark：标记该边是否被搜索过
          • ivex、jvex：改边连接的两个顶点的位置
          • ilink：指向下一条连接ivex顶点的边
          • jlink：指向下一条连接jvex顶点的边
          • info：边的相关信息
      • 十字链表（有向图优化）
        • 顶点结点：| data | firstin | fisrtout |
        • 弧结点：| tailvex | headvex | hlink | tlink | info |
          • tailvex：弧尾顶点的位置
          • headvex：弧头顶点的位置
          • hlink：指向弧头相同的下一条弧
          • tlink：指向弧尾相同的下一条弧
    • 基本操作
  • 图的遍历
    • 广度优先搜索
      • 类似于树的层次遍历
      • 1. 任取一个顶点访问，入队，并标记已访问。
      • 2. 队列不空时循环执行：出队，依次检查出队顶点的所有邻接顶点，将没有被访问的顶点入队，并标记已访问。
      • 3. 队列空时跳出循环。
    • 深度优先搜索
      • 类似于二叉树的先序遍历，二叉树先序遍历递归的访问每个结点的左右两个分支，而图的DFS则要递归访问多个分支
      • 1. 先访问任意一个顶点
      • 2. 访问该顶点的其他任意一个未被访问的邻接顶点，重复进行
      • 3. 当一个顶点的所有邻接顶点都被访问过时，依次回退到最近访问的顶点，寻找下一个未被访问的邻接顶点，继续重复，直到所有顶点都被访问过结束
    • 基于邻接矩阵的DFS和BFS序列是唯一的，而基于邻接表可能不唯一
    • 基于邻接矩阵的搜索算法时间复杂度：o（V*V）；邻接表是o（V+E）
  • 应用
    • 最小生成树
      • 概念
        • 连通图的生成树是图的极小连通子图，即包含所有顶点，边最少的情况
        • 生成树少一条边，就变成非连通图；多一条边，就构成回路
        • 边权值之和最小的生成树称为最小生成树
        • 当各边权值互不相等时，最小生成树唯一
      • 生成算法
        • prim算法：从顶点开始扩展最小生成树
          • 从一个顶点v0开始，将v0到其他顶点的所有边当作候选边; 从候选边中挑出权值最小的边输出，并将边的另一端的顶点v并入生成树中; 考查所有剩余顶点vi，如果（v,vi）的权值比lowcost[vi]小，则用（v，vi）的权值更新lowcost[vi]; 重复2-3直到所有边都检测完为止. 时间复杂度O(n^2) 只和顶点有关，适合稠密图
        • Kruskal算法：从边按权值来构造最小生成树
          • 将图中的边按权值大小从小到大排列 从最小权值的边开始扫描，设置一个顶点的并查集T（森林的双亲表示）来记录 如果该边的两个顶点不在同一颗树中，将它们对应的树合并成一棵树 重复1-3直到所有边都检测完为止，此时T是一棵树 时间复杂度：O(E*log(E)) 只和边有关，适合稀疏图
    • 最短路径
      • 概念
        • 无权图的最短路径可以用BFS得出
        • 有权图的最短路径指从v0到vi，边权值只和最小的路径
      • 算法
        • Dijkstra：有向图中一个源点到其余结点的最短路径
          • 构造3个辅助数组s[],dist[],path[] s[i]：记录已经找到最短路径的结点，置s[i]=1; dist[i]：记录源点到其他结点的当前最短路径长度，dist[i]=Lmin; path[i]：记录源点到结点i之间最短路径上的i的前驱结点，依次找前驱结点则可将该最短路径的连接线 求一个结点的最短路径的时间复杂度：O(V^2) 求所有结点的最短路径的时间复杂度：O(V^3)
        • Floyd：所有结点到所有结点的最短路径
          • 需要维护两个矩阵A和Path A记录当前两个任意顶点的最短路径长度，行号表示起始顶点，列号表示终止顶点 Path记录当前两顶点间最短路径上要经过的中间结点 时间复杂度O(V^3) 允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路
    • 拓扑排序
      • 对一个有向图构造拓扑序列的过程 如果此图全部顶点被输出，说明它是不存在回路的AOV网（有向无环图） 如果没有输出全部顶点，说明它存在回路 排序结果通常不唯一 时间复杂度O(V+E) 拓扑排序算法： 从AOV网中选一个入度为0的顶点输出，然后删去以此顶点为弧尾的弧。重复这个步骤直到输出图中全部顶点，或者找不到入度为0的点为止
    • 关键路径
      • 对AOE网拓扑排序； 求出各事件最早发生时间（从前往后求）：前提事件全部完成才开始，即选最大值； 求出各事件最迟发生时间（从后往前求）：选最小值； 求出各活动最早发生时间：该活动（边）的起点（弧尾）事件最早发生的时间； 求出各活动最迟发生时间：该活动的终点事件最迟发生时间与该活动所需时间之差； 比较活动最迟发生时间和最早发生时间，若相等，则为关键活动；
• 串
  • 由零个或多个字符组成的有限序列
  • 定长顺序表示
    • typedef struct { char ch[MAXLEN]; // 预定义串的最大长度为MAXLEN int lenth; }SSting；
  • 堆分配存储表示
    • typedef struct { char *ch; // 之后初始化按串长动态分配 int lenth; }HString；
  • 块链存储表示
  • 基本操作
  • 模式匹配
    • 主串中从头开始与子串匹配 若匹配失败，主串下一次匹配的位置需要回退到当前匹配的起始位置的下一位 同时，子串回退到第一个字符重新与主串开始下一轮匹配 缺点：费时费力 时间复杂度：O(nm)
  • 改进的模式匹配算法——KMP
    • 利用next数组记录下一次和主串对应位置比对的字符的下标 主串i不需要回溯，仅将子串向后滑动到一个合适的位置 时间复杂度O(m+n)
    • 部分匹配值：字符串前后缀相等时的最长的长度
    • 子串中所有元素的部分匹配值构成next数组
    • 匹配失败时，找到它前一个元素的部分匹配值，字串向后移动
    • 移动位数 = 已匹配的字符数 - 对应的部分匹配值 Move = (j-1) - next[j-1]
    • 改进：next数组右移一位，就直接找自己的部分匹配值 第一个元素右移后用-1填充；最后一个元素的部分匹配值没有下一个元素使用，可以直接舍去 Move = (j-1) - next[j] 即 j = j-Move = next[j] + 1
    • 优化：将next数组整体+1，得 j = next [j]
• 查找
  • 基本概念
    • 查找表
    • 静态、动态查找
      • 是否需要动态的插入或删除元素
    • 关键字
    • 平均查找长度
      • 有序用判定树可求出平均查找长度，即每个结点所在的层数*个数之和再除以总个数
      • 一次查找长度指需要比较的关键次数
      • 通常每个元素的查找概率相等P=1/n
  • 顺序查找
    • 又称线性查找，主要用于线性表查找
    • 无序线性表查找
      • 从线性表的一端开始，依次比较关键字，直到表尾 若符合条件则查找成功，返回查找元素的位置 查找失败需要遍历整个线性表 查找成功时：ASL = (n+1)/2 查找失败时：ASL = n+1 时间复杂度：O(n)
    • 有序线性表查找
      • 从有序线性表的一端开始，依次比较key 直到表中元素对应的关键字大于（小于）key则可判定查找失败 若符合条件则查找成功，返回查找元素的位置 查找失败不一定需要遍历整个线性表 查找成功时：ASL = n(n+1)/2/n = (n+1)/2 查找失败时：ASL = (n(n+1)/2+n)/(n+1) = n/2+n/(n+1) 时间复杂度：O(n)
  • 折半查找
    • 又称二分查找，仅适用于有序的顺序表 将Key与表中中间位置元素的关键字比较； 若相等，查找成功 若不等，则在前半部分或后半部分查找； 重复1-3，直到查找到该元素，或查找失败
  • 分块查找
    • 又称索引顺序查找 是顺序查找和折半查找的综合 将查找表分为b块； 块内元素无序，块间元素有序； 建立索引表，每个元素含有各块的最大关键字和各块的第一个元素的地址； 查找索引表，确定待查记录所在的块； 顺序查找块内元素；
  • B树(多路平衡查找树)
    • 定义
      • 树中每个结点至多有m颗子树，即至多有m-1个关键字
      • 若根结点不是终端结点，则至少有两颗子树
      • 除根结点以外的所有非叶结点至少含有⌈m/2⌉颗子树，即至少含有⌈m/2⌉-1个关键字
      • 左子树关键字均小于右子树关键字
      • 所有叶结点都出现在同一层上
    • B树的高度
      • B树中大部分操作所需的磁盘存取次数与B树的高度成正比
    • 查找
      • 在B树中找结点（在磁盘中进行）
      • 在结点中找关键字（在内存中进行）
    • 插入
      • 定位：关键字一定插入在最低层的某个非叶结点内
      • 插入：插入后关键字个数大于m-1时，需要分裂结点
    • 删除
      • 删除后若关键字小于⌈m/2⌉-1时，需要合并结点
  • B+树
    • 是应数据库所需而出现的一种B树的变形树
    • 叶结点包括了所有的关键字信息，即非叶结点的关键字也会出现在叶结点中
    • 相邻叶结点之间通过指针链接
    • 有指向关键字最小的叶结点的指针，可以支持顺序查找
  • 散列表
    • 可以根据关键字直接计算出元素的存储地址
    • 散列函数的构造方法
      • 直接定址法
      • 除留余数法
      • 数字分析法
      • 平方取中法
      • 折叠法
    • 处理冲突的方法
      • 开放定址法
        • 将产生冲突的Hash地址作为自变量，通过某种冲突解决函数得到一个新的空闲的Hash地址
        • 线性探测法
          • 冲突发生时，顺序查看表中的下一个单元 缺点：造成大量的元素在相邻的散列地址上聚集，大大降低查找效率
        • 平方探测法
          • 设冲突地址为d，则依次查询d±1²，±2²，±3²...±k²的地址是否有空闲，其中k <= m/2，散列表长度m必须是4k+3的素数。 可以避免堆积现象。 缺点：不能探测到散列表的所有单元，但至少能探测到一半。
        • 再散列法
          • 使用两个散列函数 第一个散列函数得到地址冲突时，用第二个散列函数计算地址增量 H₃ = (H₁(Key) + i*H₂(Key))％m
        • 伪随机序列法
      • 拉链法
        • Hash地址不直接指向元素，而指向所有可以得到该地址的关键字组成的线性链表 增删查操作就在链表中进行
    • 散列查找及性能分析
      • 查找过程： 根据散列函数计算Hash地址 检查散列地址位置有没有记录 如果没有，查找失败 如果有，则检查该记录是否等于关键字 如果等于关键字，查找成功 如果不等于，按冲突处理计算下一个地址，再执行该过程 性能分析： 平均查找长度依赖于散列表的填装因子α α = （表中记录数）/（散列表长度） α越大，散列表越满，越容易冲突
      • 查找成功时的平均查找长度
        • 根据表中元素的个数来计算
      • 查找失败时的平均查找长度
        • 根据散列函数（%p）的p来计算，范围是0~p-1
• 排序
  • 基本概念
    • 定义
      • 重新排列表中元素，使表中元素满足按关键字递增或递减 排序算法的稳定性：排序表中两个元素R₁和R₂，其对应关键字key₁=key₂，在排序前R₁在R₂前，排序后R₁依然在R₂前，称这个算法是稳定的
    • 时空复杂度
    • 稳定性
  • 内部排序
    • 排序期间元素全部存放在内存中的排序
    • 插入排序
      • 直接插入排序
        • 空间复杂度：O(1) 最好时间复杂度：O(n) 最坏时间复杂度：O(n²) 是稳定的算法 适用于顺序存储和链式存储的线性表
      • 折半插入排序
        • 对直接插入排序的优化 查找插入位置时使用折半查找 插入方法不变，后续元素向后移位 减少了比较元素的次数 时间复杂度：最好：O(nlog₂n)，最坏：O(n²) 空间复杂度：O(1) 是稳定的排序算法 仅用于顺序存储的线性表
      • 希尔排序
        • 又称缩小增量排序 由于对直接插入排序来说，当待排序表中的元素顺序排列时耗时最少 所以提出希尔排序算法 将排序表分割成若干形如L[i, i+d, i+2d,..., i+kd]的子表 先对子表分别进行直接插入排序 当整个表中的元素“基本有序时”，再对全体记录进行一次直接插入排序 时间复杂度：最坏O(n²)；平均、最好（未知） 空间复杂读：O(1) 不稳定 仅适用于顺序表排序
        • 主要考察增量间隔d
    • 交换排序
      • 冒泡排序
        • 从后往前（或从前往后）两两比较相邻的元素，若为逆序则交换 序列比较完为一趟冒泡，可将最小元素交换到第一个位置 除去已确定的最小元素，每一趟冒泡可将剩下元素的最小元素找出 最多需要n-1趟冒泡就能把所有元素排序 时间复杂度：O(n²) 空间复杂度：O(1) 稳定 适用于顺序表和链表
      • 快速排序
        • 是对冒泡排序的改进 先任选一个元素作为基准，通过一趟排序后排序表分为独立的两部分 一部分全部小于该元素，另一部分全部大于该元素 再分别递归的对这两部分进行排序 重复，直到每个部分只有一个元素或空为止 时间复杂度：最坏O(n²); 最好、平均O(nlog₂n); 空间复杂度：最坏O(n)；平均O(log₂n) 不稳定 适用于顺序表
    • 选择排序
      • 简单选择排序
        • 把排序表分为有序序列和无序序列，有序序列初始为空 每一趟从无序序列中选一个最小的元素，放到有序序列里 n-1趟后全部有序 时间复杂度：O(n²) 空间复杂度：O(1) 不稳定 时间复杂度与初始序列无关 适用于顺序表和链表
      • 堆排序
        • 时间复杂度：O(nlog₂n) 空间复杂度：O(1) 不稳定 适用于顺序表和链表
        • 堆：一种完全二叉树
          • 小顶堆：左孩子和右孩子都大于等于双亲结点
          • 大顶堆：左孩子和右孩子都小于等于双亲结点
        • 构造初始堆
        • 插入：向下调整堆
        • 删除：向上调整堆
        • 堆排序算法
    • 2路归并排序
      • 先将原序列分为只含有一个元素的子序列 {49},{38},{65},{97},{76},{13},{27} 按顺序两两组合并组内排序 {38 49},{65 97},{13 76},{27} 继续按顺序两两组合并组内排序 {38 49 65 97},{13 27 76} 重复直到将所有数据归并成一组 {13 27 38 49 65 76 97}
      • 需要记住算法
    • 基数排序
      • 若基数为r，需要r个辅助队列，如10进制数序列基数为10，则关键字的每一位的取值范围在0~9之间，分别对应10个队列
      • 从最低（高）位开始，每一趟将关键字按该位的大小进行排序，通过分配与合并操作
  • 排序算法的比较
    • 
  • 外部排序
    • 排序期间元素无法全部存放在内存中的排序
    • 一般采用多路归并排序
    • 从外存中读入文件数据段，在内存中排序后，再置换出外存
    • 主要耗时在I/O上，所以需要增大归并路数来减少I/O次数
    • 败者树
      • 是一颗完全二叉树
      • 引入目的：使内部归并不受归并路数m的增大的影响
      • 内部结点用来记录左右子树的"失败者"段号
    • 最佳归并树
      • 让记录少的初始归并段最先归并，类似于哈夫曼树
      • 总的I/O次数 = 2*WPL（带权路径长度）
      • 是一颗只有度为0或m的的结点的严格m叉树
      • 初始段不足以构成一颗严格m叉树时，需要添加长度为0的虚段
      • 确定虚段个数
        • 设度为0的结点有N0个
        • 若(N0-1)%(m-1) = 0，不需要添加
        • 若(N0-1)%(m-1) = u，需要添加 m-u-1 个
  • 应用