哈尔滨工业大学数据结构2018年秋期末复习

发表于 | 更新于 | 分类于
这里尽可能详细的记录了数据结构的知识点，如果能完全掌握这些知识点，期末考试基本哦了\(^o^)/~

绪论

抽象数据类型

  • 抽象数据类型:(Abstract Date Type)

    -定义：一个数学模型和该模型上定义的操作集合的总称

    *ADT是程序设计语言中数据类型概念的进一步推广和进一步抽象

    *同一数学模型上定义的不同操作集，则他们代表不同的ADT

    -表现：用适当的数据结构来表示ADT中的数学模型，并用一组函数(方法)来实现该模型上的各种操作

  • 逻辑结构：

    集合——没关系

    线性表——1:1前后

    树——1：m层次

    图——网状

  • 存储结构：

    ​ 顺序——连续空间 $\Rightarrow$索引

    ​ 链式——不连续空间 +散列

算法及算法分析

  • 算法的相关概念

    -算法(Algorithm):是对特定问题求解步骤的一种描述，是指令的有限序列

    -五大特性：输入 输出 有穷性 确定性

  • 时间复杂度（time xomplexity)

    算法的执行时间，是基本(操作)语句重复执行的次数，它是问题规模的一个函数，我们把这个函数的渐进阶成为该算法的时间复杂度

  • 常见时间复杂度的比较

0(1)< <0(logn) <<0(n)< < 0(nlogn) << 0(n2) << 0(n3) <<0(2n) << 0(n!)

  • 常见设计方法：

穷举、贪心、递归/分治(二分检索、快排)、回溯(树、图的深度优先搜索)、动态规划(最佳二叉排序树)

$\alpha -\beta$裁剪和分支界限法、并行算法

  • 时空资源的折中原理

同一个问题求解，一般会存在多种算法，这些算法在时空开销上往往表现出“时空折中”（trade-off）的性质

逐步求精的程序设计方法

​ 模型化-确定算法-逐步求精

线性表

线性表的抽象数据类型

​ 顺序表：指用一组地址连续的存储单元依次存储线性表的数据元素

线性表的实现

存储结构的三种方式：

① 连续的存储空间（数组） → 静态存储

② 非连续存储空间——指针（链表） → 动态存储

③ 游标（连续存储空间+动态管理思想）→ 静态链表

线性表的数组实现：

随机存储结构，查找快 o(1)

插入和删除慢 o(n)

空间固定

链表

非随机存储结构

eg: 求中点：定义两个指针方=放链表开头，一个速度为1，另一个指针速度为2

​ 求倒数第k个：定义两个指针，i放到开头，j放到第k位，同时速度为1向后走

  • 插入元素

    a、保存后继指针

    b、申请一个内存空间

    c、插入：先链接后部分，再衔接前部分

游标

元素是结构体数组，多个线性表公用一个存储池

单链表逆置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//方法一：
//设表头为L,算法如下: 
p=L->next->next; q=p->next; L->next->next=NULL; while(p!=null) {
    p->next=L->next;
    L->next=p;
    p=q;
    q=q->next; 
}
//方法二：
//线性表由q来表示 
p=null; w=q; while(w!=null) { 
    w=w->next; 
    q->next=p;
    p=q; q=w; 
}
双向链表

双向单链表插入与删除：

环形链表

  • 数组求模可以成环

  • 判断链表是否成环：两个指针，速度分别为1和2,

  • 确定环入口：

  • 两个链表是否相交:判断两个列表最后一个元素是否相同//散列

  • 单项循环链表插入与删除：

栈
  • 多项式的代数运算

  • 后缀表达式求值：

    对后缀表达式从左至右依次扫描，与Ⅰ相反，遇到操作数 时，将操作数进栈保留；当遇到操作符时，从栈中退出两个操 作数并作相应运算，将计算结果进栈保留；直到表达式结束， 栈中唯一元素即为表达式的值。 遇到“（”进栈，当遇到“）”时，退栈输出直到“）” 为止。

队列

优先队列：

问题：如何解决循环队列中队空与队满状态相同？
方法一：约定队列头指针在队列尾指针的下一位置上(即空出一个位置）；

方法二：另设一个标志位用以区别队空与队满两种状态；
结论：两种方法的代价是相同的。

串（String）

KMP算法：

一、如何求next函数:

  • 当j=1时，next[j]=-1； //next[j]=-1表示根本不进行字符比较

  • 当j>1时，next[j]的值为：模式串的位置从1到j-1构成的串 中所出现的首尾相同的子串的最大长度。

  • 当无首尾相同的子串时next[j]的值为0。 //next[j]=0表示从模式串头部开始进行字符比较

下面给出求next函数的伪码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void get_next(SString T, int &next[]) {

 //求模式串T的next函数并存入next数组

 int i = 1; next[1] = 0; int j = 0;

 while (i < T[0]) //T[0]中存放数组长度 {

 if( j==0||T[i]==T[j]) { ++i; ++j;  next[i]=j; } 

else j= next[j]; }

 }//get_next

二、KMP算法实现步骤：

1.在串S和串T中分别设比较的起始下标i和j；

  1. 循环直到S中所剩字符长度小于T的长度或T中所有字 符均比较完毕
    2.1如果S[i]=T[j]，继续比较S和T的下一个字符；否则
    2.2将j向右滑动到next[j]位置，即j=next[j]；
    2.3 如果j=0，则将i和j分别加1，准备下一趟比较；
  2. 如果T中所有字符均比较完毕，则返回匹配的起始下标； 否则返0；
广义表

例如：

