神秘国度的爱情故事 数据结构课设

数据结构课设"/>

神秘国度的爱情故事 数据结构课设

本课设资源包神秘国度的爱情故事.zip

设计任务及要求

1. 任务：某个太空神秘国度中有很多美丽的小村，从太空中可以想见，小村间有路相连，更精确一点说，任意两村之间有且仅有一条路径。小村A 中有位年轻人爱上了自己村里的美丽姑娘。每天早晨，姑娘都会去小村B 里的面包房工作，傍晚 6 点回到家。年轻人终于决定要向姑娘表白，他打算在小村C 等着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村 C 是否在小村B 到小村 A 之间的路径上。你可以帮他解决这个问题吗？
2. 要求：输入由若干组测试数据组成。每组数据的第1行包含一正整数N ( l<N<50000) , 代表神秘国度中小村的个数，每个小村即从0到N-l编号。接下来有 N -1 行输入，每行包含一条双向道路的两个端点小村的编号，中间用空格分开。之后一行包含一正整数M (l<M<500000) ，代表着该组测试问题的个数。接下来M行，每行给出A、B、C三个小村的编号，中间用空格分开。当N为0时，表示全部测试结束，不要对该数据做任何处理。
3. 输出要求：对每一组测试给定的A、B、C，在一行里输出答案，即：如果C 在 A 和B之间的路径上，输出Yes，否则输出No.

需求分析

题意即以无向图的方式输入一个神秘国度的地图，其有N个节点、N-1条路径，节点编号为0至N-1，给出M组A、B、C,让我们求节点C是否在节点A到节点B的路径上，是则输出“Yes”,否则“No”。其中l<N<50000，l<M<500000，每组A、B、C的编号均应<=N-1且>=0。
该实质上这个地图为一棵树，树以无向图的形式输入，那么就需要这样几个功能：按输入构建地图、将输入的地图转换成树、判断C是否在路径AB上。测试数据若不在应在范围内，则提示“输入错误，请重新输入”。

系统实现

本次课设我定义了三个结构体， Edge为两个结点（村子）之间的相连的边，Vex为结点（村子），Graph为整个神秘国度，有点像无向图的邻接表表示，但每个节点的属性又多了树的双亲和深度的数据。

首先要根据输入构建神秘国度，通过遍历生成树，遍历从0号村子开始，对每个节点访问的时候处理出它在树中的深度和双亲节点信息。至于是深度优先遍历还是广度优先遍历并不重要，目的是让这个图转换成一棵树，不同方法的遍历并不会改变两个节点间的路径。
至于求C是否在AB路径上有很多求法，但基本都不能离开A与B的最近公共祖先，AB的最近公共祖先是AB路径上的必经之点，我想到了两个方法：
一是数组路径法，即从A、B节点往上跳求出A、B最近公共祖先的时候将经过的节点存到数组中，再在数组中找是否存在C，存在的话则C在AB路径上，否则不在，最好的情况时间复杂度是O(1)最坏的情况是O(NM)。

//数组路径法主要模块
void Ancestor(Graph G, int v, int w) {//求两个村子的最近公共祖先，在此过程中求得路径上的节点并存入数组中 if (G.v[v].depth < G.v[w].depth) swap(v,w);way.push_back(v);for (int i = 1;G.v[v].depth > G.v[w].depth;i++) {v = G.v[v].parent;way.push_back(v);}while (v != w) {v = G.v[v].parent;way.push_back(v);w = G.v[w].parent;way.push_back(w);}
}bool OnArc(Graph G, int a, int b, int c) {//判断C是否在AB上 Ancestor(G, a, b);while(!way.empty()){if (way.back() == c)return true;way.pop_back();}	return false;
}

二是最近公共祖先关系法，即通过判断AC、BC、AB最近公共祖先D、E、F的关系来判断C是否在AB的路径上，当D=E=C时，即C是A、B的公共祖先时，若C=F，则C在AB路径上，否则，若D=C或E=C，则C在AB路径上，其余则C不在AB路径上。

