校园导游咨询系统---数据结构课程设计

石家庄经济学院 本科生课程设计报告书 题 目 校园导游咨询系统 姓名 颜建学 学号 1 学 院 信息工程学院 专业 计算机方向 指导教师 XXXXXX 完成日期： 2012-07-5校园导游咨询系统1 需求分析本程序的主要目的是为了提供本学校的景点的路径咨询和来访客人以及刚来报到的新生提供一个快捷方便的路径咨询，快速有效的提高了用户的熟悉度。满足用户查询的需要：1、从石家庄经济学院的平面地图中选取出10个有代表性的景点。2、为来访的客人提供图中任意景点相关信息的查询。当用户输入正确时，为用户输出景点的相关信息；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。3、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。4、为来访客人推荐参观路线。2 概要设计1、抽象数据类型图的定义如下：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在路径基本操作P：CreatGraph70321(&G,V,VR)初始条件：V是图的顶点集，VR是图中边的集合。操作结果：按V和VR的定义构造图G。DestroyGraph70321(&G)初始条件：图G存在。操作结果：销毁图G。LocateVex70321(G,u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex70321(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返回v的信息。FirstEdge70321(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返回依附于v的第一条边。若该顶点在G中没有邻接点，则返回“空”。 NextEdge70321(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回依附于v的（相对于w的）下一条边。若不存在，则返回“空”。 InsertVex70321(&G,v)初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图中增添新顶点v。DeleteVex70321(&G,v)初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的边。InsertEdge70321(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添边(v,w).DeleteEdge70321(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除边(v,w)。GetShortestPath70321(G,st,nd,&Path)初始条件：图G存在，st和nd是G中两个顶点。操作结果：若st和nd之间存在路径，则以Path返回两点之间一条最短路径，否则返回其他信息。ADT Graph主程序void main()初始化； do 接受命令（输入景点信息或输出最短路径）； 处理命令； while（“命令”！=“退出”）；2、调用的函数有如下：void CreateUDN70321(int v,int a); /* 造图函数 */void narrate70321(); /*说明函数*/void ShortestPath70321(int num); /*最短路径函数*/void output70321(int sight1,int sight2); /*输出函数*/char Menu70321(); /* 主菜单 */void search70321(); /* 查询景点信息 */char SearchMenu70321(); /* 查询子菜单 */void HaMiTonian70321(int); /* 哈密尔顿图的遍历 */void NextValue70321(int); void display70321(); /* 显示遍历结果 */3、运行主界面：*欢 迎 使 用 校 园 导 游 程 序*石*家*庄*经*济*学*院*制作者：信息工程学院 1 颜建学 ！欢迎您的使用！ 景点名称 （0）教学主楼 （1）足球场 （2）灯光篮球场 （3）惠馨园 （4）实验楼 （5）计算机实验室 （6）地球科学博物馆 （7）学术报告厅 （8）图书馆 （9）喷泉 1、查询景点路径 2、查询景点信息 3、推荐参观路线 e、退出 子界面如下： 1、按照景点编号查询 2、按照景点名称查询 e、返回 3、模块图表示如下：主程序模块处理功能模块无向图存储模块为用户输出景点信息为用户输出两景点最佳路径推荐参观路径3 详细设计从石家庄经济学院的平面地图中选取出10个有代表性的景点，将其抽象成无向带权网并用邻接矩阵来表示。以图中的顶点代表景点，存放景点名称、代号、简介等信息，权值代表两地之间的距离。1、 图的存储结构如下：#define Max 20000#define NUM 9typedef struct ArcCell int adj; /* 相邻接的景点之间的路程 */ArcCell; /* 定义边的类型 */typedef struct VertexType70321 int number; /* 景点编号 */ char *sight; /* 景点名称 */ char *description; /* 景点描述 */VertexType; /* 定义顶点的类型 */typedef struct VertexType vexNUM; /* 图中的顶点，即为景点 */ ArcCell arcsNUMNUM; /* 图中的边，即为景点间的距离 */ int vexnum,arcnum; /* 顶点数，边数 */MGraph; /* 定义图的类型2、该程序的算法如下：1)void CreateUDN70321(MGraph&G) /* 造图函数 */ /采用邻接矩阵表示法，构造无向网Gscanf(&G.vexnum,&G.arcnum,&IncInfo);/ IncInfo为0则各弧不含其它信息for(i=0;i G.vexnum;+i)scanf(&G.vexsi);/构造顶点向量for(i=0;i G.vexnum;+i)/初始化邻接矩阵for(j=0;j G.vexnum;+j)G.arcsij=INFINITY,NULLfor(k=0;k G.arcnum;+k)/构造邻接矩阵scanf(&v1,&v2,&w);/输入一条边依附的顶点及权值i=LocateVex(G,v1);j= LocateVex(G,v2);/确定V1和V2在G中的位置G.arcsij.adj=w;/弧的权值If(IncInfo)Input(*G.);/若弧含有相关信息，则输入G.arcsji= G.arcsij;/置的对称弧 Return OK; 2)void narrate70321() /* 说明函数 */k=0;printf(ntt*欢 迎 使 用 校 园 导 游 程 序*n);printf(ntt*石*家*庄*经*济*学*院*n);printf(ntt制作者： 信息工程学院 1 颜建学 ！欢迎您使用！n);printf(ntt_n);printf(ttttt 景点名称ttn);printf(tt_n);for(i=0;iNUM;i+)printf(tt (%2d)%-15stt,i,G.vexi.sight);if(i%2=(NUM-1)%2)printf(n);/奇数编号景点在右边，偶数编号景点在左边k=k+1;printf(tt_n);3) void ShortestPath70321(int num) /用迪杰斯特拉算法求G的v0顶点到其余顶点的最短路径Pv及其带权长度 Dv/若Pvw为TRUE,则 w是从v0到v当前求得最短路径上的顶点 /finalv为TRUE当且仅当v属于S，即已经 求得从 v0到v的最短路径 for(v=0;vG.vexnum;+v) Finalv=FALSE;Dv= G.arcsv0v; For(w=0;w G.vexnum;+w)Pvw=FALSE; If (DvINFINITY)Pvv0=TRUE;Pvv=TRUE; /forDv0=0;finalv0=TRUE;/开始主循环，每次求得v0到某个顶点的最短路径，并加v到S集For(i=1;i G.vexnum;+i) Min=INFINITY; For(w=0;w G.vexnum;+w) If(!finalw) If(Dwmin)v=w;min=Dw; Finalv=TRUE; For(w=0;w G.vexnum;+w) If(!finalw&(min+G.arcsvwDw) Dw= min+G.arcsvw; Pw=Pv;Pww=TRUE; /if /for / ShortestPath4) void output70321(int sight1,int sight2) /* 输出函数 */ if(sight2!=sight1) /* 如果景点二不和景点一输入重合，则进行. */ printf(从G.vexsight1.sight到G.vexsight2.sight的最短路径是:);/* 输出提示信息 */ printf(Da); /* 输出sight1到sight2的最短路径长度，存放在D数组中 */ printf(G.vexsight1.sight); /* 输出景点一的名称 */ d=sight1; /* 将景点一的编号赋值给d */ for(c=0;cNUM;+c) Pasight1=0; for(b=0;bNUM;b+) if(G.arcsdb.adj20000&Pab) /* 如果景点一和它的一个临界点之间存在路径且最短路径 */ printf(G.vexb.sight); /* 输出此节点的名称 */ q=q+1; /* 计数变量加一，满8控制输出时的换行 */ Pab=0; d=b; /* 将b作为出发点进行下一次循环输出，如此反复 */ if(q%8=0) returnOK; 5)void main() /* 主函数 */CreateUDN70321(NUM,11); do switch(Menu() case 1: narrate70321(); scanf(v0); scanf(v1); ShortestPath70321(v0); /* 计算两个景点之间的最短路径 */ Output70321(v0,v1); /* 输出结果 */ break; case 2:search(); break; case 3: narrate70321(); HaMiTonian(x0); break; ; while(Menu()!=e); 6) char Menu() /* 主菜单 */ do flag=1; narrate70321(); scanf(c); if(c=1|c=2|c=3|c=e) flag=0; while(flag); return c;7) char SearchMenu70321() /* 查询子菜单 */ do flag=1; narrate70321(); scanf(&c); if(c=1|c=2|c=e) flag=0; while(flag); return c;8) void search70321() /* 查询景点信息 */do switch 70321(SearchMenu() case 1: narrate70321(); scanf(&num); for(i=0;iNUM;i+) if(num=G.vexi.number) printf(G.vexi.description); break; if(i=NUM) printf(没有找到！); getchar70321(); break; case 2: narrate70321(); scanf(name); for(i=0;i9|v19) printf(nttO(_)O 请重新输入v0,v1:n); goto M; ShortestPath70321(v0); /调用ShortestPath()函数 output70321(v0,v1); /调用output()函数 goto M; break;case 2:search70321();/调用search()函数break;case 3:system(cls);narrate70321();/调用 narrate()函数x0=1; /此处必须为x0=1 实际为x0=trueHaMiTonian70321(1); /调用哈密尔顿函数 遍历应该从第一个景点开始！如果想要修改，必须从HaMiTonian()和NextValue()内部修改printf(nntttt请按Enter继续.n);getchar();getchar();break;while(ck!=e);void daoyouzixunxitong70321:CreateUDN70321(int v, int a)int i,j;G.vexnum=v; G.arcnum=a;for(i=0;iG.vexnum;+i) G.vexi.number=i;G.vex0.sight=教学主楼;G.vex0.description=学校领导， * 办公之地;G.vex1.sight=足球场;G.vex1.description=宽阔,非常适合运动;G.vex2.sight=灯光篮球场;G.vex2.description=篮球运动的最佳活动场所;G.vex3.sight=惠馨园;G.vex3.description=石家庄经济学院惠馨园一、二楼是学生餐饮中心，三楼是教职工餐饮中心，四楼是综合办公之地，五楼是文艺文化活动中心;G.vex4.sight=实验楼;G.vex4.description=各专业试验的重要场地;G.vex5.sight=计算机实验室;G.vex5.description=计算机专业的实验实习场所;G.vex6.sight=地球科学博物馆;G.vex6.description=里面有著名的不寻常恐龙化石;G.vex7.sight=学术报告厅;G.vex7.description=学术交流中心;G.vex8.sight=图书馆;G.vex8.description=图书馆是莘莘学子学习的园地，里面有各科资料，每人可以任借五本书;G.vex9.sight=喷泉;G.vex9.description=学校的盛大节日时就可以看见;for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)G.arcsij.adj=Max;G.arcs01.adj=G.arcs10.adj=50;G.arcs09.adj=G.arcs90.adj=50;G.arcs12.adj=G.arcs21.adj=50;G.arcs23.adj=G.arcs32.adj=130;G.arcs34.adj=G.arcs43.adj=300;G.arcs05.adj=G.arcs50.adj=50;G.arcs25.adj=G.arcs52.adj=100;G.arcs06.adj=G.arcs60.adj=250;G.arcs67.adj=G.arcs76.adj=50;G.arcs49.adj=G.arcs94.adj=500;G.arcs56.adj=G.arcs65.adj=300;G.arcs58.adj=G.arcs85.adj=300;G.arcs78.adj=G.arcs87.adj=50;G.arcs79.adj=G.arcs97.adj=100;void daoyouzixunxitong70321:narrate70321()int i,k=0;printf(ntt*欢 迎 使 用 校 园 导 游 程 序*n);printf(ntt*石*家*庄*经*济*学*院*n);printf(ntt制作者： 信息工程学院 1 颜建学 !欢迎您使用!n);printf(ntt_n);printf(ttttt 景点名称ttn);printf(tt_n);for(i=0;iNUM;i+)printf(tt 【%2d】%-15stt,i,G.vexi.sight);if(i%2=(NUM-1)%2)printf(n);/奇数编号景点在右边，偶数编号景点在左边k=k+1;printf(tt_n);void daoyouzixunxitong70321:ShortestPath70321(int num)int v,w,i,t; int finalNUM;int min;for(v=0;vNUM;v+)finalv=0; Dv=G.arcsnumv.adj;for(w=0;wNUM;w+)Pvw=0;if(Dv20000) Pvnum=1;Pvv=1;Dnum=0; finalnum=1; for(i=0;iNUM;+i) min=Max; for(w=0;wNUM;+w)if(!finalw) if(Dwmin) v=w;min=Dw;finalv=1; for(w=0;wNUM;+w) if(!finalw&(min+G.arcsvw.adj)Dw)Dw=min+G.arcsvw.adj;for(t=0;tNUM;t+)Pwt=Pvt;Pww=1;void daoyouzixunxitong70321:output70321(int sight1, int sight2)int a,b,c,d,q=0;a=sight2; if(a!=sight1) printf(nttt从( %s )到( %s )的最短路径是:nn,G.vexsight1.sight,G.vexsight2.sight);printf(ttt%s,G.vexsight1.sight); d=sight1; for(c=0;cNUM;+c)gate:; Pasight1=0; for(b=0;bNUM;b+) if(G.arcsdb.adj%s,G.vexb.sight); q=q+1; Pab=0; d=b; if(q%10=0) printf(n); goto gate; printf(t(最短距离为 %dm.)nt,Da); char daoyouzixunxitong70321:Menu70321()char c;int flag;doflag=1;system(cls);narrate70321(); /调用 narrate()函数printf(n);printf(tttn);printf(ttt 【1】查询景点路径 n);printf(ttt 【2】查询景点信息 n);printf(ttt 【3】推荐参观路线 n);printf(ttt 【e】退出 n);printf(tttn);printf(tttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=3|c=e)flag=0;while(flag);return c;void daoyouzixunxitong70321:search70321()int num;int i;char c;char name20;char a4=100;dosystem(cls);c=SearchMenu70321(); /调用SearchMenu()函数switch (c)case 1: system(cls);narrate70321(); /调用 narrate()函数printf(ntttO(_)O提示：输入100退出此环节n);N: printf(ntt请输入您要查找的景点编号：); scanf(%d,&num); if(num!=100) for(i=0;iNUM;i+) if(num=G.vexi.number) printf(ntt您要查找景点信息如下:); printf(nnttt%-25sn,G.vexi.description); break; /if语句 /for语句 if(i=NUM) printf(nttt!没*有*找*到!n); /if语句 goto N; /if语句 break;case 2:system(cls);narrate70321(); /调用 narrate()函数printf(ntttO(_)O提示：输入100退出此环节n);S:printf(ntt请输入您要查找的景点名称：); scanf(%s,name); if(!strcmp(name,a)break; for(i=0;i10) return; L: NextValue70321(m);/调用NextValue()函数 if(xm=0) return; if(m=9&G.arcs0x10-1.adj!=20000)/景点个数减1 景点个数加1 display70321();/调用display()函数 else HaMiTonian70321(m+1);/调用HaMiTonian()函数 goto L; void daoyouzixunxitong70321:NextValue70321(int k)int j; l:xk=(xk+1)%1