《数据结构》课程设计--最小生成树问题

《《数据结构》课程设计--最小生成树问题》由会员分享，可在线阅读，更多相关《《数据结构》课程设计--最小生成树问题（55页珍藏版）》请在毕设资料网上搜索。

1、 数据结构课程设计报告 题目： 最小生成树问题 院（系）： 计算机工程学院 学生姓名: XXX 班级： XXX 学号: : XXXXXXXXX 起迄日期: : 2015.07.13-2015.07.24 指导教师: : XXX XXX 1 任务书任务书 最小生成树问题最小生成树问题 问题描述在 n个城市之间建设网络， 只需保证连通即可， 求最经济的架设方法。 设计要求 （1）通过输入建立一无向网，存储结构可以采用多种； （2）要求分别采用普里姆算法和克鲁斯卡尔算法实现； （3）若以图形界面输出可以适当加分。 2 一、需求分析需求分析 1.1.问题描述：问题描述： 该程序主要实现最小生成树功能，

2、 在给定的中国铁路网中， 选择城市， 生成最小生成树。 此外，改程序实现了城市介绍，指定城市到其它城市的最短距离，指定城市之间的最短距离 等图论的基本操作。直观、清晰的为用户提供全国铁路网的最基本情况。 该程序最具体的任务是最小生成树的实现，需要用到Prim算法和Kruskal算法实现。输 入指定的城市求出最小生成树， 方便查询城市间的最短连通量。 另外添加了显示全国主要铁 路网的功能，在跳出的界面，选择城市，程序会通过textBox控件显示选定的城市的相关介 绍。该程序实现了指定城市到其它城市之间的最短距离。通过在地图上选择城市，程序通过 Dijkstra算法计算出指定城市到其它城市之间的最

3、短距离，并通过textBox控件显示，一目 了然。具有较强的人机和谐性。还可以实现指定城市之间的最短路，输入两个指定的城市， 通过Floyd算法求出选定城市间的最短距离。并在图形界面上标注要经过的城市。 2.2.基本功能：基本功能： （1）通过输入建立一无向网，存储结构采用了邻接矩阵。 （2）要求分别采用 Prim 算法和 Kruskal 算法实现，分别对应 Prim.cs 和 Kruskal.cs。 （3）若以图形界面输出会适当加分。 3.附加功能：附加功能： （1）城市的介绍，在输出的全国铁路网中，点击相应的城市会出现对该城市相应的介 绍。主要实现代码在Map.cs中。 （2）指定城市到其

4、它城市的最短距离，在地图上点击指定城市，程序会显示指定城市 到其它城市的最短距离。主要实现代码在Dijkstra.cs中 （3）指定的两个城市之间的最短距离。在地图中选择两个城市，程序会显示这两个城 市之间的最短距离，并在地图上显示在这两个城市之间经过的城市。主要实现代码在 LeastRoad.cs中。 二、二、 概要设计概要设计 1.1.设计思路：设计思路： 首先，将城市和道路的主要信息，包括城市和道路的数量、城市的名称、道路的相关信 息存入文件中。 在每个程序模块中通过字节流StreamReader从文件中读取字符， 放入程序定 义的存储结构中。 （1）城市介绍。地图所含城市的主要介绍和城市名存入文本文件c5.txt中，在Map.cs 中定义选定城市的关键字T， 读取文件中的内容， 寻找关键字T相对应的城市名， 并在textBox1 中输出该城市的相关内容。 （2）指定城市到其它城市的最短路。从文件c1.txt、c2.txt、c3.txt中分别读取城市 即道路的数量、城市名称、道路的相关信息。存于指