数据结构报告 校园导航问题

《数据结构报告 校园导航问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、题目：校园导航问题班级：信计0901姓名：刘佺学号：3090104020完成日期：2011.6一：需求分析1.运行环境：MicrosoftVisualC++6.02.程序所实现的功能：设计一个校园导游程序，为来访的客人提供各种信息查询服务。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点相关信息的查询。3.程序的输入和包含输入的数据格式和说明：用户只需要按照页面的提示输入需要操作的序号，然后按回车确认即可。4.程序的输出格式和说明：当用户输入所要查询的地点序号，并且回车后，屏幕自动生成所查询路径的最短路

2、线和距离。5.测试数据：当用户进入最短距离查询界面后，输入起始地点序号1（江苏大学校大门）和终点序号后5（药学院），屏幕上自动生成这两条路径之间的最短距离519米，和最短路径江苏大学校大门→图书馆→药学院。当用户输入起始地点序号7（三江楼）和终点序号后13（女生一区），屏幕上自动生成这两条路径之间的最短距离1305米，和最短路径为三江楼→三山楼→东山操场→女生一区。二：设计说明(1).主要的数据结构设计说明：结构体的定义：typedefstructVertexType{intnumber;char*sight;}Verte

3、xType;typedefstruct{VertexTypevex[NUM];intarcs[NUM][NUM];intvexnum;}MGraph;常量的定义：#defineMax32767#defineNUM1各个函数的定义：voidCreateMGraph(intv)//创建图的函数，其中v表示图中的顶点数voidMap()//地图展示函数,用于输出西安科技大学的平面简略图charMenu()//主菜单显示于操作界面voidInfo()//资料介绍函数，用于当用户选择查询地点资料时输出地点的资料信息voidDijks

4、tra(intnum)//迪杰斯特拉函数voidDisplay(intsight1,intsight2)//地图展示函数voidmain()//主函数的定义(2).程序的主要流程图求最短路径算法流程图：(3.)主函数对各个函数的调用工作(4).主要函数的说明：#defineMax32767//用Max来表示权值为此时的两点间直接不可达#defineNUM15//选取了学校的十七个地点用数组存储，其中数组第一个元素不存储地点以方便操作typedefstructVertexType{intnumber;char*sight;}

5、VertexType;//定义顶点的结构体类型，number表示顶点编号，字符数组表示顶点的名称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]

6、;//定义全局变量D[NUM]存储点之间最短路径的权值voidDijkstra(intnum)//通过迪杰斯特拉算法求num点到其余点的最短路径，并将最短路径保存在数组P[NUM][NUM]中，将最短路径的权值保存在数组D[NUM]中{intv,w,i,t;intfinal[NUM];intmin;for(v=1;v

7、v]<32767){P[v][num]=1;P[v][v]=1;}}D[num]=0;final[num]=1;//初始化num顶点属于S集for(i=1;i

8、)//更新最短路径if(!final[w]&&((min+G.arcs[v][w])