1、 数 据 结 构 课 程 设 计 校园导游系统的设计与实现 学院名称： 计算机科学与通信工程 专业班级： 嵌入式软件 2012 学 号： 2014 年 6 月 一、 问题描述 校园里有若干个景点，使用顶点表示，景点之间有路可通，使用边表示，边 上的权值表示景点之间的距离，如上图所示。请为校园的来访客人设计一个导游 咨询程序。 二、 系统功能结构 使用语言或者图形方式表示你所实现的所有功能，如下图所示 1，在控制台应用程序中画出此图，并把所有的可行路径表示出来 2，以 V0 为顶点进行深度遍历，显示出遍历序列 3，以 V0 为顶点进行广度遍历，显示出遍历序列 4，利用 Prime 算法生成最小生
2、成树 5，实现查找两点之间的最短距离的功能，方便游客选择路径 三、 主要数据结构 使用 C#语言，采用控制台方式 编程过程应该采用先建框架、逐步求精的方式 1，在控制台应用程序中画出此图，并把所有的可行路径表示出来 （1）用一个类来存储点，用构造方法为节点名，以及是否被访问赋值 class Vertex public Vertex(string vna) vname = vna; wasVisited = false; public string vname; public bool wasVisited; （2）在另一个类来实现功能，先声明成员变量 A.用于存放节点： private Ver
3、tex vertices = new Vertex7; B.用于构造邻接矩阵，以此来存放权值 private int, cost = new int7, 7; C.用于计算数组中节点数目 private int n; D.用于表示，即两点之间没有直接的路径 int infinity = 9999999; E.用于进行深度遍历而声明的栈，先进后出 Stack thestack = new Stack(7); F.用于进行广度遍历而声明的队列，先进先出 Queue thequeue = new Queue();/ （3）先画没有直接路径的邻接矩阵的各个点 public Graph() n = 0;
4、 for (int i = 0; i “ + verticesj.vname + “ = “ + Distancej); 四、 系统使用说明 通过文字和主要功能截图的方式，大致说明系统的使用方法 1、 主菜单：显示所有功能，便于旅客自由选择所需要的功能 2、 输入你的选择： A.输入 1：显示所有景点和所有路径 B.输入 2：进行深度遍历 C,输入 3：进行广度遍历： D,输入 4：采用 Prime 算法实现最小生成树： E,输入 5：查找两点之间最短路径： 当输入点不存在时： 五、 课程设计中遇到的问题及解决方法 1，问题：在添加边或者点时需要判断该边是否已经存在： 比如添加边时的解决方法：
5、 private bool edgeExists() for (int i = 0; i 0) int w = getAdjUnvisitedVertex(getIndex(thequeue.Peek().vname); if (w = -1) thequeue.Dequeue(); else Console.Write(verticesw.vname + “,“); verticesw.wasVisited = true; thequeue.Enqueue(verticesw); for (int j = 0; j “ + verticesj.vname + “ = “ + Distance
6、j); class Program static void Main(string args) Graph obj = new Graph(); string a = “V0“, b = “V1“, c = “V2“, d = “V3“, e = “V4“, f = “V5“, g = “V6“; obj.addVertex(a); obj.addVertex(b); obj.addVertex(c); obj.addVertex(d); obj.addVertex(e); obj.addVertex(f); obj.addVertex(g); obj.addEdge(a, b, 2); obj.addEdge(a, d, 5); obj.addEdge(a, c, 3); obj.addEdge(a, g, 5); obj.addEdge(b, d, 2); obj.addEdge(b, f, 7); o