//最近公共祖先关系法（未优化）主要模块
int LCA(Graph G, int u, int v) {//在树中找出结点u和结点v的最近公共祖先 if (G.v[u].depth > G.v[v].depth)swap(u, v);//u为深度较小的结点，v为深度较大的结点 int du = G.v[u].depth, dv = G.v[v].depth;int tu = u, tv = v;for (int det = dv - du, i = 0; i < det; i++)//两个结点的深度差为det，结点v先往上跑det个长度，使得这两个结点在同一深度 tv = G.v[tv].parent;if (tu == tv) return tu;//如果他们在同一深度的时候，在同一结点了，那么这个结点就是这两个结点的最近公共祖先 while (tu != tv) {//他们不在同一结点，却在同一深度了，那就两个结点一起往上跳一个单位tu = G.v[tu].parent;//直到跳到同一个结点，那这个结点就是它们的最近公共祖先 tv = G.v[tv].parent;}return tu;//返回最近公共祖先 
}void solve(Graph G, int a, int b, int c) {//在树node中，查询结点c是否在a和b的路径上 int d = LCA(G, a, b);//找出a和b结点的最近公共祖先为d int ac = LCA(G, a, c);//找出a和c结点的最近公共祖先为ac int bc = LCA(G, b, c);//找出b和c结点的最近公共祖先为bc//cout<<d<<" "<<ac<<" "<<bc<<endl;if (ac == c&&bc == c) {//如果ac==c并且bc==c，说明c结点是a和b结点的公共祖先 if (c == d) //如果c==d，说明c就是a和b的最近公共祖先,c必定在a和b的路径上 cout << "Yes" << endl;elsecout << "No" << endl;//如果c!=d，说明c不是a和b的最近公共祖先，a和b的路径上不包括c }else if (ac == c || bc == c) //c是a的祖先或者是b的祖先，说明c在a到d的路径上或者在b到d的路径上 cout << "Yes" << endl;//此时c一定是a和b路径上的点 else cout << "No" << endl;//如果c不是a的祖先，也不是b的祖先，则a和b的路径上不会经过c点 
}

而最近公共祖先法又进行了一次优化，所以分为未优化和优化版本，未优化版本同数组路径法一样从A、B一级一级往上跳找最近公共祖先, 最好的情况时间复杂度是O(1)最坏的情况是O(NM)，数量级上与数组法相同，但由于数组法只求了一次最近公共祖先，而该方法用了三次，所以该方法所用时间比数组法要多；优化版本则从A、B以2^i递增地向上跳找最近公共祖先，时间复杂度是O(MlogN)，数据量较大时节省了很多时间。

//最近公共祖先关系法（优化）
int LCA_(Graph G, int u, int v) {if (G.v[u].depth > G.v[v].depth)swap(u, v); int du = G.v[u].depth, dv = G.v[v].depth;int tu = u, tv = v;for (int det = dv - du, i = 0; det; det >>= 1, i++) if (det & 1) //将深度差拆分成二进制进行结点的2^i跳跃，优化了之前的一个一个跳跃的方法tv = G.v[tv].p[i];if (tu == tv)return tu; for (int i = 20 - 1; i >= 0; i--) {//他们不在同一结点，却在同一深度了，那就两个结点一起往上跳2^i单位if (G.v[tu].p[i] == G.v[tv].p[i])//如果会跳过头了，则跳过这一步跳跃continue;tu = G.v[tu].p[i];tv = G.v[tv].p[i];}return G.v[tu].p[0];//循环结束后，这两个结点在同一深度，并且差一个单位就会跳跃到同一个结点上，
}void solve_(Graph G, int a, int b, int c) { int d = LCA_(G, a, b); int ac = LCA_(G, a, c); int bc = LCA_(G, b, c);//cout<<d<<" "<<ac<<" "<<bc<<endl;if (ac == c&&bc == c) { if (c == d) cout << "Yes" << endl;elsecout << "No" << endl; }else if (ac == c || bc == c) cout << "Yes" << endl;else cout << "No" << endl; 
}

