5.六度空间、哈利波特的考试
六度空间
“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。
输入格式
输入第1行给出两个正整数，分别表示社交网络图的结点数NNN（1<N≤1031<N≤10^31<N≤103，表示人数）、边数MMM（≤33×N≤33×N≤33×N，表示社交关系数）。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。
输出格式
对每个结点输出与该结点距离不 ...
多项式的表示和运算
最短路径问题(图的WPL)
最短路径问题的抽象
在网络中，求两个不同顶点之间所有路径中，边的权值之和最小的那一条路径
这条路径就是两点之间的最短路径(Shortest Path)
第一个顶点为源点(Source)
最后一个顶点为终点(Destination)
问题分类
单源点最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
(有向)无权图
(有向)有权图
无向图是一种特殊的有向图，与有向图的原理相同
多源点最短路径问题：求任意两顶点间的最短路径
从某任意源点出发，求所有源点所有其他顶点的最短路径
无权图的单源点最短路径算法
按照递增(非递减)的顺序找出各个顶点的最短路径
这种情况的最短路径的本质：顶点与源点之间的顶点最少
间隔的顶点最少——高度/深度/层数最少
由BFS逐层搜索找到符合条件的最短路径
void BFS(Vertex S)
{
Enqueue(S,Q);
while(!Isempty(Q))
{
V=Dequeue(Q);
f ...
4.救邦德-简单版
Saving James Bond - Easy Version
This time let us consider the situation in the movie “Live and Let Die” in which James Bond, the world’s most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape – he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head… Finally he reached the b ...
图
什么是“图”(Graph)？
表示“多对多”的关系
线性表：“一对一”关系，树：“一对多”关系
实际上，线性表和树都可以认为是图的一种特例
图中包含(两种结构共同建立起图的结构)
一组顶点：通常用V(Vertex)表示顶点集合
一组边：通常用E(Edge)表示边的集合
边是顶点对的组合：
(v,w)∈E(v,w)∈E(v,w)∈E，其中v,w∈Vv,w∈Vv,w∈V，表示无向边v−wv-wv−w
<v,w><v,w><v,w>表示从vvv指向www的边(单行线)，表示有向边v→wv\rightarrow wv→w
不考虑重边和自回路
无重边：对无向边，两个结点之间的边只有一条
无自回路：对有向边，从一个顶点出发的边不能指向该顶点自身
权重：如果图的边上带有权重，则称为“网络”
图的抽象数据类型定义
类型名称：图(Graph)
数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成
操作集：对于任意图G ∈ Graph，以及v ∈ V，e ∈ E
Graph Create():建立并返回空图;
...
继续
每个人都背负着一个沉重的十字架，在缓慢而艰难地向前行走，突然有个人就停了下来，“上帝，这实在太沉重了，请允许我砍掉一些吧！”，于是他把十字架砍去了一小节，背负着减负的十字架继续前行，虽稍微轻松，但前路漫漫，十字架的压力让人依然感觉行走艰难，哦，上帝，让我再砍去一点点吧。感谢上帝，这样我的旅途就轻松多了。
当别人都负重奋力艰难的前行时，他哼着欢快的歌谣，不费力走到了队伍的前头，并暗暗得意于自己的聪明举措。突然前方出现一个宽大的沟壑，眼看着无计可施。这时，后面赶上来的人用他们的十字架搭成了桥梁，顺利渡过。当他也尝试着效仿他们时，才发现他的十字架远远达不到对岸。当别人都已渐渐远行，他只能停在原地懊恼不已。“如果当初不偷懒，我本也可以和他们一样，跨过这道沟壑的”，可是人生很多事情事发后再去后悔已经晚了……
其实我们每个人都背负着各种各样的十字架，在艰难前行。它也许是我们的学习、工作中的压力，也许是我们必须承担的责任和义务。
也许放弃了一切，我们会暂时过得很轻松，但是当人生出现沟坎时，我们将很难跨越。生命中很多东西看似承受会很痛苦，但是如果你面对了、抗过去了，也许就云开日出了。我们的高度也将在这 ...
优先队列、堆、哈夫曼树
table th:nth-of-type(1){
width: 15%;
}
table th:nth-of-type(2){
width: 15%;
;
}
table th:nth-of-type(3){
width: 15%;
}
table th:nth-of-type(4){
width: 15%;
}
table th:nth-of-type(5){
width: 15%;
}
table th:nth-of-type(6){
width: 15%;
}
优先队列
优先队列(Priority Queue)：特殊的“队列”，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序
问题：如何组织优先队列？
一般的数组、链表？
有序的数组或链表？
二叉搜索树、AVL树？
优先队列的实现
若采用数组或链表实现优先队列
数组：
插入——元素总是插入尾部——Θ(1)Θ(1)Θ(1)
删除——查找最大(或最小)的关键字——Θ(n)Θ(n)Θ(n)
从数组中删去关键字需要移动其他元素——Θ(n)Θ(n)Θ(n)
链表：
插入——元素总是插入 ...
二叉搜索树、平衡二叉树
table th:nth-of-type(1){
width: 12%;
}
table th:nth-of-type(2){
width: 8%;
;
}
table th:nth-of-type(3){
width: 8%;
}
table th:nth-of-type(4){
width: 8%;
}
table th:nth-of-type(5){
width: 8%;
}
table th:nth-of-type(6){
width: 8%;
}
table th:nth-of-type(7){
width: 8%;
}
table th:nth-of-type(8){
width: 8%;
}
table th:nth-of-type(9){
width: 8%;
}
table th:nth-of-type(10){
width: 8%;
}
table th:nth-of-type(11){
width: 8%;
}
二叉搜索树
由查找问题：针对静态查找和动态查找，数据应如何组织
需要特定的数据读取、插入和删除方式
二叉搜索树的定义
二叉搜索树(BST,B ...
3.二叉树的同构、判断是否同一棵二叉搜索树
二叉树的同构
给定两棵二叉树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则称两棵二叉树是“同构”的
现给定两棵树，请判断是否同构
输入格式
输入给出两颗二叉树的信息
先在一行中给出该树的结点数
随后n行中，第i行对应编号第i个结点，给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的百脑汇
如果孩子结点为空，则在相应位置上给出’-’
输入样例
8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
求解思路
二叉树表示
建二叉树
同构判别
二叉树表示
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1 //注意区别于cstdlib中的NULL(0)，因为0也是下标，所以将“指针”为空的情况设置为-1
结构数组表示二叉树：静态链表 ...
二叉树
二叉树
二叉树(Binary Tree):一个有穷的结点集合
集合可以为空
若不为空，则它是由根结点以及它的左子树Tl和右子树Tr的两个不相交的二叉树组成
二叉树五种具体基本形态
空树/叶结点/只有左子树/只有右子树/同时具有左子树和右子树
二叉树的子树有左右顺序之分
二叉树类型(结点分布形态的角度)
斜二叉树(Skewed Binary Tree)
只在一个方向上有孩子结点，实际上相当于一个线性结构
完美二叉树(Perfect Binary Tree)
满二叉树(Full Binary Tree)
完全二叉树(Complete Binary Tree)
完全二叉树和满二叉树的关系：
有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i(1<=i<=n)结点与满二叉树中编号为i结点在二叉树中位置相同(允许缺失最后几个结点)
二叉树的几个重要性质
一个二叉树第i层的最大结点数为：2i−1,i≥12^{i-1},i\geq12i−1,i≥1
深度为k的二叉树有最大结点总数(满二叉树)为：−1+2k,k≥1-1+ ...
2.汉诺塔的非递归实现、File Transfer
汉诺塔的非递归实现
借助堆栈以非递归（循环）方式求解汉诺塔的问题（n, a, b, c），即将N个盘子从起始柱（标记为“a”）通过借助柱（标记为“b”）移动到目标柱（标记为“c”），并保证每个移动符合汉诺塔问题的要求。
输入格式
输入为一个正整数N，即起始柱上的盘数。
输出格式
每个操作（移动）占一行，按柱1 -> 柱2的格式输出。
输入样例
3
输出样例
a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c
参考代码
/* hanoi塔的递归实现
#include<cstdio>
void hanoi(int,char,char,char)；
int main(){
int n;
scanf("%d",&n);
hanoi(n,'a','c','b');
return 0;
}
void hanoi(int ranks,cha ...
