数据结构课程设计地铁建设问题.docx
- 文档编号:1720834
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:24
- 大小:125.68KB
数据结构课程设计地铁建设问题.docx
《数据结构课程设计地铁建设问题.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计地铁建设问题.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构课程设计地铁建设问题
软件学院
课程设计报告书
课程名称数据结构
设计题目地铁建设问题
专业班级
学号
姓名
指导教师
2013年1月
1设计时间................................................2
2设计目的................................................2
3设计任务................................................2
4设计内容................................................2
4.1需求分析...............................................2
4.1.1程序所能达到的功能...................................2
4.1.2输入、输出的形式和输入值的范围........................2
4.1.3测试数据.............................................3
4.2总体设计...............................................3
4.2.1抽象数据类型定义.....................................3
4.2.2主程序的流程、模块之间的调用关系......................4
4.3详细设计...............................................5
4.3.1数据类型、函数的伪码算法.............................5
4.3.2函数的调用关系图.....................................9
4.4测试与分析............................................10
4.4.1测试................................................10
4.4.2分析................................................11
4.5附录.................................................11
5总结与展望.............................................16
参考文献.................................................17
成绩评定.................................................17
1设计时间
2012年1月21日——2012年1月25日
2设计目的
1.通过这次设计,在数据结构的逻辑结构和存储结构、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解
2.训练程序设计方法以及上机操作等基本技能,积累编程经验
3.培养用计算机解决实际问题的能力
3设计任务
某城市要在各个辖区之间修建地铁,由于地铁建设费用昂贵,因此需要合理安排地铁建设线路,使市民可以沿地铁到达各个辖区,并使总费用最小。
4设计内容
4.1需求分析
4.1.1程序所能达到的功能
城市要在各个辖区之间修建地铁来加快经济发展,但由于建设地铁的费用昂贵,因此需要编写程序合理安排地铁的建设路线,使乘客可以沿地铁到达各个辖区,并使总的建设费用最小。
(1)使用结构体数组,存储辖区名称
(2)建立辖区间直接距离的无向图,用邻接矩阵存储辖区间直接距离信息
(2)根据读入的辖区距离信息,计算出应该建设哪些辖区的地铁路线
(3)输出应该建设的路线,以及所需建设的总里程信息
4.1.2输入、输出的形式和输入值的范围
输出的形式和输入值的范围
输入数字和字母,字母为辖区名,数字为辖区间直接距离,名称个数o,0<线路个数 输出的形式 1: 辖区名辖区名路程 2: 辖区名辖区名路程 3: 辖区名辖区名路程 总费用为: 路程的和 4.1.3测试数据 正确输入: 辖区个数: 4 名称abcd 线路起止辖区及直接距离: ab3、ac5、ad4、bc2、bd3、cd2、000 开始辖区: a 输出为: 1: ab3 2: bc2 3: cd2 总费用: 7 错误输入: 辖区个数: 4 名称abcd 线路及之间距离: asb3 输出为: 没有as这个辖区 4.2总体设计 4.2.1抽象数据类型定义 1.抽象数据类型图的定义 ADTGraph{ 数据对象v: v是具有相同特性的数据元素的集合,成为顶点集。 数据关系R: R={VR} VR={ 谓词P(v,w)定义了弧 基本操作P: CreateGraph(&G,V,VR); 初始条件: V是图的顶点集,VR是图中弧的集合。 操作结果: 按V和VR的定义构造图G。 }ADTGraph 4.2.2主程序的流程、模块之间的调用关系 主程序的流程 模块之间的调用关系 (1)主函数main()调用intcreatgraph(Graph*g)建立无向图,用邻接矩阵存储; (2)voidMiniSpanTree_PRIM(Graphg,chara[10])调用intminimun(structtree*a,Graphg)和intlocatevex(Graph*g,chara[10])生成树,判断辖区名称输入是否正确; (3)主函数main()调用voidMiniSpanTree_PRIM(Graphg,chara[10])计算最小生成树,输出最优线路和总里程。 4.3详细设计 4.3.1数据类型、函数的伪码算法 1.结构体类型 typedefstruct{ charV[M][10]; intR[M][M]; intvexnum; }Graph; 2.函数算法 创建无向图 intlocatevex(Graph*g,chara[10]) { inti; for(i=0;i { if(strcmp(a,g->V[i])==0) returni; } if(i==g->vexnum) return-1; } intcreatgraph(Graph*g) { inti=0,j,m,k,p,o,e; chara[10],b[10]; printf("设置辖区的个数: ");//城市中辖区的个数 scanf("%d",&o); for(i=0;i { printf("第%d个城市辖区名称为: ",i+1); scanf("%s",g->V[i]); } g->vexnum=o; for(i=0;i for(j=0;j g->R[i][j]=INFINITY; printf("辖区之间的路程,以000为结束标志\n"); scanf("%s%s%d",a,b,&m); while(strcmp("0",a)! =0||strcmp("0",b)! =0||m! =0) { k=locatevex(g,a);p=locatevex(g,b); if(k==-1) { printf("没有%s这个辖区\n",a); return0; } if(p==-1) { printf("没有%s这个辖区\n",b); return0; } g->R[k][p]=g->R[p][k]=m; scanf("%s%s%d",a,b,&m); } return1; } structtree{ intweizhi; intlowcost; }; intminimun(structtree*a,Graphg) { inti,k,m=0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 地铁 建设 问题