数据结构课程设计
学院： 计算机科学与教育软件学院
专业班级：网络工程
161
班
姓名： 卟咚君
学号： 000000000000
2018.07.1
1 / 30
广州大学学生实验报告
开课学院及实验室：计算机科学与工程实验室
2018 年 07 月 11 日
学院
计算机科学与
教育软件学院
年级/专
业/班
网络
161
姓名
卟咚君
学号
实验课
程名称
数据结构课程设计
成绩
实验项
目名称
神秘国度的爱情故事
指导老师
张远平
张艳玲
一、实验目的
1. 自行设计数据的存储结构
2. 自行设计数据的数据结构
3. 能熟练应用所学知识,有一定查阅文献及运用文献资料能力
4. 能体现创造性思维,或有独特见解
5. 能将自己的算法进行优化，并且分析优化的思路
二、实验原理
1、树的广度优先和深度优先的遍历策略
2、时间截，队列的入栈和出栈时间
3、树的结点深度，以及父亲结点的处理
4、求出两个结点的 lca
5、分情况讨论 c 点是否在 a 和 b 结点的路径上
三、实验内容
神秘国度的爱情故事（难度系数 1.5）
题目要求：某个太空神秘国度中有很多美丽的小村，从太空中可以想见，小村
间有路相连，更精确一点说，任意两村之间有且仅有一条路径。小村 A 中有位
年轻人爱上了自己村里的美丽姑娘。每天早晨，姑娘都会去小村 B 里的面包房
工作，傍晚 6 点回到家。年轻人终于决定要向姑娘表白，他打算在小村 C 等着
2 / 30
姑娘路过的时候把爱慕说出来。问题是，他不能确定小村 C 是否在小村 B 到
小村 A 之间的路径上。你可以帮他解决这个问题吗？
输入要求：输入由若干组测试数据组成。每组数据的第 1 行包含一正整数 N ( l
《 N 《 50000 ) , 代表神秘国度中小村的个数，每个小村即从 0 到 N - l 编号。
接下来有 N -1 行输入，每行包含一条双向道路的两个端点小村的编号，中间
用空格分开。之后一行包含一正整数 M ( l 《 M 《 500000 ) ，代表着该组测
试问题的个数。接下来 M 行，每行给出 A 、 B 、 C 三个小村的编号，中间用
空格分开。当 N 为 O 时，表示全部测试结束，不要对该数据做任何处理。
输出要求：对每一组测试给定的 A 、 B 、C，在一行里输出答案，即：如果 C
在 A 和 B 之间的路径上，输出 Yes ，否则输出 No。
思路：在这个课设的题目中，非常巧妙的提出了“任意两村之间有且仅有一条路
径”，我们可以想象的到，这是 n 个结点且刚好有 n-1 条边的连通图，以任意一
个结点为根结点进行广度优先遍历，便会生成一棵树。所以我们处理的方法就
是对一棵树的任意两个结点求他们的最近公共祖先（lca）。这里我定义了两个
结构体 struct Edge 和 struct Node，Edge 为两个结点（村子）之间的相连的边，
Node 为结点（村子）。Node 有两个变量 adjnode 和 next，adjnode 为结点向
量中的相邻结点，next 为指向下一邻接边的指针。Node 有村子的编号信息，
bfs 遍历时的父亲结点，深度信息。用邻接表的方式存储每一个结点与之相连
第一条边，然后每插入一个与之相连的边的时候，都会用头插法的方式更新邻
接表。通过 BFS 预处理出这棵树的结点深度和父亲结点的信息。在查询结点 a
和结点 b 之间的最近公共祖先的时候，我们可以先把结点深度比较大的结点开
始往上一个一个单位的跳，然后跳到和另外一个结点同样的深度的时候停下来，
查看这时候它们是否在同一一个结点上了，如果是，那这个结点就是它们的最
近公共祖先了，不是的话，我们这次就两个结点一起往它们的父亲结点那里一
个一个单位的跳，直到第一次跳到相同的结点的地方，这时，该结点便是它们
3 / 30
的最近公共祖先。通过课设的题目我们可以知道，任意两个结点之间必定存在
且只有一条路径互达，所以这样处理的方法必定可以找到这两个结点的最近公
共祖先。那么如何解决 C 点是否在 A 和 B 的路径上呢？我们可以先找出
A 和 B 的最近公共祖先为 D，A 和 C 的最近公共祖先为 AC，B 和 C 的最近公共
祖先为 BC。如果 AC==C 并且 BC==C，则说明 C 同时是 A 和 B 的最近公共
祖先，这里需要分情况讨论，如果 C==D 的话，则说明 C 就是 A 和 B 的最近
公共祖先，如果 C!=D,则说明 C 不是 A 和 B 的最近公共祖先，则 A 到 D 再走
到 B 的路径中，不会经过 C 结点。如果只有 AC==C 或者 BC==C，则说明 C
是 A 或者 B 中一个且只有一个结点的祖先结点。如果 C 是 A 的祖先结点，不是
B 的祖先结点，则说明 C 在 A 和 D 的路径上，则 C 肯定是在 A 和 B 的路径上。
如果 C 是 B 的祖先结点，不是 A 的祖先结点，则说明 C 在 B 和 D 的路径上，
则 C 肯定是在 A 和 B 的路径上。如果 C 不是 A 和 B 中任意一个结点的祖先结点，
那么从 A 到 B 的路径上不会经过 C 结点。
以下是未优化过的程序的：
时间复杂度为 O(QN),其中，Q 为询问次数，N 为结点（村子）的数量。
（byd001.cpp）
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 50010;
const int DEG = 20;
int edgenum, nodenum;
struct Edge { //边的邻接点
int adjnode; //邻接点在结点向量中的下表
Edge *next; //指向下一邻接边的指针
};
struct Node { //结点结点(村子）
int id; //结点信息（村子编号）
int fa; //结点的父亲结点
4 / 30
int depth; //结点的深度
Edge *firstarc; //指向第一个邻接边的指针
};
void creatgraph(Node* node, int n) { //创建一个村落图
Edge *p;
int u, v;
nodenum = n; //结点（村庄）的个数
edgenum = n - 1; //边数是结点数-1
for (int i = 0; i<nodenum; i++) {
node[i].id = i; //每个小村从0到N-1编号
node[i].firstarc = NULL; //每一个村庄的第一个邻接边的指针初始
化为NULL
}
//接下来有n-1行输入，每行包含一条双向的两个端点小村的编号，中间用空格分开。
//cout << "请输入村子的" << n - 1 << "条路径(两个端点中间用空格分隔):" <<
endl;
for (int i = 1; i <= edgenum; i++) {
cin >> u >> v;
p = new Edge; //下面完成邻接表的建立
p->adjnode = v;
p->next = node[u].firstarc;
node[u].firstarc = p; //类似于头插法
p = new Edge;
p->adjnode = u;
p->next = node[v].firstarc;
node[v].firstarc = p; //路径是双向的
}
}
void BFS(Node* &node, int root) { //bfs广度优先遍历，预处理出每一个结点
的深度和父亲结点
queue<int>que; //队列
node[root].depth = 0; //树的根结点的深度为0
node[root].fa = root; //树的根结点的父亲结点为他自己
que.push(root); //根结点入队
while (!que.empty()) {
int u = que.front(); //将队列的头结点u出队
que.pop();
Edge* p;
5 / 30
