C语言校园导航系统

1、常孝理N火孽EASTCHINAINSTITUTEOFTECHNOLOGY课程设计报告课程设计题目：校园导航专业：计算机科学与技术班级：1230701学号：201320070142学生姓名：胡玖龙指导教师：刘志锋2014年6月19日实验题目：校园导航系统实验时间：2014/6/16-2014/6/19实验地点：软件楼402实验目的：综合运用所学的数据结构知识解决一个关于学校导航系统的问题，侧重对图的相关内容特别是求最短路径的应用，使得能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下基础。实验要求：设计学校的平面图，至少包括10个以上的场所，每两

2、个场所间可以有不同的路，且路长也可能不同，找出从某个场所到达另一场所的最佳路径。求最短路径用Dijkstra或Floryd算法实现。实现思路:先分析需求，本程序的主要目的是提供本学校地点的路径查询，并提供其他各种信息查询服务。需求：1、提供校园平面图，使得能直观的了解学校。2、提供地点信息查询，为各地点提供简短的介绍。3、提供任意两地点间最短路径查询，并计算总路程。根据要求，先将校园平面图信息抽象为无向网，用邻接矩阵存储。需求1:定义map()函数，功能是输出校园的平面图。可简单的通过printf()函数实现。需求2:定义Query()函数，功能是查询输出地点信息。可直接输出无向网中的顶点信息

3、。需求3:根据输入的起点和终点，运用Floryd算法，求出最短路径，计算路径长度并输出。考虑到使用者并不一定需要使用所有的功能，所以开始时需要一个选择菜单。定义Menu()函数，功能是提供功能选择。输入1,选择查看学校平面图输入2,选择查看各地点信息输入3,选择查找两地点间最短路径输入4,退出程序总流程图:平面图模块流程图:地点信息查询模块流程图:结束求最短路径模块流程图:开始输出各地点编号结束实现过程：从学校的平面图中选取出12个比较重要的地点，将其抽象成无向带权网并用邻接矩阵来表示。以图中的顶点代表地点，存放地点名称、编号、简介等信息权值代表两地之间的距离。最短路径用Floyd算法求出。地

4、点间距离用地图软件测出。将得到的信息绘制成无向网:1801 .体育馆2 .北区宿舍3 .图书馆4 .樱花广场5 .三教6 .东门7 .青春广场8 .西区食堂9 .西区宿舍10 .南区食堂11 .南区宿舍12.南门程序用到的函数：MGraphInitGraph(MGraph&G)voidMenu()voidMap()VoidNumber()voidQuery(MGraphG)voidfloyd(MGraphG)voidshortestPath_Floyd(MGraph&G)voidmain();/构造校园图初始菜单校园平面图/隘出地点编号，在其他操作中会用到查找函数，可以输出地点

5、名称和介绍/floyd算法求最短路径主函数(1)图的存储结构：typedefstructcharname30;地点名称intnum;地点编号charintroduction200;地点介绍VertexType;/地点存储图的邻接矩阵地点数，路径数构造校园图typedefstructVertexTypevexsMAX;intarcsMAXMAX;intvexNum,arcNum;MGraph;（2）构造校园图：MGraphInitGraph（MGraph&G）inti,j;GvexNum=12;GarcNum=16;for（i=1;i<=G.vexNum;i+）Gvexsi.num

6、=i;strcpy（G.,"体育馆"）;strcpy（G.roduction,"有田径场及各种体育活动场馆"）;strcpy（G.,"北区宿舍"）；strcpy（G.roduction,"学校北区的宿舍"）；strcpy（G.,"图书馆"）;strcpy（G.roduction,"有着丰富的藏书，是学习、自习的好地方"）;strcpy（G.,&

7、quot;樱花广场"）;strcpy（G.roduction,"有很多樱花树，适合早读"）；strcpy（G.,"三教"）;strcpy（G.roduction,”学校的教学区"）；strcpy（G.,"东门）strcpy（G.roduction,"学校的正门"）;strcpy（G.,"青春广场"）;strcpy（G.roduction,"经常有

8、各种各样的社团活动"）;strcpy（G.,"西区食堂"）;strcpy（G.roduction,"西区的食堂，饭菜很好吃"）;strcpy（G.,"西区宿舍"）;"）;strcpy（G.roduction,"学校西区的宿舍，既有男生宿舍也有女生宿舍strcpy（G.,"南区食堂"）；strcpy（G.roduction,"南区食堂，饭菜很好吃"）;

9、strcpy（G.,"南区宿舍"）;strcpy（G.roduction,"学校南区的宿舍，全是男生宿舍"）；strcpy（G.,"南门）strcpy（G.roduction,"学校的南门，比较小"）;for（i=0;i<G.vexNum;i+）for(j=0;j<G.vexNum;j+)Garcsij=INFINITY;Garcs01=170;Garcs12=200;Garcs14=150;Garcs23=30;Garcs24=

10、150;Garcs25=300;Garcs34=30;Garcs46=170;Garcs47=160;Garcs56=500;Garcs510=570;Garcs67=100;Garcs78=160;G.arcs89=180;Garcs910=100;Garcs1011=20;for(i=0;i<G.vexNum;i+)for(j=0;j<G.vexNum;j+)Garcsji=G.arcsij;returnG;/不存在的路径长度设为无穷大无向网的邻接矩阵关于对角线对称(3)菜单模块：voidMenu()初始菜单printf("nn东华理工大学校园导游系统n")

