《数据结构》课程设计最小生成树问题.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=