1、 课程设计课程设计报告书报告书 课程名称课程名称 数据结构数据结构 设计题目设计题目 地铁建设问题地铁建设问题 专业班级专业班级 学学 号号 姓姓 名名 指导教师指导教师 2013 年年 1 月月 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.
2、4测试与分析10 4.4.1测试10 4.4.2分析11 4.5 附录.11 5 总结与展望.16 参考文献.17 成绩评定.17 2 1 1 设计时间设计时间 2012 年 1 月 21 日2012 年 1 月 25 日 2 2 设计目的设计目的 1.通过这次设计，在数据结构的逻辑结构和存储结构、数据结构的选择应用、算法的 设计及其实现等方面加深对课程基本内容的理解 2.训练程序设计方法以及上机操作等基本技能，积累编程经验 3.培养用计算机解决实际问题的能力 3 3 设计任务设计任务 某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁 建设线路，使市民可以沿地铁到达各
3、个辖区，并使总费用最小。 4 4 设计内容设计内容 4.1 需求分析 4.1.1 程序所能达到的功能 城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此 需要编写程序合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设 费用最小。 （1）使用结构体数组，存储辖区名称 （2）建立辖区间直接距离的无向图，用邻接矩阵存储辖区间直接距离信息 （2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线 （3）输出应该建设的路线，以及所需建设的总里程信息 4.1.2 输入、输出的形式和输入值的范围 输出的形式和输入值的范围 输入数字和字母，字母为辖区名，数字为辖区
4、间直接距离，名称个数 o， 0Vi)=0) return i; if(i=g-vexnum) return -1; int creatgraph(Graph *g) int i=0,j,m,k,p,o,e; char a10,b10; 6 printf(“设置辖区的个数: “);/城市中辖区的个数 scanf(“%d“, for(i=0;iVi); g-vexnum=o; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-Rij=INFINITY; printf(“辖区之间的路程，以0 0 0为结束标志n“); scanf(“%s%s%d“,a,b, whil
5、e(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); return 0; if(p=-1) printf(“没有%s这个辖区n“,b); return 0; g-Rkp=g-Rpk=m; scanf(“%s%s%d“,a,b, 7 return 1; struct tree int weizhi; int lowcost; ; int minimun(struct tree *a,Graph g) int i,k,m=0; for(i=0;iVi)=0) 12 return i; if(i=g-vexnum) return -1; int creatgraph(Graph *g) int i=0,j,m,k,p,o,e; char a10,b10; printf(“设置辖区的个数: “);/城市中辖区的个数 scanf(“%d“, for(i=0;iVi); g-vexnum=o; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-Rij=INFINIT
