欢迎来到天天文库
浏览记录
ID:55036036
大小:569.50 KB
页数:18页
时间:2020-04-26
《数据结构报告-校园导航问题.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、一:需求分析1.运行环境:MicrosoftVisualC++6.02.程序所实现的功能:设计一个校园导游程序,为来访的客人提供各种信息查询服务。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点相关信息的查询。3.程序的输入和包含输入的数据格式和说明:用户只需要按照页面的提示输入需要操作的序号,然后按回车确认即可。4.程序的输出格式和说明:当用户输入所要查询的地点序号,并且回车后,屏幕自动生成所查询路径的最短路线和距离。5.测试数据:当用户进入最短距离查询界面后,输入起始地点序号1(江苏大学校大门)和终
2、点序号后5(药学院),屏幕上自动生成这两条路径之间的最短距离519米,和最短路径江苏大学校大门→图书馆→药学院。当用户输入起始地点序号7(三江楼)和终点序号后13(女生一区),屏幕上自动生成这两条路径之间的最短距离1305米,和最短路径为三江楼→三山楼→东山操场→女生一区。二:设计说明(1).主要的数据结构设计说明:结构体的定义:typedefstructVertexType{intnumber;char*sight;}VertexType;typedefstruct{VertexTypevex[NUM];intarcs[
3、NUM][NUM];intvexnum;}MGraph;常量的定义:#defineMax32767#defineNUM1各个函数的定义:voidCreateMGraph(intv)//创建图的函数,其中v表示图中的顶点数voidMap()//地图展示函数,用于输出西安科技大学的平面简略图charMenu()//主菜单显示于操作界面voidInfo()//资料介绍函数,用于当用户选择查询地点资料时输出地点的资料信息voidDijkstra(intnum)//迪杰斯特拉函数voidDisplay(intsight1,intsi
4、ght2)//地图展示函数voidmain()//主函数的定义(2).程序的主要流程图求最短路径算法流程图:(3.)主函数对各个函数的调用工作(4).主要函数的说明:#defineMax32767//用Max来表示权值为此时的两点间直接不可达#defineNUM15//选取了学校的十七个地点用数组存储,其中数组第一个元素不存储地点以方便操作typedefstructVertexType{intnumber;char*sight;}VertexType;//定义顶点的结构体类型,number表示顶点编号,字符数组表示顶点的名
5、称typedefstruct{VertexTypevex[NUM];intarcs[NUM][NUM];intvexnum;}MGraph;//定义图的结构体类型,vex[NUM]数组存储顶点,arcsp[NUM][NUM]矩阵存储边的权值,vexnum表示顶点的个数MGraphG;{生成G表示结构体变量MGraph}intP[NUM][NUM];//定义全局变量P[NUM][NUM]存储点之间的最短路径longintD[NUM];//定义全局变量D[NUM]存储点之间最短路径的权值voidDijkstra(intnum)
6、//通过迪杰斯特拉算法求num点到其余点的最短路径,并将最短路径保存在数组P[NUM][NUM]中,将最短路径的权值保存在数组D[NUM]中{intv,w,i,t;intfinal[NUM];intmin;for(v=1;v7、l[num]=1;//初始化num顶点属于S集for(i=1;i8、))//修改D[w]和P[w],w在V-S集中{D[w]=min+G.arcs[v][w];for(t=0;t
7、l[num]=1;//初始化num顶点属于S集for(i=1;i8、))//修改D[w]和P[w],w在V-S集中{D[w]=min+G.arcs[v][w];for(t=0;t
8、))//修改D[w]和P[w],w在V-S集中{D[w]=min+G.arcs[v][w];for(t=0;t
此文档下载收益归作者所有