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

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

《《数据结构》课程设计最小生成树问题.docx》由会员分享，可在线阅读，更多相关《《数据结构》课程设计最小生成树问题.docx（76页珍藏版）》请在冰点文库上搜索。

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

数据结构课程设计报告

题目：

最小生成树问题

院（系）：

计算机工程学院

学生姓名:

XXX

班级：

XXX学号:

XXXXXXXXX

起迄日期:

2015.07.13-2015.07.24

指导教师:

XXXXXX

任务书

最小生成树问题

[问题描述]在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中。

2、概要设计

1.设计思路：

首先，将城市和道路的主要信息，包括城市和道路的数量、城市的名称、道路的相关信息存入文件中。

在每个程序模块中通过字节流StreamReader从文件中读取字符，放入程序定义的存储结构中。

（1）城市介绍。

地图所含城市的主要介绍和城市名存入文本文件c5.txt中，在Map.cs中定义选定城市的关键字T，读取文件中的内容，寻找关键字T相对应的城市名，并在textBox1中输出该城市的相关内容。

（2）指定城市到其它城市的最短路。

从文件c1.txt、c2.txt、c3.txt中分别读取城市即道路的数量、城市名称、道路的相关信息。

存于指定的变量中。

采用Dijkstra算法求出指定城市到其它城市的最短路，存入指定变量中。

Dijkstra算法用于求某个顶点到其余各顶点的最短路径。

（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=newstring[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

操作结果：

根据选定的城市，输出最小生成树并在图像中显示。

Kruskal.Button2；

初始条件：

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

操作结果：

根据选定的城市，输出最小生成树并在图像中显示。

}

