第22章 图的基本算法 22.5 强联通分支
最后更新于：2022-04-01 07:36:12
# 一、综述
定义：
# 二、代码
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_5.cpp
# 三、练习
### 22.5-1
不变或减少
### 22.5-2
第一次DFS结果：
r u q t y x z s v w
G转置的结果：
q:y
r:
s:q w
t:q
u:r
v:s
w:q v
x:t z
y:r t u
z:x
第二次DFS的结果：
r
u
q y t
x z
s w v
### 22.5-3
简化后的算法不可行，证明如下。
在原算法中，过程总结为这样几步
（1）对图G作DFS，计算每个点的结束时间f
（2）将结点以f递减排序
（3）对图作转置，得到GT
（4）以f递减顺序对GT作DFS
（5）第二次DFS后得到的一个树里的点都属于同一个强联通分支
如果以DFS后的f递减排序，排序的结点有规律呢？
假设f[u]>f[v]，那么u和v的关系可能有几下四种情况
（1）u和v互相不可达
（2）u和v互相可达，即在同一个联通分支内
（3）u到v可达 && v到u不可达
（4）u到v不可达 && v到u可达 && (v,u)不是G中的边 && 存在另一个结点w && w与v在同一个联通分支 && w到u可达 && f[w]>f[u]>f[v]
以下将针对这四种情况做第（3）（4）操作，看是否能得到第（5）的结果
<table style="border-collapse: collapse; table-layout: fixed; margin-left: 0px;" height="242" width="865"><tbody><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.37278106508876%;"><div>对G做DFS后，f[u]>f[v]，u和v的关系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.25443786982248%;"><div>在GT中u和v的关系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.25443786982248%;"><div>在GT中对u做DFS，v是否会成为u的后继</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可达，即在同一个联通分支内</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可达，即在同一个联通分支内</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可达 && v到u不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可达 && v到u可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可达 && v到u可达</div><div>&& (v,u)不是G中的边</div><div>&& 存在另一个结点w && w与v在同一个联通分支</div><div>&& w到u可达 && f[w]>f[u]>f[v]</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可达 && v到u不可达</div><div>&& (u,v)不是G中的边 &&</div><div>存在另一个结点w && w与v在同一个联通分支 &&</div><div>u到w可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会。</div><div>虽然u到v可达。但由于f[w]<f[v]，会先对w做DFS，v已经是w的后继了，所以不会成为u的后继</div></td></tr></tbody></table>
由此可以知道，以f递减的顺序对GT作DFS，同一个连通分支的点会到一棵不树上，不是同一个连通分支的点不会到一棵树上。
再看本题的算法过程，总结为以下几步：
（1）对图G作DFS，计算每个点的结束时间f
（2）将结点以f递增排序
（3）以f递增的顺序对GT作DFS
（4）第二次DFS后得到的一个树里的点都属于同一个强联通分支
与上述步骤类似，我们先分析f递增排序后结点的关系，然后针对这些关系做第（3）步，分析是否能得到第（4）步的结果
<table style="border-collapse: collapse; margin-left: 0px; table-layout: fixed;" height="242" width="646"><tbody><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:50.05917159763313%;"><div>对G做DFS后，f[u]<f[v]，u和v的关系</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:49.82248520710059%;"><div>在G中对u做DFS，v是否会成为u的后继</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相不可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u和v互相可达，即在同一个联通分支内</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v不可达 && v到u可达</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>不会</div></td></tr><tr><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>u到v可达 && v到u不可达</div><div>&& (u,v)不是G中的边</div><div>&& 存在另一个结点w && w与u在同一个联通分支</div><div>&& w到v可达 && f[w]>f[v]>f[u]</div></td><td style="border-style:solid;border-width:1px;border-color:rgb(211,211,211);padding:10px;margin:0px;width:33.33%;"><div>会。</div><div>此处不对。u和v不属于同一个联通分支，但v会成为u的后继</div></td></tr></tbody></table>
因此该算法不可行。
### 22.5-5
见[算法导论 22.5-5 O(V+E)求有向图的分支图](http://blog.csdn.net/mishifangxiangdefeng/article/details/8461683)
### 22.5-6
待解决，题目的意思不太懂，网上找了个答案，主要是其中的第四步不懂。
令所求图为G2，翻译一下：
STEP1：使用22.5中的算法计算出所有的强连通分支
STEP2：使用22.5中和算法计算出分支图G|SCC
STEP3：将G2的边集初始化为空
STEP4：将每个强连通分支中的顶点构成环。比如强连通分支a中有ea1,ea2,ea3,ea4这四个顶点，就在G2中加入边ea1->ea2,ea2->ea3,ea3->ea4,ea4->ea1
STEP5：把分支图的边加到G2中。比如分支图中有一条强连通分支a到强连通分支b的边，就在G2中加入一条ea到eb的边。其中ea是a中的任意一个顶点，eb是b中的任意一个顶点
解释：
强连通分支：
分支图：
G与G2有相同的强连通分支 ===> G2的顶点与G的顶点相同
G与G2有相同的分支图 ===> G2至少有着G|SCC中的边 ===> STEP5
G2有最小的边 ===> 具有最少边的强连通图是一个环，边的个数与顶点的个数相同 ===> STEP4
### 22.5-7
STEP1：使用22.5-5中的算法得到SCC。
STEP2：对SCC求拓扑序列(v1, v2, ……, vk)
STEP3：若在边SCC中存在边(v1,v2),(v2,v3),……,(vk-1,vk)，则图G为半连通。
第22章 图的基本算法 22.4 拓扑排序
最后更新于：2022-04-01 07:36:10
# 一、综述
定义：对有向无回路图G=(V,E)进行须拓扑排序后，结果为该图所有顶点的一个线性序列，满足如果G包含边(u, v)，则在该序列中，u就出现在v的前面（如果图是有回路的，就不可能存在这样的线性序列）。
定理：一个有向图G是无回路图，当且仅当对G进行深度优先搜索时没有得到反向边。
# 二、代码
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_4.cpp
# 三、练习
### 22.4-1
t q u z w x v y r m s o n p
### 22.4-2
书上给的结果不对，psryv不通，因此是3条通路。
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/Exercise22_4_2.cpp
### 22.4-3
回路即反向边，只要不存在反向边，就没有回路
### 22.4-5
[算法导论-22.4-5-用队列实现拓扑排序](http://blog.csdn.net/mishifangxiangdefeng/article/details/7840091)
第22章 图算法 22.3 深度优先搜索
最后更新于：2022-04-01 07:36:07
# 一、综述
深搜策略：在深搜过程中，对于最新发现的顶点，如果它还有以此为起点的而未探测到的边，就沿此边继续探测下去。当顶点v的所有边都已被探测过后，搜索将回溯到发现顶点v有起始点的那些边。
时间戳：当顶点v第一次被发现时记录下第一个时间戳d[v]，当结束检查v的邻接表时，记录下第二个时间戳f[v]。v在d[v]时刻前是白色的，在时刻d[v]和f[v]之间是灰色的，在时刻f[v]之后是黑色的。
括号定理，后裔区间的嵌套，白色路径定理
边的分类：（1）树边（2）反向边（3）正向边（4）交叉边
对无向图G进行深度搜索时，G的每一条边，要么是树边，要么是反向边。
# 二、代码
### 1.Link_Graph.h
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter22/section22_3.cpp
### 2.main.cpp
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter22/section22_3Test.cpp
### 3.测试数据
书P335，图22-6
10 14
q s
s v
v w
w s
q w
q t
t y
y q
t x
x z
z x
u y
r y
r u
### 4.输出结果
见22.3-2
# 三、练习
### 22.3-1
关键是“任何时刻”
有向图
| | WHITE | GRAY | BLACK |
|-----|-----|-----|-----|
| WHITE | TBFC | BC | C |
| GRAY | TF | TFB | TFC |
| BLACK | | B | TFBC |
无向图
| | WHITE | GRAY | BLACK |
|-----|-----|-----|-----|
| WHITE | TB | TB | |
| GRAY | TB | TB | TB |
| BLACK | | TB | TB |
### 22.3-2
q:1 16
r:17 20
s:2 7
t:8 15
u:18 19
v:3 6
w:4 5
x:9 12
y:13 14
z:10 11
q->s: 树边
q->t: 树边
q->w: 正向边
r->u: 树边
r->y: 交叉边
s->v: 树边
t->x: 树边
t->y: 树边
u->y: 交叉边
v->w: 树边
w->s: 反向边
x->z: 树边
y->q: 反向边
z->x: 反向边
### 22.3-3
(u(v(y(xx)y)v)u)(w(zz))w)
### 22.3-6
[算法导论-22.3-6-用栈实现DFS](http://blog.csdn.net/mishifangxiangdefeng/article/details/7839628)
### 22.3-7
参考1楼所给的答案：
V={w,u,v}
E={(w,u), (u,w), (w,v)}
有一条从u到v的路径，即u->w->v
DFS的顺序为w,u,u,v,v,w，d[u]=2，d[v]=4，d[u]<d[v]
得到的森林中，u和v都是w的后裔
### 22.3-8
如图所示，（1）有一条从u到v的路径
### 22.3-9
貌似不用改
### 22.3-10
### 22.3-11
联通分支的数量用ceil表示，代码修改如下：
~~~
void Link_Graph::DFS()
{
int u, ceil = 0;
//对每个顶点初始化
for(u = 1; u <= n; u++)
{
V[u].color = WHITE;
V[u].p = NULL;
}
//时间戳初始化
time = 0;
//依次检索V中的顶点，发现白色顶点时，调用DFS_Visit访问该顶点
for(u = 1; u <= n; u++)
{
if(V[u].color == WHITE)
{
ceil++;
DFS_Visit(u, ceil);
}
}
}
void Link_Graph::DFS_Visit(int u, int ceil)
{
int v;
Edge *e;
//将u置为灰色
V[u].color = GRAY;
//使全局变量time增值
time++;
//将time的新值记录为发现时间
V[u].d = time;
e = V[u].head;
while(e)
{
v = e->end;
//如果顶点为白色
if(V[v].color == WHITE)
{
//递归访问顶点
V[v].p = u;
DFS_Visit(v, ceil);
//树边
e->type = TREE;
}
else if(V[v].color == GRAY)
{
//反向边
e->type = BACK;
}
else if(V[v].color == BLACK)
{
//正向边
if(V[u].d < V[v].d)
e->type = FORWARD;
//交叉边
else
e->type = CROSS;
}
e = e->next;
}
//以u为起点的所有边都被探寻后，置u为黑色
V[u].color = BLACK;
V[u].ceil = ceil;
//并将完成时间记录在f[u]中
time++;
V[u].f = time;
}
~~~
### 22.3-12
单连通图没有正向边
第22章 图算法 22.2 广度优先搜索
最后更新于：2022-04-01 07:36:05
# 一、综述
BFS蛮简单的，没什么好的综述的。
BFS算法的算法过程与它是有向图还是无向图没有关系，也与用邻接图还是用矩阵表示也没有关系。本文的代码是用邻接图实现的，例子是22-3的有向图。
用邻接矩阵实现的BFS见[算法导论-22.2-3-邻接矩阵实现图的广度优先搜索](http://blog.csdn.net/mishifangxiangdefeng/article/details/7837922)
# 二、代码
### 1.Link_Graph.h
~~~
#include <iostream>
#include <queue>
using namespace std;
#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
queue<int> Q;
struct Vertex;
struct Edge
{
int start;
int end;
int value;
Edge *next;
Edge(int s, int e, int v):start(s),end(e),value(v),next(NULL){}
};
struct Vertex
{
int color;
int d;
int Pie;
Edge *head;
Vertex():head(NULL),color(WHITE),d(0x7fffffff),Pie(0){};
};
class Link_Graph
{
public:
int n;
Vertex *V;
Link_Graph(int num):n(num)
{
V = new Vertex[n+1];
}
~Link_Graph(){delete []V;}
void AddSingleEdge(int start, int end, int value = 1)
{
Edge *NewEdge = new Edge(start, end, value);
if(V[start].head == NULL || V[start].head->end > end)
{
NewEdge->next = V[start].head;
V[start].head = NewEdge;
}
else
{
Edge *e = V[start].head, *pre = e;
while(e != NULL && e->end < end)
{
pre = e;
e = e->next;
}
if(e && e->end == end)
{
delete NewEdge;
return;
}
NewEdge->next = e;
pre->next = NewEdge;
}
}
void AddDoubleEdge(int a, int b, int value = 1)
{
AddSingleEdge(a, b, value);
AddSingleEdge(b, a, value);
}
void DeleteSingleEdge(int start, int end)
{
Edge *e = V[start].head, *pre = e;
while(e && e->end < end)
{
pre = e;
e = e->next;
}
if(e == NULL || e->end > end) return;
if(e == V[start].head)
V[start].head = e->next;
else
pre->next = e->next;
delete e;
}
void DeleteDoubleEdge(int a, int b)
{
DeleteSingleEdge(a, b);
DeleteSingleEdge(b, a);
}
//22.2
//广度优先搜索
void BFS(int s);
//广度优先树
void Print_Path(int s, int v);
};
void Link_Graph::BFS(int s)
{
int i;
for(i = 1; i <= n; i++)
{
V[i].color = WHITE;
V[i].d = 0x7fffffff;
V[i].Pie = 0;
}
V[s].color = GRAY;
V[s].d = 0;
V[s].Pie = 0;
while(!Q.empty())Q.pop();
Q.push(s);
while(!Q.empty())
{
int u, v;
u = Q.front();Q.pop();
Edge *e = V[u].head;
while(e)
{
v = e->end;
if(V[v].color == WHITE)
{
V[v].color = GRAY;
V[v].d = V[u].d + 1;
V[v].Pie = u;
Q.push(v);
}
e = e->next;
}
V[u].color = BLACK;
}
}
void Link_Graph::Print_Path(int s, int v)
{
BFS(s);
if(v == s)
cout<<s<<' ';
else
{
if(V[v].Pie == 0)
cout<<"no path from "<<s<<" to "<<v<<" exists.";
else
{
Print_Path(s, V[v].Pie);
cout<<v<<' ';
}
}
}
~~~
### 2.main.cpp
~~~
#include <iostream>
#include "Link_Graph.h"
using namespace std;
/*
1 2
1 5
2 6
6 7
6 3
3 7
3 4
7 8
7 4
4 8
*/
int main()
{
Link_Graph *G = new Link_Graph(8);
int i = 0, a, b;
for(i = 1; i <= 10; i++)
{
cin>>a>>b;
G->AddDoubleEdge(a,b);
}
G->BFS(2);
for(i = 1; i <= 8; i++)
cout<<G->V[i].d<<' ';
cout<<endl;
int s, v;
while(cin>>s>>v)
{
G->Print_Path(s, v);
cout<<endl;
}
return 0;
}
~~~
# 三、练习
### 22.2-1
d：2147483647 3 0 2 1 1
p：-1 4 -1 5 3 3
### 22.2-2
d：4 3 1 0 5 2 1 1
p：2 6 4 -1 1 3 4 4
### 22.2-3
[算法导论-22.2-3-邻接矩阵实现图的广度优先搜索](http://blog.csdn.net/mishifangxiangdefeng/article/details/7837922)
### 22.2-4
（1）原图：
（2）第一种邻接表顺序与对应的广度优先树
（3）第二种邻接表顺序与对应的广度优先树
### 22.2-5
这题的意思应该是举一种特殊的例子吧。
以上是一个有向图，令源顶点为s，带阴影的边组成一个边的集合e，e属于E。e满足对每一顶点v属于V，从s到v的唯一路径是G中的一条最短路径。
对G做BFS，无法产生边的集合e。
### 22.2-6
这道题第一反应是用并查集来解决，处理起来有点麻烦。后来发现用BFS也可以处理。
[算法导论 22.6 职业摔跤手](http://blog.csdn.net/mishifangxiangdefeng/article/details/8393722)
### 22.2-7
[算法导论-22.2-7-树的直径](http://blog.csdn.net/mishifangxiangdefeng/article/details/7838106)
### 22.2-8
感觉应该是深搜，但是这一节讲的是广搜，怎么用广搜解决这个问题呢？求想法.
使用DFS的解题方法见[算法导论 22.2-8 无向图遍历](http://blog.csdn.net/mishifangxiangdefeng/article/details/8395479)
第22章 图的基本算法 22.1 图的表示
最后更新于：2022-04-01 07:36:03
# 一、综述
图的表示方法通常有两种，即邻接表表示法和邻接矩阵表示法。这两种方法都可以表示有向图和无向图
### 1.邻接表表示法
（1）用邻接表表示无向图
（2）用邻接表表示有向图
（3）邻接表的优点及适用场合
使用邻接表表示稀疏图比较紧凑
### 2.邻接矩阵表示法
（1）用邻接矩阵表示无向图
（2）用邻接矩阵表示有向图
（3）邻接矩阵的优点与适用场合
用邻接矩阵表示稠密图可以很快地判别两个给定顶点是否存在邻接边
# 二、代码
### 1.邻接表表示法 "Link_Graph.h"
~~~
#include <iostream>
using namespace std;
#define N 100
struct Vertex;
struct Edge
{
int start;
int end;
int value;
Edge *next;
Edge(int s, int e, int v):start(s),end(e),value(v),next(NULL){}
};
struct Vertex
{
Edge *head;
Vertex():head(NULL){};
};
class Link_Graph
{
public:
int n;
Vertex *V;
Link_Graph(int num):n(num)
{
V = new Vertex[n+1];
}
~Link_Graph(){delete []V;}
void AddSingleEdge(int start, int end, int value = 1)
{
Edge *NewEdge = new Edge(start, end, value);
if(V[start].head == NULL || V[start].head->end > end)
{
NewEdge->next = V[start].head;
V[start].head = NewEdge;
}
else
{
Edge *e = V[start].head, *pre = e;
while(e != NULL && e->end < end)
{
pre = e;
e = e->next;
}
if(e && e->end == end)
{
delete NewEdge;
return;
}
NewEdge->next = e;
pre->next = NewEdge;
}
}
void AddDoubleEdge(int a, int b, int value = 1)
{
AddSingleEdge(a, b, value);
AddSingleEdge(b, a, value);
}
void DeleteSingleEdge(int start, int end)
{
Edge *e = V[start].head, *pre = e;
while(e && e->end < end)
{
pre = e;
e = e->next;
}
if(e == NULL || e->end > end) return;
if(e == V[start].head)
V[start].head = e->next;
else
pre->next = e->next;
delete e;
}
void DeleteDoubleEdge(int a, int b)
{
DeleteSingleEdge(a, b);
DeleteSingleEdge(b, a);
}
//22.1-1
void OutDegree();
void InDegree();
//22.1-2
void Print();
//22.1-3
Link_Graph* Reverse();
//22.1-5
Link_Graph* Square();
};
void Link_Graph::OutDegree()
{
int i, cnt = 0;
Edge *e;
for(i = 1; i <= n; i++)
{
cnt = 0;
e = V[i].head;
while(e)
{
cnt++;
e = e->next;
}
cout<<"顶点"<<i<<"的出度为"<<cnt<<endl;
}
}
void Link_Graph::InDegree()
{
int ret[N+1] = {0}, i;
Edge *e;
for(i = 1; i <= n; i++)
{
e = V[i].head;
while(e)
{
ret[e->end]++;
e = e->next;
}
}
for(i = 1; i <= n; i++)
cout<<"顶点"<<i<<"的入度为"<<ret[i]<<endl;
}
void Link_Graph::Print()
{
int i;
Edge *e;
for(i = 1; i <= n; i++)
{
cout<<i;
e = V[i].head;
while(e)
{
cout<<"->"<<e->end;
e = e->next;
}
cout<<endl;
}
}
Link_Graph* Link_Graph::Reverse()
{
Link_Graph *ret = new Link_Graph(n);
int i;
//遍历图G中的每一条边，以终点为起点，以起点为终点，加入到新图RET中
for(i = 1; i <= n; i++)
{
Edge *e = V[i].head;
while(e)
{
ret->AddSingleEdge(e->end, e->start);
e = e->next;
}
}
return ret;
}
Link_Graph* Link_Graph::Square()
{
int i;
Link_Graph *ret = new Link_Graph(n);
//遍历图中每个顶点
for(i = 1; i <= n; i++)
{
//遍历以该顶点为起点的边
Edge *e = V[i].head, *e2;
while(e)
{
//把原来有的边加入到新图中
ret->AddSingleEdge(e->start, e->end);
//把以E的终点为起点的边加入新图中
e2 = V[e->end].head;
while(e2)
{
ret->AddSingleEdge(e->start, e2->end);
e2 = e2->next;
}
e = e->next;
}
}
return ret;
}
~~~
### 2.邻接矩阵表示法
~~~
#include <iostream>
using namespace std;
#define N 100
class Mat_Graph
{
public:
int n;
int Map[N+1][N+1];
Mat_Graph(int num):n(num)
{
memset(Map, 0, sizeof(Map));
}
void AddDoubleEdge(int a, int b, int value = 1)
{
AddSingleEdge(a, b, value);
AddSingleEdge(b, a, value);
}
void AddSingleEdge(int start, int end, int value = 1)
{
Map[start][end] = value;
}
void DeleteDoubleEdge(int a, int b)
{
DeleteSingleEdge(a, b);
DeleteSingleEdge(b, a);
}
void DeleteSingleEdge(int start, int end)
{
Map[start][end] = 0;
}
//22.1-2
void Print();
//22.1-3
Mat_Graph* Reverse();
//22.1-5
Mat_Graph* Square();
//22.1-6
bool Universal_Sink();
};
void Mat_Graph::Print()
{
int i, j;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
cout<<Map[i][j]<<' ';
cout<<endl;
}
}
Mat_Graph* Mat_Graph::Reverse()
{
int i, j;
Mat_Graph *ret = new Mat_Graph(n);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
if(Map[i][j])
ret->AddSingleEdge(j, i);
}
return ret;
}
Mat_Graph* Mat_Graph::Square()
{
int i, j, k;
Mat_Graph *ret = new Mat_Graph(n);
//遍历图中每个顶点
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(Map[i][j])
{
//把原来有的边加入到新图中
ret->AddSingleEdge(i, j);
//把以E的终点为起点的边加入新图中
for(k = 1; k <= n; k++)
if(Map[j][k])
ret->AddSingleEdge(i, k);
}
}
}
return ret;
}
bool Mat_Graph::Universal_Sink()
{
//i指向有可能是汇的编号最小的点
int i = 1, j = 1;
while(j <= n)
{
//map[i][j] = 0,那么j没有i的入，一定不是汇，i可能是汇
if(Map[i][j] == 0)
j++;
//若map[i][j] = 1，则(1)i有出，i不是汇(2)map[i][i+1..j-1]=0，i+1..j-1都不是汇(3)j及j以后的点可能是汇
//若i=j，j也不是汇，j+1可能是汇
else if(i == j)
{
i++;
j++;
}
//若i!=j，j以前的点都不是汇，j可能是汇
else i = j;
}
//没有汇
if(i > n)
return false;
//找到有可能是汇的点，但是还是需要验证一下
else
{
//汇的纵向都是1，除了map[i][i]
for(j = 1; j <= i-1; j++)
{
if(Map[i][j] == 1)
return false;
}
//汇的横向都是0
for(j = 1; j <= n; j++)
if( i != j && Map[j][i] == 0)
return false;
return true;
}
}
~~~
###
3.main.cpp
~~~
#include <iostream>
using namespace std;
#include "Link_Graph.h"
#include "Mat_Graph.h"
void Test1()
{
cout<<"Test1"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
while(cin>>a>>b && a && b)//输入00时结束
LG->AddSingleEdge(a, b);
LG->OutDegree();
LG->InDegree();
delete LG;
}
void Test2()
{
cout<<"Test2"<<endl;
Link_Graph *LG = new Link_Graph(6);
Mat_Graph *MG = new Mat_Graph(6);
int edge[6][2] = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,6}};
int i = 0;
for(i = 0; i < 6; i++)
{
LG->AddSingleEdge(edge[i][0], edge[i][1]);
MG->AddSingleEdge(edge[i][0], edge[i][1]);
}
LG->Print();
MG->Print();
delete LG;
delete MG;
}
void Test3()
{
cout<<"Test3"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
Mat_Graph *MG = new Mat_Graph(n);
while(cin>>a>>b && a && b)//输入00时结束
{
LG->AddSingleEdge(a, b);
MG->AddSingleEdge(a, b);
}
Link_Graph *NewLG = LG->Reverse();
NewLG->Print();
Mat_Graph *NewMG = MG->Reverse();
NewMG->Print();
delete LG;
delete MG;
delete NewLG;
delete NewMG;
}
void Test5()
{
cout<<"Test5"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
Mat_Graph *MG = new Mat_Graph(n);
while(cin>>a>>b && a && b)//输入00时结束
{
LG->AddSingleEdge(a, b);
MG->AddSingleEdge(a, b);
}
Link_Graph *NewLG = LG->Square();
NewLG->Print();
Mat_Graph *NewMG = MG->Square();
NewMG->Print();
delete LG;
delete MG;
delete NewLG;
delete NewMG;
}
void Test6()
{
cout<<"Test6"<<endl;
int n, a, b;
cin>>n;
Mat_Graph *MG = new Mat_Graph(n);
while(cin>>a>>b && a && b)//输入00时结束
MG->AddSingleEdge(a, b);
if(MG->Universal_Sink())
cout<<"包含通用的汇"<<endl;
else
cout<<"不包含通用的汇"<<endl;
delete MG;
}
/*
6
1 2
1 4
4 2
2 5
5 4
3 5
3 6
6 6
0 0
*/
int main()
{
Test1();
Test2();
Test3();
Test5();
Test6();
return 0;
}
~~~
# 三、练习
22.1-1
计算出度的时间：E
计算入度的时间：E
~~~
void Test1()
{
cout<<"Test1"<<endl;
int n, a, b;
cin>>n;
Link_Graph *LG = new Link_Graph(n);
while(cin>>a>>b && a && b)//输入00时结束
LG->AddSingleEdge(a, b);
LG->OutDegree();
LG->InDegree();
delete LG;
}
~~~
22.1-2
~~~
void Test2()
{
cout<<"Test2"<<endl;
Link_Graph *LG = new Link_Graph(6);
Mat_Graph *MG = new Mat_Graph(6);
int edge[6][2] = {{1,2},{1,3},{2,4},{2,5},{3,6},{3,6}};
int i = 0;
for(i = 0; i < 6; i++)
{
LG->AddSingleEdge(edge[i][0], edge[i][1]);
MG->AddSingleEdge(edge[i][0], edge[i][1]);
}
LG->Print();
MG->Print();
delete LG;
delete MG;
}
~~~
邻接表表示：
1->2->3
2->4->5
3->6->7
4
5
6
7
矩阵表示：
0110000
0001100
0000011
0000000
0000000
0000000
0000000
22.1-3
邻接表表示的有向图的转置
~~~
Link_Graph* Link_Graph::Reverse()
{
Link_Graph *ret = new Link_Graph(n);
int i;
//遍历图G中的每一条边，以终点为起点，以起点为终点，加入到新图RET中
for(i = 1; i <= n; i++)
{
Edge *e = V[i].head;
while(e)
{
ret->AddSingleEdge(e->end, e->start);
e = e->next;
}
}
return ret;
}
~~~
邻接矩阵表示的有向图的转置
~~~
Mat_Graph* Mat_Graph::Reverse()
{
int i, j;
Mat_Graph *ret = new Mat_Graph(n);
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
if(Map[i][j])
ret->AddSingleEdge(j, i);
}
return ret;
}
~~~
22.1-4
遍历多重图中的每一条边，通过AddDoubleAdge()函数把它加入到另一个图中
22.1-5
邻接表表示的有向图的平方图
~~~
Link_Graph* Link_Graph::Square()
{
int i;
Link_Graph *ret = new Link_Graph(n);
//遍历图中每个顶点
for(i = 1; i <= n; i++)
{
//遍历以该顶点为起点的边
Edge *e = V[i].head, *e2;
while(e)
{
//把原来有的边加入到新图中
ret->AddSingleEdge(e->start, e->end);
//把以E的终点为起点的边加入新图中
e2 = V[e->end].head;
while(e2)
{
ret->AddSingleEdge(e->start, e2->end);
e2 = e2->next;
}
e = e->next;
}
}
return ret;
}
~~~
邻接矩阵表示的有向图的平方图
~~~
Mat_Graph* Mat_Graph::Square()
{
int i, j, k;
Mat_Graph *ret = new Mat_Graph(n);
//遍历图中每个顶点
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
if(Map[i][j])
{
//把原来有的边加入到新图中
ret->AddSingleEdge(i, j);
//把以E的终点为起点的边加入新图中
for(k = 1; k <= n; k++)
if(Map[j][k])
ret->AddSingleEdge(i, k);
}
}
}
return ret;
}
~~~
22.1-6
如果A[i, j] = 1，即(i, j)∈E（1≤i≤|V|，1≤j≤|V|，E是G的边集），那么顶点i就不可能是通用汇点，因为它有一条出边。
现在假设A[i, j] = 0，即(i, j)∉E，且i≠j。在这种情况下，顶点j就不可能是通用汇点，因为它的入度小于|V|-1
因此，这个问题等价于：给定一个有向图Ｇ的|V|×|V|邻接矩阵A，在O(|V|)时间内判断是否存在一个整数j（1≤j≤|V|），使得对于所有的i（1≤i≤|V|且i≠j）都有A[i, j] = 1，对于所有的k（1≤k≤|V|）都有A[j, k] = 0。更形象地说，就是判断A里面是否有这样一个“十”字：这“十”字的横全是0，竖全是1（除了“十”字的中心）。
~~~
bool Mat_Graph::Universal_Sink()
{
//i指向有可能是汇的编号最小的点
int i = 1, j = 1;
while(j <= n)
{
//map[i][j] = 0,那么j没有i的入，一定不是汇，i可能是汇
if(Map[i][j] == 0)
j++;
//若map[i][j] = 1，则(1)i有出，i不是汇(2)map[i][i+1..j-1]=0，i+1..j-1都不是汇(3)j及j以后的点可能是汇
//若i=j，j也不是汇，j+1可能是汇
else if(i == j)
{
i++;
j++;
}
//若i!=j，j以前的点都不是汇，j可能是汇
else i = j;
}
//没有汇
if(i > n)
return false;
//找到有可能是汇的点，但是还是需要验证一下
else
{
//汇的纵向都是1，除了map[i][i]
for(j = 1; j <= i-1; j++)
{
if(Map[i][j] == 1)
return false;
}
//汇的横向都是0
for(j = 1; j <= n; j++)
if( i != j && Map[j][i] == 0)
return false;
return true;
}
}
~~~
22.1-7
B = -BT
BBT = -B2
22.1-8
类似于邻接表与邻接矩阵的折中策略
第21章 用于不相交集合的数据结构
最后更新于：2022-04-01 07:36:00
# 一、综述
不相交集合数据结构（disjoint-set data struct）保持一组不相交的动态集合S={S1,S2,……,Sk}
这种数组结构支持三种操作：
（1）MAKE-SET(x)：构造一种只有元素x的集合
（2）UNION(x,y)：合并两个集合
（3）FIND-SET(x)：找出元素x所属的集合
# 二、代码
### 1.UnionFindSet.h
~~~
/*
UnionFindSet.h
并查集，非递归方法，含路径压缩，数组从0开始
*/
#include <iostream>
using namespace std;
#define MAXN 30005
class UFS
{
public:
int n;
int p[MAXN+1];//集合根结点
int rank[MAXN+1]; //集合中点的个数
public:
UFS(int size = MAXN);
void clear();
int Find_Set(int x);
//a并入b中，不区分大小
void Union(int x, int y);
void Make_Set(int x);
void Link(int x, int y);
};
UFS::UFS(int size):n(size)
{
//必须从0开始
for(int i = 0; i <= n; i++)
Make_Set(i);
}
void UFS::Make_Set(int x)
{
p[x] = x;
rank[x] = 0;
}
void UFS::clear()
{
for(int i = 0; i <= n; i++)
Make_Set(i);
}
int UFS::Find_Set(int x)
{
if(x != p[x])
p[x] = Find_Set(p[x]);
return p[x];
}
void UFS::Union(int x, int y)
{
Link(Find_Set(x), Find_Set(y));
}
void UFS::Link(int x, int y)
{
if(rank[x] > rank[y])
p[y] = x;
else
{
p[x] = y;
if(rank[x] == rank[y])
rank[y]++;
}
}
~~~
# 三、练习
### 21.1 不相交集合上的操作
21.1-1
~~~
Input:d i
Output:a b c e f g h i j k
Input:f k
Output:a b c e g h i j k
Input:g i
Output:a b c e h i j k
Input:b g
Output:a c e h i j k
Input:a h
Output:c e h i j k
Input:i j
Output:c e h i k
Input:d k
Output:c e h i
Input:b j
Output:c e h i
Input:d f
Output:c e h i
Input:g j
Output:c e h i
Input:a e
Output:c h i
Press any key to continue
~~~
21.1-3
FIND-SET 2|E|次
UNION |E|次
### 21.2 不相交集合的链表表示
21.2-1
~~~
void Make_Set(int x)
{
S[x].head = x;
S[x].tail = x;
S[x].size = 1;
n[x].rep = x;
n[x].next = 0;
}
int Find_Set(int x)
{
return n[x].rep;
}
void Union(int x, int y)
{
x = n[x].rep;
y = n[y].rep;
if(S[x].size >S[y].size)
swap(x, y);
n[S[y].tail].next = S[x].head;
S[y].size = S[y].size + S[x].size;
int i;
for(i = S[x].head; i != 0; i = n[i].next)
n[i].rep = y;
S[x].head = 0;
}
~~~
21.2-2
16
16
21.2-5
~~~
void Union2(int x, int y)
{
x = n[x].rep;
y = n[y].rep;
if(x == y)
return ;
if(S[x].size >S[y].size)
swap(x, y);
S[y].size = S[y].size + S[x].size;
int i;
for(i = S[x].head;; i = n[i].next)
{
n[i].rep = y;
if(n[i].next == 0)
{
n[i].next = n[S[y].head].next;
break;
}
}
n[S[y].head].next = S[x].head;
S[x].head = 0;
}
~~~
###
21.3 不相交集合森林
21.3-2
~~~
void UFS::Find_Set2(int x)
{
int ret = x, t;
while(ret != p[ret])
ret = p[ret];
while(p[x] != ret)
{
t = p[x];
p[x] = ret;
x = p[x];
}
}
~~~
21.3-3
题目的意思不懂
# 四、思考题
### 21-1脱机最小值
### 21-2深度确定
见[算法导论 第21章 21-2 深度确定](http://blog.csdn.net/mishifangxiangdefeng/article/details/8231652)
### 21-3Tarjan的脱机最小公共祖先算法
第20章 斐波那契堆
最后更新于：2022-04-01 07:35:58
# 一、综述
### 1.斐波那契堆
斐波那契堆是可合并堆
在不涉及删除的操作（除去EXTRACT和DELETE）中，操作仅需O(1)的平摊运行时间
当EXTRACT和DELETE的操作数目较小时斐波那契堆能得到较好的运行效率。
斐波那契堆不能有效地支持SEARCH操作
用于解决诸如最小生成树和寻找单源最短路径等问题的快速算法都要用到斐波那契堆。
### 2.斐波那契堆的结构
斐波那契堆由一组最小堆构成，这些最小堆是有根的无序树。
结点结构：
key: 关键字，作为排序、判断结点大小的标准
left, right：用于维护双链表，所有的根结点形成一个双链表，每个结点的孩子们形成双链表
parent, child : 维护父子关系
mark : 这个域与维护堆结构无关，只与具体的算法策略有关，不在这里讲
degree： 记录该结点有几个孩子
斐波那契堆
n：堆中结点的个数
min：批向最小的结点
### 3.可合并堆
引理19.1中给出的二项树的性质对无序二项树仍然成立P278
有n个结点FibHeap，结点的最大度数D(n) = lgn(向下取整)
将合并堆的操作尽可能地推后
### 4.最大度数的界
在一个包含n个结点的斐波那契堆中，结点的最大度数D(n)为O(lgn)
# 二、理解
### 1.延迟合并操作
FIB-HEAP-INSERT和FIB-HEAP-UNION只是最基础的链表合入操作，因为合并操作要尽可能地拖后
FIB-HEAP-EXTRACT-MIN除了要完成本职工作外，还要作合并调整
### 2.合并调整操作
CONSOLIDATE是作合并调整的函数
它将度数相同的根链接起来，直到对应每个度数至多只有一个根
遍历每一个根结点去判断，如果两个根结点的度是一样的，让大的结点作为小的结点的孩子
### 3.mark的作用
为了防止堆太宽，需要策略来调整堆，使根结点成为别的根结点的孩子，该策略就是CONSOLIDATE
同理，为了防止堆太深，也需要有相应的策略去调整，在适当的时候，把某个结点的孩子变成根
这一策略就是CUT和CASCADING-CUT，mark在实现这一策略的过程中起到辅助作用。
原理：当一个非根结点被切掉了2个孩子，就把它升为根结点
在删除一个结点时，怎么区分是第一个被删除的孩子，还是第二个？此时需要用mark来标记
### 4.P300那句话
因为翻译不好，严重影响理解
一旦第二个孩子也失掉后，x与其父结点之间的联系就被切断了，并成为一个新根。
原文：As soon as the second child has been lost, we cut x from its parent, making it a new root.
# 三、改进
### 1.命名
mark的命名不能体现它的作用，影响理解，如果换一个好一点的名字，就不用那么大段的文字去说明
外部函数不需要FIB-HEAP-这样的前缀，因为本来就是为它写的接口
内部函数的名字要说明函数的作用，因为内部函数是被自己调用的，不要给自己添麻烦
### 2.分解函数
提取了一些对双链表的常用操作
### 3.合并函数
CUT和CASCADING-CUT合并成一个函数，因为它们其实是一个功能，就是根据策略把孩子结点升为根结点
### 4.参数和返回值
CUT和CASCADING-CUT中的x和y是父子关系，而且重点是子，父是只为了方便处理，不需要作为参数传进来，在函数里面重新获取一个就可以了。多传一个函数，就一个出错源
对于带参数的函数，增加一返回值。用于告知调用者是否成功，或什么原因导致失败
### 5.功能
FIB-HEAP-DECREASE-KEY和FIB-HEAP-DELETE这两个函数作用不大。
因为它们的入参是node*。要想调用这两个函数，就必须先获取目标结点的指针。
可是没有一个接口返回指向结点的指针，怎么找到我的目标结点的指针呢？
调用者必须自己在创建结点后保持这个结点，这样不合理
# 四、代码
### 1.[FibHeap.h](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter20/FibHeap.h)
### 2.[FibHeap.cpp](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter20/FibHeap.cpp)
### 3.[测试用例](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter20/FibHeapTest.cpp)
# 五、习题
### 20.1斐波那契堆
### 20.2可合并堆
### 20.2-1
### 20.2-4
McGee和FibHeap的区别在于合并的时机。
Fibheap认为合并调整应该尽量地推迟，而McGee则在每次堆中结点有增加的时候就作合并调整。
个人认为，合并调整操作的意义是防止堆过宽而影响性能。但是从算法过程上看，根结点的个数多少不会影响INSERT和UNION的性能，因此没有必要。
比较认可FibHeap的做法。
### 20.3减小一个关键字与删除一个结点
### 20.3-1
根据P300的描述，只有非根结点才可能被打上标记，如果根结点有标记，一定是它是非根结点的时候打上标记，然后被移到根结点的位置。
把结点移至根结点是通过上面代码中的函数addNodeToRootList和addListToRootList完成的，目标缩小至这两个函数周围
让根结点成为有标记结点，须满足以下两个条件
（1）调用这两个函数前，该结点是非根结点
（2）调用后没有清标记
结论：x是pMinData的孩子，根据P300的步骤被打上标记后，执行extract()时又成为根结点
### 20.4最大度的界
# 四、思考题
### 20-1删除的另一种实现
把FIB-HEAP-DELETE中的两个函数展开，再和PISANO-DELETE对比，并附上x不是min[H]的假设，可以发现这两个函数执行的操作基本上是一样的，区别在于
（1）PISANO-DELETE中去掉了FIB-HEAP-DELETE中多余的判断，不影响效率
（2）FIB-HEAP-DELETE在删掉结点之后有合并调整的动作
a)add x's child list to the root list of H的时间不是O(1)，因为每个child都有一个pParent指针，必须依次修改每个child的指针
### 20-2其它斐波那契堆的操作
a)
（1）k < key[x]的情况，直接调用FIB-HEAP-DECREASE-KEY
（2）k = key[x]的情况，不用处理
（3）k > key[x]的情况，交换它与它孩子的内容，但是指针保持不变，直到符合最小堆的情况，时间与堆的深度有关
b)
以我有限的智商，只能想到执行min(r, n[H])次EXTRACT
第19章-二项堆
最后更新于：2022-04-01 07:35:56
# 一、概念
### 1.可合并堆
（1）可合并堆应支持的操作
MAKE-HEAP()
INSERT(H, x)
MINIMUM(H)
EXTRACT-MIN(H)
UNION(H1, H2)
（2）二项堆是一种可合并堆
### 2.二项树
### （1）二项树的定义
二项树是Bk一种递归定义的有序树
B0只包含一个结点
Bk(k>0)由两棵二项树B|k-1连接而成，其中一棵作为另一棵的左孩子
### （2）二项树Bk的性质
a.共有2^k个结点
b.树的高度为k
c.在深度i处恰有C(i, k)个结点
d.树的度数为k，它大于任何其它结点的度；并且，如果根的子女从左到右编号为k-1, k-1, ……, 0，子女i是子树Bi的根
### （3）二项树的结构
用左孩子用兄弟的方法表示二项树
### （4）二项树的举例
### 3.二项堆
### （1）二项堆的定义与性质
### （2）二项堆的结构
### （3）二项堆提供的操作
# 二、代码
### Binomial_Heap.h
~~~
#include <iostream>
using namespace std;
//二项堆结点结构
struct node
{
int key;//关键字
int data;//卫星数据
node *p;//指向父结点的指针，父或左兄
node *child;//指向左孩子的指针
node *sibling;//指向右兄弟的指针
int degree;//度
//初始化
node(int n, node *nil):key(n),p(nil),child(nil),sibling(nil),degree(0){}
};
//二项堆结构
class Binomial_Heap
{
public:
node *head;
node *nil;
//构造函数
Binomial_Heap(){nil = new node(-1, nil);}
Binomial_Heap(node *NIL){nil = NIL;}
//19.2
void Make_Binomial_Heap();
node* Binomial_Heap_Minimum();
void Binomial_Link(node *y, node *z);
node *Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2);
void Binomial_Heap_Union(Binomial_Heap *H2);
void Binomial_Heap_Insert(node *x);
node* Binomial_Heap_Extract_Min();
void Binomial_Heap_Decrease_Key(node *x, int k);
void Binomial_Heap_Delete(node *x);
};
//构造一个空的二项堆
void Binomial_Heap::Make_Binomial_Heap()
{
//初始化对象
head = nil;
}
//寻找最小关键字
node* Binomial_Heap::Binomial_Heap_Minimum()
{
//最小关键字一定位于某个二项树的根结点上
node *x = head, *y = nil;
int min = 0x7fffffff;
//遍历每个二项树的根结点
while(x != nil)
{
//找出最小值
if(x->key < min)
{
min = x->key;
y = x;
}
x = x->sibling;
}
return y;
}
//将以结点y为根的树与以结点z为根的树连接起来，使z成为y的父结点
void Binomial_Heap::Binomial_Link(node *y, node *z)
{
//只是按照定义修改指针
y->p = z;
y->sibling = z->child;
z->child = y;
//增加度
z->degree++;
}
//将H1和H2的根表合并成一个按度数的单调递增次序排列的链表
//不带头结点的单调链表的合并，返回合并后的头，不需要解释
node *Binomial_Heap::Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2)
{
node *l1 = H1->head, *l2 = H2->head, *ret = nil, *c = ret, *temp;
while(l1 != nil && l2 != nil)
{
if(l1->degree <= l2->degree)
temp = l1;
else
temp = l2;
if(ret == nil)
{
ret = temp;
c = ret;
}
else
{
c->sibling = temp;
c = temp;
}
if(l1 == temp)l1 = l1->sibling;
else l2 = l2->sibling;
}
if(l1 != nil)
{
if(ret == nil)
ret = l1;
else
c->sibling = l1;
}
else
{
if(ret == nil)
ret = l2;
else
c->sibling = l2;
}
delete H2;
return ret;
}
//将两个二项堆合并
void Binomial_Heap::Binomial_Heap_Union(Binomial_Heap *H2)
{
//H是合并结点，用于输出
Binomial_Heap *H = new Binomial_Heap(nil);
H->Make_Binomial_Heap();
Binomial_Heap *H1 = this;
//将H1和H2的根表合并成一个按度数的单调递增次序排列的链表，并放入H中
H->head = Binomial_Heap_Merge(H1, H2);
//free the objects H1 and H2 but not the lists they point to
//如果H为空，直接返回
if(H->head == nil)
return;
//将相等度数的根连接起来，直到每个度数至多一个根时为止
//x指向当前被检查的根，prev-x指向x的前面一个根，next-x指向x的后一个根
node *x = H->head, *prev_x = nil, *next_x = x->sibling;
//根据x和next-x的度数来确定是否把两个连接起来
while(next_x != nil)
{
//情况1：度数不相等
if(x->degree != next_x->degree ||
//情况2：x为具有相同度数的三个根中的第一个
(next_x->sibling != nil && next_x->sibling->degree == x->degree))
{
//将指针指向下一个位置
prev_x = x;
x = next_x;
}
//情况3：x->key较小，将next-x连接到x上，将next-x从根表中去掉
else if(x->key <= next_x->key)
{
//去掉next-x
x->sibling = next_x->sibling;
//使next-x成为x的左孩子
Binomial_Link(next_x, x);
}
//情况4：next-x->key关键字较小，x被连接到next-x上
else
{
//将x从根表中去掉
if(prev_x == nil)//x是根表中的第一个根
H->head = next_x;
else//x不是根表中的第一个根
prev_x->sibling = next_x;
//使x成为next-x的最左孩子
Binomial_Link(x, next_x);
//更新x以进入下一轮迭代
x = next_x;
}
next_x = x->sibling;
}
head = H->head;
}
//将结点x插入到二项堆H中
void Binomial_Heap::Binomial_Heap_Insert(node *x)
{
//构造一个临时的二项堆HH，只包含一个结点x
Binomial_Heap *HH = new Binomial_Heap;
HH->Make_Binomial_Heap();
x->p = nil;
x->child = nil;
x->sibling = nil;
x->degree = 0;
HH->head = x;
//将H与HH合并，同时释放HH
Binomial_Heap_Union(HH);
}
//抽取具有最小关键字的结点
node* Binomial_Heap::Binomial_Heap_Extract_Min()
{
//最小关键字一定位于某个二项树的根结点上
node *x = head, *y = nil, *ret;
int min;
if(x == nil)
{
//cout<<"empty"<<endl;
return nil;
}
min = x->key;
//1.find the root x with the minimum key in the root list of H,
//遍历每个二项树的根结点，为了删除这个结点，还需要知道x的前一个根结点
while(x->sibling != nil)
{
//找出最小值
if(x->sibling->key < min)
{
min = x->sibling->key;
y = x;
}
x = x->sibling;
}
ret = x;
//1.and remove x from the root list of H
//删除结点分为两个情况，结点是二项堆中的第一个树，删除结点后，结点的child保存到temp中
node *temp = NULL;
if(y == nil)
{
x = head;
temp = x->child;
head = x->sibling;
}
//结点不是二项堆中的第一个树
else
{
x = y->sibling;
y->sibling = x->sibling;
temp = x->child;
}
//2.
//设待删除结点是二项树T的根，那么删除这个结点后，T变成了一个二项堆
Binomial_Heap *HH = new Binomial_Heap(nil);
HH->Make_Binomial_Heap();
//3.reverse the order of the linked list of x'childern,setting the p field of each child to NIL, and set head[HH] to point to the head of the resulting list
//正常情况下，二项堆中的树的度从小到大排。此时HH中的树的度是从大到排的，因此要对HH中的树做一个逆序
node *p;
while(temp != nil)
{
p = temp->sibling;
temp->sibling = HH->head;
HH->head = temp;
temp->p = nil;
temp = p;
}
//4.
//原二项堆H删除二项树T后成为新二项堆H，二项树T删除根结点后变成新二项堆HH
//将H和HH合并
Binomial_Heap_Union(HH);
return x;
}
//将二项堆H中的某一结点x的关键字减小为一个新值k
void Binomial_Heap::Binomial_Heap_Decrease_Key(node *x, int k)
{
//引发错误
if(k > x->key)
{
cout<<"new key is greater than current key"<<endl;
return ;
}
//与二叉最小堆中相同的方式来减小一个关键字，使该关键字在堆中冒泡上升
x->key = k;
node *y = x, *z = y->p;
while(z != nil && y->key < z->key)
{
swap(y->key, z->key);
swap(y->data, z->data);
y = z;
z = y->p;
}
}
//删除一个关键字
void Binomial_Heap::Binomial_Heap_Delete(node *x)
{
//将值变为最小，升到堆顶
Binomial_Heap_Decrease_Key(x, -0x7fffffff);
//删除堆顶元素
Binomial_Heap_Extract_Min();
}
~~~
### main.cpp
~~~
#include <iostream>
using namespace std;
#include "Binomial_Heap.h"
int main()
{
char ch;
int n;
//生成一个空的二项堆
Binomial_Heap *H = new Binomial_Heap;
H->Make_Binomial_Heap();
//各种测试
while(cin>>ch)
{
switch (ch)
{
case 'I'://插入一个元素
{
cin>>n;
node *x = new node(n, H->nil);
H->Binomial_Heap_Insert(x);
break;
}
case 'M'://返回最小值
{
node *ret = H->Binomial_Heap_Minimum();
if(ret == H->nil)
cout<<"empty"<<endl;
else
cout<<ret->key<<endl;
break;
}
case 'K'://更改某个关键字的值，使之变小
{
//因为没有Search函数，只能对最小值的结点进行测试
node *ret = H->Binomial_Heap_Minimum();
if(ret == H->nil)
cout<<"empty"<<endl;
else
{
cin>>n;
H->Binomial_Heap_Decrease_Key(ret, n);
}
break;
}
case 'E'://提取关键字最小的值并从堆中删除
{
H->Binomial_Heap_Extract_Min();
break;
}
case 'D'://删除某个结点
{
node *ret = H->Binomial_Heap_Minimum();
if(ret == H->nil)
cout<<"empty"<<endl;
else
H->Binomial_Heap_Delete(ret);
break;
}
}
}
return 0;
}
~~~
# 三、练习
### 19.1二项树与二项堆
~~~
19.1-1
x不是根，则degree[sibling[x]] < degree[x]
x是根，则degree[sibling[x]] > degree[x]
19.1-2
degree[p[x]] > degree[x]
~~~
### 19.2对二项堆的操作
19.2-1
木有伪代码，直接看代码
~~~
//将H1和H2的根表合并成一个按度数的单调递增次序排列的链表
//不带头结点的单调链表的合并，返回合并后的头，不需要解释
node *Binomial_Heap::Binomial_Heap_Merge(Binomial_Heap *H1, Binomial_Heap *H2)
{
node *l1 = H1->head, *l2 = H2->head, *ret = nil, *c = ret, *temp;
while(l1 != nil && l2 != nil)
{
if(l1->degree <= l2->degree)
temp = l1;
else
temp = l2;
if(ret == nil)
{
ret = temp;
c = ret;
}
else
{
c->sibling = temp;
c = temp;
}
if(l1 == temp)l1 = l1->sibling;
else l2 = l2->sibling;
}
if(l1 != nil)
{
if(ret == nil)
ret = l1;
else
c->sibling = l1;
}
else
{
if(ret == nil)
ret = l2;
else
c->sibling = l2;
}
delete H2;
return ret;
}
~~~
19.2-2
19.2-3
19.2-5
如果可以将关键字的值置为正无穷，BINOMIAL-HEAP-MINIMUM将无法区分二项堆为空和最小关键字为无穷大这两种情况，只需在返回加以区分即可
~~~
BINOMIAL-HEAP-MINIMUM(H)
1 y <- NIL
2 x <- head[H]
3 min <- 0x7fffffff
4 while x != NIL
5 do if key[x] < min
6 then min <- key[x]
7 y <- x
8 x <- sibling[x]
9 if min = 0x7fffffff and head[H] != NIL
10 then return head[H]
11 return y
~~~
19.2-6
不需要表示-0x7fffffff，只要比最小值小就可以了
~~~
BINOMIAL-HEAP-DELETE(H)
1 y <- BINOMIAL-HEAP-MINIMUM(H)
2 BINOMIAL-HEAP-DECREASE-KEY(H, x, key[y]-1)
3 BINOMIAL-HEAP-EXTRACT-MIN(H)
~~~
19.2-7
将一个二项堆H与一个二进制数x对应，对应方式x=func(H)为：
若H中有一棵二项树的根的度数为k，则将x的第k为置1。
（1）令一个二项堆H1有x1=func(H1)，在H1上插入一个结点后变为H2，有x2=func(H2)，则x2=x1+1
（2）令两个二项堆H1、H2，H1、H2合并后为二项堆H3，，有x1=func(H1)、x2=func(H2)、x3=func(H3)，则x1+x2=x3
19.2-8
待解决
# 四、思考题
### 19-1 2-3-4堆
求思路
### 19-2 采用二项堆的最小生成树算法
见[算法导论 19-2 采用二项堆的最小生成树算法](http://blog.csdn.net/mishifangxiangdefeng/article/details/8184470)
第18章 B树
最后更新于：2022-04-01 07:35:54
# 一、定义
### 1、B树
B树是为磁盘或其它直接存取辅助存储设备而设计的一种平衡查找树，主要特点是降低磁盘I/O操作次数。
B树以自然的方式推广二叉查找树。
B树的分支因子由磁盘特性所决定。
### 2、B数的数据结构
int n：当前存储在结点x中的关键字数
key[N]：n个关键，以非降序存放
bool leaf;//TRUE:x是叶子；FALSE:x是内结点
node *child[N+1]：只有内结点才有。指向其n+1个孩子的指针。child[1].key <= key[1] <= child[2].key……
### 3.B树的特征
（1）只有内结点才有指向子女的指针，且child[1].key <= key[1] <= child[2].key……
（2）每个叶结点具有相同的深度
（3）分支因子t>=2
（4）每个非根结点至少有t-1个关键字，如果是内结点，至少有t个子女
（5）每个结点至多有2t-1个关键字，如果是内结点，到多有2t个子女
### 4.B树上的操作
B-Tree-Search(x, k)
B-Tree-Create(T)
B-Tree-Split-Child(x,i,y)
B-Tree-Insert(T,k)
B-Tree-Insert-Nonfull(x,k)
B-Tree-Delete(T,x)
# 二、代码
### B_Tree.h
~~~
#include <iostream>
using namespace std;
#define N 10
int t = 2;
//B树结点结构
struct node
{
int n;//当前存储在结点x中的关键字数
char key[N];//n个关键字，以非降序存放
bool leaf;//TRUE:x是叶子；FALSE:x是内结点
node *child[N+1];//指向其n+1个孩子的指针
//构造函数
node(int num, bool IsLeaf):n(num),leaf(IsLeaf){}
//磁盘读写操作
void Disk_Read(){}
void Disk_Write(){}
};
//B树结构
class B_Tree
{
public:
//指向根结点
node *root;
B_Tree():root(NULL){}
//从以x为根结点的树中寻找关键字为k的结点，若找到，将结果存入y中，返回其是第几个关键字
int B_Tree_Search(node *x, char k, node&y);
//构造一棵带树结点的空树
void B_Tree_Create();
//分裂，把y分裂为两个结点，选择其中一个关键字插入到x中的第i个位置
void B_Tree_Split_Child(node *x, int i, node *y);
//将关键字k插入到一个未满的结点x中
void B_Tree_Insert_Nonfull(node *x, char k);
//向T中插入关键字k
void B_Tree_Insert(char k);
//删除T树中关键字为k的结点，由于是递归方法，当前处理的是x结点
void B_Tree_Delete(node *x, char k);
//按关键字从小到大输出结点
void Print(node *n);
};
//从以x为根结点的树中寻找关键字为k的结点，若找到，将结果存入y中，返回其是第几个关键字
int B_Tree::B_Tree_Search(node *x, char k, node&y)
{
int i = 1;
//找到第一个关键字不大于k的i
while(i < x->n && k > x->key[i])
i++;
//若key[i] = k，则找到了
if(i <= x->n && k == x->key[i])
{
//将结果存入y中
y = *x;
//返回其是第几个关键字
return i;
}
//若没找到，则返回空
if(x->leaf)
{
// &y = NULL;
return 0;
}
//若还有子树可以找，则递归查找第i个子树
x->child[i]->Disk_Read();
return B_Tree_Search(x->child[i], k, y);
}
//构造一棵带树结点的空树
void B_Tree::B_Tree_Create()
{
//生成一个根结点
//初始时，根结点为叶子结点，根结点中没有关键字
root = new node(0, true);
root->Disk_Write();
}
//分裂，把y分裂为两个结点，选择其中一个关键字插入到x中的第i个位置
void B_Tree::B_Tree_Split_Child(node *x, int i, node *y)
{
int j;
//生成一个新结点z
//要把y分裂为y和z，因此z的叶子属性与y相同
//分裂前y有2t-1个关键字，分裂后前t-1个属于y，后t-1个属于z，中间第t个属于x
node *z = new node(t-1, y->leaf);
y->n = t - 1;
//后t-1个关键字依次复制给z
for(j = 1; j < t; j++)
z->key[j] = y->key[j+t];
//如果有孩子，孩子也要复制过去，原来有2t个子树，前t个属于y，后t个属于z
if(y->leaf == false)
{
for(j = 1; j <= t; j++)
z->child[j] = y->child[j+t];
}
//使z作为x的第i+1个孩子(y已经是x的第i个孩子)
for(j = x->n+1; j > i; j--)
x->child[j+1] = x->child[j];
x->child[i+1] = z;
//把y中第t个关键字插入到x的第i个位置
for(j = x->n; j >= i; j--)
x->key[j+1] = x->key[j];
x->key[i] = y->key[t];
//x的关键字+1
x->n++;
y->Disk_Write();
z->Disk_Write();
x->Disk_Write();
}
//将关键字k插入到一个未满的结点x中
void B_Tree::B_Tree_Insert_Nonfull(node *x, char k)
{
int i = x->n;
//若x是叶子结点
if(x->leaf)
{
//找到该插入的位置
while(i >= 1 && k < x->key[i])
{
x->key[i+1] = x->key[i];
i--;
}
//插入关键字k
x->key[i+1] = k;
x->n++;
x->Disk_Write();
}
//若不是叶子结点
else
{
//找到该插入的位置
while(i >= 1 && k < x->key[i])
i--;
i++;
//读取其孩子，将关键字插入到它的孩子中，分两种情况
x->child[i]->Disk_Read();
//孩子已满
if(x->child[i]->n == 2 * t - 1)
{
//对孩子执行分裂操作，分裂后，孩子不变为不满
B_Tree_Split_Child(x, i, x->child[i]);
if(k > x->key[i])
i++;
}
//孩子不满，直接对孩子进行插入操作
B_Tree_Insert_Nonfull(x->child[i], k);
}
}
//向T中插入关键字k
void B_Tree::B_Tree_Insert(char k)
{
node *r = root, *s;
//若根结点已满
if(r->n == 2*t-1)
{
//申请一个新的结点,将新的结点作为根结点
root = new node(0, false);
root->child[1] = r;
//将原根结点分裂为两个结点，分别作为s的第0个孩子和第1个孩子
B_Tree_Split_Child(root, 1, r);
//把关键字k插入到根结点中，此时根结点一定不满
B_Tree_Insert_Nonfull(root, k);
}
//若根结点不满
else
//直接把关键字插入到根结点中
B_Tree_Insert_Nonfull(r, k);
}
//删除T树中关键字为k的结点，由于是递归方法，当前处理的是x结点
void B_Tree::B_Tree_Delete(node *x, char k)
{
int i, j;
//找到x中第一个不小于k的关键字，即待处理的位置
for(i = 1; i <= x->n; i++)
if(x->key[i] >= k)
break;
//y是关键字k之前的结点,即小于k的最大孩子
//z是关键字k之后的结点,即大于k的最小孩子
node *y = x->child[i], *z = x->child[i+1], *d;
//若关键字k在结点x中的第i个位置
if(x->key[i] == k && i <= x->n)
{
//1)y是叶子结点，则直接从x中删除k
if(x->leaf == true)
{
//关键字依次前移
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//关键字数-1
x->n--;
return;
}
//2)x是内结点
//2-a：x中前于k的子结点y包含至少t个关键字
if(y->n >= t)
{
//找出k在以y为根的子树中的前驱d
d = y;
while(d->leaf == false)
d = d->child[d->n+1];
//用d取代k
x->key[i] = d->key[d->n];
//递归地删除d
B_Tree_Delete(y, d->key[d->n]);
}
//2-b：x是位于k之后的子结点z包含至少t个关键字
else if(z->n >= t)
{
//找出k在以z为根的子树中的后继d
d = z;
while(d->leaf == false)
d = d->child[1];
//用d取代k
x->key[i] = d->key[1];
//递归地删除d
B_Tree_Delete(z, d->key[1]);
}
//2-c：y和z都只有t-1个关键字，将k和z中所有关键字合并进y，使得x失去k和指向z的指针
else
{
//将k关键字合并进y
y->key[y->n+1] = k;
//将z中所有关键字合并进y
for(j = 1; j <= z->n; j++)
y->key[y->n+j+1] = z->key[j];
//如果有孩子，孩子也要合并
if(y->leaf == false)
{
//使得x指向z的指针
for(j = 1; j <= z->n+1; j++)
y->child[y->n+j+1] = z->child[j];
}
//y包含2t-1个关键字
y->n = y->n + 1 + z->n;
//使得x失去k
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//使x失去指向z的指针
for(j = i+1; j <= x->n; j++)
x->child[j] = x->child[j+1];
x->n--;
//如果x是根结点，x
if(x->n == 0 && root == x)
root = y;
//释放z
delete z;
//将k从y中递归删除
B_Tree_Delete(y, k);
}
}
//3)关键字不在结点x中，则必定包含k的正确的子树的根x->child[i]
else
{
//x是叶子结点,找到根结点都没有找到k，则k不在树中
if(x->leaf == true)
{
cout<<"error:not exist"<<endl;
return;
}
//x是内结点
//3-a:child[i]中只有t-1个关键字
if(y->n == t-1)
{
//它的相邻兄弟x->child[i+1](用z表示)包含至少t个关键字
if(i <= x->n && i <= x->n && z->n >= t)
{
//将x中的关键字下降至y
y->n++;
y->key[y->n] = x->key[i];
//将z的某一关键字上升至x
x->key[i] = z->key[1];
for(j = 1; j < z->n; j++)
z->key[j] = z->key[j+1];
//将z适合的子女指针移到y
if(y->leaf == false)
{
y->child[y->n+1] = z->child[1];
for(j = 1; j <= z->n; j++)
z->child[j] = z->child[j+1];
}
//z的关键字数-1
z->n--;
}
//它的相邻兄弟x->child[i-1]包含至少t个关键字
else if(i > 1 && x->child[i-1]->n >= t )
{
//将x中的关键字下降至y
for(j = y->n; j >= 1; j--)
y->key[j+1] = y->key[j];
y->key[1] = x->key[i-1];
y->n++;
//将y的相邻兄弟x->child[i-1]的某一关键字上升至x
x->key[i-1] = x->child[i-1]->key[x->child[i-1]->n];
//将该兄弟适合的子女指针移到y
if(y->leaf == false)
{
for(j = y->n; j >= 1; j--)
y->child[j+1] = y->child[j];
y->child[1] = x->child[i-1]->child[x->child[i-1]->n+1];
}
//x->child[i-1]的关键字数-1
x->child[i-1]->n--;
}
//y和其所有相邻兄弟都只有t-1个关键字，则与其中一个兄弟合并
else
{
//与后面一个结点(用z表示)合并
if(i <= x->n)
{
//将x->key[i]并入y中
y->key[y->n+1] = x->key[i];
//将z中所有关键字并入y中
for(j = 1; j <= z->n; j++)
y->key[j+y->n+1] = z->key[j];
//如果有孩子，所有孩子也要并入
if(y->leaf == false)
{
for(j = 1; j <= z->n+1; j++)
y->child[j+y->n+1] = z->child[j];
}
//修改y的关键字数
y->n = y->n + 1 + z->n;
//将x->key[i]从x中移出
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//把指向z的指针从x->child中移出
for(j = i+1; j <= x->n; j++)
x->child[j] = x->child[j+1];
//x的关键字数-1
x->n--;
//若根结点被删除，更新根结点
if(x->n==0 && root == x)
root = y;
}
//与前面一个结点合并
else
{
//令z=x->child[i-1],y=x->child[i]，把z并入y中
z = y;i--;
y = x->child[i];
//将x->key[i]并入y中
y->key[y->n+1] = x->key[i];
//将z中所有关键字并入y中
for(j = 1; j <= z->n; j++)
y->key[j+y->n+1] = z->key[j];
//如果有孩子，所有孩子也要并入
if(y->leaf == false)
{
for(j = 1; j <= z->n+1; j++)
y->child[j+y->n+1] = z->child[j];
}
//修改y的关键字数
y->n = y->n + 1 + z->n;
//将x->key[i]从x中移出
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//把指向z的指针从x->child中移出
for(j = i+1; j <= x->n; j++)
x->child[j] = x->child[j+1];
//x的关键字数-1
x->n--;
//若根结点被删除，更新根结点
if(x->n==0 && root == x)
root = y;
}
}
}
//递归执行删除操作
B_Tree_Delete(y, k);
}
}
//按关键字从小到大输出结点
void B_Tree::Print(node *n)
{
int i;
for(i = 1; i <= n->n; i++)
{
if(n->leaf == false)
Print(n->child[i]);
cout<<n->key[i]<<' ';
}
if(n->leaf == false)
Print(n->child[n->n+1]);
}
~~~
### main.cpp
~~~
#include <iostream>
using namespace std;
#include "B_Tree.h"
int main()
{
//测试数据
char ch[] = {'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E'};
//生成一棵B树
B_Tree *T = new B_Tree;
T->B_Tree_Create();
//依次插入关键字
cout<<"插入测试"<<endl;
int i;
for(i = 0; i < 21; i++)
{
T->B_Tree_Insert(ch[i]);
T->Print(T->root);
cout<<endl;
}
//输出这棵树
T->Print(T->root);
cout<<endl;
//B树删除操作测试
cout<<"查找与删除测试"<<endl;
char c;
for(i = 0; i < 100; i++)
{
cin>>c;
T->B_Tree_Delete(T->root, c);
T->Print(T->root);
cout<<endl;
}
return 0;
}
~~~
# 三、练习
### 18.1B树的定义
18.1-1
若t=1，树中的结点最少有0个关键字，就没有意义了
18.1-2
t=2
18.1-3
[http://zh.clrs-ans.wikia.com/index.php?title=18.1_B%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89&variant=zh-cn](http://zh.clrs-ans.wikia.com/index.php?title=18.1_B%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89&variant=zh-cn)
18.1-4
2^(2t)-1
18.1-5
没看懂题目
### 18.2对B树的基本操作
18.2-1
18.2-2
待解决
[http://bbs.csdn.net/topics/390279127](http://bbs.csdn.net/topics/390279127)
18.2-3
类似于红黑树中的找前驱和后继的操作
~~~
//若要找x->key[i]的前驱d
d = x->child[i];
while(d->leaf == false)
d = d->child[d->n+1];
~~~
~~~
//若要找x->key[i]的后继d
d = x->child[i+1];
while(d->leaf == false)
d = d->child[1];
~~~
18.2-4
在网上找了份答案 说是 至少n - 2lg（N） - 2个节点 没有解答！ 总之渐进意义上说 是n个 没必要太纠结与细节
没想到怎么求，写了个程序来计算，依次插入1-n，每分裂一次就cnt+1
~~~
#include <iostream>
using namespace std;
#define N 10
int t = 2, cnt;
//B树结点结构
struct node
{
int n;//当前存储在结点x中的关键字数
int key[N];//n个关键字，以非降序存放
bool leaf;//TRUE:如果x是叶子FALSE:内结点
node *child[N+1];//指向其n+1个孩子的指针
};
//B树结构
struct B_Tree
{
//指向根结点
node *root;
};
//磁盘读写操作
void Disk_Read(node *x){}
void Disk_Write(node *x){}
//构造一棵带树结点的空树
void B_Tree_Create(B_Tree *T)
{
//生成一个根结点
node *x = new node;
//初始时，根结点为叶子结点
x->leaf = true;
//初始时，根结点中没有关键字
x->n = 0;
Disk_Write(x);
T->root = x;
cnt = 1;
}
//分裂，把y分裂为两个结点，选择其中一个关键字插入到x中的第i个位置
void B_Tree_Split_Child(node *x, int i, node *y)
{
cnt++;
int j;
//生成一个新结点z
node *z = new node;
//要把y分裂为y和z，因此z的叶子属性与y相同
z->leaf = y->leaf;
//分裂前y有2t-1个关键字，分裂后前t-1个属于y，后t-1个属于z，中间第t个属于x
z->n = t - 1;y->n = t - 1;
//后t-1个关键字依次复制给z
for(j = 1; j < t; j++)
z->key[j] = y->key[j+t];
//如果有孩子，孩子也要复制过去，原来有2t个子树，前t个属于y，后t个属于z
if(y->leaf == false)
{
for(j = 1; j <= t; j++)
z->child[j] = y->child[j+t];
}
//使z作为x的第i+1个孩子(y已经是x的第i个孩子)
for(j = x->n+1; j > i; j--)
x->child[j+1] = x->child[j];
x->child[i+1] = z;
//把y中第t个关键字插入到x的第i个位置
for(j = x->n; j >= i; j--)
x->key[j+1] = x->key[j];
x->key[i] = y->key[t];
//x的关键字+1
x->n++;
Disk_Write(y);
Disk_Write(z);
Disk_Write(x);
}
//将关键字k插入到一个未满的结点x中
void B_Tree_Insert_Nonfull(node *x, int k)
{
int i = x->n;
//若x是叶子结点
if(x->leaf)
{
//找到该插入的位置
while(i >= 1 && k < x->key[i])
{
x->key[i+1] = x->key[i];
i--;
}
//插入关键字k
x->key[i+1] = k;
x->n++;
Disk_Write(x);
}
//若不是叶子结点
else
{
//找到该插入的位置
while(i >= 1 && k < x->key[i])
i--;
i++;
//读取其孩子，将关键字插入到它的孩子中，分两种情况
Disk_Read(x->child[i]);
//孩子已满
if(x->child[i]->n == 2 * t - 1)
{
//对孩子执行分裂操作，分裂后，孩子不变为不满
B_Tree_Split_Child(x, i, x->child[i]);
if(k > x->key[i])
i++;
}
//孩子不满，直接对孩子进行插入操作
B_Tree_Insert_Nonfull(x->child[i], k);
}
}
//向T中插入关键字k
void B_Tree_Insert(B_Tree *T, int k)
{
node *r = T->root;
//若根结点已满
if(r->n == 2*t-1)
{
//申请一个新的结点
node *s = new node;
//将的结点作为根结点
T->root = s;
s->leaf = false;
s->n = 0;
s->child[1] = r;
//将原根结点分裂为两个结点，分别作为s的第0个孩子和第1个孩子
B_Tree_Split_Child(s, 1, r);
//把关键字k插入到根结点中，此时根结点一定不满
B_Tree_Insert_Nonfull(s, k);
}
//若根结点不满
else
//直接把关键字插入到根结点中
B_Tree_Insert_Nonfull(r, k);
}
int main()
{
//生成一棵B树
B_Tree *T = new B_Tree;
B_Tree_Create(T);
//依次插入关键字
int i;
for(i = 1; i <= 100; i++)
{
B_Tree_Insert(T, i);
cout<<i<<' '<<cnt<<' '<<endl;
}
return 0;
}
~~~
18.2-5
见[算法导论-18.2-5-B树叶结点无指针](http://blog.csdn.net/mishifangxiangdefeng/article/details/7945167)
18.2-7
一棵具有n个结点且度为t的B树，可计算其高度h（P266定理18.1）。对一棵B树的操作时间T=读取磁盘页的时间*读取磁盘页的次数。根据代码可知，读取磁盘页的次数=B树的高度。
T = （a+bt）*h，代入a,b,h，求T的最大值
### 18.3从B树中删除关键字
18.3-2
木有伪代码，直接上代码
# 四、思考题
### 18-1辅存上的栈
a)2n次，O(mn)
假设一直是PUSH，且页面字数接近于m
b)2(n/m)次,O((n/m)*m)
每连续个字m个字处理一次，共处理n/m次。每次处理包括存一次（m个字），取一次（0个字）
c)2n次,O(mn)
最坏情况下，当页面满时PUSH，当页面只有一个字是POP，其中：
PUSH操作：存一次（m个字），取一次（0个字）
POP操作：存一次（0个字），取一次（m个字）
d)待解决
### 18-2连接与分裂2-3-4树
见[算法导论-18-2-连接与分裂2-3-4树](http://blog.csdn.net/mishifangxiangdefeng/article/details/7957517)
关于2楼问题的解答：
~~~
//删除T树中关键字为k的结点，由于是递归方法，当前处理的是x结点
void B_Tree::B_Tree_Delete2(node *x, char k)
{
int i, j;
//找到x中第一个不小于k的关键字，即待处理的位置
for(i = 1; i <= x->n; i++)
if(x->key[i] >= k)
break;
//y是关键字k之前的结点,即小于k的最大孩子
//z是关键字k之后的结点,即大于k的最小孩子
node *y = x->child[i], *z = x->child[i+1], *d;
//若关键字k在结点x中的第i个位置
if(x->key[i] == k && i <= x->n)
{
//1)y是叶子结点，则直接从x中删除k
if(x->leaf == true)
{
//关键字依次前移
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//关键字数-1
x->n--;
return;
}
//2)x是内结点
//2-a：x中前于k的子结点y包含至少t个关键字
if(y->n >= t)
{
//找出k在以y为根的子树中的前驱d
d = y;
while(d->leaf == false)
d = d->child[d->n+1];
//用d取代k
x->key[i] = d->key[d->n];
//递归地删除d
B_Tree_Delete2(y, d->key[d->n]);
}
//2-b：x是位于k之后的子结点z包含至少t个关键字
else if(z->n >= t)
{
//找出k在以z为根的子树中的后继d
d = z;
while(d->leaf == false)
d = d->child[1];
//用d取代k
x->key[i] = d->key[1];
//递归地删除d
B_Tree_Delete2(z, d->key[1]);
}
//2-c：y和z都只有t-1个关键字，将k和z中所有关键字合并进y，使得x失去k和指向z的指针
else
{
//将z并入y中，y是x的第i个孩子
B_Tree_Merge(x, y, z, i);
//将k从y中递归删除
B_Tree_Delete2(y, k);
}
}
//3)关键字不在结点x中，则必定包含k的正确的子树的根x->child[i]
else
{
//x是叶子结点,找到根结点都没有找到k，则k不在树中
if(x->leaf == true)
{
cout<<"error:not exist"<<endl;
return;
}
//x是内结点
//3-a:child[i]中只有t-1个关键字
if(y->n == t-1)
{
//它的相邻兄弟x->child[i+1](用z表示)包含至少t个关键字
if(i <= x->n && i <= x->n && z->n >= t)
{
//将x中的关键字下降至y
y->n++;
y->key[y->n] = x->key[i];
//将z的某一关键字上升至x
x->key[i] = z->key[1];
for(j = 1; j < z->n; j++)
z->key[j] = z->key[j+1];
//将z适合的子女指针移到y
if(y->leaf == false)
{
y->child[y->n+1] = z->child[1];
for(j = 1; j <= z->n; j++)
z->child[j] = z->child[j+1];
}
//z的关键字数-1
z->n--;
}
//它的相邻兄弟x->child[i-1]包含至少t个关键字
else if(i > 1 && x->child[i-1]->n >= t )
{
//将x中的关键字下降至y
for(j = y->n; j >= 1; j--)
y->key[j+1] = y->key[j];
y->key[1] = x->key[i-1];
y->n++;
//将y的相邻兄弟x->child[i-1]的某一关键字上升至x
x->key[i-1] = x->child[i-1]->key[x->child[i-1]->n];
//将该兄弟适合的子女指针移到y
if(y->leaf == false)
{
for(j = y->n; j >= 1; j--)
y->child[j+1] = y->child[j];
y->child[1] = x->child[i-1]->child[x->child[i-1]->n+1];
}
//x->child[i-1]的关键字数-1
x->child[i-1]->n--;
}
//y和其所有相邻兄弟都只有t-1个关键字，则与其中一个兄弟合并
else
{
//与后面一个结点(用z表示)合并
if(i <= x->n)
{
//将z并入y中，y是x的第i个孩子
B_Tree_Merge(x, y, z, i);
//将k从y中递归删除
B_Tree_Delete2(y, k);
}
//与前面一个结点合并
else
{
//将y并入z中，z是x的第i-1个孩子
B_Tree_Merge(x, z, y, i-1);
//将k从z中递归删除
B_Tree_Delete2(z, k);
}
}
}
//递归执行删除操作
B_Tree_Delete2(y, k);
}
}
//left是parent的第pos个孩子，right是parent的第pos+1个孩子，把parent->key[pos]和right都合并到left中
void B_Tree::B_Tree_Merge(node *parent, node *left, node *right, int pos)
{
int j;
//将k关键字合并进left
left->key[left->n+1] = parent->key[pos];
//将right中所有关键字合并进left
for(j = 1; j <= right->n; j++)
left->key[left->n+j+1] = right->key[j];
//如果有孩子，孩子也要合并
if(left->leaf == false)
{
//使得parent指向z的指针
for(j = 1; j <= right->n+1; j++)
left->child[left->n+j+1] = right->child[j];
}
//left包含2t-1个关键字
left->n = left->n + 1 + right->n;
//使得parent失去k
for(j = pos; j < parent->n; j++)
parent->key[j] = parent->key[j+1];
//使parent失去指向right的指针
for(j = pos+1; j <= parent->n; j++)
parent->child[j] = parent->child[j+1];
parent->n--;
//如果x是根结点，x
if(parent->n == 0 && root == parent)
root = left;
//释放z
delete right;
}
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
第16章 贪心算法
最后更新于：2022-04-01 07:35:51
# 一、综述
贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生出一个全局最优解
最小生成树算法是贪心算法的一个经典的例子
# 二、活动选择问题
### （1）代码
头文件：https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter16/chapter16.h
产品代码：https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter16/chapter16.cpp
测试代码：https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter16/chapter16Test.cpp
### （2）练习
### 16.1-1
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter16/Exercise16_1_1.cpp
### 16.1-2
先对每个活动按照它们的开始时间从小到大排序。令初始时i=n+1，其结束时间无限大，每次选择"结束时间比第i个活动的开始时间早的“的最晚开始活动
~~~
#include <iostream>
#include <algorithm>
using namespace std;
#define N 11
//一个活动用一个结点表示
struct node
{
int id;
int start;
int finish;
}A[N+1];
bool cmp(node a, node b)
{
return a.start < b.start;
}
//16.1-2
void Greedy_Activity_Selector2()
{
//先对每个活动按照它们的开始时间从小到大排序
sort(A, A+N+1, cmp);
int n = N, i = -1, m;
for(m = n; m >= 1; m--)
{
//找到最后一个“结束时间在第i个活动开始之前”的活动
if(i == -1 || A[m].finish <= A[i].start)
{
//将这个活动作为执行活动
cout<<A[m].id<<' ';
//递归第m个活动执行开始之前的贪心策略
i = m;
}
}
cout<<endl;
}
/*
0 0 //虚构活动a0
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
*/
int main()
{
int i;
//输入测试数据
for(i = 0; i <= N; i++)
{
A[i].id = i;
cin>>A[i].start>>A[i].finish;
}
Greedy_Activity_Selector2();
return 0;
}
~~~
### 16.1-3
见 [算法导论-16.1-3](http://blog.csdn.net/mishifangxiangdefeng/article/details/7747779)
常规算法：
针对一个特定的教室，然后做类似于16.1中的工作，从剩余活动中尽量多地安排活动到这个教室。如果活动安排完了，就不需要更多的教室了。如果活动没有安排完，再选择一个新的教室，做同样的工作，直到所有的活动都安排完。
这个算法的时间复杂度是O(n^2)，稍换一个角度，就能得到一个O(nlgn)的算
O(lgn)算法：
针对一个特定的活动，为它选择一个适合的教室。对所有已经选择过的教室，用一个最大堆来维护，比较的依据是在这个教室中最早开始的活动的开始时间
具体步骤是这样的：
step1：对所有活动的结束时间从小到大排序
step2：从最后一个活动开始，向第一个活动，依次针对每个活动做以下处理（1）获取堆顶元素的信息（2）如果堆顶的活动开始时间早于当前活动的结束时间，则申请一个新的教室，把活动的开始时间填入其中，再把教室作为一个结点存入堆中（3）如果堆顶的活动开始时间晚于当前活动的结束时间，就把当前活动填入堆顶元素中（4）选择下一个活动，直到所有活动都处理过
# 三、贪心策略的基本内容
### （1）练习
### 16.2-2
经典的0-1背包问题
### 16.2-3
根据假设w_1 <= w_2 <= ... <= w_n并且v_1 >= v_2 >= ... >= v_n。
贪心选择性质：如果该背包问题有解，则一定存在一个最优解包含物品1。
证明：给定一个最优解，如果已经包含物品1，则证明结束。否则用物品1替代背包中任何一个物品i，因为w_1 <= w_i，所以替换一定是可行的；其次，v_1 >= v_i，所以价值一定不会减小。可见替换后仍然是一个最优解。所以从按物品1，2，...的顺序加入背包，直到不能加入为止。
### 16.2-4
设ai表示第i个加油站一第i-1个加油站的距离。
最后一次加满了油是在第j个站(j初始时为0)
若第k个站满足aj + a|j+1 + …… +ak <= n 且 aj + a|j+1 + …… +a|k+1 > n，那么他应该在第k个站处加油
### 16.2-5
对所有点进行从小到大的排序，然后每次取值最小的点xi，把区间[xi,xi+1]加入到所求的区间集合中，并把属于区间[xi,xi+1]的点xj从点集中除去。
### 16.2-6
见[算法导论-16.2-6](http://blog.csdn.net/mishifangxiangdefeng/article/details/7748435)
常规算法：
先求avgi= vi/wi，按照avgi从大到小排序，再贪心选择，时间复杂度为O(nlgn)
改进：
更一般的情况，不需要排序，例如:如果a1, a2，a3是avgi最大的三个物品，如果它们的总量和不大于W，我们是不需要知道它们间的相对顺序的。
O(n)算法：
选择一个物品作为主元，对所有物品进行Paitition操作。将avg 分为三个集合G = {ai: avgi< m}, Q = {ai：avgi= m}, P = {ai: avgi> m}。分别对G, Q, P中元素求和得SG, SQ, SP。
1. 如果W < SG, 则令物体的集合为O = G，对集合O递归进行上述过程。
2. 如果 SG<=W <= SG+SQ，则将集合G中的元素都放入包中，并将集合Q总元素尽可能多的放入包中，结束。
3. 如果 SG+SQ < W, 将G，Q中元素放入包中。令物体集合O = P，总重W = W - SG - SQ。递归进行上述过程。
16.2-7
对集合A和B进行排序，每次取最大值，计算a^b
# 四、哈夫曼编码
### （1）代码
~~~
#include <iostream>
#include "Heap.h"
using namespace std;
#define N 6
extern int length;
int result[N+1];
//哈夫曼树
struct Huffman_Tree
{
node *root;
Huffman_Tree():root(NULL){}
};
//哈夫曼编码
void Huffman(unsigned int *A, Huffman_Tree *T)
{
int n = N;
while(n > 1)
{
//生成一个新的结点
node *z = new node;
//选择堆顶元素作为其左结点
z->left = (node *)Heap_Extract_Min(A);
//选择堆顶元素作为其右结点
z->right = (node *)Heap_Extract_Min(A);
z->p = z->left->p + z->right->p;
//将新结点插入堆中
Min_Heap_Insert(A, (unsigned int)z);
n--;
}
//剩下最后一个结点时，这个结点就是树的根结点
T->root = (node *)Heap_Extract_Min(A);
}
//输出这棵树上每个字母的编码
void PrintTree(node *t, int cnt)
{
int i;
//叶子结点
if(t->data != -1)
{
//输出其值及编码
cout<<t->data<<' ';
for(i = 0; i < cnt; i++)
cout<<result[i];
cout<<endl;
return ;
}
//非叶子结点，对其孩子进行递归
result[cnt] = 0;
PrintTree(t->left, cnt+1);
result[cnt] = 1;
PrintTree(t->right, cnt+1);
}
/*
f 5
e 9
c 12
b 13
d 16
a 45
*/
int main()
{
unsigned int A[N+1] = {};//存储的是结点的地址
length = N;
int i;
char c;
double p;
//构造N个结点
for(i = 1; i <= N; i++)
{
cin>>c>>p;
node *z = new node(c, p);
A[i] = (unsigned int)z;
}
//构造最小堆
Build_Min_Heap(A);
//构造哈夫曼树
Huffman_Tree *T = new Huffman_Tree();
Huffman(A, T);
//输出编码结果
PrintTree(T->root, 0);
return 0;
}
~~~
### （2）习题
### 16.3-2
能
### 16.3-6
~~~
#include <iostream>
#include "Heap.h"//选择p最小的结点时要借助于堆来实现
using namespace std;
#define N 6
extern int length;
int result[N+1];
//哈夫曼树
struct Huffman_Tree
{
node *root;
Huffman_Tree():root(NULL){}
};
//哈夫曼编码
void Huffman(unsigned int *A, Huffman_Tree *T)
{
int n = N;
while(n > 1)
{
//生成一个新的结点
node *z = new node;
if(n--)
{
//选择堆顶元素作为其左结点
z->left = (node *)Heap_Extract_Min(A);
z->p = z->p + z->left->p;
}
if(n--)
{
//选择堆顶元素作为其中间结点
z->middle = (node *)Heap_Extract_Min(A);
z->p = z->p + z->middle->p;
}
if(n--)
{
//选择堆顶元素作为其右结点
z->right = (node *)Heap_Extract_Min(A);
z->p = z->p + z->right->p;
}
//将新结点插入堆中
Min_Heap_Insert(A, (unsigned int)z);
n++;
}
//剩下最后一个结点时，这个结点就是树的根结点
T->root = (node *)Heap_Extract_Min(A);
}
//输出这棵树上每个字母的编码
void PrintTree(node *t, int cnt)
{
int i;
//叶子结点
if(t->data != -1)
{
//输出其值及编码
cout<<t->data<<' ';
for(i = 0; i < cnt; i++)
cout<<result[i];
cout<<endl;
return ;
}
//非叶子结点，对其孩子进行递归
result[cnt] = 0;
PrintTree(t->left, cnt+1);
result[cnt] = 1;
PrintTree(t->middle, cnt+1);
if(t->right)
{
result[cnt] = 2;
PrintTree(t->right, cnt+1);
}
}
/*
f 5
e 9
c 12
b 13
d 16
a 45
*/
int main()
{
unsigned int A[N+1] = {};//存储的是结点的地址
length = N;
int i;
char c;
double p;
//构造N个结点
for(i = 1; i <= N; i++)
{
cin>>c>>p;
node *z = new node(c, p);
A[i] = (unsigned int)z;
}
//构造最小堆
Build_Min_Heap(A);
//构造哈夫曼树
Huffman_Tree *T = new Huffman_Tree();
Huffman(A, T);
//输出编码结果
PrintTree(T->root, 0);
return 0;
}
~~~
# 五、思考题
### 16-1 找换硬币
a）每次都尽量选最大的、
c）1 4 5
d）找换i分钱的最少硬币数是ans[i]，ans[i] = max{ans[i-s[j]]+1}
~~~
#include <iostream>
#include <algorithm>
using namespace std;
//用于排序
bool cmp(int a, int b)
{
return a < b;
}
int main()
{
int n, k, i, j;
//输入数据
cin>>n>>k;
int s[100], ans[100];
for(i = 0; i < k; i++)
cin>>s[i];
//对硬币从小到大排序
sort(s, s + k, cmp);
//找换i分钱的最少硬币数是ans[i]
memset(ans, 0, sizeof(ans));
//ans[i] = max{ans[i-s[j]]+1}
for(i = 1; i <= n; i++)
{
for(j = 0; s[j] <= i; j++)
{
if(ans[i] == 0 || ans[i-s[j]]+1 < ans[i])
ans[i] = ans[i-s[j]]+1;
}
}
cout<<ans[n]<<endl;
return 0;
}
~~~
### 16-2 最小化平均结束时间的调度
a）每当一个任务执行完时，就选则剩下的任务中选择执行时间最短的任务执行
b）每当一个任务执行完时，就选则剩下的任务中选择剩余执行时间最短的任务执行，每当一个新的任务到来时，如果它的执行时间比当前任务的剩余执行时间要短，就抢占
第15章 动态规划
最后更新于：2022-04-01 07:35:49
# 一、综述
动态规划是通过组合子问题的解而解决整个问题的。
动态规划适用于子问题不是独立的情况，也就是各子问题的包含公共的子子问题。
动态规划对每个子问题只求解一次，将其结果保存在一张表中。
动态规划通常用于最优化问题。
动态规划的设计步骤：a.描述最优解的结构b.递归定义最优解的值c.按自底向上的方式计算最优觖的值d.由计算出的结构构造一个最优解
# 二、代码
### 15.1装配线调度
~~~
#include <iostream>
using namespace std;
#define I 2
#define J 6
int a[I+1][J+1], t[I+1][J+1], e[I+1], x[I+1], n = J;//输入
int f[I+1][J+1], l[I+1][J+1],rf,rl; //输出
//书上的伪代码
void Fastest_Way()
{
//初始化
f[1][1] = e[1] + a[1][1];
f[2][1] = e[2] + a[2][1];
int j;
for(j = 2; j <= n; j++)
{
//根据公式15.6计算
if(f[1][j-1] + a[1][j] <= f[2][j-1] + t[2][j-1] + a[1][j])
{
//记录计算结果
f[1][j] = f[1][j-1] + a[1][j];
l[1][j] = 1;
}
else
{
//记录计算结果
f[1][j] = f[2][j-1] + t[2][j-1] + a[1][j];
l[1][j] = 2;
}
//根据公式15.7计算
if(f[2][j-1] + a[2][j] <= f[1][j-1] + t[1][j-1] + a[2][j])
{
//记录计算结果
f[2][j] = f[2][j-1] + a[2][j];
l[2][j] = 2;
}
else
{
//记录计算结果
f[2][j] = f[1][j-1] + t[1][j-1] + a[2][j];
l[2][j] = 1;
}
}
//最后一个结果另外记录
if(f[1][n] + x[1] <= f[2][n] + x[2])
{
rf = f[1][n] + x[1];
rl = 1;
}
else
{
rf = f[2][n] + x[2];
rl = 2;
}
}
//输出
void Print_Stations()
{
cout<<"输出装配路线"<<endl;
int i = rl, j;
//从后向前输出
cout<<"line "<<i<<" station "<<n<<endl;
for(j = n; j > 1; j--)
{
//获取记录的结果
i = l[i][j];
cout<<"line "<<i<<" station "<<j-1<<endl;
}
}
//练习
//15.1-1
void Print_Stations2(int i, int j)
{
cout<<"顺序输出装配路线"<<endl;
if(j != n)
i = l[i][j+1];
//先输出前面的
if(j > 1)
Print_Stations2(i, j-1);
//再输出当前的
cout<<"line "<<i<<" station "<<j<<endl;
}
//输入数据
void Input()
{
int i, j;
cout<<"输入在装配站S(i,j)的装配时间a(i,j)："<<endl;
//7 9 3 4 8 4 8 5 6 4 5 7
for(i = 1; i <= I; i++)
{
for(j = 1; j <= J; j++)
cin>>a[i][j];
}
cout<<"输入进入装配线i的花费时间e(i)："<<endl;
//2 4
for(i = 1; i <= I; i++)
cin>>e[i];
cout<<"输入从S(i,j)站移动S(i2,j+1)的花费时间t(i,j)："<<endl;
//2 3 1 3 4 2 1 2 2 1
for(i = 1; i <= I; i++)
{
for(j = 1; j < J; j++)
cin>>t[i][j];
}
cout<<"输入从装配线i离开的花费时间x(i)："<<endl;
//3 2
for(i = 1; i <= I; i++)
cin>>x[i];
}
void Output()
{
int i, j;
cout<<"输出f[i][j]"<<endl;
//f[i][j]表示第j个站是在装配线i上完成的，完成1到j的装配最少需要的时间
for(i = 1; i <= I; i++)
{
for(j = 1; j <= J; j++)
cout<<f[i][j]<<' ';
cout<<endl;
}
cout<<"输出l[i][j]"<<endl;
//l[i][j]表示使得f[i][j]最小时在哪个装配线上装配j-1
for(i = 2; i <= I; i++)
{
for(j = 1; j <= J; j++)
cout<<l[i][j]<<' ';
cout<<endl;
}
}
int main()
{
Input();
Output();
Fastest_Way();
Print_Stations();
Print_Stations2(rl, J);
return 0;
}
~~~
### 15.2矩阵链乘法
~~~
#include <iostream>
using namespace std;
#define N 6
int m[N+1][N+1] = {0}, s[N+1][N+1] = {0};
void Matrix_Chain_Order(int *p)
{
int i, l, j, k, q;
for(i = 1; i <= N; i++)
m[i][i] = 0;
for(l = 2; l <= N; l++)
{
for(i = 1; i <= N - l + 1; i++)
{
j = i + l - 1;
m[i][j] = 0x7fffffff;
for(k = i; k <= j - 1; k++)
{
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if(q < m[i][j])
{
m[i][j] = q;
s[i][j] = k;
}
}
}
}
}
//15.2-2递归算法
int Matrix_Chain_Order(int *A, int start, int end)
{
//只有一个矩阵时，不需要括号
if(start == end)
return 0;
//如果已经有结果，直接使用结果
if(m[start][end])
return m[start][end];
int i, q;
m[start][end] = 0x7fffffff;
//P199，公式15.15
for(i = start; i < end; i++)
{
q = Matrix_Chain_Order(A, start, i) +
Matrix_Chain_Order(A, i+1, end) +
A[start-1] * A[i] * A[end];
//选最小值
if(q < m[start][end])
{
m[start][end] = q;
s[start][end] = i;
}
}
return m[start][end];
}
//输出结果
void Print_Optimal_Parens(int *A, int i, int j)
{
if(i == j)
cout<<'A'<<i;
else
{
cout<<'(';
Print_Optimal_Parens(A, i, s[i][j]);
Print_Optimal_Parens(A, s[i][j]+1, j);
cout<<")";
}
}
int main()
{
int A[N+1] = {5, 10, 3, 12, 5, 50, 6};
int A2[N+1] = {30, 35, 15, 5, 10, 20, 25};
Matrix_Chain_Order(A, 1, N);
Print_Optimal_Parens(A, 1, N);
return 0;
}
~~~
### 15.3动态规划基础
~~~
#include <iostream>
using namespace std;
#define N 6
int m[N+1][N+1] = {0}, s[N+1][N+1] = {0};
//重叠子问题
int Recursive_Matrix_Chain(int *p, int i, int j)
{
//只有一个矩阵时，不需要括号
if(i == j)
return 0;
//如果已经有结果，直接使用结果
if(m[i][j])
return m[i][j];
int k, q;
m[i][j] = 0x7fffffff;
//P199，公式15.15
for(k = i; k < j; k++)
{
q = Recursive_Matrix_Chain(p, i, k) +
Recursive_Matrix_Chain(p, k+1, j) +
p[i-1] * p[k] * p[j];
//选最小值
if(q < m[i][j])
{
m[i][j] = q;
s[i][j] = k;
}
}
return m[i][j];
}
//做备忘录
int Lookup_Chain(int *p, int i, int j)
{
int k, q;
if(m[i][j] < 0x7fffffff)
return m[i][j];
if(i == j)
m[i][j] = 0;
else
{
for(k = i; k < j; k++)
{
q = Lookup_Chain(p, i, k) + Lookup_Chain(p, k+1, j) + p[i-1]*p[k]*p[j];
if(q < m[i][j])
{
m[i][j] = q;
s[i][j] = k;
}
}
}
return m[i][j];
}
int Medorized_Matrix_Chain(int *p)
{
int n = N, i, j;
for(i = 1; i <= n; i++)
{
for(j = i; j <= n; j++)
m[i][j] = 0x7fffffff;
}
return Lookup_Chain(p, 1, n);
}
//输出结果
void Print_Optimal_Parens(int *p, int i, int j)
{
if(i == j)
cout<<'A'<<i;
else
{
cout<<'(';
Print_Optimal_Parens(p, i, s[i][j]);
Print_Optimal_Parens(p, s[i][j]+1, j);
cout<<")";
}
}
int main()
{
int A[N+1] = {5, 10, 3, 12, 5, 50, 6};
int A2[N+1] = {30, 35, 15, 5, 10, 20, 25};
//重叠子问题
memset(s, 0, sizeof(s));
cout<<Recursive_Matrix_Chain(A, 1, N)<<endl;
Print_Optimal_Parens(A, 1, N);
cout<<endl;
//做备忘录
memset(s, 0, sizeof(s));
cout<<Medorized_Matrix_Chain(A)<<endl;
Print_Optimal_Parens(A, 1, N);
cout<<endl;
return 0;
}
~~~
### 15.4最长公共子序列
~~~
#include <iostream>
using namespace std;
#define M 8
#define N 9
int b[M+1][N+1] = {0}, c[M+1][N+1] = {0};
int c2[2][M+1] = {0};
/****书上的伪代码***********************/
void Lcs_Length(int *x, int *y)
{
int i, j;
//初始化
for(i = 1; i <= M; i++)
c[i][0] = 0;
for(j = 1; j <= N; j++)
c[0][j] = 0;
//根据公式15.14计算
for(i = 1; i <= M; i++)
{
for(j = 1; j <= N; j++)
{
//记录计算结果
if(x[i] == y[j])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 2;
}
else
{
if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 1;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = 3;
}
}
}
}
}
//输出
void Print_Lcs(int *x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 2)
{
Print_Lcs(x, i-1, j-1);
cout<<x[i]<<' ';
}
else if(b[i][j] == 1)
Print_Lcs(x, i-1, j);
else
Print_Lcs(x, i, j-1);
}
//15.4-2 不使用表b的情况下计算最LCS并输出
void Lcs_Length2(int *x, int *y)
{
int i, j;
//初始化
for(i = 1; i <= M; i++)
c[i][0] = 0;
for(j = 1; j <= N; j++)
c[0][j] = 0;
//求LCS的时间没有什么区别，只要把与b有关的去掉就可以了
for(i = 1; i <= M; i++)
{
for(j = 1; j <= N; j++)
{
//第一种情况
if(x[i] == y[j])
c[i][j] = c[i-1][j-1] + 1;
else
{
//第二种情况
if(c[i-1][j] >= c[i][j-1])
c[i][j] = c[i-1][j];
//第三种情况
else
c[i][j] = c[i][j-1];
}
}
}
}
//区别在于输出，根据计算反推出前一个数据，而不是通过查找获得
void Print_Lcs2(int *x, int i, int j)
{
//递归到初始位置了
if(i == 0 || j == 0)
return;
//三种情况，刚好与Lcs_Length2中的三种情况相对应（不是按顺序对应）
//第二种情况
if(c[i][j] == c[i-1][j])
Print_Lcs2(x, i-1, j);
//第三种情况
else if(c[i][j] == c[i][j-1])
Print_Lcs2(x, i, j-1);
//第一种情况
else
{
//匹配位置
Print_Lcs2(x, i-1, j-1);
cout<<x[i]<<' ';
}
}
//15.4-3备忘录版本，类似于递归，只是对做过的计算记录下来，不重复计算
//每一次迭代是x[1..m]和y[1..n]的匹配
int Lcs_Length3(int *x, int *y, int m, int n)
{
//长度为0，肯定匹配为0
if(m == 0|| n == 0)
return 0;
//若已经计算，直接返回结果
if(c[m][n] != 0)
return c[m][n];
//公式15.14的对应
if(x[m] == y[n])
c[m][n] = Lcs_Length3(x, y, m-1, n-1) + 1;
else
{
int a = Lcs_Length3(x, y, m-1, n);
int b = Lcs_Length3(x, y, m, n-1);
c[m][n] = a > b ? a : b;
}
return c[m][n];
}
//15.4-4(1)使用2*min(m,n)及O(1)的额外空间来计算LCS的长度
void Lcs_Length4(int *x, int *y)
{
int i, j;
//c2是2*min(M,N)的矩阵，初始化
memset(c2, 0 ,sizeof(c2));
//类似于上文的循环，只是i%2代表当前行，(i-1)%2代表上一行，其余内容相似
for(i = 1; i <= N; i++)
{
for(j = 1; j <= M; j++)
{
if(y[i] == x[j])
c2[i%2][j] = c2[(i-1)%2][j-1] + 1;
else
{
if(c2[(i-1)%2][j] >= c2[i%2][j-1])
c2[i%2][j] = c2[(i-1)%2][j];
else
c2[i%2][j] = c2[i%2][j-1];
}
}
}
//输出结果
cout<<c2[N%2][M]<<endl;
}
void Lcs_Length5(int *x, int *y)
{
int i, j, temp = 0;
memset(c2, 0 ,sizeof(c2));
for(i = 1; i <= N; i++)
{
for(j = 1; j <= M; j++)
{
if(y[i] == x[j])
c2[i%2][j] = c2[(i-1)%2][j-1] + 1;
else
{
if(c2[(i-1)%2][j] >= c2[i%2][j-1])
c2[i%2][j] = c2[(i-1)%2][j];
else
c2[i%2][j] = c2[i%2][j-1];
}
}
}
cout<<c2[N%2][M]<<endl;
}
void Print()
{
int i, j;
for(i = 1; i <= M; i++)
{
for(j = 1; j <= N; j++)
cout<<c[i][j]<<' ';
cout<<endl;
}
}
int main()
{
int x[M+1] = {0,1,0,0,1,0,1,0,1};
int y[N+1] = {0,0,1,0,1,1,0,1,1,0};
Lcs_Length(x, y);
// Print();
Print_Lcs(x, M, N);
// Lcs_Length2(x, y);
// Lcs_Length3(x, y, M, N);
// Print();
// Print_Lcs2(x, M, N);
// Lcs_Length4(x, y);
return 0;
}
~~~
### 15.5最优二叉查找树
~~~
#include <iostream>
using namespace std;
#define N 7
double e[N+2][N+2] = {0};//期望
double w[N+2][N+2] = {0};//概率
int root[N+2][N+2] = {0};//记录树的根结点的位置
/*****调试过程中用于输出中间信息***************************/
void PrintE()
{
int i, j;
for(i = 1; i <= N+1; i++)
{
for(j = 1; j <= N+1; j++)
cout<<e[i][j]<<' ';
cout<<endl;
}
cout<<endl;
}
void PrintW()
{
int i, j;
for(i = 1; i <= N+1; i++)
{
for(j = 1; j <= N+1; j++)
cout<<w[i][j]<<' ';
cout<<endl;
}
cout<<endl;
}
void PrintRoot()
{
int i, j;
for(i = 1; i <= N+1; i++)
{
for(j = 1; j <= N+1; j++)
cout<<root[i][j]<<' ';
cout<<endl;
}
cout<<endl;
}
/****书上的伪代码对应的程序****************************/
//构造最做树
void Optimal_Bst(double * p, double *q, int n)
{
int i, j, r ,l;
double t;
//初始化。当j=i-1时，只有一个虚拟键d|i-1
for(i = 1; i <= n+1; i++)
{
e[i][i-1] = q[i-1];
w[i][i-1] = q[i-1];
}
//公式15.19
for(l = 1; l <= n; l++)
{
for(i = 1; i <= n-l+1; i++)
{
j = i+l-1;
e[i][j] = 0x7fffffff;
//公式15.20
w[i][j] = w[i][j-1] + p[j] + q[j];
for(r = i; r <= j; r++)
{
//公式15.19
t = e[i][r-1] + e[r+1][j] + w[i][j];
//取最小值
if(t < e[i][j])
{
e[i][j] = t;
//记录根结点
root[i][j] = r;
}
}
}
}
}
/****练习**********************/
//15.5-1输出最优二叉查找树
void Construct_Optimal_Best(int start, int end)
{
//找到根结点
int r = root[start][end];
//如果左子树是叶子
if(r-1 < start)
cout<<'d'<<r-1<<" is k"<<r<<"'s left child"<<endl;
//如果左子树不是叶子
else
{
cout<<'k'<<root[start][r-1]<<" is k"<<r<<"'s left child"<<endl;
//对左子树递归使用Construct_Optimal_Best
Construct_Optimal_Best(start, r-1);
}
//如果右子树是叶子
if(end < r+1)
cout<<'d'<<end<<" is k"<<r<<"'s right child"<<endl;
//如果右子树不是叶子
else
{
cout<<'k'<<root[r+1][end]<<" is k"<<r<<"'s right child"<<endl;
//对右子树递归使用Construct_Optimal_Best
Construct_Optimal_Best(r+1, end);
}
}
int main()
{
int n = N;
// double p[N+1] = {0, 0.15, 0.10, 0.05, 0.10, 0.20};
// double q[N+1] = {0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
double p[N+1] = {0, 0.04, 0.06, 0.08, 0.02, 0.10, 0.12, 0.14};
double q[N+1] = {0.06, 0.06, 0.06, 0.06, 0.05, 0.05, 0.05};
Optimal_Bst(p, q, n);
// PrintE();
// PrintW();
// PrintRoot();
cout<<'k'<<root[1][N]<<" is root"<<endl;
Construct_Optimal_Best(1, N);
return 0;
}
~~~
# 三、练习
### 15.1装配线调度
### 15.1-1
~~~
//15.1-1
void Print_Stations2(int i, int j)
{
cout<<"顺序输出装配路线"<<endl;
if(j != n)
i = l[i][j+1];
//先输出前面的
if(j > 1)
Print_Stations2(i, j-1);
//再输出当前的
cout<<"line "<<i<<" station "<<j<<endl;
}
~~~
### 15.1-4
不使用l数组来记录，输出时根据类似L4-L13的比较来计算出前一个station的数据
### 15.2矩阵链乘法
### 15.2-1
算法：类似于15.3的做备忘录
运行结果：((A1A2)((A3A4)(A5A6)))
### 15.2-2
~~~
//15.2-2递归算法
int Matrix_Chain_Order(int *A, int start, int end)
{
//只有一个矩阵时，不需要括号
if(start == end)
return 0;
//如果已经有结果，直接使用结果
if(m[start][end])
return m[start][end];
int i, q;
m[start][end] = 0x7fffffff;
//P199，公式15.15
for(i = start; i < end; i++)
{
q = Matrix_Chain_Order(A, start, i) +
Matrix_Chain_Order(A, i+1, end) +
A[start-1] * A[i] * A[end];
//选最小值
if(q < m[start][end])
{
m[start][end] = q;
s[start][end] = i;
}
}
return m[start][end];
}
~~~
### 15.3动态规划基础
### 15.3-1
枚举的时间的复杂度是O(4^n)/(n^(3/2))
RECURSIVE-MATRIX-CHAIN的时间复杂度是O(n*3^(n-1))
显然后者更有效
### 15.3-3
解释见1楼
~~~
#include <iostream>
using namespace std;
#define N 6
int m[N+1][N+1] = {0}, s[N+1][N+1] = {0};
//15.2-2递归算法
int Matrix_Chain_Order(int *A, int start, int end)
{
//只有一个矩阵时，不需要括号
if(start == end)
return 0;
//如果已经有结果，直接使用结果
if(m[start][end])
return m[start][end];
int i, q;
m[start][end] = -1;
//P199，公式15.15
for(i = start; i < end; i++)
{
q = Matrix_Chain_Order(A, start, i) +
Matrix_Chain_Order(A, i+1, end) +
A[start-1] * A[i] * A[end];
//选最小值
if(q > m[start][end])
{
m[start][end] = q;
s[start][end] = i;
}
}
return m[start][end];
}
//输出结果
void Print_Optimal_Parens(int *A, int i, int j)
{
if(i == j)
cout<<'A'<<i;
else
{
cout<<'(';
Print_Optimal_Parens(A, i, s[i][j]);
Print_Optimal_Parens(A, s[i][j]+1, j);
cout<<")";
}
}
int main()
{
int A[N+1] = {5, 10, 3, 12, 5, 50, 6};
int A2[N+1] = {30, 35, 15, 5, 10, 20, 25};
Matrix_Chain_Order(A, 1, N);
Print_Optimal_Parens(A, 1, N);
return 0;
}
~~~
### 15.4最长公共子序列
### 15.4-1
1 0 0 1 1 0
### 15.4-2
~~~
//15.4-2 不使用表b的情况下计算最LCS并输出
void Lcs_Length2(int *x, int *y)
{
int i, j;
//初始化
for(i = 1; i <= M; i++)
c[i][0] = 0;
for(j = 1; j <= N; j++)
c[0][j] = 0;
//求LCS的时间没有什么区别，只要把与b有关的去掉就可以了
for(i = 1; i <= M; i++)
{
for(j = 1; j <= N; j++)
{
//第一种情况
if(x[i] == y[j])
c[i][j] = c[i-1][j-1] + 1;
else
{
//第二种情况
if(c[i-1][j] >= c[i][j-1])
c[i][j] = c[i-1][j];
//第三种情况
else
c[i][j] = c[i][j-1];
}
}
}
}
//区别在于输出，根据计算反推出前一个数据，而不是通过查找获得
void Print_Lcs2(int *x, int i, int j)
{
//递归到初始位置了
if(i == 0 || j == 0)
return;
//三种情况，刚好与Lcs_Length2中的三种情况相对应（不是按顺序对应）
//第二种情况
if(c[i][j] == c[i-1][j])
Print_Lcs2(x, i-1, j);
//第三种情况
else if(c[i][j] == c[i][j-1])
Print_Lcs2(x, i, j-1);
//第一种情况
else
{
//匹配位置
Print_Lcs2(x, i-1, j-1);
cout<<x[i]<<' ';
}
}
~~~
### 15.4-3
~~~
//15.4-3备忘录版本，类似于递归，只是对做过的计算记录下来，不重复计算
//每一次迭代是x[1..m]和y[1..n]的匹配
int Lcs_Length3(int *x, int *y, int m, int n)
{
//长度为0，肯定匹配为0
if(m == 0|| n == 0)
return 0;
//若已经计算，直接返回结果
if(c[m][n] != 0)
return c[m][n];
//公式15.14的对应
if(x[m] == y[n])
c[m][n] = Lcs_Length3(x, y, m-1, n-1) + 1;
else
{
int a = Lcs_Length3(x, y, m-1, n);
int b = Lcs_Length3(x, y, m, n-1);
c[m][n] = a > b ? a : b;
}
return c[m][n];
}
~~~
### 15.4-4
（1）使用2*min(m,n)及O(1)的额外空间来计算LCS的长度
因为这里只需要求长度，而不需要求序列，可以只存储需要的内容。每一次的计算c[i][j]只与c[i-1][j]、c[i][j-1]、c[i-1][j-1]有关，所以只保留第i行和第i-1行
~~~
//15.4-4(1)使用2*min(m,n)及O(1)的额外空间来计算LCS的长度
void Lcs_Length4(int *x, int *y)
{
int i, j;
//c2是2*min(M,N)的矩阵，初始化
memset(c2, 0 ,sizeof(c2));
//类似于上文的循环，只是i%2代表当前行，(i-1)%2代表上一行，其余内容相似
for(i = 1; i <= N; i++)
{
for(j = 1; j <= M; j++)
{
if(y[i] == x[j])
c2[i%2][j] = c2[(i-1)%2][j-1] + 1;
else
{
if(c2[(i-1)%2][j] >= c2[i%2][j-1])
c2[i%2][j] = c2[(i-1)%2][j];
else
c2[i%2][j] = c2[i%2][j-1];
}
}
}
//输出结果
cout<<c2[N%2][M]<<endl;
}
~~~
（2）使用min(m,n)项以及O(1)空间
~~~
//15.4-4(2)使用min(m,n)及O(1)的额外空间来计算LCS的长度
void Lcs_Length4(int *x, int *y)
{
int i, j;
//c2是min(M,N)的矩阵，初始化
memset(c2, 0 ,sizeof(c2));
//类似于上文的循环，只是i%2代表当前行，(i-1)%2代表上一行，其余内容相似
int t1 = 0, t2;
for(i = 1; i <= N; i++)
{
t2 = c[j];
for(j = 1; j <= M; j++)
{
if(y[i] == x[j])
c2[j] = t1 + 1;
else
c2[j] = max(c2[j], c2[j-1]);
t1 = t2;
}
}
//输出结果
cout<<c2[M]<<endl;
}
~~~
### 15.4-5
~~~
#include <iostream>
#include <string>
using namespace std;
#define N 10
int c[N+1] = {0};//c[i]表示A[1..i]的最长递增子序列
int pre[N+1];//pre[i]表示若要得到A[1..i]的最长递增子序列，i的前一个是哪个
//求最长递增子序列
void Length(int *A)
{
int i, j;
//A[i] = max{A[j]+1} if A[j]>A[i] and j<i
for(i = 1; i <= N; i++)
{
//初始化
c[i] = 0;
pre[i] = 0;
for(j = 0; j < i; j++)
{
if(A[i] > A[j])
{
if(c[j] + 1 > c[i])
{
c[i] = c[j]+1;
pre[i] = j;
}
}
}
}
cout<<c[N]<<endl;
}
//若要输出A[1..n]中的最长单调子序列，先输出A[1..pre[n]]中的最长单调子序列
void Print(int *A, int n)
{
if(pre[n])
Print(A, pre[n]);
cout<<A[n]<<' ';
}
int main()
{
//因为从第开始记数，所以数组中的第一个数不算，只是占一个位置
// int A[N+1] = {0,1,2,3,4,5,6,7,8,9,10};
int A[N+1] = {0,11,2,13,4,15,6,17,8,19,10};
Length(A);
Print(A, N);
return 0;
}
~~~
### 15.1最优二叉查找树
### 15.5-1
~~~
//15.5-1输出最优二叉查找树
void Construct_Optimal_Best(int start, int end)
{
//找到根结点
int r = root[start][end];
//如果左子树是叶子
if(r-1 < start)
cout<<'d'<<r-1<<" is k"<<r<<"'s left child"<<endl;
//如果左子树不是叶子
else
{
cout<<'k'<<root[start][r-1]<<" is k"<<r<<"'s left child"<<endl;
//对左子树递归使用Construct_Optimal_Best
Construct_Optimal_Best(start, r-1);
}
//如果右子树是叶子
if(end < r+1)
cout<<'d'<<end<<" is k"<<r<<"'s right child"<<endl;
//如果右子树不是叶子
else
{
cout<<'k'<<root[r+1][end]<<" is k"<<r<<"'s right child"<<endl;
//对右子树递归使用Construct_Optimal_Best
Construct_Optimal_Best(r+1, end);
}
}
~~~
### 15.5-2
k5 is root
k2 is k5's left child
k1 is k2's left child
d0 is k1's left child
d1 is k1's right child
k3 is k2's right child
d2 is k3's left child
k4 is k3's right child
d3 is k4's left child
d4 is k4's right child
k6 is k5's right child
d5 is k6's left child
k7 is k6's right child
d6 is k7's left child
d7 is k7's right child
### 15.5-4
~~~
//15.5-4
void Optimal_Bst(double * p, double *q, int n)
{
int i, j, r ,l;
double t;
//初始化。当j=i-1时，只有一个虚拟键d|i-1
for(i = 1; i <= n+1; i++)
{
e[i][i-1] = q[i-1];
w[i][i-1] = q[i-1];
}
//公式15.19
for(l = 1; l <= n; l++)
{
for(i = 1; i <= n-l+1; i++)
{
j = i+l-1;
e[i][j] = 0x7fffffff;
//公式15.20
w[i][j] = w[i][j-1] + p[j] + q[j];
//root[i,j-1] <= root[i,j] <= root[i+1,j]
for(r = root[i][j-1]; r <= root[i+1][j]; r++)
{
//公式15.19
t = e[i][r-1] + e[r+1][j] + w[i][j];
//取最小值
if(t < e[i][j])
{
e[i][j] = t;
//记录根结点
root[i][j] = r;
}
}
}
}
}
~~~
# 四、思考题
### 15-1 双调欧几里德旅行商问题
见[算法导论-15-1-双调欧几里得旅行商问题](http://blog.csdn.net/mishifangxiangdefeng/article/details/7918983)
### 15-2 整齐打印
见[算法导论-15-2-整齐打印](http://blog.csdn.net/mishifangxiangdefeng/article/details/7921947)
### 15-3 编辑距离
见[算法导论-15-3-编辑距离](http://blog.csdn.net/mishifangxiangdefeng/article/details/7925025)
### 15-4 计划一个公司聚会
见[算法导论-15-4-计划一个公司聚会](http://blog.csdn.net/mishifangxiangdefeng/article/details/7930830)
### 15-6 在棋盘上的移动
见[算法导论-15-6-在棋盘上移动](http://blog.csdn.net/mishifangxiangdefeng/article/details/7931438)
### 15-7 达到最高效益的调度
见[算法导论-15-7-达到最高效益的调度](http://blog.csdn.net/mishifangxiangdefeng/article/details/7932349)
第14章 14.3 区间树
最后更新于：2022-04-01 07:35:47
# 一、综述
### 1.区间树
区间树中一种对动态集合进行维护的红黑树，该集合中的每个元素x都包含一个区间int[x]
### 2.基础数据结构
红黑树，其中每个结点x包含一个区间域int[x]，x的关键字为区间的低端点
### 3.附加信息
max[x]：以x为根的子树中所有区间的 端点的最大值
### 4.对信息的维护
max[x] = max(high[int[x]], max[left[x]], max[right[x]])
### 5.设计新的操作
INTERVAL-SEARCH(T, i)：找出树T中覆盖区间i的那个结点。
# 二、代码
### 1.section14_3.cpp
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/section14_3.cpp
### 2.main.cpp
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter14/section14_3Test.cpp
# 三、练习
### 14.3-1
~~~
LEFT-ROTATE(T, x)
1 y <- right[x]
2 right[x] <- left[y]
3 if left[y] != nil[T]
4 then p[left[y]] <- x
5 p[y] <- p[x]
6 if p[x] = nil[T]
7 then root[T] <- y
8 else if x = left[p[x]]
9 then left[p[x]] <- y
10 else right[p[x]] <- y
11 left[y] <- x
12 p[x] <- y
13 max[y] <- max[x]
14 max[x] <- max(high[int[x]], max[left[x]], max[right[x]])
~~~
### 14.3-2
~~~
对二中的程序做三点修改
（1）L37，<改成<=
（2）L40，>改成>=
（3）L443，>=改成>
~~~
### 14.3-3
那本答案PDF写得比较麻烦，不明天为什么要写得这么复杂，我只分了三种情况
~~~
node* Interval_Tree::Search_Min(node *root, interval i)
{
node *x = root, *y;
//先从左子树上找
if(x->left && x->left->max >= i.low)
{
y = Search_Min(x->left, i);
if(y != nil)
return y;
}
//如果x与i相交，就不需要找左子树了
if(Overlap(x->inte, i))
return x;
//最后在右子树上找
if(x->right)
return Search_Min(x->right, i);
return nil;
}
~~~
### 14.3-4
~~~
void Interval_Tree::Search_All(node *root, interval i)
{
node *x = root, *y;
//如果当前结点与i相交
if(Overlap(x->inte, i))
cout<<x->inte.low<<' '<<x->inte.high<<endl;
//先从左子树上找
if(x->left && x->left->max >= i.low)
Search_All(x->left, i);
//从右子树上找
if(x->right && x->key <= i.high)
Search_All(x->right, i);
}
~~~
### 14.3-5
~~~
node* Interval_Tree::Search_Exactly(interval i)
{
//从根结点开始
node *x = root;
//不是叶子且不重叠
while(x != nil)
{
if(x->inte.low == i.low && x->inte.high == i.high)
return x;
//在左子树中
if(x->left != nil && x->key >= i.low)
x = x->left;
//在右子树中
else
x = x->right;
}
return nil;
}
~~~
### 14.3-6
见[算法导论-14.3-6-MIN-GAP](http://blog.csdn.net/mishifangxiangdefeng/article/details/7907597)
### 14.3-7
见[算法导论-14.3-7-O(nlgn)时间求矩形集合中重叠矩形的个数](http://blog.csdn.net/mishifangxiangdefeng/article/details/7909307)
算法导论-14-2-Josephus排列
最后更新于：2022-04-01 07:35:44
题目：
Josephus问题的定义如下：假设n个人排成环形，且有以正整数m<=n。从某个制定的人开始，沿环报数，每遇到第m个人就让其出列，且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1，2，...，n的(n, m)-Josephus排列。例如，(7,3)-Josephus排列为<3,6,2,7,5,1,4>。
a)假设m为整数。请描述一个O(n)时间的算法，使之对给定的整数n，输出(n, m)-Josephus排列。
b)假设m不是个常数。请描述一个O(nlgn)时间的算法，使给定的整数n和m，输出(n, m)-Josephus排列。
思考：
利用14.1中的动态顺序统计，假设刚刚删除的是剩余点中的第start个点（初始时为0），此时还剩下t个点，那么下一个要删除的是剩余点的第（start+m-1）%t个点
步骤1：基础数据结构
红黑树
步骤2：附加信息
size[x]：以x为根的子树的（内部）结点数（包括x本身），即子树的大小。size[nil[T]]=0
步骤3：对信息的维护
size[x] = size[left[x]] + size[right[x]] + 1
插入操作：从插入结点到根结点都要更新O(lgn)
旋转操作：只需要更新旋转轴上的两个点O(1)
删除操作：从删除结点的父结点开始到根结点都要更新O(lgn)
代码：
https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/exercise14_2.cpp
算法导论-14-1-最大重叠点
最后更新于：2022-04-01 07:35:42
题目：
假设希望对一组区间记录一个最大重叠点，亦即覆盖它的区间最多的那个点。
a)证明：最大重叠点总存在于某段的端点上。
b)设计一数据结构，能有效地支持操作INTERVAL-INSERT,INTERVAL-DELETE和返回最大重叠点操作FIND-POM。（提示：将所有端点组织成红黑树。左端点关联+1值，而右端点关联-1值。附加一些维护最大重叠点的信息以扩张树中结点。）
思考：
设有n个区间，将所有2n个点从小到大排序，对于排序后的第i个点，若它是某个区间的左端点，则p[i]=1，若它是某个区间的右端点，则p[i]=-1。由第一问可知，所求的点一定是某条线段的端点，所以从端点集合中找出被最多区间覆盖的那个。若一个端点是排序后的第i个点，则有个SUM(s[1],s[i])个区间覆盖这个点。
使用红黑树对所有的端点进行动态排序并保证有较好的性质，在树的结点中增加一些顺序统计量的信息，用于求SUM(s[1],s[i])
步骤1：基础数据结构
红黑树，p[x]=1表示它是区间的左端点，p[x]=-1表示它是区间的右端点
步骤2：附加信息
v[x]：以x为根的所有结点的p值之和
m[x]：MAX(SUM([left[x], i))
o[x]：以x为根的所有结点中的最大覆盖点
步骤3：对信息的维护
步骤4：设计新的操作
Find_Pom()：返回根结点的p值
代码：
[头文件](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter14/section14_1.h)
[产品代码](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter14/section14_1.cpp)
[测试代码](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter14/section14_1Test.cpp)
第14章 14.1 动态顺序统计
最后更新于：2022-04-01 07:35:40
# 一、概念
### 1.动态顺序统计
动态顺序统计是指，在一个动态的无序的集合中，任意的顺序统计量都可以在O(lgn)时间内确定。
### 2.基础数组结构
红黑树，每个树结点的域包括：key[x]，color[x]，left[x]，right[x]
### 3.附加信息
size[x]：以结点x为根的子树的内部结点（包括x）数，即子树的大小。
如果定义哨兵nil，则size[nil[T]]为0
size[x] = size[left[x]] + size[right[x]] + 1
### 4.对信息的维护
（1）插入操作：
第一个阶段，即从根开始，沿树下降，将新结点插入为某个已有结点的孩子，这一阶段的维护方法是对路径上每个结点的size都+1，时间是O(lgn)
第二个阶段，即沿树上升，做一些颜色修改和旋转以保持红黑性质，例如LEFT-ROTATE(T, x)，维护方法是size[y]<-size[x]，size[x]<-size[left[x]] + size[right[x]] + 1，由于至多旋转两次，时间是O(1)
（2）删除操作：
第一阶段，即对查找树进行操作，维护方法是对路径上每个结点的size都-1，时间是O(lgn)
第二阶段到多做三次旋转，维护方式与上面相同，时间是O(1)
### 5.设计新的操作
OS-SELECT(x, i)：找出顺序统计树T中的第i小关键字，时间为O(lgn)
OS-RANK(T, x)：给定指向一顺序统计树T中结点x的指针，返回对T进行中序遍历后得到 的线性序中x的位置，时间为O(lgn)
# 二、代码
### 1.Os_Tree.h
~~~
#include <iostream>
using namespace std;
#define BLACK 0
#define RED 1
//顺序统计量树结点结构
struct node
{
/*红黑树的域*/
int key;
bool color;
node *p;
node *left;
node *right;
/*附加信息*/
int size;//以结点x为根的子树的内部结点的个数，x->key=x->left->key+x->right->key+1
/*构造函数*/
node(node *init, int k):left(init),right(init),p(init),key(k),color(BLACK),size(1){}
};
//顺序统计量树结构
class Os_Tree
{
public:
node *root;
node *nil;//哨兵
/*构造函数*/
Os_Tree(){nil = new node(NULL, -1);root = nil;nil->size = 0;};
/*动态顺序统计相关操作*/
node *Os_Select(node *x, int i);
int Os_Rank(node *x);
/*红黑树的相关操作*/
void Left_Rotate(node *x);//左旋
void Right_Rotate(node *x);//右旋
void Os_Insert_Fixup(node *z);//插入调整
void Os_Insert(node *z);//插入
void Os_Delete_Fixup(node *x);//删除调整
node *Os_Delete(node *z);//删除
void Print();//输出
void Print(node *x);//输出
node *Os_Search(node *x, int k);//在x的子树中查找关键字为k的结点
node *Tree_Successor(node *x);//求后继
node *Tree_Minimum(node *x);//求关键字最小的点
};
//左旋，令y = x->right, 左旋是以x和y之间的链为支轴进行旋转
//涉及到的结点包括：x,y,y->left，令node={p,l,r},具体变化如下：
//x={x->p,x->left,y}变为{y,x->left,y->left}
//y={x,y->left,y->right}变为{x->p,x,y->right}
//y->left={y,y->left->left,y->left->right}变为{x,y->left->left,y->left->right}
void Os_Tree::Left_Rotate(node *x)
{
//令y = x->right
node *y = x->right;
//按照上面的方式修改三个结点的指针，注意修改指针的顺序
x->right = y->left;
if(y->left != nil)
y->left->p = x;
y->p = x->p;
if(x->p == nil)//特殊情况：x是根结点
root = y;
else if(x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
//对附加信息的维护
y->size = x->size;
x->size = x->left->size + x->right->size + 1;
}
//右旋，令y = x->left, 左旋是以x和y之间的链为支轴进行旋转
//旋转过程与上文类似
void Os_Tree::Right_Rotate(node *x)
{
node *y = x->left;
x->left = y->right;
if(y->right != nil)
y->right->p = x;
y->p = x->p;
if(x->p == nil)
root = y;
else if(x == x->p->right)
x->p->right = y;
else
x->p->left = y;
y->right = x;
x->p = y;
//对附加信息的维护
y->size = x->size;
x->size = x->left->size + x->right->size + 1;
}
//红黑树调整
void Os_Tree::Os_Insert_Fixup(node *z)
{
node *y;
//唯一需要调整的情况，就是违反性质2的时候，如果不违反性质2，调整结束
while(z->p->color == RED)
{
//p[z]是左孩子时，有三种情况
if(z->p == z->p->p->left)
{
//令y是z的叔结点
y = z->p->p->right;
//第一种情况，z的叔叔y是红色的
if(y->color == RED)
{
//将p[z]和y都着为黑色以解决z和p[z]都是红色的问题
z->p->color = BLACK;
y->color = BLACK;
//将p[p[z]]着为红色以保持性质5
z->p->p->color = RED;
//把p[p[z]]当作新增的结点z来重复while循环
z = z->p->p;
}
else
{
//第二种情况：z的叔叔是黑色的，且z是右孩子
if(z == z->p->right)
{
//对p[z]左旋，转为第三种情况
z = z->p;
Left_Rotate(z);
}
//第三种情况：z的叔叔是黑色的，且z是左孩子
//交换p[z]和p[p[z]]的颜色，并右旋
z->p->color = BLACK;
z->p->p->color = RED;
Right_Rotate(z->p->p);
}
}
//p[z]是右孩子时，有三种情况，与上面类似
else if(z->p == z->p->p->right)
{
y = z->p->p->left;
if(y->color == RED)
{
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else
{
if(z == z->p->left)
{
z = z->p;
Right_Rotate(z);
}
z->p->color = BLACK;
z->p->p->color = RED;
Left_Rotate(z->p->p);
}
}
}
//根结点置为黑色
root->color = BLACK;
}
//插入一个结点
void Os_Tree::Os_Insert(node *z)
{
node *y = nil, *x = root;
//找到应该插入的位置，与二叉查找树的插入相同
while(x != nil)
{
x->size++;
y = x;
if(z->key < x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if(y == nil)
root = z;
else if(z->key < y->key)
y->left = z;
else
y->right = z;
z->left = nil;
z->right = nil;
//将新插入的结点转为红色
z->color = RED;
//从新插入的结点开始，向上调整
Os_Insert_Fixup(z);
}
//对树进行调整，x指向一个红黑结点，调整的过程是将额外的黑色沿树上移
void Os_Tree::Os_Delete_Fixup(node *x)
{
node *w;
//如果这个额外的黑色在一个根结点或一个红结点上，结点会吸收额外的黑色，成为一个黑色的结点
while(x != root && x->color == BLACK)
{
//若x是其父的左结点（右结点的情况相对应）
if(x == x->p->left)
{
//令w为x的兄弟，根据w的不同，分为三种情况来处理
//执行删除操作前x肯定是没有兄弟的，执行删除操作后x肯定是有兄弟的
w = x->p->right;
//第一种情况：w是红色的
if(w->color == RED)
{
//改变w和p[x]的颜色
w->color = BLACK;
x->p->color = RED;
//对p[x]进行一次左旋
Left_Rotate(x->p);
//令w为x的新兄弟
w = x->p->right;
//转为2.3.4三种情况之一
}
//第二情况：w为黑色，w的两个孩子也都是黑色
if(w->left->color == BLACK && w->right->color == BLACK)
{
//去掉w和x的黑色
//w只有一层黑色，去掉变为红色，x有多余的一层黑色，去掉后恢复原来颜色
w->color = RED;
//在p[x]上补一层黑色
x = x->p;
//现在新x上有个额外的黑色，转入for循环继续处理
}
//第三种情况，w是黑色的,w->left是红色的,w->right是黑色的
else
{
if(w->right->color == BLACK)
{
//改变w和left[x]的颜色
w->left->color = BLACK;
w->color = RED;
//对w进行一次右旋
Right_Rotate(w);
//令w为x的新兄弟
w = x->p->right;
//此时转变为第四种情况
}
//第四种情况：w是黑色的,w->left是黑色的,w->right是红色的
//修改w和p[x]的颜色
w->color =x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
//对p[x]进行一次左旋
Left_Rotate(x->p);
//此时调整已经结束，将x置为根结点是为了结束循环
x = root;
}
}
//若x是其父的左结点（右结点的情况相对应）
else if(x == x->p->right)
{
//令w为x的兄弟，根据w的不同，分为三种情况来处理
//执行删除操作前x肯定是没有兄弟的，执行删除操作后x肯定是有兄弟的
w = x->p->left;
//第一种情况：w是红色的
if(w->color == RED)
{
//改变w和p[x]的颜色
w->color = BLACK;
x->p->color = RED;
//对p[x]进行一次左旋
Right_Rotate(x->p);
//令w为x的新兄弟
w = x->p->left;
//转为2.3.4三种情况之一
}
//第二情况：w为黑色，w的两个孩子也都是黑色
if(w->right->color == BLACK && w->left->color == BLACK)
{
//去掉w和x的黑色
//w只有一层黑色，去掉变为红色，x有多余的一层黑色，去掉后恢复原来颜色
w->color = RED;
//在p[x]上补一层黑色
x = x->p;
//现在新x上有个额外的黑色，转入for循环继续处理
}
//第三种情况，w是黑色的,w->right是红色的,w->left是黑色的
else
{
if(w->left->color == BLACK)
{
//改变w和right[x]的颜色
w->right->color = BLACK;
w->color = RED;
//对w进行一次右旋
Left_Rotate(w);
//令w为x的新兄弟
w = x->p->left;
//此时转变为第四种情况
}
//第四种情况：w是黑色的,w->right是黑色的,w->left是红色的
//修改w和p[x]的颜色
w->color =x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
//对p[x]进行一次左旋
Right_Rotate(x->p);
//此时调整已经结束，将x置为根结点是为了结束循环
x = root;
}
}
}
//吸收了额外的黑色
x->color = BLACK;
}
//找最小值
node *Os_Tree::Tree_Minimum(node *x)
{
//只要有比当前结点小的结点
while(x->left != nil)
x = x->left;
return x;
}
//查找中序遍历下x结点的后继，后继是大于key[x]的最小的结点
node *Os_Tree::Tree_Successor(node *x)
{
//如果有右孩子
if(x->right != nil)
//右子树中的最小值
return Tree_Minimum(x->right);
//如果x的右子树为空且x有后继y，那么y是x的最低祖先结点，且y的左儿子也是
node *y = x->p;
while(y != NULL && x == y->right)
{
x = y;
y = y->p;
}
return y;
}
//递归地查询二叉查找树
node *Os_Tree::Os_Search(node *x, int k)
{
//找到叶子结点了还没找到，或当前结点是所查找的结点
if(x->key == -1 || k == x->key)
return x;
//所查找的结点位于当前结点的左子树
if(k < x->key)
return Os_Search(x->left, k);
//所查找的结点位于当前结点的左子树
else
return Os_Search(x->right, k);
}
//红黑树的删除
node *Os_Tree::Os_Delete(node *z)
{
//找到结点的位置并删除，这一部分与二叉查找树的删除相同
node *x, *y;
if(z->left == nil || z->right == nil)
y = z;
else y = Tree_Successor(z);
node *p = y->p;
while(p != nil)
{
p->size--;
p = p->p;
}
if(y->left != nil)
x = y->left;
else x = y->right;
x->p = y->p;
if(y->p == nil)
root = x;
else if(y == y->p->left)
y->p->left = x;
else
y->p->right = x;
if(y != z)
z->key = y->key;
//如果被删除的结点是黑色的，则需要调整
if(y->color == BLACK)
Os_Delete_Fixup(x);
return y;
}
void Os_Tree::Print(node *x)
{
if(x->key == -1)
return;
Print(x->left);
cout<<x->key<<' '<<x->color<<endl;
Print(x->right);
}
void Os_Tree::Print()
{
Print(root);
cout<<endl;
}
//查找以x为根结点的树中第i大的结点
node *Os_Tree::Os_Select(node *x, int i)
{
//令x左子树中点的个数为r-1,
int r = x->left->size +1;
//那么x是x树中第r大的结点
if(r == i)
return x;
//第i大的元素在x->left中
else if(i < r)
return Os_Select(x->left, i);
//第i大的元素在x->right中
else
return Os_Select(x->right, i - r);
}
//计算树T中进行顺序遍历后得到的线性序中x的位置
int Os_Tree::Os_Rank(node *x)
{
//置r为以x为根的子树中key[x]的秩
int r = x->left->size + 1;
node *y = x;
while(y != root)
{
//若y是p[y]的右孩子，p[y]和p[y]左子树中所有结点前于x
if(y == y->p->right)
r = r + y->p->left->size + 1;
y = y->p;
}
return r;
}
~~~
### 2.main.cpp
~~~
#include <iostream>
#include "Os_Tree.h"
using namespace std;
int main()
{
char ch;
int x;
//生成一棵顺序统计树
Os_Tree *T = new Os_Tree;
while(1)
{
cin>>ch;
switch(ch)
{
//插入一个元素
case 'I':
{
cin>>x;
node *z = new node(T->nil, x);
T->Os_Insert(z);
break;
}
//删除一个元素
case 'D':
{
cin>>x;
node *z = T->Os_Search(T->root, x);
if(z == NULL)
cout<<"not exist"<<endl;
else
T->Os_Delete(z);
break;
}
//计算第x小关键字
case 'S':
{
cin>>x;
node *z = T->Os_Select(T->root, x);
if(z == NULL)
cout<<"not exist"<<endl;
else
cout<<z->key<<endl;
break;
}
//计算x的位置
case 'R':
{
cin>>x;
node *z = T->Os_Search(T->root, x);
if(z == NULL)
cout<<"not exist"<<endl;
else
cout<<T->Os_Rank(z)<<endl;
break;
}
case 'P':
T->Print();
break;
default:
break;
}
}
return 0;
}
~~~
# 三、练习
14.1-3
~~~
//14.1-3非递归地查找以x为根结点的树中第i大的结点
node *Os_Tree::Os_Select_Iterative(node *x, int i)
{
//根结点开始找起
while(x != NULL)
{
int r = x->left->size + 1;
//如果找到了
if(r == i)
return x;
//如果位置更靠前
if(i < r)
x = x->left;
//如果位置更靠后
else
{
x = x->right;
i = i - r;
}
}
}
~~~
14.1-4
~~~
//14.1-4递归地计算树T中进行顺序遍历后得到的线性序中x的位置
int Os_Tree::Os_Rank_Recursion(node *root, node *x)
{
if(x->key == root->key)
return root->left->size + 1;
if(x->key > root->key)
//左子树的结点个数 + 根结点 + x在右结点中的秩
return root->left->size + 1 + Os_Rank_Recursion(root->right, x);
//在左子树中的秩
return Os_Rank_Recursion(root->left, x);
}
~~~
14.1-5
~~~
//14.1-5确定x在该树的线性序中第i个后继
node *Os_Tree::Next(node *x, int i)
{
//就是当前结点
if(i == 0)
return x;
//在x的右子树中
if(x->right != nil && x->right->size >= i)
return Os_Select(x->right, i);
//或在x某个祖先的右子树中
else
{
//找到某个“有右子树”且“x不在其右子树上”的祖先
while(x->p != NULL && x == x->p->right)
x = x->p;
//找到了根结点，就停止查找
if(x->p == NULL)
{
cout<<"error:not exist"<<endl;
exit(0);
}
//对这个祖先进行递归的查找
Next(x, i-1);
}
}
~~~
15.1-6
~~~
附加信息rank[x]
插入时，若插入到x结点的左子树中，则rank[x] = rank[x] + 1，否则不变
删除时，若删除的结点在x的左子树中，则rank[x] = rank[x] - 1，否则不变
左旋时，若对x执行左旋，令y=x->right，则rank[x]不变，rank[y] = rank[y] + rank[x]
右旋时，若对x执行右旋，令y=x->left，则rank[y]不变，rank[x] = rank[x] + rank[y]
~~~
14.1-7
见[算法导论-14.1-7](http://blog.csdn.net/mishifangxiangdefeng/article/details/7730702)
[求逆序数](http://blog.csdn.net/mishifangxiangdefeng/article/details/7175642)中介绍了使用树状数组或归并排序求逆序对，这里使用顺序统计数。
数组中某个数字s[i]的逆序数是指出现在s[i]之前，但是比s[i]大的数字的个数。
根据顺序统计量的Os_Rank()，每插入到一个元素x后，可以求得在已经出现的元素中，比x大的数字的个数
14.1-8【转】
通过角度来判断两条弦是否相交，这样可以在O(n*logn)内完成。
对于两条弦P1P2和Q1Q2来说（顺时针），圆心与端点形成的向量有一个角度A
如果A(P1)<A(Q1)<A(P2)<A(Q2)或者A(Q1)<A(P1)<A(Q2)<A(P2)，这样角度区间“交叉”就意味着两条弦有交叉。
通过角度来统计交叉弦的对数，和“逆序对”的问题本质上是一样的
这可以看做是“顺序统计树”的典型应用。
我们判断两条弦是否相交的依据还是上面提到的“角度”区间是否有“交叉”现象发生
（注意一个区间包含另一个区间的情况不能算作“交叉”）
首先n条弦共2n个端点，每个端点对于圆心来说，都对应一个[0,2*pi)内的角度。
我们按角度大小（实际上就是逆时针方向）对这2n个角度进行排序，这一步需要花费O(n*logn)
对于每条弦来说，它的两个端点都可以看做是“事件点”：从0角度开始逆时针在圆上扫描，遇到弦的第一个点可以看成是弦的“起点”，遇到的第二个点看成是弦的“终点”。
然后，我们用一棵“顺序统计树”来辅助进行处理（初始化当然为空）。
~~~
按照角度小到大的顺序遍历这2n个端点：
如果该端点是某条弦X的“起点”
{
将弦X插入顺序统计树中（以X的“起点”角度作为key）；
}
如果该端点是某条弦X的“终点”
{
统计出目前这棵树中有多少条弦的“起点”角度比X的“起点”角度大，这就是与X相交的弦的数量；
//对于顺序统计树来说，上面这步只要O(logn)就能实现
将弦X从顺序统计树中删除； //这一步同样只需要O(logn)
}
~~~
第13章 红黑树
最后更新于：2022-04-01 07:35:38
# 一、概念
### 1.定义与性质
（1）定义
红黑树字义：满足(a)每个结点或是红的，或是黑的(b)根结点是黑的(c)每个叶结点（NIL）是黑的(d)如果一个结点是红的，则它的两个儿子是黑的(e)对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点的二叉查找树称为红黑树。
黑高度定义：从某个结点x出发（不包括该结点）到达一个叶结点的任意一条路径上的黑色结点的个数称为x的黑高度。
（2）性质
红黑树确保没有一条路径会比其它路径长出两倍。
一棵有n个内结点的红黑树的高度至多为2lg(n+1)
### 2.结构
（1）红黑树结点结构
~~~
struct node
{
node *left;
node *right;
node *p;
int key;
bool color;
};
~~~
（2）红黑树结构
~~~
struct Red_Black_Tree
{
node *root;//根结点
node *nil;//哨兵
};
~~~
### 3.红黑树上的操作
SEARCH
PREDECESSOR
MINIMUM
MAXIMUM
INSERT
DELETE
# 二、代码
[头文件](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/include/chapter13/redBlackTree.h)
[产品代码](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/src/chapter13/redBlackTree.cpp)
[测试代码](https://code.csdn.net/mishifangxiangdefeng/exerciseforalgorithmsecond/tree/master/tst/chapter13/redBlackTreeTest.cpp)
代码说明：
1.使用NIL作为叶子结点，代替NULL，这样可以少一些特殊处理
2.删除一个结点,delete改为remove，一方面是避免与关键字冲突，另一方面，觉得remove语义更符合
3.insert和remove使用int key代替node *z作为参数，觉得这样使用更方便
# 三、练习
### 13.1 红黑树的性质
13.1-1
黑高度是指从根结点到叶结点的路径上黑色结点的个数，需要注意的是，计算黑高度时，出发的结点不计算在内，叶结点是指nil结点
13.1-2
不是，因为违反性质4
不是，因为违反性质5
13.1-3
是
13.1-4
[http://zh.clrs-ans.wikia.com/index.php?title=13.1_%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8&variant=zh-cn](http://zh.clrs-ans.wikia.com/index.php?title=13.1_%E7%BA%A2%E9%BB%91%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8&variant=zh-cn)
叶子深度为黑高度
13.1-5
bh(x)为黑高度，相应的定义rh(x)为红高度，根据RB树性质
rh(x)<=bh(x)，而每条路径的bh(x)都想等，最长可能路径bh(x)+rh(x)，最短可能路径bh(x)，故最长是最短的至多两倍。
13.1-6
最多：2^(2k+1)-1
高少：2^(k)-1
13.1-7
比值最大为2：1，奇数层的结点为红色，偶数层的结点为黑色。n为奇数。
比值最小为0，全部结点都为黑色
### 13.2 旋转
~~~
13.2-1，代码见上文
RIGHT-ROTATE
1 y <- left[x]
2 left[x] <- right[y]
3 if right[y] != nil[T]
4 then p[right[y]] <- x
5 p[y] <- p[x]
6 if p[x] = nil[T]
7 then root[T] <- y
8 else if x = right[p[x]]
9 then right[p[x]] <- y
10 else left[p[x]] <- y
11 right[y] <- x
12 p[x] <- y
13.2-3
a的深度+1，b的深度不变，c的深度-1
~~~
### 13.3 插入
13.3-1
1楼说得很好
~~~
不是因为违反了性质5才不会采用把节点标志位黑色。如果只是因为违反了性质5，完全可以调整，就跟RB-INSERT中将插入的节点标志位红色违反了性质4或者2一样，都是可以通过跳整来符合要求。其原因是插入节点共有六种情况（通过RB-INSERT-FIXUP中的判断语句可以看出：插入节点z的父节点为左孩子有三种，为右孩子也有三种。举父节点为左孩子为例：第一种为如果z的叔叔为红是第一种情况，如果叔叔为黑且z为右孩子为第二种情况，如果叔叔为黑且z为左孩子为第三种情况），前三种情况中只有第二种z最终为黑色节点，其余两种z最终为红色。z最终为红色的比例较高，（4:2），所以一开始将z定义为红色，最后不用修改的概率较高，这是考虑到代码的优化而不是因为违反了性质5。
~~~
13.3-2
运行以上程序能得到结果
13.3-6
见[算法导论-13.3-6](http://blog.csdn.net/mishifangxiangdefeng/article/details/7727271)
令待插入的元素是z。在插入的过程记录从根结点到z的路径，并用栈存储。那么z的父结点就是栈顶元素，z的祖父结点就是栈的次顶元素。
在向上迭代的过程同时出栈，控制好出栈的时间，就能正确实现RB-INSERT
### 13.4 删除
~~~
13.4-3
运行以上程序能得到结点
13.4-4
（1）某黑色结点被删除后，第一个被调整的点是被删除结点的孩子（这个被删除的结点最多只有一个孩子），若这个被删除结点没有孩子，那么第一个被高速的点是nil
（2）x的兄弟w没有孩子，或左旋时w没有左孩子，或右旋时w没有右孩子
13.4-7
可能不相同。
（1）新加入结点后可能会导致某些旋转操作，删除后不会转回来
（2）即使树的结构不变，结点的颜色也有可能会改变
~~~
# 四、思考题
### 13-1 动态持久集合
见[算法导论-13-1-持久动态集合](http://blog.csdn.net/mishifangxiangdefeng/article/details/7903794)
### 13-2 红黑树上的连接操作
见[算法导论-13-2-红黑树上的连接操作](http://blog.csdn.net/mishifangxiangdefeng/article/details/7904581)
第12章 二叉查找树
最后更新于：2022-04-01 07:35:35
# 一、概念
### 1.定义与性质
（1）设x为二叉查找树中的一个结点，若y是x左子树中的一个结点，则key[y] <= key[x]；若y是x右子树中的一个结点，则key[x]<=key[y]
（2）二叉查找树上执行的基本操作的时间与树的高度成正比。
### 2.结构
（1）结点结构：
关键字key
卫星数据data
分别指向父、左右孩子的指针p, left, right
### 3.在二叉查找树上的操作
查找一个关键字：SEARCH(x, k)
求最小关键字：MINIMUM(x)
求最大关键字：MAXIMUM(x)
求前驱：PREDECESSOR(x)
求后继：SUCCESSOR(x)
插入一个结点：INSERT(T, z)
删除一个结点：DELETE(z)
### 4.二叉查找树的应用
1.遍历：中序遍历、先序遍历、后序遍历
2.查找：查找包含某个关键字的结点，查找关键字最大或最小的结点、查找某个结点的前驱或后继
# 二、代码
[头文件](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/include/binarySearchTree.h)
[产品代码](https://code.csdn.net/mishifangxiangdefeng/algoritmcollection/tree/master/src/binarySearchTree.cpp)
测试代码
# 三、练习
### 12.1 二叉查找树
12.1-2
二叉查找树：左子树关键字<根结点关键字<右子树关键字
堆：左子树关键字<根结点关键字 && 右子树关键字<根结点关键字
不能，因为一个结点的的左子树与右子树的关键字大小没有关系
12.1-3
用栈实现：见[算法导论-10.4-有根树的表示](http://blog.csdn.net/mishifangxiangdefeng/article/details/7707756)中的10.4-3
不用栈实现：见[算法导论-10.4-5](http://blog.csdn.net/mishifangxiangdefeng/article/details/7708490)
12.1-4
~~~
//递归的先序遍历
void BST_Tree::Preorder_Tree_Walk(BST_Node *x)
{
//x不是叶子结点
if(x != NULL)
{
//访问当前结点
cout<<x->key<<' ';
//先序遍历当前结点的左子树
Preorder_Tree_Walk(x->left);
//先序遍历当前结点的右子树
Preorder_Tree_Walk(x->right);
}
}
//递归的后序遍历
void BST_Tree::Postorder_Tree_Walk(BST_Node *x)
{
//x不是叶子结点
if(x != NULL)
{
//后序遍历当前结点的左子树
Postorder_Tree_Walk(x->left);
//后序遍历当前结点的右子树
Postorder_Tree_Walk(x->right);
//访问当前结点
cout<<x->data<<' ';
}
}
~~~
### 12.2 查询二叉查找树
~~~
12.2-1
c，e
12.2-2
//递归地查找最小值
BST_Node *BST_Tree::Tree_Minimum(BST_Node *x)
{
if(x->left != NULL)
return Tree_Minimum(x->left);
else return x;
}
//递归的查找最大值
BST_Node *BST_Tree::Tree_Maximum(BST_Node *x)
{
if(x->right != NULL)
return Tree_Maximum(x->right);
else return x;
}
12.2-3
//查找中序遍历下x的前驱，即小于x的最大值
BST_Node *BST_Tree::Tree_Predecessor(BST_Node *x)
{
//如果x的左子树非空
if(x->left != NULL)
//x的前驱是x的左子树的最大值
return Tree_Maximum(x->left);
//如果x的左子树为空且x有前驱y，那么y是x的最低祖先结点，且y的右儿子也是
BST_Node *y = x->p;
while(y != NULL && x == y->left)
{
x = y;
y = y->p;
}
return y;
}
12.2-4
（1）
4->left = 2 4->right =NIL
2->left = 1 2->right = 3
搜索路径4-2-1
（2）
1->right = 3 1->left = NUL
3->left = 2 3->right = 4
搜索路径1-3-4
~~~
### 12.3 插入和删除
12.3-1
~~~
//递归的二叉查找树的插入操作，分三种情况
void BST_Tree::Tree_Insert(BST_Node *x, BST_Node *z)
{
//已经存在
if(z->key == x->key)
{
cout<<"error:exist"<<endl;
return;
}
//插入到x的左子树中
else if(z->key < x->key)
{
//x没有左子树
if(x->left == NULL)
{
//修改指针，插入操作
x->left = z;
z->p = x;
return;
}
//x有左子树
else
//对x的左子树执行插入操作
Tree_Insert(x->left, z);
}
//插入到x的右子树中，与上面类似
else if(z->key > x->key)
{
if(x->right == NULL)
{
x->right = z;
z->p = x;
}
else
Tree_Insert(x->right, z);
}
}
~~~
12.3-3
最坏是n^2
最好是nlgn
12.3-4
求y的前驱z分为两种情况，以下分别讨论：
（1）y有左孩子，则z是left[y]中最右边的结点，z没有右孩子，因此删除z时直接删除修改指针即可，没有问题
（2）y没有左孩子，则z是y的祖先，y是z右子树是最左边的点，又分为两种情况：
（2.1）若z没有左孩子，则直接删除z并修改指针，没有问题。
（2.2）若z有左孩子，则不直接删除z，而是用z代替y存在并删除y。这里会有问题，另一个数据结构中的保存了指向y的指针，但是y的内容转移到另一个结点上了，指向y的指针指向了一个被释放的空间。
解决方法：使TREE-DELETE返回删除后的y的指针，这个值可能会变，可能不变。让另一个数据结构的y指针指向TREE-DELETE的返回值。
12.3-5
不或交换，反例如图
12.3-6
当待删除结点有两个子树时，不删除待删除结点，而是删除它的前驱或后继，用随机数rand()%2来确定删除的前驱还是后继
代码见文：二
# 四、思考题
### 12-1 具有相同关键字元素的二叉树
见[算法导论-12-1-具有相同关键字元素的二叉查找树](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719138)
### 12-2 基数树
见[算法导论-12-2-基数树](http://blog.csdn.net/mishifangxiangdefeng/article/details/7719324)
12-3 随机构造的二叉查找树中的平均结点深度
f）待解决
第11章-散列表
最后更新于：2022-04-01 07:35:33
# 一、概念
### 1.综述
散表表仅支持INSERT、SEARCH、DELETE操作。
把关键字k映射到槽h(k)上的过程称为散列。
多个关键字映射到同一个数组下标位置称为碰撞。
好的散列函数应使每个关键字都等可能地散列到m个槽位中
### 2.散表函数
（1）若函数为h(k)=k，就是直接寻址表
（2）除法散列法：h(k) = k mod m
（3）乘法散列法：h(k) = m * (k * A mod 1) (0<A<1)
（4）全域散列：从一组仔细设计的散列函数中随机地选择一个。（即使对同一个输入，每次也都不一样，平均性态较好）
3.冲突解决策略
（1）链接法
（2）开放寻址法
a.线性探测：h(k, i) = (h'(k) + i) mod m
b.二次探测：h(k, i) = (h'(k) + c1*i + c2 *i^2) mod m
c.双重散列：h(k, i) = (h1(k) + i * h2(k)) mod m
（3）完全散列：设计一个较小的二次散列表
# 二、代码
代码中用到了函数指针，函数指针的用法参考[函数指针总结](http://blog.csdn.net/mishifangxiangdefeng/article/details/7209060)
~~~
//Hash.h
#include <iostream>
using namespace std;
int m, NIL = 0;
//11.4 开放寻址法
typedef int (*Probing)(int k, int i);
int h(int k)
{
return k % m;
}
int h2(int k)
{
return 1 + k % (m-1);
}
//线性探测
int Linear_Probing(int k, int i)
{
return (h(k) + i) % m;
}
//二次探测
int Quadratic_Probint(int k, int i)
{
int c1 = 1, c2 = 3;
return (h(k) + c1 * i + c2 * i * i) % m;
}
//双重探测
int Double_Probint(int k, int i)
{
return (h(k) + i * h2(k)) % m;
}
int Hash_Insert(int *T, int k, Probing p)
{
int i = 0, j;
do{
j = p(k, i);
if(T[j] == NIL)
{
T[j] = k;
return j;
}
i++;
}
while(i != m);
cout<<"error:hash table overflow"<<endl;
}
int Hash_Search(int *T, int k, Probing p)
{
int i = 0, j;
while(1)
{
j = p(k, i);
if(T[j] == NIL || i == m)
break;
if(T[j] == k)
return j;
i++;
}
}
~~~
# 三、习题
### 11.1 直接寻址表
~~~
11.1-1
O(m)，最坏情况时，集合中只有一个最小关键字
11.1-2
如果插入x，就把向量的第x位置为1
如果删除x，就把向量的第x位置为0
11.1-3
当存在关键字为key的卫星数据时，T[key]指向其中一个关键字为key的卫星数据。若不存在，T[key]指向空。
每一个卫星数据用一个结点表示，结点中有三个域，分别是：关键字key，卫星数据data，指向下一个所有相同关键字的卫星数据的指针next
DIRECT-ADDRESS-SEARCH(T, k)
return T[k];
DIRECT-ADDRESS-INSERT(T, x)
if T[key[x]] = NULL
then T[key[x]] <- x
else next[x] <- next[T[key[x]]]
next[T[key[x]]] <- x
~~~
11.1-4 见[算法导论-11.1-4](http://blog.csdn.net/mishifangxiangdefeng/article/details/7709567)
用一个栈来存储实际插入的数据，插入时栈向上扩展一个空间，删除时，用栈顶元素补充被删除元素的位置，栈向下回收一个空间，方法类似于P127-11.3-4.
这个非常大的数组中不直接存放数据，而是存放数据在Stack中的位置。
对于一个元素p，如果H[p] < 栈中总元素的个数 && p = Stack[H[p]]，就是存入，否则就是不存在
### 11.2 散列表
11.2-3
所有操作的时间都是O(n/2)，n是一个链表的长度
11.2-4 见[算法导论-11.2-4](http://blog.csdn.net/mishifangxiangdefeng/article/details/7712094)
插入操作时，从自由链表中取出一个空闲slot，填入关键字x，修改指针，链表相应的队列中，具体可以分为以下几种情况：
（1）x所属的slot未被占用，则
step1：把这个slot从自由链表中移出
step2：填入关键字x
step3：修改指针，在这种情况下其next和pre都置为-1
（2）x所属的slot已经被占用，令占用这个slot的关键是y，y也属于这个slot，则
step1：从自由链表中取出一个空闲的slot，这个slot肯定不是x所属的slot，只是拿过来用
step2：填入关键字x
step3：修改指针，把slot链表入到“以x所属的slot为头结点的队列”中
（3）x所属的slot已经被占用，令占用这个slot的关键是y，y不属于这个slot，通过（2）可知，这个情况是有可能的
step1：从自由链表中取出一个空闲的slot，这个slot肯定不是x所属的slot，也不是y所属的slot，只是拿过来用
step2：在新slot中填入关键字y，修改指针，让y使用这个新slot，而把原来的slot空出来还给x
step3：在x所属的slot中填入关键字x
step4：修改“x所属的slot”指针，类似(1)-step3
删除操作时，令待删除的关键字是x，释放x所占用的slot，具体可以分为以下几种情况
（1）x所占用的slot正是x所属的slot，且slot->next=-1，即所有关键字中只有x属于这个slot，x被删除后，slot就空闲了
step1：释放slot到自由链表中
（2）x所占用的slot正是x所属的slot，但还有别的关键字中只有x属于这个slot，应该优先使用关键所属于的slot，而释放“不自己关键字的、临时拿过来用的”slat
step1：从以slot为头结点的队列中另选一个slot2，slot2的关键字属于slot而不属于slot2，只是因为slot被占用，所以才用slot2
step2：把slot2的内容填入slot
step3：修改指针，让slot代替slot2存在于队列中，不同的是slot还是队列头
step4：释放slot2到自由链表中
（3）x所占用的slot不是x所属的slot，这个种情况下，这个slot一定不是队列头，还有别的关键字存在于队列中，并且占用了x所属的slot
step1：把x所占用的slot从“以x所属的slot为头的队列”中移出
step2：释放slot到自由链表中
查找操作，如果理解了插入和删除，查找操作就比较简单了，令待查找的关键字是x，也可分为几种情况
（1）x所属的slot未被占用，即不存在与x相同slot的关键字，当然也不存在x了
（2）x所属的slot被占用了，但它所存的关键不属于这个slot，与（1）相同，不存在与x相同slot的关键字
（3）x所属的slot被占用了，且它所存的关键属于这个slot，即存在与x相同slot的关键字，只是不知这个关键字是不是x，需要进一步查找
### 11.3 散列函数
11.3-1
从散列表中的第h(k)个表中搜索关键字为k的一项
11.3-2
每处理字符串中的一个字符，就取一次模
11.3-4
~~~
#include <cmath>
int main()
{
int n;
while(cin>>n)
{
double A = (sqrt(5.0)-1) / 2;
double t1 = A * n;
int t2 = (int)t1;
double t3 = t1 - t2;
int t4 = t3 * 1000;
cout<<t4<<endl;
}
}
~~~
h(61) = 700
h(62) = 318
h(63) = 936
h(64) = 554
h(65) = 172
### 11.4 开放寻址法
11.4-1
线性探测：22 88 0 0 4 15 28 17 59 31 10
二次探测：22 0 88 17 4 0 28 59 15 31 10
双重探测：22 0 59 17 4 15 28 88 0 31 10
代码如下：代码中用到了函数指针，函数指针的用法参考[函数指针总结](http://blog.csdn.net/mishifangxiangdefeng/article/details/7209060)
~~~
#include <iostream>
#include <string>
#include "Hash.h"
using namespace std;
void Print(int *T)
{
int i;
for(i = 0; i < m; i++)
cout<<T[i]<<' ';
cout<<endl;
}
int main()
{
string str;
int i, j;
m = 11;
int T[11], A[9] = {10, 22, 31, 4, 15, 28, 17, 88, 59};
Probing P[3] = {Linear_Probing, Quadratic_Probint, Double_Probint};
for(i = 0; i < 3; i++)
{
memset(T, 0, sizeof(T));
for(j = 0; j < 9; j++)
Hash_Insert(T, A[j], P[i]);
Print(T);
}
return 0;
}
~~~
11.4-2
删除一个元素后，将这个位置置为DELETED，在插入操作中，L3改为if T[j] = NIL or T[j] = DELETED
~~~
#define DELETED -1
int Hash_Insert(int *T, int k, Probing p)
{
int i = 0, j;
do{
j = p(k, i);
if(T[j] == NIL || T[j] == DELETED)
{
T[j] = k;
return j;
}
i++;
}
while(i != m);
cout<<"error:hash table overflow"<<endl;
}
void Hash_Delete(int *T, int k, Probing p)
{
int j = Hash_Search(T, k, p);
if(j != NIL)
T[j] = DELETED;
}
~~~
第10章 10.4 有根树的表示
最后更新于：2022-04-01 07:35:31
# 一、概念
### 1.二叉树
（1）用域p、left、right来存放指向二叉树T中的父亲、左儿子、右儿子。没有则为NULL。
（2）结点结构
~~~
struct node
{
node *p;
node *left;
node *right;
int key;
};
~~~
（3）树的结构
~~~
struct Bin_Tree
{
node *head;
};
~~~
### 2.分支数无限的有根树
（1）左孩子右兄弟表示法
（2）结点结构
~~~
struct node
{
node *p;
node *left_child;
node *right_sibling;
int key;
};
~~~
（3）树的结构
~~~
struct Tree
{
node *head;
};
~~~
# 二、练习
10.4-2
[算法导论 10.4-2 O(n)时间 递归遍历二叉树](http://blog.csdn.net/mishifangxiangdefeng/article/details/39010925)
~~~
TREE-PRINT(T)
1 print key[T]
2 if left[T] != NIL
3 TREE-PRINT(left[T])
4 if right[T] != NIL
5 TREE-PRINT(right[T])
~~~
10.4-3
[算法导论 10.4-3 O(n) 二叉树 非递归遍历](http://blog.csdn.net/mishifangxiangdefeng/article/details/39012249)
~~~
TREE-PRINT(T, S)
1 print key[T]
2 PUSH(S, T)
3 while true
4 if left[T] != NIL
5 then T <- left[T]
6 else
7 do
8 T = POP(S)
9 if T = NIL
10 then return
11 while left[T] = NIL
12 T <- right[T]
~~~
10.4-4
与二叉树的遍历过程相同
10.4-5
见[算法导论-10.4-5](http://blog.csdn.net/mishifangxiangdefeng/article/details/7708490)
采用类似中序遍历的处理方法，对一个结点，可以分为以下几种情况
1.从父结点进入子结点进行处理
（1）如果有左孩子，就处理左孩子
（2）返回到自己
（3）访问自己
（4）如果有右孩子，就处理右孩子
（5）返回到自己的父结点
2.从左孩子返回，说明左孩子已经处理过，自己还没访问，自己的右孩子也没有处理过，就进行1-（2）
3.从右孩子返回，说明左右孩子都已经处理，自己也访问过，就返回到更上层
4.返回到根结点时，遍历结束
10.4-6
去掉parent指针，当布尔值为1时，rightchild指向父结点，当布尔值为0值，rightchild指向右兄弟，其余用法保持不变
第10章 10.3 指针和对象实现
最后更新于：2022-04-01 07:35:29
# 一、概念
1.对象的多重数组表示：对一组具有相同域的对象，每一个对象都可以用一个数组来表示
2.对象的单数组表示：一个对象占据存储中的一组连续位置
# 二、代码
~~~
int Allocate_Object()
{
if(free == NULL)
{
cout<<"error:out of space"<<endl;
exit(0);
}
else
{
int x = free;
free = next[x];
return x;
}
}
void Free_Object(int x)
{
next[x] = free;
free = x;
}
~~~
# 三、练习
10.3-1
多重数组
key :13, 4, 8, 19, 5, 11
next:1, 2, 3, 4, 5, -1
pre:-1, 0, 1, 2, 3, 4
单数组：
13, 3, -1, 4, 6, 3, 8, 9, 6, 19, 12, 9, 5, 15, 12, 11, 18, 15
10.3-2
~~~
ALLOCATE-OBJECT()
1 if free = NIL
2 then error "out of space"
3 else x <- free
4 free <- A[x+1]
5 return x
FREE-OBJECT(x)
1 A[x+1] <- free
2 free <- x
~~~
10.3-3
在这里prev域没有
在这里在这里prev域没有意义，用不到
10.3-4 见[算法导论-10.3-4](http://blog.csdn.net/mishifangxiangdefeng/article/details/7707149)
假设当前的数组是紧凑的，即数组中有f个元素，都位于数组的前f个位置
分配一个新的元素时，把f+1的位置分配给它
删除一个元素时，假设待删除的元素的位置是i，先修改元素prev[i]的next指针和元素next[i]的prev指针，删除这个元素。这里数组中间就留下一个空位，让第f个元素填充这个空位，具体方法是修改元素prev[f]的next指针和元素next[f]和prev指针
10.3-5
与10.3-4类似