地铁建设问题数据结构课程设计

地铁建设问题数据结构课程设计软件学院课程设计报告书课程名称数据结构课程设计设计题目地铁建设问题专业班级学号姓名指导教师2013年1月TOC\o"1-5"\h\z1设计时间12设计目的13设计任务14设计内容14・1需求分析14.2总体设计24・3详细设计444测试与分析114.4.1测试・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・114.4.2分析134・5附录145总结与展望20参考文献・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・22成绩评定・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・22#1设计时间2013年1月16日至2013年1月21日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。3设计任务某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）；根据辖区距离信息，计算出应该在哪些辖区建立地铁线路；输出应该建设的地铁线路及所需建设总里程。4设计内容4.1需求分析1、程序所能达到的功能：⑴根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵存储。⑵根据普利姆算法计算最小生成树。（3）输入各个辖区代号，名称和各辖区间直接距离（地铁铺设费用与距离成正比）。⑷根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。⑸输出应该建设的地铁线路及所需建设总里程。2、输入的形式及内容：包括城市名称、城市间距离权值、起始地点，详见4.4.1测试部分。3、输出的形式及内容：包括生成的邻接表、应建设铁路的辖区名称及权值、最终地铁的总里程，详见4.4.1测试部分。4、测试数据：四个城市abed及其之间的距离权值，详见4.4.1测试部分。4.2总体设计4.2.1数据类型的定义1•图的邻接矩阵存储数据类型定义：typedefstruct{charV[M][10];intR[M][M];intvexnum;Graph;)2•辅助数组数据类型定义：typedefstruct{intadjvex;intlowcost;}closedge[MAX];4.2.2基本操作：CreateCity(&G)操作结果：构造一个无向图G；LocateDistri(Graphg,intu)操作结果：找出目标城市的位置；Min(Graphg,closedgeclosedge)操作结果：求出点与点之间的最短路径；Prim(G,G.distrinam[1])操作结果：用普里姆算法找到连接各辖区的最短路;4.2.3主程序的流程主程序的流程如图1所示：开始」创薙辖区无向图*输出辖区无向图的邻接矩阵」求解辖区图g的最小生咸树T」求解辖区u往辖区图g中的位置P求解最小生成树的结点4图14.2.4各程序模块之间的层次（调用）关系各程序模块之间的层次（调用）关系如图2所示:图24.3详细设计4.3.1预处理#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#defineINFINITY10000#defineM20typedefstruct{〃创建图的结构体charV[M][10];〃顶点数组，用来存储辖区的值即辖区的名称intR[M][M];〃邻接矩阵，邻接矩阵的元素值为辖区之间的距离intvexnum;//辖区的个数}Graph;structtree{intweizhi;intlowcost;}；4.3.2创建辖区无向图的算法intcreatgraph(Graph*g)〃创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵{inti=0sj9m9k9p;chara[10],b[10];printf("*****欢迎使用本程序解决地铁建设问题*****\n");printf("*******请按照提示依次输入相关信息*******\n");printf("衬*请输入所有的辖区，以0作为结束标志****\n");scanf("%s",g->V[i]);//输入结点值while(strcmp("0",g->V[i])!=0){i++;scanf("%s",g->V[i]);}g->vexnum=i;for(i=0;ivg->vexnum;i++)for(j=0；jvg->vexnum;j++)g->R[i][j]=INFINITY;//初始化printf("请输入辖区之间的路程，以000为结束标志*\n");scanf("%s%s%d"9a,b,&m);//输入辖区结点及辖区之间的距离while(strcmp("0",a)!=0IIstrcmp("0",b)!=0IIm!=0){k=locatevex(g,a);p=locatevex(g,b);//查找a,b在图中的位置if(k==-1){printf("*****对不起，输入错误，没有％冷这个辖区*****\n",a);return0;}if(p==-1){printf("*****对不起，输入错误，没有％$这个辖区*****\n",b);return0;}g->R[k][p]=g->R[p][k]=m;//k到p和p到k之间的距离相同scanf("%s%s%d",a,b,&m);//输入辖区结点及辖区之间的距离}return1;}

