3《数据结构》课程设计报告.pdf

青岛理工大学 数据结构课程设计报告 题目： 最小生成树问题 院 （系）： 计算机工程学院 学生姓名: XXX 班级： XXX 学号: XXXXXXXXX 起迄日期: 2015.07.13-2015.07.24 指导教师: XXX XXX 任务书 最小生成树问题 [问题描述]在n个城市之间建设网络，只需保证连通即可， 求最经济的架设方法。 [设计要求] （1）通过输入建立一无向网，存储结构可以采用多种； （2）要求分别采用普里姆算法和克鲁斯卡尔算法实现； （3）若以图形界面输出可以适当加分。 1 一、需求分析 1.问题描述： 该程序主要实现最小生成树功能，在给定的中国铁路网中，选择城市，生成最小生成树。 此外，改程序实现了城市介绍，指定城市到其它城市的最短距离，指定城市之间的最短距离 等图论的基本操作。直观、清晰的为用户提供全国铁路网的最基本情况。 该程序最具体的任务是最小生成树的实现，需要用到Prim算法和Kruskal算法实现。输 入指定的城市求出最小生成树，方便查询城市间的最短连通量。另外添加了显示全国主要铁 路网的功能，在跳出的界面，选择城市，程序会通过textBox控件显示选定的城市的相关介 绍。该程序实现了指定城市到其它城市之间的最短距离。通过在地图上选择城市，程序通过 Dijkstra算法计算出指定城市到其它城市之间的最短距离，并通过textBox控件显示，一目 了然。具有较强的人机和谐性。还可以实现指定城市之间的最短路，输入两个指定的城市， 通过Floyd算法求出选定城市间的最短距离。并在图形界面上标注要经过的城市。 2.基本功能： （1）通过输入建立一无向网，存储结构采用了邻接矩阵。 （2）要求分别采用Prim 算法和Kruskal算法实现，分别对应Prim.cs 和Kruskal.cs。 （3）若以图形界面输出会适当加分。 3.附加功能： （1）城市的介绍，在输出的全国铁路网中，点击相应的城市会出现对该城市相应的介 绍。主要实现代码在Map.cs中。 （2）指定城市到其它城市的最短距离，在地图上点击指定城市，程序会显示指定城市 到其它城市的最短距离。主要实现代码在Dijkstra.cs中 （3）指定的两个城市之间的最短距离。在地图中选择两个城市，程序会显示这两个城 市之间的最短距离，并在地图上显示在这两个城市之间经过的城市。主要实现代码在 LeastRoad.cs中。 二、 概要设计 1.设计思路： 首先，将城市和道路的主要信息，包括城市和道路的数量、城市的名称、道路的相关信 息存入文件中。在每个程序模块中通过字节流StreamReader从文件中读取字符，放入程序定 义的存储结构中。 （1）城市介绍。地图所含城市的主要介绍和城市名存入文本文件c5.txt中，在Map.cs 中定义选定城市的关键字T，读取文件中的内容，寻找关键字T相对应的城市名，并在textBox1 中输出该城市的相关内容。 （2）指定城市到其它城市的最短路。从文件c1.txt、c2.txt、c3.txt中分别读取城市 即道路的数量、城市名称、道路的相关信息。存于指定的变量中。采用Dijkstra算法求出指 定城市到其它城市的最短路，存入指定变量中。Dijkstra算法用于求某个顶点到其余各顶点 2 的最短路径。 （3）指定城市之间的最短路。从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路 的数量、城市名称、道路的相关信息。存于指定的变量中。在给定的图中选择两个城市，存 入相应的变量中。采用Floyd算法求出指定城市之间的最短路径。Floyd算法用于求每一对顶 点之间的最短路径。 （4）最小生成树(Prim)。从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路的数 量、