A = （a，（b，a，b），（），c，（（（2））））；

B = （）； C = （e ）； D = （A，B，C ）； E = （a，E ）；

长度：广义表LS中的直接元素的个数；
深度：广义表LS中括号的最大嵌套层数。
表头：广义表LS非空时，称第一个元素为LS的表头；
表尾：广义表LS中除表头外其余元素组成的广义表。

树与二叉树

二叉树
性质：

在非空二叉树中，如果叶子结点数为n0，出度为2的结点数为n2，则有: n0＝n2＋11，而与出度数为1的结点数n1无关

建立

建立：

先序建立：

非递归建立：

遍历
  • 先序递归：

  • 先序非递归：

1.栈s初始化；
2.循环直到root为空且栈s为空
​ 2.1 当root不空时循环
​ 2.1.1 输出root->data;
2.1.2 将指针root的值保存到栈中；
​ 2.1.3 继续遍历root的左子树
​ 2.2 如果栈s不空，则
​ 2.2.1 将栈顶元素弹出至root；
​ 2.2.2 准备遍历root的右子树；

  • 中序非递归：

1.栈s初始化；

2.循环直到root为空且栈s为空
​ 2.1 当root不空时循环
​ 2.1.1 将指针root的值保存到栈中；
2.1.2 继续遍历root的左子树
2.2 如果栈s不空，则
2.2.1 将栈顶元素弹出至root；
2.2.2 输出root->data;
​ 2.2.3 准备遍历root的右子树

  • 后序非递归：
  1. 栈s初始化；
  2. 循环直到root为空且栈s为空
    2.1 当root非空时循环
    ​ 2.1.1 将root连同标志flag=1 入栈；
    ​ 2.1.2 继续遍历root的左子树；
    2.2 当栈s 非空且栈顶元素的标志为2 时，出栈并输出栈 顶结点;
    2.3 若栈非空，将栈顶元素的标志改为2，准备遍历栈顶结 点的右子树；

  • 层序遍历：
  1. 队列Q初始化；
  2. 如果二叉树非空，将根指针入队；
  3. 循环直到队列Q为空
    3.1 q=队列Q的队头元素出队；
    3.2 访问结点q的数据域；
    3.3 若结点q存在左孩子，则将左孩子指针入队；
    3.4 若结点q存在右孩子，则将右孩子指针入队；
应用
  • 1、已知先序中序确定二叉树：

遍历前序序列的每个节点A【i】，在中序序列中找到相同节点B【j】，
​ 如果栈为空，将下标 j 入栈；
​ 否则，栈不为空：
​ 如果 j 小于当前栈顶元素，则中序序列B【top】左孩子为 j，下标 j 入栈；否则，当 j 大于栈顶元素时且栈不为空，弹栈，循环后的栈顶top，B【top】的右孩子为 j ， j 入栈

  • 2、求二叉树任意两节点公共祖先：
1
2
3
4
5
6
7
8
9
10
11
12
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root) 
        return NULL;//如果当前节点为NULL说明走到了叶节点都没有找到两个节点中的其中一个
    if (root == p || root == q) 
        return root;//如果当前节点为p,q之中的一个，那么返回当前找到的节点中的一个
    TreeNode *L = lowestCommonAncestor(root->left, p, q);//左子树中是否能最先找到p,q中的一个节点
    TreeNode *R = lowestCommonAncestor(root->right, p, q);
    if (L && R) 
        return root;  //如果当前节点左右节点都各找到一个，那么返回当前节点
    return L ? L : R; //只在左节 点或者右节点找到一个，说明还有一个节点是在当前节点的下面
    }
  • 3、求二叉树宽度：
1
2
3
4
5
6
7
8
9
10
int  front=-1,rear=-1,count=0,max=0,right
if (T!=NULL) 
	q[++rear]=T;max=1;right=rear; 