4.3.3定位函数intlocatevex(Graph*g,chara[10])//查找辖区u在辖区图中的位置{inti;for(i=0;i<g->vexnum;i++)〃循环执行条件是当u=V[i]时停止，求i值{if(strcmp(a,g->V[i])==0)returni;}if(i==g->vexnum)return-1;}4.3.4求最小生成树的结点算法intminimun(structtree*a,Graphg)〃求出第k辖区，此时i辖区与k辖区之间的距离最短{inti^kmuO;for(i=0;i<g.vexnum;i++){if(m==0&&a[i].lowcost!=0){m=1;k=i;if(m==1&&a[i]・lowcost!=0){if(a[i].lowcost<a[k].lowcost)k=i;}returnk;}4.3.5PRIM算法及输出voidMiniSpanTree_PRIM(Graphg,chara[10]){structtreeclosedge[M];intij,k,money=0;k=locatevex(&g,a);for(i=0;i<g.vexnum;i++){if(i!=k){closedge[i].lowcost=g.R[k][i];//M辖区k,i之间的距离closedge[i].weizhi=k;〃与辖区i相邻的最近的辖区设为辖区k}}closedge[k]・lowcost=0;//初始化，U={u}printf("********根据您的输入建立邻接表为:********\n");for(i=0;i<g.vexnum;i++){f0r(j=0jvg・vexnum;j++){printf("l%dl",g.R[i][j])；}printf("\n\n");}printf("****得到应建设地铁的辖区及之间权值为:****\n");for(i=1;ivg.vexnum;i++){k=minimun(closedge,g);〃求出最小生成树T的下一个结点，第k结点money+=closedge[k].lowcost;printf("%d:%s%s%d\n"9i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost);〃输出生成树的边closedge[k].lowcost=0;〃第k顶点并入U集for(j=0;jvg.vexnum;j++){if(g.R[k][j]vclosedge[j].lowcost)//新顶点并入集后，选择新的边，将小的边放到辅助数组中{

