1.1 基本概念

• 数据元素
  • 是数据的基本单位
  • 由若干个数据项组成
• 数据项
  • 初等项
  • 组合项
  • 关键字：能够唯一标识一个数据元素的数据项（例如学号，身份证号）
• 数据对象
  • 性质相同的数据元素的集合（整张表）

1.2 数据结构的分类

• 逻辑结构
  • 线性结构
  • 非线性结构
• 存储结构（物理结构）
  • 顺序存储
  • 链接存储
  • 索引存储
  • 散列存储
• 运算

1.4 算法和算法分析

• 算法特性
  • 输入
  • 输出
  • 确定性
  • 有穷性
  • 可行性
• 算法要求（好的算法）
  • 正确性
  • 可读性
  • 健壮性
  • 高效率（时间效率和存储占用量低）
• 时间复杂度
  • 最坏情况下的时间复杂度

第2章 向量、栈和队列

2.1 线性表

• 线性表
  • 顺序存储
    • 向量/数组
  • 链式存储
    • 链表
• 各个数据元素不一定是同种数据类型
  • 若相同，就是向量

2.4 递归

• 整数分划问题
  • 问题
    • 把一个正整数 n 表示成形如 n=n1+n2+…+nk 的一系列正整数的和，称为 n 的一个分划。其中，ni≥1, i=1, 2, …, k,k≥1，且满足条件n1≥n2≥…≥nk≥1
    • 形如 n=n1+n2+…+nk 的不同表达式的个数称为整数 n 的分划数。记为 P(n)
    • 求：给定任意正整数 n，求其分划数 P(n)
  • 题解
    • P(n)=Q(n,n)
    • 
    • Q(n,m)表示：满足最大加数不大于 m 的 n 的分划数
    • 前两行很好理解，略；
    • 第三行是说当m与n相等，则有两种情况：
      • 最大加数不大于 n-1，即Q(n,n-1)
      • 最大加数刚好等于n（不可能大于n），只有一种可能
    • 第四行是当n大于m，同样有两种情况：
      • 最大加数不大于m-1，即Q(n,m-1)
      • 最大加数刚好等于m，即Q(n-m,m)，推导如下图
        • 
  • 变式
    • 要求分划中的整数互异
      • 
      • 另外注意在m=1的处理上，与原题不同
        • 原题用不超过1的正整数进行分划，因为不用考虑重复问题，所以任意大于等于1的数都有且只有一种分划
        • 但若要考虑不能重复，则用不超过1的正整数只能对1进行分划
    • 将n分划为k份
      • 
    • 将i划分成j个奇数或j个偶数
      • 
• 递归方程求解
  • 迭代法
    • 思想
      • 不断用递推方程的右部替代左部
      • 每次替换，随着 n 的降低在和式中多出一项
      • 直到出现初值停止迭代
      • 将初值代入并对和式求和
    • 调和级数
      • 
    • 换元迭代
      • 递推式中存在n/2的，可以考虑令n=2^k
  • 生成函数求解
  • 特征方程求解
  • 递归树方法
    • 递归树是迭代计算的模型，其生成过程与迭代过程一致
    • 递归树上所有项恰好是迭代之后产生和式中的项
    • 对递归树上的项求和就是迭代后方程的解
  • 主定理
    • 
• 递归空间复杂度
  • 与递归深度有关

2.5 队列与链表

• 队列特征
  • 是一种操作受限的线性表
  • 只允许插入的一端称为队尾，只允许删除的一端称为队头
  • 先进先出表（FIFO）
• 队列指针
  • 队头指针front，指向队头元素
  • 队尾指针rear，指向下一个入队元素的存储位置
• 循环队列
  • 为避免浪费存储空间
  • 无论插入或删除，一旦指针rear和front增1越出了所分配的队列空间，就让其指向队列空间的起始位置
  • 规定最多只能有MaxSize－1个元素，当队列空间中只剩下一个空单元时，队列满。
    • 若front=rear，则队空
    • 若front=(rear+1)%MaxSize，则队满
• 链表形式实现队列
  • 

第4章 串与KMP

