西安邮电大学数据结构课程设计.doc

西安郵電學 计算机学院 学生姓名 专业名称 班 级 学号 指导教师 衡 霞 时间 2012年12月15日 至 2012年12月21日 实验题目 **市著名景点导游系统 一、实验目的 1.通过本次课程设计巩固《数据结构》课程中的所学内容； 2.提高自己上机编程以及调试能力。 二、实验内容 1.设计家乡著名景点平面图，所含景点不少于10个。以图中顶点表示城市中的各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 2.为来访游客提供图中任意景点相关信息的查询。 3.为来访游客提供图中任意景点的问路查询，即查询任意两个景点之间的所有路径和一条最短的简单路径。 三、需求分析 对所开发系统功能的描述，想要实现的目标，测试数据等 （问题提出、功能要求） 此系统可以进行韩城市的著名景点平面图查询，可以所有任意景点的详细介绍，可以查询任意两景点的所有路径，最短路径以及中转最少的路径，充当的导航的功能，使得出来此地的人可以方便游览。 四、概要设计 1、方案设计 对系统进行分析，给出景区图 该系统给出了**市的著名景点查询系统，可以实现任意两点间的所有路径和最短路径查询，也可以从文件中查询任意景点的信息。 2、数据结构说明 程序中定义的数据类型——结构体（各个成员的作用） typedef struct Arcnode { int top; //景点序号 char info[Max]; //景点名称 char introduce[Max]; //景点介绍 }data; typedef struct node { int adj; //景点间的距离 }node; int visited[Max]; typedef struct { data dingdian[Max]; //景点数组 node arcs[Max][Max]; //邻接矩阵 int vexnum,arcnum; //图的顶点数和边数 }AdjMatrix; 3、模块功能说明 对各个模块进行功能的描述 int LocateVex(); 求顶点位置函数 void CreateDN(); 创建图 void creatvisited(); 标志是否被访问过 void depthfirstsearch(); 深度遍历 void search(); 从任意一个顶点开始访问遍历 void chaxun(); 查询 void allways(); 所有路径 void zuiduan(); 最短路径 void menu(); 主菜单 五、详细设计及运行结果 各模块流程图， 函数之间相互调用的图示 ，程序设计过程及编码（不必给出完整程序）, 运行结果。 1, 功能函数的调用关系图； 2, 各功能函数的数据流程图 3重点设计及编码。 void zuiduan(AdjMatrix *G) { int vi,v0;//起始点与终点 int visit[Max];//访问标志 int path[Max];//记录当前查找到的最短路径 int dist[Max];//当前查找的最短路径长度 int i,j,k,t; int min; printf(请输入起始点:\n); scanf(%d,v0); if(v00||v0G-vexnum) { printf(the data is error!\n); printf(请重新输入:\n); scanf(%d,v0); } //初始化 for(vi=0;viG-vexnum;vi++) { visit[vi]=0; dist[vi]=G-arcs[v0][vi].adj; if(dist[vi]jidazhi) path[vi]=v0; else path[vi]=-3; } //迪杰斯特拉斯算法求任意两点间的最短路径 visit[v0]=1; path[v0]=0; for(t=1;tG-vexnum-1;t++) { min=j