logo资料库

神秘国度的爱情故事-数据结构课设-广州大学.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：1.13M 资料格式：doc 举报 版权申诉
第1页 / 共30页
第2页 / 共30页
第3页 / 共30页
第4页 / 共30页
第5页 / 共30页
第6页 / 共30页
第7页 / 共30页
第8页 / 共30页
资料共30页，剩余部分请下载后查看
    数据结构课程设计
    数据结构课程设计 学院： 计算机科学与教育软件学院 专业班级：网络工程 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 等 着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村 C 是否在小村 B 到小村 A 之间的路径上。你可以帮他解决这个问题吗？ 2 / 30
    输入要求：输入由若干组测试数据组成。每组数据的第 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 #include #include 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; int depth; Edge *firstarc; //结点信息（村子编号） //结点的父亲结点 //结点的深度 //指向第一个邻接边的指针 4 / 30
    }; void creatgraph(Node* node, int n) { //创建一个村落图 Edge *p; int u, v; nodenum = n; edgenum = n - 1; //结点（村庄）的个数 //边数是结点数-1 for (int i = 0; i> 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广度优先遍历，预处理出每一个结点的深度和 父亲结点 queueque; node[root].depth = 0; node[root].fa = root; que.push(root); while (!que.empty()) { //队列 //树的根结点的深度为0 //树的根结点的父亲结点为他自己 //根结点入队 int u = que.front(); //将队列的头结点u出队 que.pop(); Edge* p; for (p = node[u].firstarc; p != NULL; p = p->next) { //找出和u相连的 边 int v = p->adjnode; //v为对应邻 5 / 30
    接边的邻接结点 是双向边，所以防止再访问到已经访问过的父亲结点 if (v == node[u].fa) continue; node[v].depth = node[u].depth + 1; 为父亲结点的深度+1 的父亲结点为u } } } node[v].fa = u; que.push(v); //因为存储的 //结点的深度 //记录v结点 //v结点入队 int LCA(Node* node, int u, int v) { u和结点v的最近公共祖先 //在树node中，找出结点 if (node[u].depth > node[v].depth)swap(u, v); //u为深度较小的结 点，v为深度较大的结点 int hu = node[u].depth, hv = node[v].depth; int tu = u, tv = v; for (int det = hv - hu, i = 1; i <= det; i++) //两个结点的深度 差为det，结点v先往上跑det个长度，使得这两个结点在同一深度 tv = node[tv].fa; if (tu == tv)return tu; 度的时候，在同一结点了，那么这个结点就是这两个结点的最近公共祖先 while (tu != tv) { 点，却在同一深度了，那就两个结点一起往上跳一个单位 tu = node[tu].fa; 结点，那这个结点就是它们的最近公共祖先 tv = node[tv].fa; } return tu; } //如果他们在同一深 //他们不在同一结 //直到跳到同一个 //返回最近公共祖先 void solve(Node* node, int a, int b, int c) { //在树node中，查询 结点c是否在a和b的路径上 int d = LCA(node, a, b); 的最近公共祖先为d int ac = LCA(node, a, c); 的最近公共祖先为ac int bc = LCA(node, b, c); 的最近公共祖先为bc 6 / 30 //找出a和b结点 //找出a和c结点 //找出b和c结点
    //cout<> T; while (T--) { cin >> n; Node *node = new Node[n + 1]; creatgraph(node, n); BFS(node, 0); 7 / 30 //输入测试样例数T //输入结点数n //动态申请n+1个结点空间 //建树 //bfs预处理出树结点的深度和对应的父
    亲结点 径上 间 } cin >> m; while (m--) { //输入m个询问 cin >> a >> b >> c; solve(node, a, b, c); //输入结点编号a，b和c //询问c结点是否在a和b结点的路 } delete node; } return 0; //这组测试样例处理结束，撤销申请的空 未优化过的程序，在查找最近公共祖先的时候是一个一个往上面查找的，所以 在最坏的情况下，时间复杂度会退化到 O(QN),比如说在树退化成单链表的时候 就会时间复杂度就会很高。优化的策略是按照倍增思想进行向上查找，比如 说，一个结点需要跳到它的第 7 个祖先结点那里，一次一次的往上跳跃需要 7 次（如图 001 所示），如果把 7 转换成二进制 111，那就是需要往上跳跃三 次，第一次跳跃 4 个单位，第二次跳跃 2 个单位，第三次跳跃 1 个单位就可以 跳跃到第 7 个祖先结点那里（如图 002 所示）。 8 / 30
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料