• 串
  • memcpy(str1,str2,length)
    • 将字符串str2的前length位复制到数组str1中
    • 注意是否需要让length为字符串长度+1，以复制末尾的`'\0'
    • 效率远高于for循环赋值
• KMP匹配算法
  • next数组实现思路

  next[0]=-1;
  // 计算next[i] i>0
  k(i)=max{k=i-1,i-2,...,0,-1|满足p[0:k-1]=p[i-k:i-1]} 
  //上式即p[0:i-1]的最左最右、相同的、最长的、真子串的长度
  
  if (p[k(i)]≠p[i]) 
      next[i]=k(i);
  else 
      next[i]=next[k(i)]

  • next数组计算示例
    • 
    • find过程（p为小串，t为大串）
      • 当在p[i]处发生匹配失败
        • 若next[i]≥0，将p右移i-next[i]位，再从p[next[i]]开始匹配
        • 若next[i]=-1，将p右移i+1位，再从p[0]开始匹配

第5章 排序

5.1 基本概念

• 排序码
  • 是结点中的一个或多个字段，其值作为排序运算中的依据
  • 可以是关键字或非关键字。不是关键字时，可能有多个结点的排序码相同，这时排序结果不唯一
  • 例如{"Mike, 90","John, 90","Tom, 80"}中，姓名是关键字，分数是排序码，排序码存在相同
• 记录和文件
  • 记录：排序的结点，每个记录有一个排序码
  • 文件：一系列结点构成的线性表
• 排序算法的稳定性
  • 具有相同排序码的记录在排序前后的相对次序一定能保持不变
  • 对于上例，{"Tom, 80","Mike, 90","John, 90"} Mike和John的相对次序与排序前相同，因此稳定

5.2 插入排序

直接插入排序

• 思路：先将第一个记录看作是一个有序的记录序列，然后从第二个记录开始，依次将未排序的记录插入到这个有序的记录序列中去，直到整个文件中的全部记录排序完毕
• 
• 比较次数
  • 最好情况下，第i趟插入发生在A[i]处，这时总的比较次数为n-1次，$O(n)$
  • 最坏情况下，每一趟插入发生在A[0]处，这时总的比较次数为为n(n-1)/2，$O(n^2)$
  • 平均情况，第i趟需要i/2次比较，因而总的比较次数为1/2+2/2+...+(n-1)/2=n(n-1)/4，$O(n^2)$
• 移动次数
  • 没有额外的移动次数
  • 因为一边比较，一边就在移动
• 稳定性：稳定

折半插入排序

• 思路：在已经排序的A[0 : i-1]里采用折半查找的方式为A[i]寻找插入位置
  • 注意这里折半查找是找插入的位置，通俗来讲就是找到一个位置前面的元素比待插入的元素小，后面比它大；这与直接用折半查找去找一个元素的情况不完全一样，后者只要找到待查找元素则结束，而前者查找次数是固定的，仅与记录的个数有关
  • 前提是文件记录按顺序存储
  • 用折半查找的方式弥补直接插入排序的缺点
• 比较次数：$O(n\log_{2}{n})$
• 移动次数
  • 最好情况，已排好，$O(n)$
  • 最坏情况，reverse，$O(n^2)$
  • 平均情况，$O(n^2)$
• 稳定性：稳定

Shell排序

• 思路：把待排序的n个记录分成si个组，距离为si的记录为一个组，对每一组进行排序。si逐渐变小
• 
• 
• 
• 时间复杂度 $O(n^{1.3})$
• 稳定性：不稳定

5.3 选择排序

直接选择排序

• 思路：每次从A[i : n-1]中选出排序码最小的记录A[k]，放在已排序的记录A[0 : i-1]的后面（交换A[i]与A[k]）
• 当n很大，且只需得到前k个结果，可以得到有意义的中间结果
• 比较次数
  • 最好情况，已排好，$O(n^2)$
  • 平均情况，$O(n^2)$
  • 最坏情况，reverse，$O(n^2)$
• 稳定性：不稳定

树形选择排序

• 思路：把待排序的n个记录的排序码两两进行比较，取出┌n/2 ┐个较小的排序码作为作为结果保存下来，这┌n/2┐个排序码进一步两两进行比较，重复上述过程直到得到最小的排序码
• 
• 
• 比较次数：$O(n\log_{2}{n})$
• 稳定性：稳定

5.4 交换排序

冒泡排序

• 思路：对A[0:n-1]进行一趟冒泡：for j=0, …, n-2：若A[j]>A[j+1]则两者交换，不断冒泡，直到不再出现交换
• 比较次数
  • 最好情况，已排好，$O(n)$
  • 平均情况，$O(n^2)$
  • 最坏情况，reverse，$O(n^2)$
• 移动次数
  • 最好情况，已排好，0
  • 平均情况，$O(n^2)$
  • 最坏情况，reverse，$O(n^2)$
• 稳定性：稳定

快速排序

• 思路：从待排序记录中任选一个记录，以这个记录的排序码作为中心值，将其它记录划分为两个部分，第一部分包含所有排序码小于等于中心值的记录，第二部分包含所有排序码大于中心值的记录。对这两个部分采用同样的方法进行处理，直到每个部分为空或只含一个记录为止
• 
• 
• 比较次数
  • 最好情况（每次拆分均衡）：最好情况下每次选取的中心值恰好将其它记录分成大小相等（或相差一个记录）的两个部分，$O(n\log_{2}{n})$
  • 最坏情况：待排序文件已经排好序，所选中心值总是最大或最小的排序码，$O(n^2)$
  • 平均情况：$O(n\log_{2}{n})$
• 稳定性：不稳定

5.5 分配排序

基数排序

• 思路：先按排序码最低位的值从小到大将待排序的记录分配到r个队列中，队列中的记录按分配进来的先后排放，然后依次收集这些记录。再将收集起来的序列按排序码次低位进行分配和收集，如此反复，直到按排序码最高位进行分配后，收集起来的序列就是排序后的有序序列
• 分类
  • 最低位优先：从低位往高位进行分配和收集（常用）
  • 最高位优先：从高位往低位进行分配和收集
• 优化
  • 采用链式存储结构，将移动记录改为修改指针，则可克服时间和空间消耗问题
• 时间复杂度
  • 符号的含义：r（每一位排序码的可能取值个数，例如十进制数就为10），n（待排序元素个数），d（排序码位数）
  • 以链表实现：每执行一次分配和收集，队列初始化需要$O(r)$的时间，分配工作需要$O(n)$的时间，收集工作需要$O(r)$的时间，即每趟需要$O(n+2r)$的时间，总共执行d趟，共需$O(d(n+2r))$的时间

5.6 归并排序

• 思路：将两个或者多个已有序的序列，合并成一个有序序列
• 
• 设计代码的自顶向下逻辑
  • 待排序的数组为ForSort A[]，长度为n
  • 两个有序子序列归并为一个有序序列：TwoWayMerge(ForSort Dst[],ForSort Src[],int s,int e1,int e2)
  • 一趟归并 ：每两个相邻有序子序列归并OnePassMerge(ForSort Dst[],ForSort Src[],int Len,int n)
  • 实现归并排序：MergeSort(ForSort A[], int n)
• 时间复杂度
  • $O(n\log_{2}{n})$
  • 可以并行

第6章 查找

6.1 基本概念

• 衡量一个查找算法好坏的依据主要是查找过程中需要执行的平均比较次数，或称为平均查找长度
• 假设：结点是等长的，查找是基于关键码的，关键码都是整数

6.2 顺序查找

• 思路：逐个将每个结点的关键码和待查的关键码值进行比较，直到找出相等的结点或者找遍了所有的结点
• 要求：被查找的线性表可以是顺序存储或链接存储，对结点没有排序要求
• 时间复杂度
  • 最好情况，$O(1)$
  • 平均情况，$O(n)$
  • 最坏情况，$O(n)$
• 优化
  • 将查找概率大的数据元素放在线性表的前面
    • 降低查找成功的平均查找长度
  • 先将关键码排序再查找
    • 降低查找失败的平均查找长度

6.3 折半查找

• 思路：折半查找，首先找到表的中间结点，将其关键码与给定的要查找的值进行比较，若相等，则查找成功；若大于要查找的值，则继续在表的前半部分折半查找，否则继续在表的后半部分进行折半查找
• 要求：顺序存储且结点排序
• 时间复杂度
  • 最好情况，$O(1)$
  • 平均情况，$O(\log_{2}{n})$
  • 最坏情况，$O(\log_{2}{n})$

6.4 分块查找

• 思路：分块查找将一个大的线性表划分成若干块，块内不排序，块之间排序。建立一个索引表，把每块中的最大关键码值作为索引表的关键码值，且非递减排序。
  • 查找某结点时，先在索引表中顺序查找或者折半查找，找到该结点对应的块，然后在块内顺序查找。
• 适用于：既要有较快的查找速度，又要满足元素动态变化的要求
  • 当增加或减少结点以及结点的关键码改变时，只需要调整结点所在的块即可
  • 当结点变化频繁，导致块与块之间结点数相差很大时，查找效率会下降
• 时间复杂度
  • 最优情况，$O(n^{0.5})$
    • 把n个节点分为大小相等的$n^{0.5}$块，每块有$n^{0.5}$个结点

6.5 散列查找

6.5.1 概述

• 思路
  • 散列函数：将分散在一个大区间的关键码值映射到一个较小的区间，用映射后的值作为访问结点的下标
  • 散列表或哈希表（Hash Table）：与散列函数相关联的长度为n的表，用来存放结点的数据或数据的引用
• 问题
  • 散列函数经常是多对一的，导致冲突（碰撞），具有相同散列值的关键码值称为同义词。两个结点不能占据同一个位置，需要一种冲突解决策略。
• 负载因子$α＝填入表中的结点数/散列表长度$

6.5.2 散列函数

• 要求
  • 有效减少冲突
  • 很高的执行效率
• 除留余数法
  • 思路：利用余数运算将整数型的关键码值映射到0～n-1的范围内。选择一个适当的正整数p，用关键码值去除以p，所得余数作为该关键码的散列值
  • 除留余数法的关键是p的选取：一般取p为小于等于n的最大素数
• 数字分析法
  • 思路：当关键码的位数很多时，可以通过对关键码的各位进行分析，丢掉分布不均匀的位，留下分布均匀的位作为散列值
  • 只适合静态的关键码值集合
• 平方取中法
  • 思路：计算关键码值的平方，从平方的中间位置取连续若干位，将这些位构成的数作为散列值
• 随机乘数法
  • 思路：使用一个随机实数f(0≤f<1)，$f\times key的小数部分$与散列表长度n相乘，将乘积的整数部分作为key的散列值
  • 
• 折叠法
  • 思路：将关键码值分成若干段，其中至少有一段的长度等于散列表长度值的位数，把这些多段数相加，并舍弃可能产生的进位，所得整数作为散列值
  • 适用于：关键码值的位数比散列表长度值的位数多出很多时
    • 例，关键码key=852422241，散列表长度为4000
    • 

6.5.3 冲突的处理

• 两个大的思路
  • 开放地址法：将引起冲突的新数据项存放在表中另外的位置
  • 链表地址法：为每个散列值单独建立一个表以存放具有相同散列值的所有数据项
• 开放地址法
  • 思路：散列表的每个表项有一个表示该表项是否被占用的标志，当试图加入新的数据项到散列表中时，首先判断散列值指定的表项是否被占用，如果被占用，则依据一定的规则在表中寻找其它空闲的表项
  • 评价：表长是固定的，如果增加元素可能溢出
  • 线性探测法
    • 思路：当冲突发生时，顺序地探测下一个表项是否空闲。若Hash(key)=d，而第d表项已被占用，则依次探测d+1,d+2,...,n-1,0,1,...,d-1
    • 缺点：可能产生堆积
  • 双散列函数探测法
    • 思路：使用2个散列函数Hash1和Hash2，其中Hash1以关键码值为自变量，产生一个0～n-1之间的数。Hash1用来产生基本的散列值，当发生冲突时，利用Hash2计算探测序列。当Hash1(key)=d时发生冲突，则再计算k=Hash2(key) ，得到探测序列为(d+k)%n, (d+2k)%n, (d+3k)%n, ...
    • 优点：双散列函数可以使探测序列跳跃地分散到整个存储区域里，从而有助于减少“堆积”的产生
    • 缺点：不能随便删除散列表中的表项目，因为删除一个表项可能使得同义词序列断开
• 链表地址法
  • 思路：为散列表的每个表项建立一个单链表，用于链接同义词子表，每个表项需增加一个指针域
  • 评价：表项是动态分配的，不会溢出；缺点是要为每个表项设立指针域
  • 独立链表地址法
    • 思路：在散列表的基本存储区域外开辟一个新的区域用于存储同义词子表
    • 评价：是查找效率最好的解决冲突的方法，是解决冲突的首选方法
    • 
  • 公共链表地址法
    • 思路：将同义词子表存储在散列表所在基本存储区域里。在基本存储区域探测空闲表项，找到后将其链接到同义词子表中
    • 

第7章 树和二叉树

7.1 树的概念

• 度：一个结点的儿子个数
• 叶结点：没有儿子的结点
• 分支结点：有儿子的结点
• 祖先：从根r到结点p的路径上的所有结点都是p的祖先，其中除p之外是p的真祖先
• 层数：根结点层数为1

7.2 二叉树

7.2.1 二叉树的概念

• 二叉树：每个结点至多有2个子女，而且有左、右之分
• 满二叉树
  • 
• 完全二叉树
  • 

7.2.2 二叉树的性质

• 性质1: 任何一棵含有n(n>0)个结点的二叉树恰有n-1条边
• 性质2：深度为h的二叉树至多有$2^h-1$个结点(h>=0)
  • 二叉树的第i层最多有$2^{i-1}$个结点
• 性质3：设二叉树的结点数为n，深度为h，则$log2(n+1)≤h≤n$
• 性质4：如果一棵有n个结点的完全二叉树的结点，按层次序编号(每层从左至右)，则对任意结点i(1≤i≤n)：
  • 若2i>n，则结点i无左子女；否则，结点2i为结点i的左子女
  • 若2i+1>n，则结点i无右子女；否则，结点2i+1为结点i的右子女
  • 若i=1，则结点i为二叉树的根结点；若i>1，则结点$[i/2]$为其父母结点
• 性质5：如果一颗二叉树每个分支结点都两个儿子（不一定是满二叉树），设叶结点个数为n，则分支结点的个数为n-1
  • 证明：设分支结点的个数为x，则该二叉树有2x条边，结点总数为n+x。因为二叉树的边数为其结点数减1，所以2x=n+x-1，所以x=n-1
• 性质6：设二叉树中叶结点个数为n0, 只有一个儿子的分支结点个数为n1, 有两个儿子的分支结点个数为n2，边的数量为e。则：
  • e=2n2+n1
  • e=(n0+n1+n2)-1 （由性质1）
  • n2=n0-1

7.2.3 二叉树的存储方式

• 顺序存储
  • 完全二叉树
    • 由性质4
  • 非完全二叉树
    • 补设一些虚结点，使它成为一棵完全二叉树
    • 虚结点需要对应存储位置，并设立虚结点标志
• 链接存储
  • LeftChild-RighChild表示法（二指针式）
    • 
  • 三重链表示(三指针式)
    • 

7.2.4 树与二叉树的相互转换

• 方法
  • 树的根与转换二叉树的根对应
  • 树中结点x的第一个儿子与转换二叉树中结点x的左儿子对应
  • 树中结点x的下一个兄弟与转换二叉树中结点x的右儿子对应
  • 

7.3 二叉树、树、树林的遍历

7.3.1 树（树林）的遍历

• 先根遍历
  • 访问根
  • 依次先根遍历根的各个子树
• 后根遍历
  • 依次后根遍历根的各个子树，
  • 访问根
• 层序遍历
  • 依次（从上到下）访问每层（从左到右）

7.3.2 二叉树的遍历

• 前序遍历
  • 访问根结点
  • 前序遍历左子树
  • 前序遍历右子树
  • 
• 中序遍历
  • 中序遍历左子树
  • 访问根结点
  • 中序遍历右子树
  • 
• 后序遍历
  • 后序遍历左子树
  • 后序遍历右子树
  • 访问根结点
  • 
• 层序遍历
  • 从左到右访问第1层
  • 从左到右访问第2层
  • ……
  • 
• 中序+任意序 => 唯一二叉树

7.4 二叉树的遍历算法

7.4.1 非递归（使用栈）的遍历算法

• 效率比递归算法高，但时间复杂度可认为和递归算法相同
• 前序遍历
  • 思路：从二叉树的根结点开始，将根结点设为当前结点p，执行以下操作：
    1. 边遍历边打印，并存入栈中（一开始当前结点p为根结点）→先打印当前结点p的数据→再将当前结点p入栈→若左孩子存在，将左孩子设为当前结点→重复执行此操作，直至到达二叉树左子树最左下角
    2. 栈顶元素出栈，将栈顶元素设为当前结点p→若当前结点p的右孩子存在，将右孩子设为当前结点p（进入右子树）→回到步骤1，重复执行 1、2，直至栈空
• 中序遍历
  • 思路：从二叉树的根结点开始，将根结点设为当前结点p，执行以下操作：
    1. 当前结点p入栈（一开始当前结点p为根结点）→若当前结点p存在左孩子→将左孩子设为当前结点p→重复此操作，直至到达二叉树左子树最左下角
    2. 将栈顶元素出栈，将出栈元素设为当前结点p→打印该结点p的数据
    3. 若当前结点p存在右孩子，则将右孩子设为当前结点p→回到步骤1，重复执行 1、2、3，直至栈空
• 后序遍历

7.4.2 线索化二叉树

• 思路：用空链域存放结点在某种遍历方式下的前趋或后继指针
  • 对任一结点，用空左链域存放它的前驱的指针，而用空右链存放它的后继的指针
  • 若某链域不空，则不存储这种前驱与后继指针
• 优点：既保持了原树的结构，又利用空链表示了部分前驱与后继关系

第8章 树形结构的应用

8.1 二叉排序树

• 二叉排序树（检索树）：二叉树中的每个结点的关键码都比其左子树的任何结点的关键码大，比其右子树的任何结点的关键码小
• 中序遍历：- 得到有序序列
• 查找
  • 从根出发沿着左子树或右子树往下搜索，若x小于根结点，则沿着左子树搜索，若x大于根结点，则沿着右子树搜索，重复此过程，直到遇到值为x的结点，或遇到空子树
  • 
• 插入
  • 若二叉排序树是空树，则新结点为二叉排序树的根结点
  • 否则比较插入结点和根结点，若小于根结点，则插入左子树，否则插入到右子树
  • 
• 删除
  • 无子节点
    • 即叶子节点，直接删除
  • 有一个子节点
    • 让其儿子代替该结点的位置
  • 有两个子节点
    • 方法1：用结点A的数据替换结点P的数据，并删除结点A（高度不会增加，最多减少1）
    • 方法2：用结点B的数据替换结点P的数据，并删除结点B（高度不会增加，最多减少1）
    • 方法3：将P的右子树改作为A的右子树，若P存在父结点，则将其父结点指向P的指针改为指向L，否则L作为新的根（可能导致高度增加）
    • 方法4：将P的左子树改作为B的左子树，若P存在父结点，则将其父结点指向P的指针改为指向R，否则R作为新的根（可能导致高度增加）
    • 
• 比较次数
  • 对于成功的查找，比较次数为目标结点所在的层数
  • 对于失败的查找，比较次数为对应的外部结点所在层数减1
• 内部路径和外部路径长度及其关系
  • 
  • 
• 等概率查找最佳二叉排序树
  • 定义：在等概率假设下，综合考虑成功/失败的情况的平均代价
  • 特点：度小于2的结点在最下面两层（不一定是完全二叉树）
  • 构造
    • 将关键码排序
    • 以中间结点为根，将左半部分构造最佳排序二叉树作为根的左子树，将右半部分构造最佳排序二叉树作为根的右子树。

8.2 平衡的二叉排序树

• 平衡二叉树
  • 定义：任意结点的两棵子树的高度差不大于1
  • 插入新节点后，旋转以保持平衡 TODO

8.3 Huffman最优树

• 应用
  • 判定树
  • 数据压缩
    • 为避免二义性，要求不等长编码是前缀码
    • 即任一字符的编码不是另一字符编码的前缀
• 定义：给定n个值，那么，可以构造出任意多棵具有n个叶结点且叶权分别为这n个给定值的二叉树，而其中加权路径长最小的那棵为Huffman最优树
• 构建Huffman最优树
  • 
• Huffman编码
  • 对一棵具有n个叶子的哈夫曼树，若对树中的每个左分支赋予0，右分支赋予1，则从根到每个叶子的通路上，各分支的赋值分别构成一个二进制串，这种二进制串就称为哈夫曼码
  • 是最短前缀码

8.4 堆排序

• 堆
  • 完全二叉树中，若任意结点的值大于它的儿子结点的值，则该完全二叉树的层序遍历序列是一个大根堆
  • 一个堆对应一棵完全二叉树
• 堆插入
  • 
• 堆调整
  • 从最后一个分支节点开始向上依次调整
  • 
  • 
• 堆中删除首结点
  • 将首节点与最后一个节点交换并删除，然后对首节点进行堆调整
  • 
• 堆排序
  • 建堆（调整法或插入法）
  • 反复删除首结点
  • 
  • 时间复杂度
    • 初始建堆 $O(n)$
    • 每次删除堆的根时间不超过 $O(\log n)$
    • 总时间不超过 $O(n\log n)$
    • 不受数据初始状态影响

第9章 图

9.1 基本概念

• 图G=(V, E)由非空有穷顶点集V和V上的顶点对构成的边集E组成
  • E中任意顶点对是无序的，则G是无向图 (v1,v2)
  • E中任意顶点对是有序的，则G是有向图 <v1,v2> v1指向v2
• 子图
  • 若G1=(V1,E1),G2=(V2,E2)是两个图，且V2⊆V1，E2 ⊆ E1，则称G2是G1的子图。
• 加权图
  • 图的每条边对应一个权值
• 相关联
  • 设G=(V, E)是无向图，若边(V1,V2)∈E，则称V1和V2是相邻顶点，边(V1,V2)是与顶点V1和V2相关联的边
  • 设G =(V, E)是有向图，若边<V1,V2>∈E，则称顶点V1邻接到顶点V2，顶点V2邻接于顶点V1，边<V1,V2>是与顶点V1和V2相关联的边
• 度
  • 有向图中出度为0的顶点称为终端顶点（叶子）
  • 设图G有t条边，则所有顶点的度数之和为2t
• 简单图
  • 简单无向图
    • 任意两个顶点之间最多一条边，且不含自回路（顶点到其自身的边，即Reset）
    • n个顶点，最大边数为n(n-1)/2
  • 简单有向图
    • 任意两个顶点之间最多两条方向相反的边，且不含自回路
    • n个顶点，最大边数为n(n-1)
• 完全图（简单图边数最大的情况）
  • 无向完全图
    • 任意两个顶点间都有一条边的简单无向图
    • n个顶点，有n(n-1)/2条边
  • 有向完全图
    • 任意两个顶点间都有方向相反的两条边的简单有向图
    • 有n个顶点，有n(n-1)条边
• 路径
  • 在有向或无向图中，无重复边且相邻边前后衔接的边序列称为一条路径
  • 路径的长度：序列中的边数
  • 简单路径
    • 除了首尾可以相同外，路径上所有顶点各不相同
    • 回路或环：首尾相同的简单路径
• 连通图/强连通图
  • 连通图->无向图
    • 任意两个顶点Vi和Vj之间有路径
  • 强连通图->有向图
    • 任意两个顶点Vi和Vj，存在Vi到Vj的路径，以及Vj到Vi的路径
• 连通分量/强连通分量
  • 连通分量->无向图
    • 极大连通子图
    • 何谓极大？再添加任意一个点或边，都不满足连通或子图的条件
  • 强连通分量->有向图
    • 极大强连通子图
• 生成树->无向图
  • 含有全部n个顶点和n-1条边的连通图
    • 即含有全部n个顶点的极小连通子图
  • 生成树林
    • 每个连通分量都有一棵生成树，构成树林

9.2 存储表示

• 相邻矩阵（邻接矩阵）
  • 一个顺序表存储n个顶点
  • 一个n*n的矩阵存储边
    • 有向图，需要$n^2$个单元
    • 无向图，只需存上三角或下三角，需n(n-1)/2个单元
  • 缺点
    • 不便于增加和删除顶点
    • 浪费空间：存稀疏图（点很多而边很少）时有大量无效元素
    • 浪费时间：统计稀疏图中一共有多少条边
• 邻接表：顶点表和边表
  • 无向图
    • 边表
      • 对于每个顶点，将与顶点相关联的边组织成一个链表
    • 顶点表
      • 每个表项对应一个顶点，保存与该顶点相关联的边表的表头指针
    • 
  • 有向图
    • 出边表
      • 将与顶点相关联的出边组织成链表，作为与该顶点相关联的边表
    • 入边表
    • 
  • 加权图(网)
    • 在边表的每个结点加上一个表示权的字段
  • 特点
    • 邻接表存储具有n个顶点、m条边的图
    • 顶点表：n个表项
    • 边表
      • 无向图的所有边表共有2m个表项，每条边对应2个边表结点
      • 有向图的每个边表有m个表项
• 邻接多重表：顶点表和边表（每条边只对应一个边表结点）
  • 顶点表
    • 包含data域（保存顶点信息）和edge域（指向与该顶点相关联的第一条边）
    • 对有向图，含有两个edge域
      • edge1：指向以该顶点为始点的边表的第一条边
      • edge2：指向以该顶点为终点的边表的第一条边
  • 边表
    • 对于有向图
      • ilink指向以Vi为始点的下一条边
      • jlink指向以Vj为终点的下一条边
  • 
  • 

9.3 遍历

• 宽度优先遍历（BFS）
  • 先访问出发顶点（第1层），然后访问与出发顶点相邻的所有顶点（第2层），接下来访问与第2层顶点相邻的所有没被访问的顶点（第3层），依此类推
  • 用队列实现
  • 算法实现
    • 1. 选一个未被访问过的顶点加入队列尾部
    • 2. while（队列不空） 删除队列头结点v；若v未被访问（不在生成树里，在栈里不算），则访问v，且将与v相邻的所有未访问过的顶点（未被加入生成树的结点）依次加入队列尾部
    • 3. 如果还有顶点没被访问过，则转1
  • 宽度优先生成树
    • 将每次前进路过的结点和边记录下来，得到以出发点为根的树
    • 宽度优先生成树林：如果必须从多个结点出发才能遍历所有结点，则得到多棵生成树
• 深度优先遍历（DFS）
  • 从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到
  • 用栈实现
  • 算法实现
    • 1. 选一个未被访问过的顶点加入栈
    • 2. while（栈不空） 栈顶结点v出栈；若v未被访问，则访问v，且将与v相邻的所有未访问过的顶点依次入栈
    • 3. 如果还有顶点没被访问过，则转1。
  • 深度优先生成树（同上）

9.4 最小生成树

• Prim算法
  • 算法实现
    • 1. U={u0}, T=
    • 2. while(U!=V) (u*,w*) =min{weight(u,w)|u∈U,w∈V-U} T = T + {(u*,w*)} U = U + {w*}
  • 时间复杂度$O(n^2)$ n为顶点个数
• Kruskal算法
  • 算法实现
    • 1. T=Ф（顶点分成子集，每个顶点一个子集）
    • 2. while(T含有少于n-1条边且E不空) { 从E中挑选一条权最小的边(u*,w*); 从E中删去边(u*,w*); 若(u*,w*)加入T后不形成回路，（若u*,w*来自两个不同子集） 则(u*,w*)加入T;（并将这两个子集合并） }

9.5 单源最短路径

• 定义：给定单个源点s，求s到其它各顶点的最短路径
• Dijkstra算法
  • 算法实现
    • 1. A={v0}; B=V\A；对于每个顶点v, 若adj(v0,v)=∞,则v.length=∞,v.pre=-1，否则v.length=adj(v0,v),v.pre=v0；
    • 2. 从B中选择length值最小的顶点vm, 从B中删除vm， A中加入vm；
    • 3. 对于B中的每个顶点v, 若v.length>vm.length+<vm,v>的权, 则v.length＝vm.length+<vm,v>的权,且v.pre=vm；
    • 4. 重复2和3，直到B空或B中每个顶点的length值为∞。
  • 时间复杂度$O(n^2)$

9.6 每对顶点间最短路径

• 定义：计算每对顶点之间的最短路径
  • 以网络中每个顶点为源点，分别调用Dijkstra()
    • 时间复杂性为$O(n^3)$
• 结果保存：D和path矩阵
  • D[i][j] 为从vi到vj的最短路径长度
  • path[i][j] 为从vi到vj的最短路径上，vj前面的那个顶点
• Floyd算法
  • D(k)[i][j]=允许v0,v1,...,vk为中间顶点，从vi到vj的最短路径长度
  • path(k)[i][j]表示允许以v0,v1,...,vk作为中间顶点，从vi到vj的最短路径上vj前面的那个顶点
  • 算法实现
    • 1. 初始化D(-1)[i][j]，如果没有直接相连的两点那么默认为一个很大的值，而自己的长度为0
    • 2. 从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。
      • 试探方法：遍历图中每一个点，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改
      • 
    • 3. 重复2直到所有点插入完成

9.7 有向无回路图（DAG）

• DAG
  • AOV（顶点表示活动，Vertex）
    • 活动v1是活动v2的前提，当且仅当AOV网中v1是v2的前驱
    • 课程关系
  • AOE（边表示活动，Edge）
    • 顶点表示活动的开始和结束（事件），边上的权表示完成活动所需的时间长度
    • 活动e1是活动e2的前提，当且仅当AOE网中e1的终点是e2的起点
      • 只有当顶点入边上的活动全部结束后，顶点事件才可以发生
      • 只有当顶点事件发生后，顶点出边上的活动才可以启动
    • 完成工程的最短时间
• AOV拓扑排序
  • 要求：若<vi,vj>是G的边，则序列中vi位于vj之前
  • 算法实现
    • 1. 从图中选择一个入度为0的顶点并输出
    • 2. 从图中删除此顶点及其所有的出边
    • 3. 重复1和2，直到输出图的全部顶点。如果不能输出图的全部顶点，说明图中有回路
  • 拓扑序列通常不唯一
  • DAG图一定存在拓扑序列，不存在拓扑序列的有向图一定存在回路
• AOE关键路径
  • 概念
    • 入度为0的顶点，称为源点，代表工程的始点
    • 出度为0的顶点，称为汇点，代表工程的终点
    • 从源点到汇点的最长路径称为关键路径
    • 完成工程的最短时间：从源点到汇点的最长路径长度，即关键路径长度
  • 最早发生时间
    • 事件vj的最早发生时间e(j)：从源点到vj的最长路径长
  • 最晚发生时间
    • 在不耽误工程进度的前提下，事件vi的最晚发生时间l(i)：关键路径长减去从vi到汇点的最长路径长
  • 关键事件
    • 最早和最晚发生时间相等的事件
  • 关键活动
    • 活动ai=<vj, vk>的最早启动时间ae(i)=e(j)，最晚启动时间al(i)=l(k)-t(j,k)
    • 最早和最晚启动时间相等的活动
    • 算法实现
      • 对顶点进行拓扑排序
      • 按顶点的拓扑次序从前往后，计算每个顶点vi的最早发生时间e(i)
      • 按顶点的拓扑次序从后往前，计算每个顶点vk的最晚发生时间l(k)
      • 若l(k)-t(j,k)=e(j)，则<vj, vk>是关键活动