最小生成树问题_课程设计报告.doc

最小生成树问题_课程设计报告 《数据结构》
课程设计报告
专业: 软件工程
题目: 最小生成树问题
目录
一. 设计目的 2
二. 设计内容 2
三. 概要设计 1
1、功能模块图 1
2、各个模块详细的功能描述 1
2
2
2、主要函数的程序流程图 6
3、函数之间的调用关系图 13
14
14
2、非正常测试数据及运行结果 15
,设计技巧及体会 17
17
:源代码 17
一. 设计目的
课程设计是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力,培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼:
1、能根据实际问题的具体情况,结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。通过上机实习,验证自己设计的算法的正确性。学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改。
3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平。
二. 设计内容
最小生成树问题:
设计要求:在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。存储结构采用多种。求解算法多种。
概要设计
1、功能模块图
开始
创建一个图
功能选择


3. PRIM算法
4.
kruscal算法
结束
2、各个模块详细的功能描述
※创建一个图:通过给用户信息提示,让用户将城市信息及城市之间的联系关系和连接权值写入程序,并根据写入的数据创建成一个图。
※功能选择:给用户提示信息,让用户选择相应功能。
※建立邻接矩阵:将用户输入的数据整理成邻接矩阵并显现在屏幕上。
※建立邻接表:将用户输入的数据整理成临接表并显现在屏幕上。
※PRIM算法:利用PRIM算法求出图的最小生成树,即:城市之间最经济的连接方案。


※主函数:
void main()
{
MGraph G;
Dgevalue dgevalue;
CreateUDG(G,dgevalue);
char u;
cout<<"图创建成功。";
cout<<"请根据如下菜单选择操作。\n";
cout<<" *****************************************"<<endl;
cout<<" **1、用邻接矩阵存储:********************"<<endl;
cout<<" **2、用邻接表存储:**********************"<<endl;
cout<<" **3、普里姆算法求最经济的连接方案********"<<endl;
cout<<" **4、克鲁斯卡尔算法求最经济的连接方案****"<<endl;
cout<<" *****************************************"<<endl<<endl;
int s;
char y='y';
while(y='y')
{
cout<<"请选择菜单:"<<endl;
cin>>s;
switch(s)
{
case 1:
cout<<"用邻接矩阵存储为:"<<endl;
Adjacency_Matrix(G);
break;
case 2:
cout<<"用邻接表存储为:"<<endl;
Adjacency_List(G,dgevalue);
break;
case 3:
cout<<"普里姆算法最经济的连接方案为:"<<endl;
cout<<"请输入起始城市名称:";
cin>>u;
MiniSpanTree_PRIM(G,u);
break;
case 4:
cout<<"克鲁斯卡尔算法最经济的连接方案为:"<<endl;
MiniSpanTree_KRSL(G,dgevalue);
break;
default:
cout<<"您的输入有误!";
break;
}
cout<<endl<<"是否继续?y/n:";
cin>>y;
if(y=='n')
break;
}
}
※邻接矩阵和临接表的创建:
int CreateUDG(MGraph & G,Dg