1、 课程设计课程设计报告书报告书 课程名称课程名称 数据结构课程设计数据结构课程设计 设计题目设计题目 地铁建设问题地铁建设问题 专业班级专业班级 学学 号号 姓姓 名名 指导教师指导教师 2013 年年 1 月月 目目 录录 1 设计时间 1 2 设计目的 1 3设计任务 . 1 4 设计内容 1 4.1需求分析 . 1 4.2总体设计 . 2 4.3详细设计 . 4 4.4测试与分析 . 11 4.4.1测试 11 4.4.2分析 13 4.5 附录 14 5 总结与展望 20 参考文献. 22 成绩评定. 22 1 1 1 设计时间设计时间 2013 年 1 月 16 日至 2013 年
2、1 月 21 日 2 2 设计目的设计目的 数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的 技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有 力手段。要求学生掌握数据结构的应用、算法的编写、类 C 语言的算法转换成 C 程序 并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范 的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件 工作者工作作风的训练，将起到显著的促进作用。 3 3 设计任务设计任务 某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排 地铁建设线路，使市民可以沿地
3、铁到达各个辖区，并使总费用最小。 1. 输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比） ； 2. 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路； 3. 输出应该建设的地铁线路及所需建设总里程。 4 4 设设计内容计内容 4.1 需求分析 1、程序所能达到的功能： (1)根据输入的辖区信息，建立图模型，使用的数据结构是无向图，采用邻接矩阵 存储。 (2)根据普利姆算法计算最小生成树。 (3)输入各个辖区代号，名称和各辖区间直接距离（地铁铺设费用与距离成正比） 。 (4)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。 2 (5)输出应该建设的地铁线路及所需建设总里程。
4、2、输入的形式及内容： 包括城市名称、城市间距离权值、起始地点，详见 4.4.1 测试部分。 3、输出的形式及内容： 包括生成的邻接表、 应建设铁路的辖区名称及权值、 最终地铁的总里程， 详见 4.4.1 测试部分。 4、测试数据： 四个城市 abcd 及其之间的距离权值，详见 4.4.1 测试部分。 4.2 总体设计 4.2.1 数据类型的定义 1.图的邻接矩阵存储数据类型定义： typedef struct char VM10; int RMM; int vexnum;Graph;） 2.辅助数组数据类型定义： typedef struct int adjvex; int lowcost;
5、 closedgeMAX; 4.2.2 基本操作： CreateCity( /顶点数组，用来存储辖区的值即辖区的名称 int RMM; /邻接矩阵，邻接矩阵的元素值为辖区之间的距离 5 int vexnum; /辖区的个数 Graph; struct tree int weizhi; int lowcost; ; 4.3.2 创建辖区无向图的算法 int creatgraph(Graph *g) /创建辖区无向图，图中含有 n个结点，创建辖区邻接矩阵 int i=0,j,m,k,p; char a10,b10; printf(“*欢迎使用本程序解决地铁建设问题*n“); printf(“*请按照提示依次输入相关信息*n“); printf(“*请输入所有的辖区，以 0 作为结束标志*n“); scanf(“%s“,g-Vi);/输入结点值 while(strcmp(“0“,g-Vi)!=0) i+; scanf(“%s“,g-Vi); g-vexnum=i; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) 6 g-Rij=INFINITY;/初始化 printf(“*请输入辖区之间的路程，以 0 0 0 为结束标志*n“)