while(front!=rear) {
	T=q[++front];
	if(T->lc!=NULL)q[++rear]=T->lc; count++;
	if(T->rc!=NULL q[++rear]=T->rc; count++; 
	if(front==right) { 
		if(max<count)max=count; count=0;right=rear;}
 }
  • 4、线索树：

1）在中序线索二叉树中求一个结点p的中序后继p：

​ 当p->rtag==False时，p->rchild 即为所求(线索)。

当p->rtag==True时，p为p 的右子树的最左结点

2）利用InNext（求中序后继节点）算法，中序遍历线索二叉树

1
2
3
4
5
6
void ThInOrder(ThTree HEAD) {  
ThTree   tmp ; tmp = HEAD ; 
  do { 
  	tmp = InNext ( tmp ) ; 
 if ( tmp != HEAD ) visit ( tmp -> data ) ;
} while ( tmp != HEAD ) ; }

3）求中序线索二叉树中结点p 的先序顺序后继结点p*

(1) p 的左子树不空时，p 的左儿子p->lchild 即为 p；
(2) p 的左子树空但右子树不空时，p 的p->rchild 为p；
(3) p 的左右子树均空时，右线索序列中第一个有右孩子 结点的右儿子或头结点即为p*.

1
2
3
4
5
6
7
8
THTREE PreNext( ThTree p) {   
	ThTree Q ;
	if (p->ltag = = True ) Q=p->lchild ; 
	else{
		Q = p;
		while(Q->rtag = = False) Q = Q->rchild ; 
		Q = Q->rchild ;
	}  return ( Q ) ;

  • 相似二叉树:具有相同结构的二叉树为相似二叉树。

  • 相似且对应结点包含相同信息的二叉树称为等价二叉树。

堆

最大堆：

如果一棵完全二叉树的任意一个非终结结点的元素都不小于其 左儿子结点和右儿子结点（如果有的话）的元素，则称此完全二叉 树为最大堆

  • 大根堆插入：

void Insert ( Heap &heap，Elementtype x)//大根堆插入一个元素 {
​ int i;
​ if ( ! HeapFull ( heap ) ) {
​ i=heap.n+1;
​ while ( (i!=1)&&(x >heap.ele [i/2] ) ) {
​ heap.ele [i]=heap.ele [i/2]; i=i/2;
} heap.ele [i] = x;

  • 大根堆删除：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void DeleteMax (Heap & heap )//大根堆删除 {  
	int parent=1, child=2;  Elementtype  ele,  tmp;
	if (! HeapEmpty(heap)) { 
		ele=heap.ele [1]; tmp=heap.ele [heap.n--];
 		while (child<= heap.n){
			if(child<heap.n)&&(heap.ele [child]<heap.ele [child+1]))
                	child++;
			if (tmp>=heap.ele [child])  break;
			heap.ele [parent]=heap.ele [child]; 
			parent=child; child*=2;
		}//while
 		heap.ele [parent]=tmp; return ele; 
	}//if
}
选择树

​ 胜者树、败者树

树

存储结构：

双亲表示法（数组）、孩子链表表示法（邻接表）、双亲孩子表示法、二叉链表表示法（(左)孩子(右)兄弟链表表示））

树 二叉树
节点关系 兄弟关系 双亲和右孩子
双亲和长子 双亲和左孩子
森林与二叉树的相互转换
  • 森林转化成二叉树：

1、连线： 把每株树的各兄弟结点连起来； 把各株树的根结点连起来（视为兄弟）

2、抹线： 对于每个结点，只保留与其最左儿子的连线，抹去该结 点与其它结点之间的连线

3、旋转： 按顺时针旋转45度角（左链竖画，右链横画）

  • 二叉树转化成森林（树）

连线： 若某个结点 k 是其双亲结点的左孩子，则将该结点 k 的右孩子以及（当且仅当）连续地沿着右孩子的右链不 断搜索到的所有右孩子，都分别与结点k 的双亲结点相 连；

抹线： 把二叉树中的所有结点与其右孩子的连线以及（ 当且 仅当）连续地沿着右孩子的右链不断搜索到的所有右孩 子的连线全部抹去;

旋转： 按逆时针旋转45度角（即把结点按层次排列）

  • 将一株树转换为二叉树，二叉树一定没有右子树
  • 一般结论：森林中的任何没有右兄弟的结点在对应的二叉 树中，该没有右子树；

  • 任何一个森林（树）对应唯一的一株二叉树，反之亦然。 且第一株树的根对应二叉树的根； 第一株树的所有子树对应二叉树的左子树； 其余子树森林对应二叉树的右子树；

  • 森林(树)转换成二叉树的递归算法：

    F ={T1,T2, …,Tn}
    二叉树B(F) 若n=0，则B(F)为空；否则，n〉0，则
    B(F)的根就是root（T1）；
    B(F)的左子树是F的第一棵树T1的子树森林；
    B(F)的右子树F的其余子树森林。

  • 二叉树转换成森林(树) 的递归算法 ：

若B 为空，则F 为空；若B 不空，则
F中的第一株树T1 的根对应二叉树B 的根；
T1中根结点的子树森林F1是由B的左子树转换来的；
F中除T1之外其余子树组成的森林F’={T2,…Tn}是由B 的右子树转换而来的。

树的应用

  • 堆的复杂度：O(n)

  • 败者树的复杂度：O(2n-1)

用树结构表示集合：

等价分类算法：

  1. 令S中的每一个元素自身构成一个等价类，S1,S2,…S7

  2. 重复读入等价对（i, j）
    2.1对每个读入的等价对(i, j),求出i 和j 所在的集合Sk 和Sm （不失一般性）
    2.2若Sk≠Sm,则将Sk并入Sm,并将Sk置空。

1
2
3
4
5
6
7
8
9
10
11
void Equivalence (MFSET S)   //等价分类算法 { 
   int i ,j , k ,m; 
   for(i=1; i<=n+1;i++) Initial(i,S);  //使集合S只包含元素i
   cin>>i>>j;        // 读入等价对
   while(!(i==0&&j==0){ // 等价对未读完
       k=Find(i,S);           //求i的根 
       m=Find(j,S);        // 求j的根
       if(k!=m)          //if k==m,i,j已在一个树中，不需合并 
           Union(i,j,S);     //合并 
       cin<<i<<j;          
   }  }
判定树

判定树的特点：

一个判定树是一个算法的描述；
每个内部结点对应一个部分解； 每个叶子对应一个解；
每个内部结点连接与一个获得新信息的测试；
从每个结点出发的分支标记着不同的测试结果；
一个解决过程的执行对应于通过根到叶的一条路 一个判定树是所有可能的解的集合

判断树高度：$h=\frac{n+1}{n}log_2(n+1)-1$

哈夫曼树：
  • 内外路径：

  • 哈夫曼树性质：

没有度数为1的结点 外结点数 =内结点数 + 1(为什么?) 有 n 个外结点的扩充二叉树共有 2n-1 个结点。

  • 码长计算：

  • 哈夫曼编码一定具有前缀性；
    哈夫曼编码是最小冗余码;
    哈夫曼编码方法，使出现概率大的字符对应的码长较短；
    哈夫曼编码不唯一，可以用于加密；
    哈夫曼编码译码简单唯一，没有二义性.
表达式求值

把中缀表达式转换为后缀表达式（栈结构、树结构）；根据后缀表 达式计算表达式的值

利用后序遍历算法，先计算左子树的值，然后再计算右子树的值。 当到达某结点时，该结点的左右操作数都以求出。

图

简单路径：若路径上各顶点 v1,v2,…,vm 均互不相同(第一个顶点和最后 一个顶点可以相同）, 则称这样的路径为简单路径。

简单回路：若路径上第一个顶点 v1与最后一个顶点vm重合, 则称这样 的简单路径为简单回路或环。 一条环路的长度至少为1（无向图为3），且起点和终点相同的简单路径。

图的存储结构
空间性能 时间性能 唯一性 适用范围
邻接矩阵 O(n^2) O(n^2) 唯一 稠密图
邻接表 O(n+e) O(n+e) 不唯一 稀疏图

十字链表、邻接多重表

图的搜索
  • 深度优先搜索

从一个顶点出发的一次深度优先遍历算法：
实现步骤：

  1. 访问顶点v; visited[v]=1;
  2. w=顶点v的第一个邻接点；
  3. while (w存在)
    3.1 if (w未被访问) 从顶点w出发递归执行该算法;
    3.2 w=顶点v的下一个邻接点;

邻接矩阵：空间：O(n^2) 时间： O(n^2)

邻接表：O(n) O(V+E)

  • 广度优先搜索

1 . 初始化队列Q;

  1. 访问顶点v; visited [v]=1; 顶点v入队Q;
  2. while (队列Q非空)
    3.1 v=队列Q的队头元素出队;
    3.2 w=顶点v的第一个邻接点;
    3.3 while (w存在) 
    3.3.1 如果w 未被访问，则 访问顶点w; visited[w]=1; 顶点w入队列Q；
3.3.2 w=顶点v的下一个邻接点；
图与树、最小生成树
先深和先广生成森林
  • 先深搜索对边的分类
    两类: 树边—在搜索过程中所经过的边；回退边—图中的 其它边 特点: 树边是从先深编号较小的指向较大的顶点;回退边相 反;
    结论:若G中存在环路,则在先广搜索过程中必遇到回退边;反之亦然
  • 先广搜索对边的分类
    两类: 树边—在搜索过程中所经过的边；横边—图中的其 它边. 特点: 树边是从先深编号较小的指向较大的顶点; 而横边不一定与之相反，但可规定：大→小.
    结论:若G中存在环路,则在先广搜索过程中必遇到横边;反之亦然
无向图与开放树

连通而无环路的无向图称作开放树（Free Tree）

（1）具有n≥1个顶点的开放树包含n-1条边；

（2）如果在开放树中任意加上一条边，便得到一条回路

最小生成树算法
  • 普里姆Prim算法：

基本思想
① 首先从集合V中任取一顶点(如顶点v0)放入集合U中。这时U={v0}， 边集TE={ }
② 然后找出权值最小的边(u，v) ，且u∈U，v∈(V-U)，将边加入TE， 并将顶点v加入集合U
③ 重复上述操作直到U=V为止。这时TE中有n-1条边，T=(U，TE)就 是G的一棵最小生成树

如何找到连接U和V-U的最短边 ：
利用MST性质，可以用下述方法构造候选最短边集：对于V-U 中的每个顶点，保存从该顶点到U中的各顶点的最短边。

  1. 初始化两个辅助数组LOWCOST和CLOSEST；

  2. 输出顶点v0，将顶点v0加入集合U中；

  3. 重复执行下列操作n-1次
    3.1 在LOWCOST中选取最短边，取CLOSEST中对应的顶点序号k；
    3.2 输出顶点k和对应的权值；
    3.3 将顶点k加入集合U中；
    3.4 调整数组LOWCOST和CLOSEST；

    LOWCOST[j]=min { cost (vk，vj) | vj∈U, LOWCOST[j]}
    CLOSEST[j]=k

时间复杂度：O(n^2)

  • 克鲁斯卡尔（Kruskal）算法

注：边值各不相同时生成树唯一

基本思想：
设无向连通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)，其初 态为U＝V，TE＝{ }，
然后，按照边的权值由小到大的顺序，依次考察G的边集E中的各条 边。
若被考察的边连接的是两个不同连通分量，则将此边作为最小生成 树的边加入到T中，同时把两个连通分量连接为一个连通分量； 若被考察的边连接的是同一个连通分量，则舍去此边，以免造成回 路，
如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵 最小生成树。

  1. 初始化：U=V； TE={ }；
  2. 循环直到T中的连通分量个数为1
    2.1 在E中选择最短边(u，v);
    2.2 如果顶点u、v位于T的两个不同连通分量，则
    ​ 2.2.1 将边(u，v)并入TE；
    ​ 2.2.2 将这两个连通分量合为一个；
    2.3 在E中标记边(u，v)，使得(u，v)不参加后续最短边的选取

时间复杂度：O(eloge)

无向图的双连通性

若在删去顶点 v 以及与之相邻的边之后，将图的一个连通分量分割成两个或 两个以上的连通分量，则称该顶点为关节点。

1、没有关节点的连通图称为双连通图。
2、双连通的无向图是连通的，但连通的无向图未必双连通。
3、一个连通的无向图是双连通的，当且仅当它没有关节点。
4、在双连通图上, 任何一对顶点之间至少存在有两条路径，在删去某个顶点 及与该顶点相关联的边时, 也不破坏图的连通性。
5、一个连通图G如果是重连通图，那么它可以包括几个双连通分量。

  • 由先深生成树可得出两类关节点的特性：

    1、若生成树的根有两株或两株以上子树，则此根结点必为关节（第一类关 节点）。因为图中不存在连接不同子树中顶点的边，因此，若删去根顶 点，生成树变成生成森林。

2、若生成树中非叶顶点v，其某株子树的根和子树中的其它结点均没有指向 v 的祖先的回退边，则v 是关节点（第二类关节点）。 因为删去v，则其 子树和图的其它部分被分割开来

算法要点：
1.计算先深编号：对图进行先深搜索，计算每个结点v的先深编号dnf[v]，形成 先深生成树S＝（V,T）。
2.计算low[v]：在先深生成树上按后根顺序进行计算每个顶点v的 low[v]， low[v]取下述三个结点中的最小者：
(1) dfn[v]；
(2) dfn[w]，凡是有回退边（v,w）的任何结点w；
(3) low[y]，对v的任何儿子y。
3.求关节点： (1)树根是关节点，当且仅当它有两个或两个以上的儿子（第一类关节点）； (2)非树根结点v是关节点当且仅当v有某个儿子y，使 low[y]≥dnf[v]（第二类关节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//求双连通分量的算法 
void main() { 
	count = 1; for (all v ∈ V)  mark v “new”; searchB( v0 );
}

//v0是V中任一结点,建立以v0为根的先深生成树,计算low(v)
void searchB(v) { 
	mark v “old”;
	dfn[v] = count;count++; 
	low[v]=dfn[v]; 
 	for (each w ∈ L[v])
     	if (w is marked “new”) { 
         	father [w]=v；searchB (w); 
         	low [v]= min { low [v], low [w] }; 
        	if (low[w]>=dfn[v]) //表明W及子孙均无指向V的祖先的回退边，v是关节点
           	 cout<<“a biconnected component”; } 
    	else if (w != father [v]) //(v ,w)是回退边   
          low [v]= min { low [v],  dfn [w] };
拓扑排序

是由某个集合上的一个偏序得到该集合上的一个全序的过程。所得到 的线性序列称为拓扑序列。（不唯一）

实质：广度优先搜索算法

AOV网（有向图）

  • 利用队列算法：
    1.建立入度为零的顶点排队
    2.扫描顶点表，将入度为0的顶点入队；
    3.while（排队不空）{
    输出队头结点； 记下输出结点的数目；
    删去与之关联的出边； 若有入度为0的结点，入队 }
    4.若输出结点个数小于n，则输出有环路；否则拓扑排序 正常结束。

  • 利用栈算法：
    1.建立入度为零的顶点栈
    2.扫描顶点表，将入度为0的顶点栈；
    3.while（栈不空）{
    输出队头结点； 记下输出结点的数目；
    删去与之关联的出边； 若有入度为0的结点，入栈 }
    4.若输出结点个数小于n，则输出有环路；否则拓扑排序 正常结束。

注：图中还有未输出的顶 点, 但已跳出循环处 理。说明图中还剩下 一些顶点, 它们都有 直接前驱。这时网络 中必存在有向环；或 全部顶点均已输出， 拓扑有序序列形成， 拓扑排序完成。

  • 说明：
    • 与先广搜索的差别：
      ​ 搜索起点是入度为0的顶点；
      ​ 需判断是否有环路；
      ​ 需对访问并输出的顶点计数（引入计数器nodes）。
      ​ 需删除邻接于 v 的边（引入数组indegree[ ]或在顶点表中增加一 个属性域indegree）。
    • 也可以采用栈数据结构进行广度优先拓扑排序。
    • 亦可采用无后继顶点优先的拓扑排序算法
    • 也可以利用DFS遍历进行拓扑排序
  • 基于DFS的拓扑排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void topodfs ( v ) {   
    Push( v ,S ) ; 
    mark[v]=True; 
    for ( L[v] 中的每一个顶点w) 
        if ( mark[w] = False ) topodfs ( w ) ; 
    printf ( Top( S ) ) ; 
    Pop ( S ) ; 
}

void  dfs-topo ( GRAPH  L ) {  
    MakeNull( S ); 
    for( u=1;u<=n; u++) 
        mark[u]=False; 
    for( u=1;u<=n;u++) 
        if ( !mark[u] ) 
            topodfs( u ) ;

思想：借助栈，在DFS中，把第一次 遇到的顶点入栈，到达某一顶点递归 返回时，从栈中弹出顶点并输出。

关键路径

AOE网：带权有向图，顶点表示事件，用边表示活动，边上权表示活 动的开销（如持续时间）

最大长度的路径称为关键路径。
一个AOE中，关键路径可能不只一条。
关键活动：关键路径上的活动称为关键活动。

关键路径算法步骤：

（1）前进阶段：计算VE[j]。从源点V1出发，令VE(1) = 0，按拓扑序列 次序求出其余各顶点事件的最早发生时间: j∈T VE(j) = max{ VE(i)+ACT[i][j 】}
其中T是以顶点Vj为尾的所有边的头顶点的集合(2≤j≤n) 如果网中有回路，不能求出关键路径则算法中止；否则转（2）

（２）回退阶段：计算VL[j]从汇点Vn出发，令VL(n) = VE(n)，按逆 拓扑有序求其余各顶点的最晚发生时间(用逆邻接矩阵ACT转置即可） ： VL(j) = min{ VL(i)-ACT[j][i】 }
其中S是以顶点Vj为头的所有边的尾顶点的集合(2≤j≤n-1) k∈S

（３）计算E( i ) 和L( i ) 求每一项活动ai的最早开始时间: E( i ) = VE( j ) 求每一项活动ai的最晚开始时间: L( i ) = VL( k ) -ACT[j][k】

（４）若某条边满足E( i ) = L( i )，则它是关键活动。

注：为了简化算法, 可以在求关键路径之前已经对各顶点实现拓扑排 序, 并按拓扑有序的顺序对各顶点重新进行了编号。

最短路径
  • 边上权值非负情形的单源最短路径问题 — Dijkstra算法

Dijkstra算法实现步骤：

  1. 将Ｖ分为两个集合S（最短路径已经确定的顶点集合）和V-S（最短路径尚未确定的顶点集合。初始时，S={ 1 }，D[i]=C[1】[i】（i=2,3,…n ），P[i】=1(源点，i≠1) 。
  2. 从S之外即V-S中选取一个顶点w，使D[w]最小（即选这样的w， D[w]=min{ D[i]| i∈V-S }） ，于是从源点到达w只通过S中的顶点，且是一条最短路径（选定路径），并把w加入集合S。
  3. 调整D中记录的从源点到V-S中每个顶点的最短距离，即从原来的 D[v]和D[w]＋C[w】[v】中选择最小值作为D[v]的新值，且P[v]=w。
  4. 重复2和3，直到S中包含V的所有顶点为止。结果数组Ｄ就记录了 从源到V中各顶点的最短 距离（数组P记录最短路径）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
costtype MinCost (D, S) { 
	temp = INFINITY ; w = 2 ;
	for ( i=2 ; i<=n ; i++ )
		if (!S[i]&&D[i]<temp)  {
  			temp = D[i] ; w = i ; } 
	return  w ;
}

void  Dijkstra(GRAPH  C, costtype D[n+1] ，int P[n+1]，bool S[n+1]) { 
	for ( i=2 ; i<=n; i++ ) {  
	D[i]=C[1][i] ; S[i]=False ;P[i]=1;}
	S [1]= True ; 
	for( i=1; i<=n-1; i++) {  
		w=MinCost ( D, S ) ; S[w]=True ; 
	for ( v=2 ; v<= n ; n++ ) 
		if ( S[v]!=True ) {  
        	        sum=D[w] + C[w][v] ;
 			if (sum < D[v】 ){D[v] = sum ; P[v]=w;}
		}
    }
 }//   时间复杂度：O（n^2）
  • 所有顶点之间的最短路径问题 — Floyd算法

基本思想：动态规划

求解过程：

设 C 为 n 行 n 列的代价矩阵，c[ i, j ] 为 i —> j 的权值。如果 i=j ；那么 c[ i, j ] = 0。如果 i 和 j 之间无有向边； 则 c[ i, j ] = ∞

1、使用 n 行 n 列的矩阵A 用于计算最短路径。 初始时，A[ i, j ] = c[ i, j ]

2、进行 n 次迭代 在进行第 k 次迭代时，将使用如下的公式： Ak[ i, j ] = min {Ak-1[ i, j ]，Ak-1[ i, k ] + Ak-1[ k, j ] }注意：第 k 次迭代时，针对结点 k 进行。原Ak-1矩阵 的第 k行，第 k 列保持不变。左上至右下的对角线元素 也不 变。

1
2
3
4
5
6
7
8
9
10
11
12
13
void Floyd( costtype A[][], costtype C[][], int P[][], int n) {   
	for ( i = 0; i < n; i++ )
		for ( j = 0; j< n; j++ ) {
			A[i][j] = C[i][j];  P[i][j] = -1； }
	for ( k = 0; k < n; k++ ) 
		for ( i = 0; i < n; i++ ) 
			for ( j = 0; j < n; j++ )
				if ( A[i][k] + A[k][j] < A[i][j] ){ 
                	A[i][j] = A[i][k] + A[k][j] ; P[i][j] = k;
            } 
} /* 时间复杂度：O(n3) */
Warshall算法 求有向图邻接矩阵C的传递闭包D A[i][j]=A[i][j]∪(A[i][k]∩A[k][j]);
可以判定有向图任意两点间是否存在有向 路。

查找

线性查找

插入和删除：从后往前

第0个元素做为伪记录或哨兵

折半查找

折半查找只适合于静态查找

  • 数组：时间复杂度O(logn)

  • 判定树:

高度： (n+1)/nlog2(n+1)-1

当n 很大时，ASLbs≈ log2(n+1)-1作为查找成功时的平均查找长度；在查找不成功和最坏情况下查找成功所需关键字的比较次数都不超过判 定树的高度；折半查找的最坏性能与平均性能相当接近

分块查找

基本思想：均匀分块，块间有序，块内无序

索引表：建一个线性表，用以存放每块中最大(或最小)的关键 字，此线性表称为索引表，它是一个有序表.

块内的平均查找长度： ASLblk=∑ pi · ci = — ∑ j

所以分块查找平均长度为： ASL(L)=ASLix+ ASLblk = (b+1)/2+(L+1)/2=(n/L+L)/2+1 可证明，当$L=\sqrt{n}$时，ASL(L) = $\sqrt{n +1}$ （最小值）。

BST-二叉查找树

  • 插入：若二叉排序树为空树，则 新插入的结点为根结点； 否则，新插入的结点必为 一个新的叶结点.

  • 删除：

  1. 若结点p是叶子，则直接删除结点p；
  2. 若结点p只有左子树，则p的左子树继承；若结点p只有右子树，则p的右子树继承 ；
  3. 若结点p的左右子树均不空，则
    3.1 查找结点p的右子树上的最左下结点s及其双亲结点par；
    3.2 将结点s数据域替换到被删结点p的数据域；
    3.3 若结点p的右孩子无左子树，则将s的右子树接到par的右子树上； 否则，将s的 右子树接到结点par的左子树上；
    3.4 删除结点s；
  • 性能：

二叉排序树的查找性能取决于二叉排序树的形态，在 O (log2n )和 O ( n ) 之间。

在最坏情况下，二叉查找树是通过把有序表的n 个结点依次插入而生 成的，此时所得到的二叉查找树退化为一株高度为n 的单支树，它的 平均查找长度和单链表上的顺序查找相同，(n+1)/2。

在最好情况下，二叉查找树的形态比较均匀，最终得到一株形态与折 半查找的判定树相似，此时的平均查找长度约为log2n。 二叉查找树的平均高度为O(log2n)。因此平均情况下，三种操作的平均时间复杂性为O(log2n)

就平均性能而言，二叉查找树上的查找与二分查找差不多 ；就维护表的有序性而言，二叉查找树更有效。

AVL树

AVL树或者是空二叉树，或者是具有如下性质的BST： 根结点的左、右子树高度之差的绝对值不超过1； 且根结点左子树和右子树仍然是AVL树。
令Nh是高为h的AVL树中结点个数的最小值，在最稀疏情况下，这棵 AVL树的一棵子树的高度为h–1，而另一棵子树的高度为h–2，这两棵子 树也都是AVL树。
因此， Nh =Nh-1+Nh-2+1，其中N0=0，N1=1，N2=2。 可以发现， Nh的递归定义与Fibonacci数的定义Fn = Fn-1 + Fn-2（其中 F0 = 0，F1 =1）相似 可以用数学归纳法证明，Nh = Fh+2–1 （h ≥ 0）
Fh≈φh/√5,其中φ=(1+√5 )/2，所以，Nh≈φh+2/√5-1
所以，一棵包含n个结点的AVL树，其高度h至多为logφ(√5(n+1))–2
因此，对于包含n个结点的AVL树，其最坏情况下的插入时间为O(log n)

B-树和B+树

  • B-树

    • 树中可容纳结点数量最大值，关键字个数最多：m^h-1

    • 树中每个结点至多有m棵子树； 根结点至少有 2 棵子树；

    • 除根结点和失败结点外，所有结点至少有 m/2 棵子树；

    • 所有的终端结点和叶子结点（失败结点）都位于同一层。

    • h 层 至少有2 *(m / 2)^( h-2)个结点(不算h+1层)

    • 关键字个数N：N +1 = 位于第 h+1 层的结点数 >= 2 *(m / 2)^ (h -1)

    • N+1>= 2 *(m / 2)^ (h -1) ; h-1 <= log(m / 2)(( N + 1 ) / 2 )

  • B+树

    • (1) 有k个子结点的结点必然有k个关键字；

    • (2) 所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针， 且叶子结点本身依关键字的大小自小而大顺序链接。
      3阶B+树

    • (3) 所有的非终结结点可以看成是索引部分，结点中仅含其子树（根结点）中的 最大（或最小）关键字。
      通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

    • (4) 可对B+树进行两种查找操作： 一种是沿叶结点链顺序查找， 另一种是从根结点开始，进行自顶向下，直至叶结点的随机查找。

散列

不同的关键字具有相同散列地址的现象称为散列冲突（碰撞）。而发 生冲突的两个关键字称为同义词

散列函数的构造的原则： 计算简单、分布均匀

  • 构造方法：
    直接定制法、质数除冗法、平方取中法、折叠法、数字分析法、随机数法、

  • 冲突处理：

1、开放定址法：
–线性探测法 ：当发生冲突时，从冲突位置的下一个位置起，依次寻找空的 散列地址 –线性补偿探测法：当发生冲突时，寻找下一个散列地址的公式为： hi=(h(key)＋di) % B （di=1c，2c，…）
–二次探测法:当发生冲突时，寻找下一个散列地址的公式为： hi=(h(key)＋di) % B （di=1^2，－1^2，2^2，－2^2，…，q^2，－q^2且q≤B/2）
–随机探测法：当发生冲突时，下一个散列地址的位移量是一个随机数列， 即寻找下一个散列地址的公式为： hi=(h(key)＋di) % B （其中，d1, d2, …,dB-1是1, 2, …, B-1的随机序列。）

2、带溢出表的内散列法：（一个）主表及其溢出表元素的散列地址相同; 空间利用率不高

3、拉链法\链地址法：

内部排序

气泡排序

最好情况（正序）: 比较次数：n-1 移动次数：0 时间复杂度： O(n)；

最坏情况（反序）： 比较次数：n(n-1)/2 移动次数：3n(n-1)/2 时间复杂度： O(n^2)

平均情况：时间复杂度为O(n^2)

空间复杂度： O(1)

快速排序

对气泡排序的改进

最好情况： 时间复杂度为O(nlog2n) 空间复杂度为O(log2n)

最坏情况： 时间复杂度为O(n^2) 空间复杂度为O(n)

平均情况： 时间复杂度为O(nlog2n) 空间复杂度为O(log2n)

直接选择排序

移动次数： 最好情况（正序）：0次 最坏情况：3(n-1)次

比较次数：n(n-1)/2

时间复杂度为O(n^2)

空间复杂度为O(1)

堆排序

对直接选择排序的改进

首先将待排序的记录序列用完全二叉树表示；
然后完全二叉树构造成一个堆，此时，选出了堆中所有记录关键字的最小者；
最后将关键字最小者从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的关键字记录，以此类推，直到堆中只有一个记录。

堆排序：令i = n, n-1 ,…, 2

1.交换：把堆顶元素(当前最小的)与位置 i(当前最大的叶结点下标) 的元素交换，即执行swap(A[1],A[i])；
2.整理:把剩余的 i-1个元素整理成堆，即执行PushDown(1 , i-1)；
3.重复执行完这一过程之后，则A[1],A[2],…,A[n]是按关键字不增顺 序的有序序列。

时间复杂度：O(nlog2n)

空间复杂度：O(1)

（直接）插入排序

最好情况下（正序）： 比较次数：n-1 移动次数：0 时间复杂度为O(n)

最坏情况下（反序）： 比较次数：（n+2)(n-1)/2 移动次数：(n+4)(n-1)/2 时间复杂度为O(n^2)

最好情况下（正序）： 比较次数：(n+2)(n-1)/4 移动次数：(n+4)(n-1)/4 时间复杂度为O(n^2)

希尔排序

对直接插入排序的改进

时间性能：在O(n^2)和O(nlog2n)之间。

当n在某个 特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n^1.3 )

(二路)归并排序

基本思想：自底向上的非递归算法

时间复杂度：O(nlog2n)

空间复杂度：O(n)

基数排序–多关键字排序

次序：从最低位排序，使用了队列

改进：桶—-链式排队

时间复杂度：O(d(n+r)) （n—记录数，d—-关键字(分量)个数，r—-基数）

空间复杂度：O((n+r))

计数排序

数组记录对应关键字出现的最后一个位置

总结：
排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性举例
冒泡 O(n^2) O(n) O(n^2) O(1) 是
快排 O(nlog2n) O(nlog2n) O(n^2) O(log2n)~O(n) 否/2,2,1
直接选择 O(n^2) O(n^2) O(n^2) O(1) 否/2,2,1
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 否/1,2,2(最小堆)
直接插入 O(n^2) O(n) O(n^2) O(1) 是
希尔排序 O(nlog2n) O(n^1.3) O(n^2) O(1) 否/3,2,2(d=2/1)
二路归并 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 是
基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(n+r) 是

最坏：

气泡排序：比较次数：n(n-1)/2 移动次数：3n(n-1)/2

选择排序： 比较次数：n(n-1)/2 移动次数：3(n-1)

插入排序： 比较次数:（n+2)(n-1)/2 移动次数：(n+4)(n-1)/2 时间复杂度为O(n^2)

外排序

磁盘文件的归并排序

方法：多路归并 、 I/O并行处理 、生成初始归并段

  • 磁盘文件的归并排序

第一阶段：初始归并段形成

第二阶段：多路归并

  • 多路归并-减少归并遍数

一般地，m 个初始段，采用K路归并，需要 logKm 遍归并。

在 K路归并时，从 K 个关键字中选择最小记录时，要比较 K-1 次。若记录总数为 n ，每遍要比较的次数为： （n-1）(K-1)[logkm]=（n-1）(K-1) [log2(m/log2K)]

  • K 路平衡归并与选择树

    • 第一次建立选择树的比较所花时间为: O( k-1 ) = O ( k)

    • 而后每次重新建造选择树所需时间为： O( log2k )

    • n 个记录处理时间为初始建立选择树的时间加上 n-1 次重新选择树的时间:

    ​ O((n-1) ·log2k)+O(k) = O ( n ·log2k ) 这就是k路归并一遍所需的CPU处理时间。

    • 归并遍数为 logkm，总时间为:O(n ·log2k ·logkm)=O(n ·log2m) ( k 路归并 CPU 时间与 k 无关 )

  • 并行操作的缓冲区处理

    ​ ——-使输入、输出和CPU处理尽可能重叠

对k个归并段进行 k 路归并至少需要k个输入和1个输出 缓冲区。 要使输入、输出和归并同时进行，k+1个缓冲区是不够的，需要2K个缓冲区实现并行操作

  • 生成初始归并段（使用选择树法）：多路平衡归并

假设初始待排序文件为输入文件FI，初始归并段文件为输出文件FO，内 存缓冲区为W，可容纳P个记录。FO,W初始为空，则置换-选择如下：
(1) 从FI输入P个记录到缓冲区W;
(2)从W中选择出关键字最小的记录MIN；
(3)将MIN记录输出到FO中去；
(4)若FI不空，则从FI输入下一个记录到W;
(5)从W中所有关键字比MIN关键字大的记录中选出最小关键字记录，作 为新的MIN;
(6)重复(3)~(5)，直到在W中选不出新的MIN为止。得到一个初始归并段， 输出归并段结束标志到FO中
(7)重复(2)~(6)，直到W为空，由此得到全部初始归并段

生成的初始归并段的平均长度是缓冲区长度的两倍

最佳归并树：使外存读写次数最少，是一棵正则树

对 K 路归并而言，设初始归并段为 m，若： ( m－1 ) % ( K－1) ＝0 则不需要加虚段，否则需要加虚段的个数为： K－( m－1 ) % ( K－1)－1

加入细节点：

  • 已知前序和后序不能确定唯一二叉树
  • //判断完全二叉树：k层的最后一个叶节点序号/2是否等于k-1层最后一个叶节点编号

  • 树转化为二叉树根一定没有右子树，森林转化为二叉树根节点可以有有子树

  • 解决冲突的方法：线性再散列、内散列表、外散列表

  • 左右链表示的二叉树共有2n个指针，其中，n+1个空指针，n-1个指向孩子的指针

  • 折半查找树高度： (n+1)/nlog2(n+1)-1