校园导游系统程序--课程设计-报告

1、需求分析设计一个校园导游系统程序，为来访的客人提供各种服务的信息查询。(1).设计工商学院校园无向图，所含的景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2).为来访客人提供图中任意景点相关信息的查询。(3).为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。2、设计思路校园旅游模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用弗洛伊德（Floyd）算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径。3 算法设计3.1 概要设计 3.1.1 程序中包含的模块（1）主程序模块主函数：void main(void)void cmd(void) cmd修改显示框大小,字体背景颜色,初始化景点，景点信息打印菜单， MGraph InitGraph(void); /初始化图。MGraph * CreatUDN(MGraph *G); /初始化图形接受用户输入void Menu(void);/菜单函数 void Browser(MGraph *G);/浏览函数void ShortestPath_DIJ(MGraph *G);void Floyd(MGraph *G);/ 查询图中任意两个景点间的所有路径void Search(MGraph *G);/查找函数int LocateVex(MGraph *G,char*v); / 迪杰斯特拉算法 计算起点各顶点间短路径,void print(MGraph *G); /输出函数（2）查询模块景点信息查询：void introduce()最短路径查询：要查找的两景点的最短距离：用floyd算法求两个景点的最短路径： （3）打印模块：void print(MGraph *G);3.1.2模块间的调用关系主函数main()调用void cmd（void）调用menu 并且用switch设置开关语句。3.2 详细设计3.2.1定义符号变量#define INFINITY 1000 /*穷*/#define MAX_VERTEX_NUM 40/*定义全局变量*/创建两个类 存储景点信息和存储景点道路和长度typedef struct ArCell /邻接矩阵int adj; /存储路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct /图顶点表示主要景点存放景点编号、名称、简介等信息char name20;int num;char introduction60;/简介infotype;typedef struct/图中的边表示景点间的道路，存放路径长度等信息。infotype vexsMAX_VERTEX_NUM;/顶点信息域AdjMatrix arcs;int vexnum,/*顶点数*/ arcnum;/边个数MGraph;MGraph b;3.2.2自定义函数原型说明给出函数声明void cmd(void);MGraph InitGraph(void);void Menu(void);void Browser(MGraph *G);void ShortestPath_DIJ(MGraph *G);void Floyd(MGraph *G);void Search(MGraph *G);int LocateVex(MGraph *G,char*v);MGraph * CreatUDN(MGraph *G);void print(MGraph *G);3.2.3定义各顶点之间的距离：for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; G.arcs01.adj=80;/*路径度*/ G.arcs02.adj=180; G.arcs06.adj=200; G.arcs111.adj=120; G.arcs12.adj=100; G.arcs25.adj=50; G.arcs34.adj=60; G.arcs49.adj=140; G.arcs59.adj=250; G.arcs57.adj=150; G.arcs67.adj=190; G.arcs69.adj=150; G.arcs87.adj=130; G.arcs86.adj=50; G.arcs1012.adj=100; G.arcs910.adj=150; G.arcs34.adj=190; G.arcs513.adj=150; G.arcs147.adj=350; G.arcs23.adj=190; G.arcs29.adj=150; G.arcs211.adj=120; G.arcs08.adj=120; G.arcs12.adj=50; G.arcs1012.adj=170; G.arcs1215.adj=160; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G;3.2.4界面菜单设计：菜单选择 void Menu() printf(n 武汉工商学院院导游图n); printf( n); printf( 1.浏览校园全景 n); printf( 2.查看所有游览路线 n); printf( 3.确定两景点之间最短距离 n); printf( 4.查看景点信息 n); printf( 5.退出导游系统 n); printf( n); printf(Option-:);Menu(); scanf(%d,&i); while(i!=5) switch(i) case 1:system(cls);Browser(&b);Menu();break; case 2:system(cls);ShortestPath_DIJ(&b);Menu();break; case 3:system(cls);Floyd(&b);Menu();break; case 4:system(cls);Search(&b);Menu();break; case 5:exit(1);break; default:break; 3.2.6介绍景点：void Browser(MGraph *G) int v; printf(n); printf(编号景点名称 简介 n); printf(n); for(v=0;vvexnum;v+)printf(%-4d%-20s%-60s n,G-vexsv.num,G-,G-roduction); printf(n);3.2.7要查找的两个景点的最短距离：用floyd算法求两个景点的最短路径void Floyd(MGraph *G)/查询图中任意两个景点间的所有路径。 int v,u,i,w,k,j,flag=1,p202020,D2020; for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(DvwINFINITY) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) printf(请输入出发地编号:); scanf(%d,&k); if(kG-vexnum) printf(景点编号存!n请输入出发地编号:); scanf(%d,&k); printf(请输入目的地编号:); scanf(%d,&j); if(jG-vexnum) printf(景点编号存!n请输入目的地编号:); scanf(%d,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0; printf(%s,G-); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-); printf(-%s,G-); printf( 总路线%dmn,Dkj); 3.2.8查看所有游览路线迪杰斯特拉算法计算单源最短路径，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v0到每个终点vi的最短路径的长度。若从v到vi有弧，则D为弧上的权值；否则置D为。4 测试分析 4.1 主程序界面 主程序从void main()开始运行void cmd(void) cmd修改显示框大小,字体背景颜色,初始化景点，景点信息的赋值初始化无向邻接图b=InitGraph(); 调用menu菜单函数打印菜单，提示用户输入选择功能。 图4-1.主程序界面4.2 浏览景点信息输出浏览比较简单就是把原来的景点信息利用for循环输出，int v=0；v小于最多的景点个数输出景点信息。依次输出。 图4-2 浏览景点信息4.3查看所有游览线路查看所有路线是使用void ShortestPath_DIJ(MGraph * G)/ 迪杰斯特拉算法 计算起点各顶点间短路径，然后利用for循环输出计算的结果。输入景点不正确时会输出景点不存在请重新输入景点编号。图4-3：查看所有游览路线4.4 确定两景点之间最短距离利用void Floyd(MGraph *G)/函数 利用循环嵌套 查询图中存在的任意两个景点间的最短路径再利用循环输出，如果景点不存在将会输出景点不存在 请输入出发地（目的地）编号。 图4-4：确定两景点之间最短距离4.5 查看景点信息利用void Search(MGraph *G)/函数，查看景点信息 查找景点编号，当输入景点编号不在范围时输出“景点编号不存在请重新输入编号：”输入正确时输出景点信息。图4-5：查看景点信息5系统功能及实现5.1 主程序界面 定义一个I,然后,调用InitGraph()函数初始化图,再调用menu()函数,再输入选择,利用switch开关语句,用户选择,需要的功能,实现想要的.。 图5-1.主程序界面5.2 浏览景点信息定义v；用for循环for（v=0；iG.vexnum;v+）当条件成立的时候执行printf语句，直到循环不成立的时候输出结束， 图5-2 浏览景点信息5.3查找所有游览线路查找路径利用，迪杰斯特拉算法，第1重循环for(x=0;xvexnum;x+)/第1重循环条件成立时执行 pwx=pvx;不成立时结束循环。图5-:3-1：查找所有游览路线第2重循环for（w=0；wvexnum;w+）循环条件成立的时候执行if(!finalw&(min+G-arcsvw.adjarcsvw.adj;第一重循环 pww=1; 循环不成立时循环结束图5-:3-2：查找所有游览路线第3重循环定义一个w ，利用for循环for（w=0；wvexnum;w+）当循环体成立时if(!finalw)if(Dwmin) v=w;min=Dw;finalv=1; 第2重for循环 循环条件 不成立循环终止结束跳出到第四重循环执行i+.图5-:3-3：查找所有游览路线第4重for循环定义I,利用for(i=0;ivexnum;i+)循环条件成立的时候执行 min=INFINITY; 以及第3重for循环 里面的代码 直到循环条件不成立,循环结束然后利用for输出查找结果 如图5-3-4图5-3-4：查看所有游览路线（第4重循环）这是查看所有路线功能里的输出循环,定义v ,i整型变量然后利用for(v=0;vvexnum;v+)判断if(v0!=v)如果成立执行 printf(%s,G-); 然后执行第二重 for(w=0;wvexnum;w+) if(pvw&w!=v0) printf(-%s,G-); t+; if(tG-vexnum&v0!=v)printf( 总路线%dmnn,Dv); 第1重循环结束后跳到第1重v+直到外重循环循环条件不成立循环结束图5-3-5：查看所有游览路线5.4 确定两景点之间最短距离利用多个for循环嵌套，计算出路径，计算出路径长度，当最外重循环不成立时循环结束.利用for循环输出图5-4-2：确定两景点之间最短距离6总结经过近两周的课程设计，总的来说收获还是很大的！首先代码能力明显提高，有了想法基本都能顺利表达出来；再者就是数据结构的选择使用能力也有了很大的提高！虽说平时的试验课我们也有用各种数据做题，但那些都是很明确的知道该做什么操作，存什么，我们的发挥空间不大一般照做就行，然而这次实习我们却在自主的选择判断，这本身就是一个很大的提高！还有就是算法方面的学习有了初步进阶，如最短路径，这样比较简单的图论算法能比较熟练的写出来。但是还是有很多的只是不了解！收获真的很多，但是最大的收获可能就是对编程的兴趣吧，在一次次的改错，一次次的完成想要的效果后，越写越有感觉！当然还收获了无知，更确切的说是自知，原来我们现在什么也不算，还有很多有用的只是等着我们去学习！7 参考文献1 谭浩强.C程序设计（第四版）M. 北京：清华大学出版社，2010:293-326.2 苏小红，孙志岗，陈惠鹏.C语言大学实用教程（第三版）M. 北京：电子工业出版社，2012:240-280.3 林锐.高质量C+/C编程指南M.北京：清华大学出版社2001.7:245-278.4 陈朔鹰,陈英.C语言程序设计习题集（第二版）M.北京：人民邮电出版社，2003.2：320-360.5 谭浩强.C语言程序设计题解与上机指导M.北京：清华大学出版社，2000.11：12-60.6 塞奇威克. 算法：C语言实现M. 北京：机械工业出版社,2009:213-225.7 里斯.深入理解C指针M. 北京：人民邮电出版社，2014:103-122.8 陈正冲.C语言深度解剖(第2版)M.北京：北京航空航天大学出版社，2012:34-42.9 贾宗璞.C语言程序设计M.江苏：中国矿业大学出版社，2007.6:112-135.10周海燕，赵重敏，齐华山.C语言程序设计M. 北京：科学出版社，2001:165-187.8附录#define INFINITY /*穷*/#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include#includetypedef struct ArCellint adj; /路径度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/邻接矩阵typedef struct /图顶点表示主要景点存放景点编号、名称、简介等信息char name20;int num;char introduction60;/简介infotype;typedef struct/图中的边表示景点间的道路，存放路径长度等信息。infotype vexsMAX_VERTEX_NUM;/顶点信息域AdjMatrix arcs;int vexnum,/*顶点数*/ arcnum;/边个数MGraph;MGraph b;void cmd(void);MGraph InitGraph(void);void Menu(void);void Browser(MGraph *G);void ShortestPath_DIJ(MGraph *G);void Floyd(MGraph *G);void Search(MGraph *G);int LocateVex(MGraph *G,char*v);MGraph * CreatUDN(MGraph *G);void print(MGraph *G);/*/void main(void) system(color 0f); system(mode con: cols=150 lines=140); cmd();/*/void cmd(void) int i; b=InitGraph(); Menu(); scanf(%d,&i); while(i!=5) switch(i) case 1:system(cls); Browser(&b); Menu();break;/1.浏览校园全景 case 2:system(cls); ShortestPath_DIJ(&b); Menu();break;/2.查看所有游览路线 case 3:system(cls); Floyd(&b); Menu(); break;/3.确定两景点之间最短距离 case 4:system(cls); Search(&b); Menu();break;/4.查看景点信息 case 5:exit(1);break; default:break; printf(请重新输入（1-5）：); scanf(%d,&i); MGraph InitGraph(void)/初始化 MGraph G; int i,j; G.vexnum=16; G.arcnum=40; for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,唐人街 ); strcpy(G.roduction,学校门口小吃街); strcpy(G.,校大门 ); strcpy(G.roduction,学校大门是学校的门面); strcpy(G.,校 综合楼 ); strcpy(G.roduction,全体教师办公场所 楼高12层 各种设施齐全 ); strcpy(G.,体育馆 足球场 ); strcpy(G.roduction,体育馆一楼为室内羽毛球 乒乓球 馆,室外为塑胶跑道, 晚上散步); strcpy(G.,医务室 ); strcpy(G.roduction,体育馆一楼为医用费用较贵 .); strcpy(G.,外语楼 ); strcpy(G.roduction,校第二教学楼,共7层环形 环境优美,适宜学习); strcpy(G.,5 号宿舍楼 ); strcpy(G.roduction,多个学院 女生宿舍楼 位于弘德楼旁边); strcpy(G.,湖边小树林 ); strcpy(G.roduction, 绿树荫阴,适宜休息 晨读 还有小情侣约会); strcpy(G.,弘德楼 ); strcpy(G.roduction,全校最高建筑物弘德楼 一楼与二楼是学生第一食堂); strcpy(G.,图书馆 ); strcpy(G.roduction,藏书145万册,设施优良 一楼有咖啡厅 环境优雅 2楼设有电子阅览室); strcpy(G.,静思湖 ); strcpy(G.roduction,校内湖,环境好 内有荷花 湖上还造了回心转意桥夏天荷花漂亮); strcpy(G.,第三教学楼); strcpy(G.roduction,校第三教楼为实验楼,环境好 内设 物理 化学实验室和电脑机房); strcpy(G.,学生第二食堂 ); strcpy(G.roduction,环境比较好 ,饭菜还可以); strcpy(G.,1 2 3 4 号宿舍楼 ); strcpy(G.roduction,1 3 号是学院女生宿舍楼,2 4号是男生宿舍楼); strcpy(G.,6 号宿舍楼 ); strcpy(G.roduction,6 栋是学校的鸳鸯楼就是男生半栋女生半栋楼); strcpy(G.,黄家湖 ); strcpy(G.roduction,位于学校足球场旁边生态湖,可以在那钓鱼 ); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; G.arcs01.adj=80;/*路径度*/ G.arcs111.adj=110; G.arcs12.adj=50; G.arcs15.adj=90; G.arcs211.adj=65; G.arcs25.adj=90; G.arcs210.adj=85; G.arcs29.adj=90; G.arcs23.adj=150; G.arcs59.adj=80; G.arcs53.adj=70; G.arcs513.adj=40; G.arcs138.adj=50; G.arcs133.adj=100; G.arcs135.adj=80; G.arcs86.adj=55; G.arcs87.adj=50; G.arcs64.adj=55; G.arcs910.adj=45; G.arcs93.adj=65; G.arcs1014.adj=120; G.arcs1012.adj=150; G.arcs1214.adj=170; G.arcs1012.adj=170; G.arcs1215.adj=160; G.arcs910.adj=150; G.arcs1012.adj=100; G.arcs1215.adj=160; G.arcs147.adj=150;for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G;/InitGraph endvoid Menu()/菜单 printf(n 武汉工商学院院导游图n); printf( n); printf( 1.浏览校园全景 n); printf( 2.查看所有游览路线 n); printf( 3.确定两景点之间最短距离 n); printf( 4.查看景点信息 n); printf( 5.退出导游系统 n); printf( n); printf(Option-:);void Browser(MGraph *G)/浏览 int v; printf(n); printf(编号景点名称 简介 n); printf(n); for(v=0;vvexnum;v+) printf(%-4d%-20s%-60s n,G-vexsv.num,G-,G-roduction); printf(n);void ShortestPath_DIJ(MGraph * G)/ 迪杰斯特拉算法 计算起点各顶点间短路径 查找所有路线 int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020; while(flag) printf(请输入起始景点编号:); scanf(%d,&v0); if(v0G-vexnum) printf(景点编号存!请重新输入景点编号:); scanf(%d,&v0); if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; Dv=G-arcsv0v.adj;/存储起始v0-末尾v之间权值 for(w=0;wvexnum;w+) pvw=0; if(DvINFINITY) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=INFINITY; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; for(v=0;vvexnum;v+) if(v0!=v) printf(%s,G-); for(w=0;wvexnum;w+) if(pvw&w!=v0) printf(-%s,G-); t+; if(tG-vexnum&v0!=v)printf( 总路线%dmnn,Dv); /ShortestPath_DIJ endvoid Floyd(MGraph *G)/查询图中任意两个景点间的最短路径。 int v,u,i,w,k,j,flag=1,p202020,D2020; for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(DvwINFINITY) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw;for(i=0;ivexnum;i+)pvwi=pvui|puwi;while(flag)printf(请输入出发地编号:);scanf(%d,&k);if(kG-vexnum)printf(景点编号存!n请输入出发地编号:);scanf(%d,&k);printf(请输入目的地编号:);scanf(%d,&j);if(jG-vexnum)printf(景点编号存!n请输入目的地编号:);scanf(%d,&j);if(k=0&kvexnum&j=0&jvexnum)flag=0;printf(%s,G-);for(u=0;uvexnum;u+)if(pkju&k!=u&j!=u)printf(-%s