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

青岛理工大学

数据结构课程设计报告

题目： 最小生成树问题

院（系）： 计算机工程学院 学生姓名: 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中分别读取城市即道路的数量、城市名称、道路的相关信息，存于指定的变量中。在给定的图中选择城市，存入相应的变量中。采用Prim算法求出最小生成树。Prim算法通过寻找最小的距离，生成最小生成树。

（5）最小生成树（Kruskal）。从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路的数量、城市名称、道路的相关信息，存于指定的变量中。在给定的图中选择城市，存入相应的变量中。采用Kruskal算法求出最小生成树。Kruskal算法通过寻找最小的边的操作，生成最小生成树。

2.数据结构设计：

逻辑结构：图状

该程序主要实现最小生成树、指定顶点间的最短距离。题目的设计要求决定，图的存储结构是最理想的选择。其次，采用图状结构，更加适用于本程序，更形象化。便于整个程序代码的编写。为之后的功能设计提供方便。

存储结构：顺序。

链式存储结构，具有操作灵活、简便等特点。由于程序采用C#语言设计。在C#中没有指针这一类型。虽然可以通过类的定义实现链式存储，但操作过于麻烦，容易造成隐藏的错误。所以采用顺序存储结构。采用顺序存储结构也可以实现图的存储，进而进行之后的一些列操作。相比于链式，顺序存储结构在一些算法的设计上，所消耗的时间可能会更少。

抽象数据类型：

抽象数据类型邻接矩阵的定义如下：

string[] city = new string[n];

City{

数据对象：数据对象：D={Ai}Ai∈city,i=1,2,3... ...,n,n≥0}

基本操作:

Dijkstra.Button1；

初始条件：city数组已定义，并存储了文件中的数据。 操作结果：输出指定城市到其余城市间的最短距离。 Dijkstra.textBox1；

初始条件：city数组已定义，并存储了文件中的数据。

操作结果：将需要显示的city信息显示到textBox1控件中。 LeastRoad.Button3；

初始条件：city数组已定义，并存储了文件中的数据。

操作结果：输出指定两个城市之间的最短距离，在图像中显示指定两城市间经过的城市。

Prim.Button2；

初始条件：city数组已定义，并存储了文件中的数据，i1

3

操作结果：根据选定的城市，输出最小生成树并在图像中显示。 Kruskal.Button2；

初始条件：city数组已定义，并存储了文件中的数据，i1

}

int[,] Railway = new int[m, m]; Railway{

数据对象：D={Bi}Bi∈city,i=1,2,3... ...,n,n≥0}

数据关系：R={}Bi-1,Bi∈Way,i=1,2,3... ...,n,n≥0} 基本操作：

Dijkstra.Button1；

初始条件：Railway数组已定义，并存储了文件中的数据。 操作结果：输出指定城市到其余城市间的最短距离。 LeastRoad.Button3；

初始条件：Railway数组已定义，并存储了文件中的数据。

操作结果：输出指定两个城市之间的最短距离，在图像中显示指定两城市间经过的城市。

Prim.Button2；

初始条件：Railway数组已定义，并存储了文件中的数据。

操作结果：根据选定的城市，输出最小生成树并在图像中显示。 Kruskal.Button2；

初始条件：Railway数组已定义，并存储了文件中的数据。

操作结果：根据选定的城市，输出最小生成树并在图像中显示。 }

3.软件结构设计：

图2.1软件结构设计

4

三、 详细设计

1.定义程序中所用到的数据及数据结构

数据：

string T; //用于记录查询的程序

string[] T = new string[1]; //用于存储选中的城市 string[] city = new string[n]; //用户存储城市信息 int[,] Railway = new int[m, m]; //用于存储铁路信息 string city1 //用于记录弧头城市 string city2 //用于记录弧尾城市 Control c //用于遍历控件

int[] con = new int[n]; //用于标记被访问过的城市 int[] td = new int[n]; //用于临时记录城市间的距离

int[] dist = new int[n]; //记录指定城市到其它城市的距离 int[,] tag = new int[n, n]; //用于给铁路标号 Point []P = new Point[n+5]; //记录城市的位置信息 int[] visit = new int[n]; //标记城市是否被访问过

bool[, ,] path = new bool[n, n, n]; //记录两城市间通过的城市 Pen pen = new Pen(Color.Green, 5); //定义画笔信息

string[] Target = textBox1.Lines; //记录从textBox1中获取的信息 int[] Selected = new int[n]; //记录选定城市的标号 int[] Pcity = new int[i1]; //用于存储选中的城市 int[] Pdistance = new int[i1]; //用于存储距离 int[,] ln = new int[n, n]; //记录道路信息 int[] set = new int[n]; //记录边的弧头、弧尾

邻接矩阵：

int n; //用于记录城市的数目 int m; //用于记录道路的数目

