数据结构课程设计目录一. 设计目的.................................................................................................... 错误!未定义书签。
二. 设计内容 (1)三．概要设计 (1)1、功能模块图 (1)2、各个模块详细的功能描述 (2)四．详细设计 (3)1．主函数和其他函数的伪码算法 (3)2、主要函数的程序流程图 (7)3、函数之间的调用关系图 (15)五．测试数据及运行结果 (15)1．正常测试数据及运行结果 (16)2、非正常测试数据及运行结果 (17)六．调试情况，设计技巧及体会 (18)七．参考文献 (19)八．附录：源代码 (19)一. 设计目的课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。
能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。
而且通过数据结构课程设计能够在下述各方面得到锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。
通过上机实习，验证自己设计的算法的正确性。
学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。
3、培养算法分析能力。
分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。
二. 设计内容最小生成树问题:设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。
存储结构采用多种。
求解算法多种。
三．概要设计1、功能模块图2、各个模块详细的功能描述※创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。
※功能选择：给用户提示信息，让用户选择相应功能。
※建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。
※建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。
※PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。
四．详细设计1．主函数和其他函数的伪码算法※主函数：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,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵{int i,j,k;cout<<"请输入城市个数及其之间的可连接线路数目：";cin>>G.vexnum>>G.arcnum;cout<<"请输入各个城市名称(分别用一个字符代替)：";for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)//初始化数组for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=MAX;}cout<<"请输入两个城市名称及其连接费用(严禁连接重复输入!)："<<endl;for(k=0;k<G.arcnum;++k){cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;i = LocateVex(G,dgevalue[k].ch1);j = LocateVex(G,dgevalue[k].ch2);G.arcs[i][j].adj = dgevalue[k].value;G.arcs[j][i].adj = G.arcs[i][j].adj;}return OK;}※临接矩阵的输出：void Adjacency_Matrix(MGraph G) //用邻接矩阵存储数据{int i,j;for(i=0; i<G.vexnum; i++){for(j=0; j<G.vexnum; j++)if(G.arcs[i][j].adj==MAX)cout<<0<<" ";elsecout<<G.arcs[i][j].adj<<" ";cout<<endl;}}※邻接表的输出：void Adjacency_List(MGraph G,Dgevalue dgevalue) //用邻接表储存数据{int i,j;for(i=0;i<G.vexnum;i++){cout<<G.vexs[i]<<"->";for(j=0;j<G.arcnum;j++)if(dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i])cout<<dgevalue[j].ch2<<"->";else if(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i])cout<<dgevalue[j].ch1<<"->";cout<<"\b\b "<<endl;}}※最小生成树PRIM算法：void MiniSpanTree_PRIM(MGraph G,char u)//普里姆算法求最小生成树{int i,j,k;Closedge closedge;k = LocateVex(G,u);for(j=0; j<G.vexnum; j++) //辅助数组初始化{if(j != k){closedge[j].adjvex = u;closedge[j].lowcost = G.arcs[k][j].adj;}}closedge[k].lowcost = 0;for(i=1; i<G.vexnum; i++){k = Minimum(G,closedge);cout<<" 城市"<<closedge[k].adjvex<<"与城市"<<G.vexs[k]<<"连接。
"<<endl;closedge[k].lowcost = 0;for(j=0; j<G.vexnum; ++j){if(G.arcs[k][j].adj < closedge[j].lowcost){closedge[j].adjvex = G.vexs[k];closedge[j].lowcost= G.arcs[k][j].adj;}}}}int Minimum(MGraph G,Closedge closedge) //求closedge中权值最小的边，并返回其顶点在vexs中的位置{int i,j;double k = 1000;for(i=0; i<G.vexnum; i++){if(closedge[i].lowcost != 0 && closedge[i].lowcost < k){k = closedge[i].lowcost;j = i;}}return j;}※最小生成树kruscal算法：void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)//克鲁斯卡尔算法求最小生成树{int p1,p2,i,j;int bj[MAX_VERTEX_NUM]; //标记数组for(i=0; i<G.vexnum; i++) //标记数组初始化bj[i]=i;Sortdge(dgevalue,G);//将所有权值按从小到大排序for(i=0; i<G.arcnum; i++){p1 = bj[LocateVex(G,dgevalue[i].ch1)];p2 = bj[LocateVex(G,dgevalue[i].ch2)];if(p1 != p2){cout<<" 城市"<<dgevalue[i].ch1<<"与城市"<<dgevalue[i].ch2<<"连接。