数据结构实验六：简单路径.docx

HUNAN UNIVERSITY课程实验报告题 目： 简单路径 学生姓名 学生学号 专业班级 指导老师 李 晓 鸿 完 成 日 期 2 0 1 5年 12 月 12日 一、需求分析1程序的功能 该程序可以通过构建一个图用来表示各个城市之间是否有高速公路连通的关系，可以实现查询两城市间所有路径的功能,如果存在路径则输出。2.输入的形式 本程序要求用户首先输入一个结点总数，然后输入结点的城市编号，最后输入要查询所有简单路径的两座城市的名称。当用户输入不合法时，提示用户输入有误，并重新输入。输入具体格式如下：请输入城市总数：n（大于零的整数）请输入输入城市1名称：请输入输入城市2名称：请输入输入城市3名称：.请输入输入城市n名称：请输入城市间的高速公路：请输入两所城市的名称：3. 输出的形式 若有路径从城市A到城市B的所有路径如下：/路径1/路径2若无路径两城市不连通4 测试数据正常的输入：请输入城市总数：4请输入输入城市1名称：0001请输入输入城市2名称：0002请输入输入城市3名称：0003请输入输入城市4名称：0004请输入城市间的高速公路：0001 0002请输入城市间的高速公路：0002 0003请输入城市间的高速公路：0003 0004请输入城市间的高速公路：0001 0004请输入城市间的高速公路：0 0请输入两所城市的名称：0001 0004输出：两城市间的路径为：0001 0002 0003 0004两城市间的路径为：0001 0004正常的输入：请输入城市总数：5请输入输入城市1名称：c1请输入输入城市2名称：c2请输入输入城市3名称：c3请输入输入城市4名称：c4请输入输入城市5名称：c5请输入城市间的高速公路：c1 c2请输入城市间的高速公路：c1 c5请输入城市间的高速公路：c5 c4请输入城市间的高速公路：c4 c3请输入城市间的高速公路：0 0请输入两所城市的名称：c2 c4输出：两城市间的路径为：c2 c1 c5 c4无路径情况：请输入城市总数：3请输入输入城市1名称：a请输入输入城市2名称：b请输入输入城市3名称：c 请输入城市间的高速公路：a b请输入城市间的高速公路：0 0请输入两所城市的名称：a c输出：两城市不连通错误的城市个数请输入城市总数：-1输入错误重新输入（大于零的整数）请输入城市总数 2请输入输入城市1名称：1请输入输入城市2名称：2 请输入城市间的高速公路：1 2请输入城市间的高速公路：0 0请输入两所城市的名称：1 2输出：两城市的路径为 1 2存在自返路径请输入城市总数：2请输入输入城市1名称：上海请输入输入城市2名称：长沙 请输入城市间的高速公路：上海 上海请输入城市间的高速公路：上海 长沙请输入两所城市的名称：长沙 上海输出：长沙 上海二、概要设计1.抽象数据类型 因为各个结点之间是网状结构，那么一个结点会和多个结点连接，因此我们使用图来存储各个结点的信息。同时我们需要一个数据结构来搜索图，该数据结构满足先进后出，所以使用栈来实现。2. ADTADT Stack数据对象：D ai | ai binNode, i=1,2,.,n, n0数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 若栈中没有元素，则为空栈。基本操作：bool push（const BinNode&item）；bool pop（BinNode&it）；bool topValue（BinNode&it）；int length()；const；ADT Graph 数据对象：V,R（图是由一个顶点集 V 和一个弧集 R构成的数据结构） 数据关系：Graph = (V,R) VR|v,wV且P(v,w) 基本操作：int n() =0; / 返回图节点数 int e() =0; /返回图边数 int first(int)=0;/返回该节点的第一条邻边 void setEdge(int v1, int v2)/加边 int next(int, int) =0; /返回下一条邻边 int getMark(int) =0;/有标记吗 void setMark(int, int) =0;/设置标记3. 算法的基本思想 使用深度优先搜索DFS对图进行遍历，在搜索过程中，每当访问一个顶点V后，DFS就会递归的访问它的所有未被访问的相邻顶点。即先访问点v，把所有与v相关联的边存入栈，弹出栈顶元素，栈顶元素代表的边所关联的另一个顶点就是就是要访问的下一个元素，重复对v的操作；依次类推直到所有元素都被处理完毕。4程序流程程序主要由四个步骤组成：（1）输入城市总数（2）输入正确的城市编号列表（3）输入所有的有高速公路直接连接的城市对编号（4）循环输入需要寻找路径的城市对的编号寻找它们之间的所有简单路径。 三详细设计1.物理数据类型 由于边数目未知，所以对于遍历图的时间效率并不清楚，所以可以用邻接表或者邻接矩阵来实现，本实验中使用邻接矩阵。 栈元素未知，用链表来实现栈。用string保存输入的城市名信息。2. 算法的具体步骤图的构建路径的存储深度优先搜索栈元素的打印图的构建：创建一个城市数n*城市数n的二阶矩阵，并且给每一个元素赋值为零。Graph(int numVert)int i, j;numVertex = numVert;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; inumVertex; i+)marki.ViMark = -1;matrix = (int*) new int*numVertex; / Make matrixfor (i = 0; inumVertex; i+)matrixi = new intnumVertex;for (i = 0; i numVertex; i+)/Edges start w/0 weightfor (int j = 0; jgetVal(v1);int v;G-setMark(v1, 1);if (G-getVal(v1) = G-getVal(v2)for (int i = 0; in(); i+)for (int j = 0; jn(); j+)G-setEdge(i, j, Mij);/将路径进栈cout 两城间的路径为：;b.print();cout setMark(v2, -1);/将v2标记为未被访问count+;/路线多一条return;for (int w = G-first(v1); wn(); w = G-next(v1, w)/访问v1所有顶点G-setEdge(w, v1, 0);if (G-getMark(w) = -1 | w = 5)DFS(G, w, origin, v2, b, M, D, count);b.pop(Ch);G-Find(Ch, v);G-setMark(v, -1);栈所有元素的打印：新建一个和需要打印栈a长度相同的栈b，栈a中每一个元素依次出栈进入栈b，直到栈a为空，栈b依次出栈，并且输出每一个元素的值，同时将这些元素进栈a，直到栈b为空。void print()string Ch;AStack b(length();while (pop(Ch)b.push(Ch);while (b.pop(Ch)coutCh ;push(Ch);3算法的时空分析及改进设想因为图的邻接矩阵是一个|V|V|矩阵，所以邻接矩阵的空间代价为(|V|2)，对于有n个顶点的和E条弧的无向图而言，DFS对每条边分别沿两个方向进行处理，且每个顶点必须被访问一次，所以总的时间代价为(|V|+|E|) 。综上可知，该程序的时间复杂度为Max（(|V|2)，(|V|+|E|)）。4. 输入和输出的格式.条件的输入请输入城市总数：n（大于零的整数）请输入输入城市1名称：请输入输入城市2名称：请输入输入城市3名称：.请输入输入城市n名称：请输入城市间的高速公路：请输入两所城市的名称：cout n;if (n = 0 )cout 输入错误重新输入(大于零的整数) endl;cout n;Graph a(n);for (int i = 0; in; i+)cout 请输入城市 i + 1 Ch;a.setVal(i, Ch);cout Ch1;cin Ch2;while (Ch1 != 0)a.Find(Ch1, v1);a.Find(Ch2, v2);a.setEdge(v1, v2, 10);a.setEdge(v2, v1, 10);cout Ch1;cin Ch2;输入要查找的城市cout Ch1 Ch2;连通情况路径的输出（即上述算法中的栈元素的打印）void print()string Ch;AStack b(length();while (pop(Ch)b.push(Ch);while (b.pop(Ch)coutCh ;push(Ch);不连通时的输出if (count = 0)cout 两个城市不连通 endl;4 测试结果正常的输入：正常的输入：无路径情况：错误的城市个数存在自返路径#include#include#include#includeusing namespace std;class AStackprivate:int size;/栈的大小int top;/栈中元素的多少string *listArray;public:AStack(int sz = 0)/构建栈size = sz;top = 0;listArray = new stringsz;AStack()/销毁栈deletelistArray;bool push(const string&item)/压栈if (top = size) return false;/如果栈已满则return falseelselistArraytop+ = item;return true;bool pop(string& it)/出栈if (top = 0) return false;/如果栈为空栈，则return falseelseit = listArray-top;return true;int length()const/获取栈的长度return top;void print()string Ch;AStack b(length();while (pop(Ch)b.push(Ch);while (b.pop(Ch)coutCh ;push(Ch);class Pointpublic:string LessonName;int ViMark;class Graph/Implement adjacency matrixprivate:int numVertex, numEdge;/Store number of vertices edgesint *matrix; / Pointer to adjacency matrixPoint *mark; / Pointer to mark arraypublic:Graph(int numVert)/ Make graph w/ numVert verticesint i, j;numVertex = numVert;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; inumVertex; i+)marki.ViMark = -1;matrix = (int*) new int*numVertex; / Make matrixfor (i = 0; inumVertex; i+)matrixi = new intnumVertex;for (i = 0; i numVertex; i+)/Edges start w/0 weightfor (int j = 0; jnumVertex; j+) matrixij = 0;Graph()delete mark;for (int i = 0; inumVertex; i+)delete matrixi;delete matrix;int n()return numVertex;int e()return numEdge;int first(int v)/ Return vs first neighborint i;for (i = 0; inumVertex; i+)if (matrixvi != 0 & marki.ViMark = -1) return i;return i; / Return n if noneint next(int v1, int v2)/ Get v1s neighbor after v2int i;for (i = v2 + 1; inumVertex; i+)if (matrixv1i != 0 & marki.ViMark = -1)/cout此时next的i值是:v1+1 i+1endl; return i;return i;/ Set edge (v1, v2) to wgtvoid setEdge(int v1, int v2, int wgt)if (matrixv1v2 = 0) numEdge+;matrixv1v2 = wgt;void delEdge(int v1, int v2) / Delete edge (v1, v2)if (matrixv1v2 != 0)numEdge-;matrixv1v2 = 0;int weight(int v1, int v2)return matrixv1v2;string getVal(int v)return markv.LessonName;int getMark(int v)return markv.ViMark;void setVal(int v, string val)markv.LessonName = val;void setMark(int v, int Mark)markv.ViMark = Mark;void Find(string search, int& v)for (int i = 0; inumVertex; i+)if (marki.LessonName = search)v = i;return;cout 路径错误 getVal(v1);/将v1边进栈int v;G-setMark(v1, 1);if (G-getVal(v1) = G-getVal(v2)/已经连通的情况cout 两城间的路径为：;b.print();cout setMark(v2, -1);/将v2标记为未被访问count+;/路线多一条return;for (int w = G