string[] city = new string[n]; //用户存储城市信息 int[,] Railway = new int[m, m]; //用于存储铁路信息

2.主函数和其他函数的伪码算法:

查询城市信息按钮:

private void button1_Click(object sender, EventArgs e) {

textBox1.Clear();

foreach (Control c in this.Controls) //遍历程序内的控件 {

if (c is GroupBox) {

5

foreach (Control d in c.Controls) //遍历GroupBox1中的所有控件

{

if (d is RadioButton) {

if (((RadioButton)d).Checked == true) {

T = ((RadioButton)d).Text; //获取指定RadioButton空间的Text属性值 } } } } }

textBox1.Text += T; //在文本控件中显示文本信息 string Target;

textBox2.Clear(); //清空textBox2中的文本信息

StreamReader filestream1 = new StreamReader(\Encoding.Default); //从指定文本文件中读取字符 Target = filestream1.ReadLine();

while(Target!=null) //将城市的相关信息写入文本控件textBox2中 {

int flag2 = 0;

if(Target==T) //检测目标文本是否和给定文本相匹配 {

for (; ; ) {

Target = filestream1.ReadLine(); if (Target == \ break; else {

textBox2.Text += Target; } }

flag2 = 1; }

if (flag2 == 1) //是否跳出循环 break;

Target = filestream1.ReadLine(); }

filestream1.Close(); //关闭字节流 }

6

指定城市到其余城市最短距离按钮：

private void button1_Click(object sender, EventArgs e) {

textBox1.Clear(); //清空textBox1中的原有信息

StreamReader filestream1 = new StreamReader(\Encoding.Default); //从c1.txt文件中读取信息

int n = int.Parse(filestream1.ReadLine()); int m = int.Parse(filestream1.ReadLine()); filestream1.Close();

StreamReader filestream2 = new StreamReader(\Encoding.Default); //从c2.txt文件中读取信息

string[] city = new string[n]; for (int i = 0; i < n; i++) {

city[i] = filestream2.ReadLine(); }

filestream2.Close();

StreamReader filestream3 = new StreamReader(\Encoding.Default); //从c3.txt文件中读取信息

int[,] Railway = new int[m, m]; int[,] tag = new int[n, n]; for (int i = 0; i < m; i++) {

for (int j = 0; j < m; j++) {

Railway[i, j] = 10000; } }

for (int i = 0; i < n; i++) //用于记录城市的标号 {

for (int j = 0; j < n; j++) {

tag[i, j] = 0; } }

string city1, city2;

for (int i = 0; i < m; i++) //获取城市间距离信息 {

7

city1 = filestream3.ReadLine(); //获取弧头城市的信息 city2 = filestream3.ReadLine(); //获取弧尾城市的信息 int flag = 0;

for (int j = 0; j < n; j++) {

for (int k = 0; k < n; k++) {

if (city1 == city[j] && city2 == city[k]) {

Railway[j, k] = Railway[k, j] = Convert.ToInt32(filestream3.ReadLine());

tag[j, k] = tag[k, j] = i; flag = 1; break; } }

if (flag == 1) {

break; } } }

filestream3.Close();

foreach (Control c in this.Controls) //遍历所有的控件，寻找groupBox1

{

if (c is GroupBox) {

foreach (Control d in c.Controls) //遍历groupBox1中的控件，寻找RadioButton控件

{

if (d is RadioButton) {

if (((RadioButton)d).Checked == true) {

T[0] = ((RadioButton)d).Text; //记录寻找的RadioButton的Text属性值

} } } } }

8

int [] r=new int[1]; int[] s = new int[1]; int[] con = new int[n]; int[] td = new int[n];

for (int i = 0; i < n; i++) //记录寻找的城市的标号 {

if (city[i] == T[0]) {

r[0] = i; } }

for (int i = 0; i < n; i++) //记录城市是否被访问过 {

con[i] = 0; }

int[] dist = new int[n]; //记录指定城市到其它城市的距离 for (int i = 0; i < n; i++) {

dist[i] = 10000; }

for (int i = 0; i < n; i++) //记录指定城市到直接关联城市的距离 {

if (Railway[r[0], i] < 10000) {

dist[i] = Railway[r[0], i]; } }

dist[r[0]] = 0; //指定城市到自己的距离为0 con[r[0]] = 1; //标记指定城市已被访问过 for (int i = 1; i < n; i++) {

int mini = 10000;

for (int j = 0; j < n; j++) //寻找最小距离 {

if (dist[j] < mini && con[j] == 0) {

mini = dist[j];

s[0] = j; //记录城市的标号 } }

con[s[0]] = 1; //标记城市已被访问过

for (int j1 = 0; j1 < n; j1++) //标记指定城市到其它城市的距离 {

9

本文来源：https://www.bwwdw.com/article/v9k.html