测试

随机生成一颗N个结点的树和Q次询问，保证生成的树是合法的和询问是合法的。思路是：先生成一个随机乱序的0~N-1组成的数组放入队列q中，队列q存储的是为匹配的结点，队列que存储的是已经即将要匹配的结点。比如说，随机生成一个乱序数组为5，3，2，4，1，0。队列q中5先出列放入却中。1.Que取出队首元素u，然后随机生成一个tmp表示u有tmp个分支结点，然后取队列中tmp个数，队列中的前tmp个数再取出来放入que中,回到1继续执行，直到q的队列为空，则生成一颗随机树成立。这样我们就可以随机生成树和查询数据来测试程序的运行效率了。

#include<iostream>
#include <cstdio>
#include <queue>
#include<ctime>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn = 250000 + 10;
const int inf = int(1e9) + 7;
const int mod = 1000000007;
int top = 1;
queue<int>q;
queue<int>que;
void init(int n) {    //随机生成0~n-1的乱序数组，存入队列q中 while (!q.empty())q.pop();int num[maxn];for (int i = 0; i<n; i++)num[i] = i;time_t t;srand((unsigned)time(&t));for (int i = 0; i<n; i++) {int tmp = (rand() + top) % n;//cout << tmp << endl;int t = num[i];num[i] = num[tmp];num[tmp] = t;}for (int i = 0; i<n; i++) {q.push(num[i]);//cout <<num[i]<<" ";}//cout<<endl;
}
void greattree(int n) {      //随机生成n个结点的树，和n-1条边的结点之间的关系 cout << n << endl;time_t t;srand((unsigned)time(&t));int u = q.front();q.pop();que.push(u);n--;while (!que.empty()) {u = que.front();que.pop();int tmp = (rand() + top) % n;    //分支情况完全随机的情况下 tmp = tmp % 2;    //退化成单链表的情况下 if (tmp == 0 && que.empty())tmp++;for (int i = 1; i <= tmp; i++) {if (q.empty())break;int v = q.front();q.pop();que.push(v);cout << u << " " << v << endl;}}
}
void greatequery(int n) {           //随机生成tmp组查询数据，保证a!=b,b!=c,a!=c time_t t;srand((unsigned)time(&t));int tmp = (rand() + top) % n + 100;cout << tmp << endl;for (int i = 1; i <= tmp; i++) {int a = (rand() + top) % n;int b = (rand() + top) % n;int c = (rand() + top) % n;if (a == b || b == c || a == c){i--;continue;}cout << a << " " << b << " " << c << endl;}
}
int main() {
#ifndef OnLINE_JUGEfreopen("D:\\test_in.txt", "w", stdout);   //将生成的随机树和随机询问写入测试样例文件test_in.txt中 
#endifint T, n;cin >> T >> n;        //生成具有T组测试样例，每组测试样例有n个结点的树 cout << T << endl;top = 0;for (int i = 1; i <= T; i++) {top++;               //全局变量top不断变化，和时间种子相结合，保证每一组随机生成的数据都不一样 init(n);             //随机生成0~n-1的乱序数组，存入队列q中greattree(n);        //随机生成n个结点的树，和n-1条边的结点之间的关系 greatequery(n);      //随机生成tmp组查询数据，保证a!=b,b!=c,a!=c }return 0;
}

读图代码

#ifndef OnLINE_JUGEfreopen("test_in.txt", "r", stdin);                        //数据输入为测试数据文件test_in.txt的内容freopen("test_out.txt", "w", stdout);                    //数据输出到结果文件test_out.txt中 
#endif 

程序代码

三种方法整合版源程序：

