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

软 件 学 院

课程设计报告书

课程名称 数据结构 设计题目 地铁建设问题 专业班级 学 号 姓 名 指导教师

2014 年 1月17日

目录

1 设计时间 ............................................... 1 2 设计目的 ............................................... 1 3设计任务 ............................................... 1 4 设计内容 ............................................... 1 4.1总体设计 ............................................. 1 4.2需求分析 ............................................. 2 4.3详细设计 ............................................. 2 4.4测试与分析 ........................................... 4 4.4.1测试 ............................................... 4 4.4.2分析 ............................................... 5 4.5 附录 ................................................. 5 5 总结与展望 ............................................. 9 参考文献 ................................................ 10 成绩评定 ................................................ 10

1 设计时间 2014年1月15日 2 设计目的 设计各辖区之间最短地铁，使修建费用最少 3设计任务 某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。 4 设计内容 (1)输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。 (2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。 (3)输出应该建设的地铁线路及所需建设总里程。 4.1总体设计

1

图4-1算法图 4.2需求分析 （1）本程序设计计算城市内各辖区间修建地铁的最短路程。 （2）运行时，输入辖区的名称，各辖区之间用空格键隔开，以#输入结束。 （3）输入各辖区间距离时，先输入两辖区名称，再输入距离。 （4）最后计算最短距离来得出最少费用。 4.3详细设计 采用邻接矩阵存储构造无向图 int creatgraph(Graph *g) { int i=0,j,m,k,p; char a[10],b[10]; printf(\请输入所有的辖区，以#为输入结束标志\\n\); scanf(\,g->V[i]); while(strcmp(\,g->V[i])!=0) { i++; scanf(\,g->V[i]); } g->vexnum=i; for(i=0;ivexnum;i++)

2

for(j=0;jvexnum;j++) g->R[i][j]=INFINITY; printf(\请输入辖区和辖区之间的路程，以##为结束标志\\n\); scanf(\,a,b,&m); while(strcmp(\,a)!=0 || strcmp(\,b)!=0 || m!=0) { k=locatevex(g,a); p=locatevex(g,b); if(k==-1) { printf(\没有%s这个辖区\\n\,a); return 0; } if(p==-1) } return 1; } 普利姆算法生成最小树 struct tree //构造最小生成树// { int weizhi; int lowcost; }; int minimun(struct tree *a,Graph g) { printf(\没有%s这个辖区\\n\,b); return 0; } g->R[k][p]=g->R[p][k]=m; scanf(\,a,b,&m);

3