11、;printf("11n");printf("|编号|功能In");printf("|11n");printf("|1|查看学校平面图In");printf("I2|查看地点信息In");printf("|3|查找两地点间最短路径In");printf("|4|退出In");printf("111n");printf("输入你的选择：")；（4）平向图模块：voidMap()校园平面图(printf("n&

12、quot;);printf("n");printf("11n");printf("11.体育馆1n");printf("11n");printf("111n");printf("1n");printf("1n");printf("11n");rtrinK/"In-1卜京密牟Inii.printf(i112口匕12M日£|1n);printf("11111n");printf("11111

13、n")printf("1r111n");printf("11111n")printf("i1111Hn")printf("+3.图书馆H116.n");printf("4.1111111东n");printf("樱门11T1nn")printf("花11JJ111n");printf("广11厂1111n");printf("场111111n")printf("111111n")prin

14、tf("士5.三教H1n");printf("L1111n")printf("111n")rtrinK/"LJ1_|nii.printf(11n);printf("1厂1.11n")printf("1n1111n");printf("11111n")printf("1117.青春广场11n");printf("18.西区食堂+11n");printf("11111n")printf("11111n

15、")printf("LJ1111n");printf("11n")printf("11n")printf("111n")printf("111n")printf("9.111n");printf("西111n")printf("区H1n")printf("printf("printf("printf("printf("printf("printf("prin

16、tf("printf("printf("printf("printf("printf("printf("printf("n");n");n");n");n");1111n");11n");11r1n");111111n");111111n");11111+n");110.南区食堂11.南区宿舍111n");111I11n");111112.南门n");1111n");

17、printf("11n");printf（"请按任意键继续!"）;getch();)(5)地点编号函数：VoidNumber()/输出地点编号，在其他操作中会用到(intv;printf("nn11n");printf("|编号|地点名称In");for(v=1;v<=G.vexNum;v+)printf("|%-4d|%-12s|n",G.vexsv.num,G.);)printf("111n");)(6)地点信息查询模块：voidQuery(MG

18、raphG)查找函数，可以输出地点名称和介绍intk,i=1;Number();while(i)printf("请输入要查询的地点编号，输入0退出:");scanf("%d",&k);if(k<0|k>G.vexNum)(printf("地点编号不存在！请重新输入地点编号：")；scanf("%d",&k);printf("%d.%s%-62snn",G.vexsk.num,G.,G.roduction);if(k=0)i=0;(

19、7)Floyd算法求最短路径：intDMAXMAX,PathMAXMAX;voidfloyd(MGraphG)/Floyd算法(inti,j,k;for(i=0;i<G.vexNum;i+)for(j=0;j<G.vexNum;j+)Dij=G.arcsij;if(i！=j&&G.arcsij<INFINITY)Pathij=i;elsePathij=-1;for(k=0;k<G.vexNum;k+)for(i=0;i<G.vexNum;i+)for(j=0;j<G.vexNum;j+)if(Dik+Dkj<Dij)Dij=Dik+Dk

20、j;Pathij=Pathkj;voidshortestPath_Floyd(MGraph&G)求最短路径inti,j,p,m,k;intb100;floyd(G);Number();doprintf("请输入起点编号：")；scanf("%d",&i);printf("请输入终点编号：")；scanf("%d",&j);if(i=j)printf("起点和终点一样，请重新输入n");elseif(i>12|i<0|j>12|j<0)printf(

21、"输入错误，t#重新输入n");while(i=j|i>12|i<0|j>12|j<0);i=i-1；j=j-1；if(i!=j)printf("起点：s,终点：sn最短路径：",G.vexsi+1.name,G.vexsj+1.name);P=Pathij;if(p=-1)printf("emptyn");elsem=0;bm+=j;while(p!=i)bm+=p;p=Pathip;bm=i;for(k=m;k>0;k-)printf("%s->",G.vexsbk+1.na

22、me);printf("%s,路程为%d米n",G.vexsb0+1.name,Dij);printf("nn按任意键继续nn");getch();(8)主函数：voidmain()主函数InitGraph(G);inti;Menu(G);scanf("%d",&i);/输入选择while(i!=4)/输入4,则退出switch(i)每次选择后会调用清屏函数，使界面美观case1:system("CLS");Map();Menu(G);break;若输入1,则输出平面图case2:system("

23、CLS");Query(G);Menu(G);break;若输入2,则查找并输出地点名称和介绍case3:system("CLS");shortestPath_Floyd(G);Menu(G);break;若输入3,则找出最短路径case4:;break;default:printf("输入错误，清重新输入n");scanf("%d",&i);运行结果:图1：初始菜单，输入1查看学校平面图，输入2查看地点信息，输入3查找两地点间最短路径,输入4退出。图2:查看地点信息输入要查询的地点编号，输入错误则出现错误提示，并重新输入。输入0则返回初始菜单。号舟I012123456789111称舍场LgWu堂舍名广食宿点春区区区肾地力修三至月西西南南南g鼐查询的翻穿星习、自习的好地方图3:查看学校平面图“C;：UsersAdmini5tratefDesklop'里程设计bug1课程没if,exe'4.瞿化广场8.西区食堂7.青春广场-南二宿告9.西区11请接任意舞继续、图4.1:查找两地间最短路径输入起点和终点编号，则会计算出最短路径