1、用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。最后switch选择语句选择执行浏览景点信息或查询最短路径和距离。 2.1.1学校以及各景点介绍模块 采用了图的邻接矩阵存储结构，首先初始化每一个景点名称（一维数组）for（i=1;iG.vexnum;+i） G.
2、vexi.number=i 景点介绍功能流程图2.1.2查询最短路径（主要） 算法的主要思想是按路径长度递增的次序产生最短路径的算法。中心思想是假设s为已求得最短路径的终点的集合，则下一条最短路径或者是弧（v,x）或者是中间经过s中是顶点而最后到达顶点x的路径。（1）arcs表示弧上的权值。若不存在，则置arcs为。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcsLocate Vex（G,v）,i viV（2）选择vj，使得Dj=MinD | viV-S （3修改从v出发到集合V-S上任一顶点vk可达的最短路
3、径长度路径查询流程图2.1.3查询各点距离由于图的结构比较复杂，任意两个点之间都可能存在联系。因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，但是却可以借助数组的数据类型表示元素之间的关系。2.1.4主函数循环体用开关语句，该语句的条件值ck是当用户选择菜单通过调用主菜单函数得到，返回值整数作开关语句的条件。根据该值调用相应的各功能函数，同时设置一个退出程序点，执行完用户的某项功能后继续显示菜单，当返回值为e时函数结束程序，以免造成死循环。2.2数据结构与函数考虑2.2.1数据结构定义结构体类型，将多个相关的变量包装成为一个整体使用。#define Max 32767 #defin
4、e NUM 20 自定义顶点的类型typedef struct VertexType int number; / 景点编号char *sight;/ 景点名称VertexType;自定义图的类型typedef structVertexType vexNUM; / 图中的顶点，即为景点int arcsNUMNUM; / 图中的边，即为景点间的距离int vexnum; / 顶点数MGraph;把图定义为全局变量MGraph G;int PNUMNUM; 辅助变量存储最短路径长度long int DNUM;2.2.2 使用的系统头文件#include stdio.h /*I/O 函数*/ stdl
5、ib.h /*使用system（）exit（）atoi（）malloc（）free（）函*/ string.h /*字符串函数，strcpy（）strlen（）strcmp（）*/ 三、主程序 #include string.hstdlib.h #define Max 32767 #define NUM 20 typedef struct VertexType int number; char *sight; typedef struct VertexType vexNUM; int arcsNUMNUM; int vexnum; MGraph; MGraph G; void CreateMG
6、raph（int v）/创建图的函数,v是函数入口 int i,j; G.vexnum=v; for（i=1;+i） G.vexi.number=i; G.vex0.sight=各个地点名字; G.vex1.sight=江南大学校北门 G.vex2.sight=第一食堂 G.vex3.sight=江南大学东偏门 G.vex4.sight=设计学院 G.vex5.sight=体育中心 G.vex6.sight=物联网工程学院 G.vex7.sight=图书馆 G.vex8.sight=江南大学东门 G.vex9.sight=国家重点实验室 G.vex10.sight=第二教学楼 G.vex11.
7、sight=第四食堂 G.vex13.sight=臻善楼 G.vex12.sight=江南大学南门for（j=1;j+j） G.arcsij=Max; G.arcs12=G.arcs21=200; G.arcs13=G.arcs31=210; G.arcs15=G.arcs51=521; G.arcs24=G.arcs42=299; G.arcs25=G.arcs52=450; G.arcs23=G.arcs32=869; G.arcs35=G.arcs53=620; G.arcs38=G.arcs83=756; G.arcs45=G.arcs54=355; G.arcs46=G.arcs64
8、=221; G.arcs57=G.arcs75=225;G.arcs58=G.arcs85=900; G.arcs67=G.arcs76=280; G.arcs69=G.arcs96=241; G.arcs78=G.arcs87=440; G.arcs710=G.arcs107=350;G.arcs810=G.arcs108=570; G.arcs910=G.arcs109=1300; G.arcs911=G.arcs119=998; G.arcs912=G.arcs129=1200; G.arcs1011=G.arcs1110=639; G.arcs1012=G.arcs1210=805;
9、G.arcs1112=G.arcs1211=283;G.arcs1213=G.arcs1312=296; void Map（）/地图展示函数 printf（t *江南大学大学地图导航系统* n）; 1 江南大学北大门 n n 2第一食堂 3江南大学东偏门 n 4设计学院5体育中心 n 6物联网工程学院7图书馆 8江南大学东门 n 9国家重点实验室 10第二教学楼 n n n 11第四食堂 n n 13臻善楼12江南大学南门 n void Info（）/资料介绍函数1 江南大学校北大门 ：这是江南大学最有名的大门，是一座充满历史感的高大的牌坊，正上面写着“江南大学”四个大字，背面写着“江南第一学
10、府”六个字n2 江南大学第一食堂n3 江南大学东偏门： n4 设计学院：n5 体育中心：6 物联网工程学院：7 图书馆：高达15层的雄伟的图书馆 n8 江南大学东门：9 国家重点实验室：10 第二教学楼：printf（11 第四食堂:13 臻善楼:12 江南大学南门:void ShortestPath（int num） / 迪杰斯特拉算法最短路径函数num为入口点的编号 int v,w,i,t; / i、w和v为计数变量 int finalNUM; int min;for（v=1;vNUM;v+） finalv=0; / 假设从顶点num到顶点v没有最短路径 Dv=G.arcsnumv;/ 将
11、与之相关的权值放入D中存放 for（w=1;ww+） / 设置为空路径 Pvw=0; if（Dv32767） /存在路径 Pvnum=1; /存在标志置为一 Pvv=1; /自身到自身 Dnum=0;finalnum=1; /初始化num顶点属于S集合/ 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合for（i=1;+i） /其余G.vexnum-1个顶点min=Max; / 当前所知离顶点num的最近距离for（w=1;+w） if（!finalw） / w顶点在v-s中if（Dwmin） / w顶点离num顶点更近 v=w;min=Dw; / 更新当前最短路径极其距离
12、finalv=1; / 离num顶点更近的v加入到s集合 if（!finalw&（min+G.arcsvw）Dw） / 不在s集合，并且比以前所找到的路径都短就更新当前路径Dw=min+G.arcsvw;for（t=0;tt+）Pwt=Pvt;Pww=1;char Menu（）/应用主界面显示函数 char c; int flag; do system（cls flag=1; Map（）; printf（tt欢迎使用江南大学导航图系统ntt 1.查询地点之间最短路径 ntt 2.江南大学景点介绍ntt e.退出 nttt请输入您的选择： scanf（%c,&c）; if（c=1|c=2e）/如
13、果输入为1,2,E中的一个，则返回C flag=0; while（flag）; return c;void Display（int sight1,int sight2）/最短距离显示函数 int a,b,c,d,q=0; a=sight2; if（a!=sight1） nt从%s到%s的最短路径是,G.vexsight1.sight,G.vexsight2.sight）;t（最短距离为 %d.m）nnt,Da）;t%s,G.vexsight1.sight）; d=sight1; for（c=0;c+c） Pasight1=0; for（b=0;bb+） if（G.arcsdb%s,G.vexb
14、.sight）; q=q+1; Pab=0; d=b; if（q%8=0） printf（ void main（）/主界面最短路线查询显示函数 int v0,v1; char e; char ck; CreateMGraph（NUM）; do ck=Menu（）; switch（ck） case : gate: system（ Map（）; do printf（nnttt请选择出发地序号（113）： scanf（%dv0）; if（v013）nntttt输入错误! while（v013）;ttt请选择目的地序号（113）：v1）; if（v113|v1=v0） while（v113|v1=v0
15、）; ShortestPath（v0）; Display（v0,v1）; printf（nntttt按回车键继续,按e退回首页n getchar（）; scanf（e）; if（e=） break; goto gate; case Info（）;nntttt按回车键返回首页.n break; ; while（ck!=四、程序调试及运行结果贴图五、总结通过这次设计，是我得以更好的掌握C语言的编程，对一些算法思想和实现方法有了更深的了解。在设计中，出现了一系列的问题，好多次都差点坚持不下去，但最终还是完成了！当程序编译并且运行成功的那一刻，真的是非常的激动。感谢老师平时上课时的教导，可以使我更好的完成这次作业