int[,]Railway=newint[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软件结构设计

3、详细设计

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

数据：

stringT;//用于记录查询的程序

string[]T=newstring[1];//用于存储选中的城市

string[]city=newstring[n];//用户存储城市信息

int[,]Railway=newint[m,m];//用于存储铁路信息

stringcity1//用于记录弧头城市

stringcity2//用于记录弧尾城市

Controlc//用于遍历控件

int[]con=newint[n];//用于标记被访问过的城市

int[]td=newint[n];//用于临时记录城市间的距离

int[]dist=newint[n];//记录指定城市到其它城市的距离

int[,]tag=newint[n,n];//用于给铁路标号

Point[]P=newPoint[n+5];//记录城市的位置信息

int[]visit=newint[n];//标记城市是否被访问过

bool[,,]path=newbool[n,n,n];//记录两城市间通过的城市

Penpen=newPen（Color.Green,5）;//定义画笔信息

string[]Target=textBox1.Lines;//记录从textBox1中获取的信息

int[]Selected=newint[n];//记录选定城市的标号

int[]Pcity=newint[i1];//用于存储选中的城市

int[]Pdistance=newint[i1];//用于存储距离

int[,]ln=newint[n,n];//记录道路信息

int[]set=newint[n];//记录边的弧头、弧尾

邻接矩阵：

intn;//用于记录城市的数目

intm;//用于记录道路的数目

string[]city=newstring[n];//用户存储城市信息

int[,]Railway=newint[m,m];//用于存储铁路信息

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

查询城市信息按钮:

privatevoidbutton1_Click（objectsender,EventArgse）

{

textBox1.Clear（）;

foreach（Controlcinthis.Controls）//遍历程序内的控件

{

if（cisGroupBox）

{

foreach（Controldinc.Controls）//遍历GroupBox1中的所有控件

{

if（disRadioButton）

{

if（（（RadioButton）d）.Checked==true）

{

T=（（RadioButton）d）.Text;//获取指定RadioButton空间的Text属性值

}

}

}

}

}

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

stringTarget;

textBox2.Clear（）;//清空textBox2中的文本信息

StreamReaderfilestream1=newStreamReader（"D:

/c5.txt",Encoding.Default）;//从指定文本文件中读取字符

Target=filestream1.ReadLine（）;

while（Target!

=null）//将城市的相关信息写入文本控件textBox2中

{

intflag2=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（）;//关闭字节流

}

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

privatevoidbutton1_Click（objectsender,EventArgse）

{

textBox1.Clear（）;//清空textBox1中的原有信息

StreamReaderfilestream1=newStreamReader（"D:

/c1.txt",Encoding.Default）;//从c1.txt文件中读取信息

intn=int.Parse（filestream1.ReadLine（））;

intm=int.Parse（filestream1.ReadLine（））;

filestream1.Close（）;

StreamReaderfilestream2=newStreamReader（"D:

/c2.txt",Encoding.Default）;//从c2.txt文件中读取信息

string[]city=newstring[n];

for（inti=0;i

{

city[i]=filestream2.ReadLine（）;

}

filestream2.Close（）;

StreamReaderfilestream3=newStreamReader（"D:

/c3.txt",Encoding.Default）;//从c3.txt文件中读取信息

int[,]Railway=newint[m,m];

int[,]tag=newint[n,n];

for（inti=0;i

{

for（intj=0;j

{

Railway[i,j]=10000;

}

}

for（inti=0;i

{

for（intj=0;j

{

tag[i,j]=0;

}

}

stringcity1,city2;

for（inti=0;i

{

city1=filestream3.ReadLine（）;//获取弧头城市的信息

city2=filestream3.ReadLine（）;//获取弧尾城市的信息

intflag=0;

for（intj=0;j

{

for（intk=0;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（Controlcinthis.Controls）//遍历所有的控件，寻找groupBox1

{

if（cisGroupBox）

{

foreach（Controldinc.Controls）//遍历groupBox1中的控件，寻找RadioButton控件

{

if（disRadioButton）

{

if（（（RadioButton）d）.Checked==true）

{

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

}

}

}

}

}

int[]r=newint[1];

int[]s=newint[1];

int[]con=newint[n];

int[]td=newint[n];

for（inti=0;i

{

if（city[i]==T[0]）

{

r[0]=i;

}

}

for（inti=0;i

{

con[i]=0;

}

int[]dist=newint[n];//记录指定城市到其它城市的距离

for（inti=0;i

{

dist[i]=10000;

}

for（inti=0;i

{

if（Railway[r[0],i]<10000）

{

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

}

}

dist[r[0]]=0;//指定城市到自己的距离为0

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

for（inti=1;i

{

intmini=10000;

for（intj=0;j

{

if（dist[j]

{

mini=dist[j];

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

}

}

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

for（intj1=0;j1

{

td[j1]=10000;

}

for（intj2=0;j2

{

if（Railway[s[0],j2]<10000）

{

td[j2]=Railway[s[0],j2];

}

}

for（intj3=0;j3

{

if（con[j3]==0&&mini<10000&&td[j3]<10000&&mini+td[j3]

{

dist[j3]=mini+td[j3];

}

}

}

for（intj4=0;j4

{

if（T[0]==city[j4]）

{

continue;

}

textBox1.Text+=T[0]+"->"+city[j4]+":

"+dist[j4]+"KM"+"\r\n";

}

}

指定城市之间最短距离按钮:

privatevoidbutton3_Click（objectsender,EventArgse）

{

Graphicsg=this.groupBox1.CreateGraphics（）;//在groupBox1中创建Graphics对象

textBox3.Clear（）;//清空textBox3中原有的信息

StreamReaderfilestream1=newStreamReader（"D:

/c1.txt",Encoding.Default）;//从c1.txt文件中读取信息

intn=int.Parse（filestream1.ReadLine（））;

intm=int.Parse（filestream1.ReadLine（））;

filestream1.Close（）;

StreamReaderfilestream2=newStreamReader（"D:

/c2.txt",Encoding.Default）;//从c2.txt文件中读取信息

string[]city=newstring[n];

for（inti=0;i

{

city[i]=filestream2.ReadLine（）;

}

filestream2.Close（）;

StreamReaderfilestream3=newStreamReader（"D:

/c3.txt",Encoding.Default）;//从c3.txt文件中读取信息

int[,]Railway=newint[m,m];

int[,]tag=newint[n,n];

for（inti=0;i

{

for（intj=0;j

{

Railway[i,j]=10000;

}

}

for（inti=0;i

{

for（intj=0;j

{

tag[i,j]=0;

}

}

stringcity1,city2;

for（inti=0;i

{

city1=filestream3.ReadLine（）;//获取弧头城市的信息

city2=filestream3.ReadLine（）;//获取弧尾城市的信息

intflag=0;

for（intj=0;j

{

for（intk=0;k

{

if（city1==city[j]&&city2==city[k]）

{

Railway[j,k]=Railway[k,j]=Convert.ToInt32（filestream3.ReadLine（））;

tag[j,k]=i;

flag=1;

break;

}

}

if（flag==1）

{

break;

}

}

}

filestream3.Close（）;

Point[]P=newPoint[n+5];//定义坐标数组，记录城市的位置信息

intX1,Y1;

intz=0;

foreach（Controlcinthis.Controls）//遍历图中所有的控件，寻找groupBox控件

{

if（cisGroupBox）

{

foreach（Controldinc.Controls）//遍历groupBox中的控件，寻找RadioButton控件

{

if（disRadioButton）

{

X1=（（RadioButton）d）.Location.X;

Y1=