《大数据结构课程设计报告材料》由会员分享，可在线阅读，更多相关《大数据结构课程设计报告材料（40页珍藏版）》请在金锄头文库上搜索。
1、西安郵電大學数据结构课程设计报告书系部名称计算机学院学生姓名高 丹计算计算机科学与技术技术专 专业名称业班级科 1 1106学号04111196指导教师衡衡霞时间2012年12月15日2012至年12月21日实验题目延安市旅游导游系统一、实验目的1 加深对数据结构这一课程所学内容的进一步理解与巩固2 通过完成课程设计，逐渐培养自己的编程能力；3 培养给出题目后，构建框架，用计算机解决的能力；4 通过调试程序积累调试 C程序设计的经验；二、实验内容编写一个延安市旅游导游系统，其中有平面图，有景点列表，可以查询景 点简介，也可以查询两个景点间的最短路径，中转次数最少路径以及所有路径， 其中要用到数
2、据结构中的图的部分的知识。三、需求分析1. 开发系统功能描述(1) 菜单类函数void Me nuShow() 主界面菜单函数void Me nuShowO()输出延安市旅游景点平面图void Me nuShow1()延安市简介void Men uList() 旅游景点列表void S_Menu()查询菜单(2) 查询两点间最短路径.(权值最小)Shortroad(MGraph*G)弗洛伊德法来查询两点间最短路径(3) 查询两点间所有路径Depsearch(MGraph*G,i nt v,i nt w)allroads(MGraph *G)利用深度优先遍历图，递归的思想来完成所有路径的查找(4
3、) .查询中转次数最少的路径int lsEmpty(Li nkQueue *Q)判断队是否为空函数int Ini tQueue(Li nkQueue *Q)初始化队列函数int En terQueue(Li nkQueue *Q,i nt x) 进队函数int DeleteQueue(Li nkQueue *Q,i nt *x) 出队函数int NextAdjVertex(MGraph *G,i nt w,i nt v)求当前顶点的前一个顶点函数void BFS(MGraph *G,i nt vi,i nt vj)void Reseach(MGraph *G)广度优先遍历图，递归思想完成查询中
4、转次数最少的功能(5) .确定顶点位置函数int LocateVertex(MGraph * G, char v)确定当前顶点所在矩阵位置函数(6) .查询景点简介函数void Search_K (MGraph * G)按景点名称查询void Search_N (MGraph * G)按景点编号查询(7) .文件保存以及读出函数in t readn fo(MGraph *G)文件保存函数int savenfo (MGraph * G) 文件读出函数(8) .平面图的创建函数MGraph * CreatUDN(MGraph *G)平面图创建函数，若们有文件，则重新建立文件并保存(9) 主函数vo
5、id ma in (void)四、概要设计1、方案设计整个程序要实现的功能是导游功能，平面图如果文件里面有存储的话便从文 件读出，如果没有存储便创建文件存储。其中可以实现的功能为：按景点名称查询，按景点编号查询，查询两点间的 所有路径，查询两点间的最短路径，查询两点间中转次数最少的路径。 按景点名 称查询和按景点编号查询在此不做赘述，重要介绍其他三种查询方式。查询两点间所有路径：该查询方法应用的是深度优先遍历平面图的方法，其中定义两个数组，visit用来标记已遍历过的结点，path用来存储已找到景点 的编号，利用递归的思想一层一层向下遍历，最后打印出path数组便可完成该功能。查询两点间最短路
6、径：该查询方法应用的是弗洛伊德算法，定义的两个二维 数组D和Q,其中Q数组是用来存储查询到最短路径的景点矩阵的， D数 组是用来比较每两个景点之间的权值，每得到一个最小值便将D数组刷新一次， 将最后结果存入Q数组。查询两点间中转次数最少的路径：利用广度优先思想遍历平面图。其中应用 的队列的知识。先将最后一个顶点入队，然后利用NextAdjVertex 函数求它的上一个结点，利用递归思想一直找到最开始的一个结点 景区图：延安市主要景点平面图T北延安杨家岭革命旧址延安大学清凉山景区人民公园二道街中国抗日军政大学延河大桥百米大道凤凰山景区宝塔山火车站万花山景区2. 数据结构说明typedef str
7、uct ArCellint adj; /*路径长度*/ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;邻接矩阵typedef struct /*图中顶点表示主要景点，存放景点的编号、名称、简介等信息，*/char nameMAX;景点名称int num; 景点编号char in troductio n1000;/*简介 */in fotype;typedef structin fotype vexsMAX_VERTEX_NUM;存储景点信息的数组AdjMatrix arcs;存
8、储邻接矩阵的权值in t vex num;/ 图中的顶点数int arcnum; / 图中的弧数MGraph;/队列的结构体typedef struct Nodeint date;队列元素的值，在该程序中用来存储景点编号struct Node *n ext;Li nkQueueNode;队中的每个结点typedef structLin kQueueNode *front;队头指针Lin kQueueNode *fear;队尾指针Lin kQueue;int visitMAX;用来存储景点是否被访问，访问标做1，未访问标做0in t pathMAX;用来存储所有访问路径int top=-1;/*
9、记录路径的长度*/in t DMAXMAX,用来比较最短路径，不断刷新数组值in t QMAXMAX;用来存储最短路径的邻接矩阵五、详细设计及运行结果1.各函数之间的调用关系图2.各模块流程图创建函数查询所有路径查询中转次数最少的路径查询带权值最小路径程序设计过程及编码创建函数/初始化图形，接受用户输入MGraph * CreatUDN(MGraph *G)int i,j,k,w;char v120,v220;printf(n请输入地图所有景点的数目，以及所有路径的数目：);scanf(%d %d,&G-vex num,&G-arcnum);for (i=1;ivexnum;i+)/G 的初始
10、化邻接矩阵)for (j=1;jvex nu m;j+)G-arcsij.adj=INFINITY;printf(n请输入景点的编号：、名称、简介:n);for(i=1;ivex nu m;i+)printf(n 景点编号:);scan f(%d,&G-vexsi. nu m);printf(n 景点名称:);scan f(%s,G-vexsi. name);printf(n 景点简介:);sca nf(%s,G-vexsi.i ntroducti on);for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)G-arcsij.adj=INFINITY;print
11、f(n请输入每条路径长度:n);for(k=1;karc nu m;k+)printf(第%d 条边:n,k);printf(n 连接的景点名称为:n);sca nf(%s,v1);sca nf(%s,v2);printf(n 该路径长度为:n);sca nf(%d,&w);i=LocateVertex(G,v1);j=LocateVertex(G,v2);if(i=1 &j=1)G-arcsij.adj=w;G-arcsji=G-arcsij;return G;查询所有路径Depsearch(MGraph *G,i nt v,i nt w)int j,i;top+;pathtop=v;vis
12、itv=1;if(v=w)for(i=0;i,G-vexspathi. name);prin tf(bbn);visitv=0;top-;return ;for( j=1;jvex nu m;j+)if(G-arcsvj.adjINFINITY & !visitj)Depsearch(G,j,w);visitv=0;top-;allroads(MGraph *G)int v,w,i;char c=y;while(c=y)printf(请输入起始和终点的景点编号:);scan f(%d,%d,&v,&w);top=-1;for(i=0;iMAX;i+)visiti=O;Depsearch(G,v,w);printf(n是否继续查询最短路径(y/n):);fflush(stdi n);c=getchar();prin tf(n);查询权值最小路径Shortroad(MGraph *G)n是顶点数，D是权值,Q是最短路径int i,j,k,v,w;char c=y;while(c=y