closedge[j]・weizhi=k;closedgej]・lowcost=g・R[k]j];}}}printf("******据统计地铁的总建设路程为：%d*******\n",money);}4,3,6主函数模块voidmain(){inti;Graphg;chara[10];i=creatgraph(&g);************\n");if(i)************\n");printf("***********W输入起始地点为:scanf("%s",a);MiniSpanTree_PRIM(g,a);}printf("**********感谢使用本程序，谢谢！*********\n");}4.4测试与分析

4.4.1测试测试数据：1•以图3为例2•2•输入城市区域名称，如图4所示:*****欢迎使***请输解次，

程示辖

*****欢迎使***请输解次，

程示辖

本需决地铁建哒冋题I■'IIITRJ'W-Tl»J,R_r€丨口JIjjIAM*-*-*结束标志****图43•根据需要，依次输入各个区域代号和边的权值，如图5所示:卜请输入辖区之间的路程，如00为结東标志关卜b9ac3Lid7aa0hc8bd5bb0cd4cc0*d00004•根据提示，输入地铁站的起始地点如图6所示:”mxxmxx请输入起始地点为:xmxxmb5•输出最终结果，如图7所示:4.4.2分析1・调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析在设计之初，我对于整个算法的思路的理解并不清晰。最首要的任务就是选择合适的计算思路，并加以实现。经过査阅，我发现解决此类问题的核心思想就

是最小生成树的生成。于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。在实验过程中遇到的最大难题是普里姆算法的编写。通过在书上和网上查阅资料,询问同学老师，结合之前上机实验的经验，我理清思路。经过编写，调试，最终完成了程序的设计。2•算法的时间复杂度和空间复杂度的分析本程序算法的时间复杂度为0(^3)，空间复杂度为O(2n)表达是求值，主要是运用栈的相关知识解决的问题。在此问题之中要运用到函数的多次调用等等。3•针对可能出现的输入错误，作出相应的应对措施：如输入辖区之间的权值时，当输入错误的辖区时会有报错提示，如图8所示：使按所

迎英

欢*输5请使按所

迎英

欢*输5请噸请输入辖区之间的路程，阪00为结東标志”h7bc3对不起！输入错误，役有£这个辖区*****4.5附录源程序：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#includevstring・h>#defineINFINITY10000#defineM20typedefstruct{〃创建图的结构体charV[M][10];〃顶点数组，用来存储辖区的值即辖区的名称intR[M][M];〃邻接矩阵，邻接矩阵的元素值为辖区之间的距离intvexnum;//辖区的个数}Graph;intlocatevex(Graph*g,chara[10])//查找辖区u在辖区图中的位置{inti;for(i=0;i<g->vexnum;i++)〃循环执行条件是当u=V[i]时停止，求i值{if(strcmp(a,g->V[i])==0)returni;}if(i==g->vexnum)return-1;}intcreatgraph(Graph*g)〃创建辖区无向图，图中含有n个结点，创建辖区邻接矩阵{inti=Oj；m,k,p;chara[10],b[10];printf("*****欢迎使用本程序解决地铁建设问题*****\n");printf("*******请按照提示依次输入相关信息*******\n");printf("***请输入所有的辖区，以0作为结束标志****\n");scanf("%s",g->V[i]);//输入结点值while(strcmp("0",g->V[i])!=0){i++；scanf("%s",g->V[i]);}g->vexnum=i;for(i=0;i<g->vexnum;i++)for(j=0;j<g->vexnum;j++)g->R[i][j]=INFINITY;/7初始化printf("请输入辖区之间的路程，以000为结束标志*\n");scanf("%s%s%d",a,b,&m);//输入辖区结点及辖区之间的距离while(strcmp("0",a)!=0IIstrcmp("0",b)!=0IIm!=0){k=locatevex(g,a);p=locatevex(g,b);//査找a,b在图中的位置if(k==-1){printf("*****对不起，输入错误，没有％冷这个辖区*****\n",a);return0;}if(p==-1){printf("*****对不起，输入错误，没有％$这个辖区*****\n",b);return0;}g->R[k][p]=g->R[p][k]=m;//k到p和p到k之间的距离相同scanf("%s%s%d",ab,&m);//输入辖区结点及辖区之间的距离}return1;}structtree{intweizhi;intlowcost;};intminimun(structtree*a,Graphg)II求出第k辖区，此时i辖区与k辖区之间的距离最短{inti,k,m=0;for(i=0;i<g.vexnum;i++){if(m==0&&a[i].lowcost!=0){m=1;k=i;}if(m==1&&a[i]・lowcost!=0){if(a[i].lowcost<a[k].lowcost)k=i;}}returnk;}voidMiniSpanTree_PRIM(Graphg,chara[10]){structtreeclosedge[M];intij,k,money=0;k=locatevex(&g,a);for(i=0;i<g.vexnum;i++){if(i!=k){closedge[i].lowcost=g.R[k][i];//两辖区k,i之间的距离closedge[i].weizhi=k;〃与辖区i相邻的最近的辖区设为辖区k}}closedge[k]・lowcost=0;/Z初始化，U={u}printf("********根据您的输入建立邻接表为:********\n")；for(i=0;ivg・vexnum;i++){for(j=0;jvg.vexnum;j++){printf("l%dl",g・R[i]j]);}printf("\n\n");}printf("****得到应建设地铁的辖区及之间权值为:****\n");for(i=1;ivg.vexnum;i++){k=minimun(closedge,g);〃求出最小生成树T的下一个结点，第k结点money+=closedge[k]・lowcost;printf("%d:%s%s%d\n",i,g.V[closedge[k].weizhi],g.V[k],closedge[k].lowcost);//输出生成树的边closedge[k].lowcost=0;〃第k顶点并入U集for(j=0jvg・vexnumj++){if(g.R[k][j]vclosedge[j].lowcost)//新顶点并入集后，选择新的边，将小的边放到辅助数组中{closedge[j].weizhi=k;closedge[j].lowcost=g.R[k][j];}}}printf("******据统计地铁的总建设路程为：％d*******\n",money);}voidmain(){inti;Graphg;chara[10];i=creatgraph(&g);if(i)printf("***********W输入起始地点为：************\n");scan