#include <iostream>
#include <stdio.h>
#include <stdlib.h> 
#include <queue>#define OVERFLOW -2
using namespace std;vector<int>way;typedef struct Edge {//两个村子相邻的边 int v;//邻接点 Edge* next;//下一个邻接点 
}Edge;typedef struct Vex {//村子int data, parent, depth;//村子的编号、双亲节点、深度 int p[20];//最近公共祖先关系法（优化）增加部分 Edge* firstedge;//第一个邻接点 
}Vex;typedef struct {Vex *v;//村子数组 int vexnum, arcnum;//村子个数、边数 
}Graph;//神秘国度void InitGraph(Graph& G, int N) {//初始化神秘国度 G.v = (Vex*)malloc(N * sizeof(Vex));if(!G.v) exit(OVERFLOW);for (int i = 0;i < N;i++) {G.v[i].data = i;G.v[i].parent = -1;G.v[i].depth = -1;G.v[i].firstedge = NULL;}G.vexnum = N;G.arcnum = N - 1;
}void CreateGraph(Graph& G, int N) {//构建神秘国度 int v, w;Edge *p,*q;cout<<"请输入村子间的"<<N-1<<"条路径（每条路输入两个端点，端点用空格分开）"<<endl; for (int i = 0;i < N - 1;i++) {while(1){cin >> v >> w;if(v<0||v>N-1||w<0||w>N-1||v==w){cout<<"输入有误，请重新输入"<<endl; }else break;}		p = (Edge*)malloc(sizeof(Edge));p->next = G.v[v].firstedge;G.v[v].firstedge = p;p->v = w;q = (Edge*)malloc(sizeof(Edge));q->next = G.v[w].firstedge;G.v[w].firstedge = q;q->v = v;}
}void BFS(Graph G) {//bfs广度优先遍历，预处理出每一个结点的深度和和对应的第2^i个父亲结点 queue<int>q;//队列G.v[0].depth = 0;//树的根结点的深度为0G.v[0].p[0] = G.v[0].parent = 0;//树的根结点的第2^0（第一）个父亲结点为他自己q.push(0);//根结点入队 while (!q.empty()) {int u = q.front();//将队列的头结点u出队q.pop();for (int i = 1; i < 20; i++)//u的第2^i个父亲结点等于u的第2^(i-1)个父亲结点的第2^(i-1)个父亲结点G.v[u].p[i] = G.v[G.v[u].p[i - 1]].p[i - 1];Edge* p;for (p = G.v[u].firstedge; p != NULL; p = p->next) {//找出和u相连的边int v = p->v;//v为对应邻接边的邻接结点 if (v == G.v[u].p[0]) continue;//因为存储的是双向边，所以防止再访问到已经访问过的父亲结点 G.v[v].depth = G.v[u].depth + 1;//结点的深度为父亲结点的深度+1G.v[v].p[0] = u;//记录v结点的父亲结点为uG.v[v].parent = u;q.push(v);//v结点入队}}
}void swap(int &v,int &w){int temp = v;v = w;w = temp;
}void Ancestor(Graph G, int v, int w) {//求两个村子的最近公共祖先，在此过程中求得路径上的节点并存入数组中 if (G.v[v].depth < G.v[w].depth) swap(v,w);way.push_back(v);for (int i = 1;G.v[v].depth > G.v[w].depth;i++) {v = G.v[v].parent;way.push_back(v);}while (v != w) {v = G.v[v].parent;way.push_back(v);w = G.v[w].parent;way.push_back(w);}
}bool OnArc(Graph G, int a, int b, int c) {//判断C是否在AB上 Ancestor(G, a, b);while(!way.empty()){if (way.back() == c)return true;way.pop_back();}	return false;
}int LCA(Graph G, int u, int v) {//在树中找出结点u和结点v的最近公共祖先 if (G.v[u].depth > G.v[v].depth)swap(u, v);//u为深度较小的结点，v为深度较大的结点 int du = G.v[u].depth, dv = G.v[v].depth;int tu = u, tv = v;for (int det = dv - du, i = 0; i < det; i++)//两个结点的深度差为det，结点v先往上跑det个长度，使得这两个结点在同一深度 tv = G.v[tv].parent;if (tu == tv) return tu;//在同一深度时，在同一结点，则该结点就是这两个结点的最近公共祖先 while (tu != tv) {//不在同一结点却在同一深度，那就两个结点一起往上跳一个单位tu = G.v[tu].parent;//直到跳到同一个结点，那这个结点就是它们的最近公共祖先 tv = G.v[tv].parent;}return tu;//返回最近公共祖先 
}int LCA_(Graph G, int u, int v) {//在树node中，找出结点u和结点v的最近公共祖先if (G.v[u].depth > G.v[v].depth)swap(u, v);int du = G.v[u].depth, dv = G.v[v].depth;int tu = u, tv = v;for (int det = dv - du, i = 0; det; det >>= 1, i++)if (det & 1)//将深度差拆分成二进制进行结点的2^i跳跃，优化了之前的一个一个跳跃的方法tv = G.v[tv].p[i];if (tu == tv)return tu;//如果他们在同一深度的时候，在同一结点了，那么这个结点就是这两个结点的最近公共祖先for (int i = 20 - 1; i >= 0; i--) {//不在同一结点却在同一深度，那就两个结点一起往上跳2^i单位if (G.v[tu].p[i] == G.v[tv].p[i])//如果会跳过了，则跳过这一步跳跃continue;tu = G.v[tu].p[i];tv = G.v[tv].p[i];}return G.v[tu].p[0];
}  void solve(Graph G, int a, int b, int c) {//在树node中，查询结点c是否在a和b的路径上 int d = LCA(G, a, b);//a、b结点的最近公共祖先为d int ac = LCA(G, a, c);//a、c结点的最近公共祖先为ac int bc = LCA(G, b, c);//bc结点的最近公共祖先为bc  if (ac == c&&bc == c) {//如果ac=c并且bc=c，说明c结点是a和b结点的公共祖先 if (c == d) //如果c==d，说明c就是a和b的最近公共祖先,c必定在a和b的路径上 cout << "Yes" << endl;elsecout << "No" << endl;//如果c!=d，说明c不是a和b的最近公共祖先，a和b的路径上不包括c }else if (ac == c || bc == c) //c是a的祖先或者是b的祖先，说明c在a到d的路径上或者在b到d的路径上 cout << "Yes" << endl;//此时c一定是a和b路径上的点 else cout << "No" << endl;//如果c不是a的祖先，也不是b的祖先，则a和b的路径上不会经过c点 
}void solve_(Graph G, int a, int b, int c) {int d = LCA_(G, a, b);int ac = LCA_(G, a, c);int bc = LCA_(G, b, c);if (ac == c&&bc == c) { if (c == d)cout << "Yes" << endl;elsecout << "No" << endl;}else if (ac == c || bc == c) cout << "Yes" << endl;else cout << "No" << endl;
}int main() {int N, M, a, b, c;while(1){cout<<"请输入村子的数目："; cin >> N;if(N<=1||N>=50000){cout<<"输入有误，请重新输入"<<endl; }else break;}Graph G;InitGraph(G, N);CreateGraph(G, N);BFS(G); while(1){cout<<"请输入测试问题个数："; cin >> M;if(M<=1||M>=500000){cout<<"输入有误，请重新输入"<<endl; }else break;}for (int i = 0;i < M;i++) {while(1){cout<<"请输入要查询的村子编号A,B,C：";cin >> a >> b >> c;if(a<0||a>N-1||b<0||b>N-1||c<0||c>N-1)cout<<"输入有误，请重新输入"<<endl;else break;}cout<<"路径数组法："<<endl; if (OnArc(G, a, b, c)) cout << "Yes" << endl;else cout << "No" << endl;way.clear();cout<<"最近公共祖先关系法（未优化）："<<endl; solve(G,a,b,c); cout<<"最近公共祖先关系法（优化）："<<endl;solve_(G,a,b,c);}return 0;
}

我做该课设时参考了brandong的这篇博客
神秘国度的爱情故事 数据结构课设-广州大学