个人资料整理仅限学习使用
软件学院
课程设计报告书
课程名称数据结构课程设计
设计题目地铁建设问题
专业班级
学号
姓名
指导教师
2018年 1 月
个人资料整理仅限学习使用目录
11 设计时间12 设计目的3设计任务14 设计内容14.1需求分析1
4.2总体设计2
4.3详细设计4
4.4测试与分析11
114.4.1测试134.4.2分析14附录4.5
20
总结与展望5
22 参考文献22
成绩评定
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
2
图详细设计4.3 4.3.1预处理#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define INFINITY 10000
#define M 20
创建图的结构体typedef struct{ // 。

//顶点数组，用来存储辖区的值即辖区的名称char V[M][10] 。

int R[M][M] //邻接矩阵，邻接矩阵的元素值为辖区之间的距离
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
4
图
根据需要，依次输入各个区域代号和边的权值，如图3.5所示：
5
图根据提示，输入地铁站的起始地点如图4.6所示：
6
图5.7输出最终结果，如图所示：
个人资料整理仅限学习使用
7
图 4.4.2分析 1.调试过程中遇到的问题是如何解决的以及对设计与实现的回
顾讨论和分析在设计之初，我对于整个算法的思路的理解并不清晰。

最首要的任务就是选择合适的计算思路，并加以实现。

经过查阅，我发现解决此类问题的核心思想就是最小生成树的生成。

于是我选用普利姆算法和简洁明了的邻接矩阵存储结构。

在实验过程中遇到的最大难题是普里姆算法的编写。

通过在书上和网上查阅资料，询问同学老师，结合之前上机实验的经验，我理清思路。

经过编写，调试，最终完成了程序的设计。

算法的时间复杂度和空间复杂度的分析2.表达是求值，主要是，空间复杂度为O(2n> 本程序算法的时间复杂度为O(n^3> 运用栈的相关知识解决的问题。

在此问题之中要运用到函数的多次调用等等。

3.针对可能出现的输入错误，作出相应的应对措施：8如输入辖区之间的权值时，当输入错误的辖区时会有报错提示，如图所示：
个人资料整理仅限学习使用
8
图 4.5 附录源程序：#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define INFINITY 10000
#define M 20
创建图的结构体typedef struct{ // 顶点数组，用来存储辖区的值即辖区的名称。

// char V[M][10] //。

邻接矩阵，邻接矩阵的元素值为辖区之间的距离int
R[M][M] //辖区的个数int vexnum。

}Graph 在辖区图中的位置int locatevex(Graph *g,char a[10]> //查找辖区u{
int i。

iu=V[i]i++>//i<g->vexnum for(i=0。

循环执行条件是当时停止，求值
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用
个人资料整理仅限学习使用。