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

1石家庄经济学院本科生课程设计报告书题目校园导游咨询系统姓名颜建学学号410109070321学院信息工程学院专业计算机方向指导教师XXXXXX完成日期：2012-07-52校园导游咨询系统1需求分析本程序的主要目的是为了提供本学校的景点的路径咨询和来访客人以及刚来报到的新生提供一个快捷方便的路径咨询，快速有效的提高了用户的熟悉度。。满足用户查询的需要：1、从石家庄经济学院的平面地图中选取出10个有代表性的景点。2、为来访的客人提供图中任意景点相关信息的查询。当用户输入正确时，为用户输出景点的相关信息；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。3、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。4、为来访客人推荐参观路线。2概要设计1、抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={(v,w)|v,w∈V,(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)3初始条件：图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返回两点之间一条最短路径，否则返回其他信息。}ADTGraph主程序voidmain(){初始化；do{接受命令（输入景点信息或输出最短路径）；处理命令；}while（“命令”！=“退出”）；｝2、调用的函数有如下：voidCreateUDN70321(intv,inta);/*造图函数*/voidnarrate70321();/*说明函数*/voidShortestPath70321(intnum);/*最短路径函数*/voidoutput70321(intsight1,intsight2);/*输出函数*/charMenu70321();/*主菜单*/voidsearch70321();/*查询景点信息*/charSearchMenu70321();/*查询子菜单*/voidHaMiTonian70321(int);/*哈密尔顿图的遍历*/voidNextValue70321(int);voiddisplay70321();/*显示遍历结果*/43、运行主界面：***************欢迎使用校园导游程序******************************石**家**庄**经**济**学**院********************制作者：信息工程学院410109070321颜建学！！！欢迎您的使用！！！————————————————————————————————景点名称————————————————————————————————（0）教学主楼（1）足球场（2）灯光篮球场（3）惠馨园（4）实验楼（5）计算机实验室（6）地球科学博物馆（7）学术报告厅（8）图书馆（9）喷泉————————————————————————————————┏━━━━━━━━━━━━━━━┓┃1、查询景点路径┃┃2、查询景点信息┃┃3、推荐参观路线┃┃e、退出┃┗━━━━━━━━━━━━━━━┛子界面如下：┏━━━━━━━━━━━━━━━┓┃1、按照景点编号查询┃┃2、按照景点名称查询┃┃e、返回┃┗━━━━━━━━━━━━━━━┛3、模块图表示如下：53详细设计从石家庄经济学院的平面地图中选取出10个有代表性的景点，将其抽象成无向带权网并用邻接矩阵来表示。以图中的顶点代表景点，存放景点名称、代号、简介等信息，权值代表两地之间的距离。1、图的存储结构如下：#defineMax20000#defineNUM9typedefstructArcCell{intadj;/*相邻接的景点之间的路程*/}ArcCell;/*定义边的类型*/typedefstructVertexType70321{intnumber;/*景点编号*/char*sight;/*景点名称*/char*description;/*景点描述*/}VertexType;/*定义顶点的类型*/typedefstruct{VertexTypevex[NUM];/*图中的顶点，即为景点*/ArcCellarcs[NUM][NUM];/*图中的边，即为景点间的距离*/intvexnum,arcnum;/*顶点数，边数*/}MGraph;/*定义图的类型2、该程序的算法如下：1)voidCreateUDN70321(MGraph&G)/*造图函数*/主程序模块处理功能模块无向图存储模块为用户输出景点信息为用户输出两景点最佳路径推荐参观路径6{//采用邻接矩阵表示法，构造无向网Gscanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其它信息for(i=0;iG.vexnum;++i)scanf(&G.vexs[i]);//构造顶点向量for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j)G.arcs[]i[j]={INFINITY,NULL}for(k=0;kG.arcnum;++k)//构造邻接矩阵{scanf(&v1,&v2,&w);//输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);//确定V1和V2在G中的位置G.arcs[i][j].adj=w;//弧v1,v2的权值If(IncInfo)Input(*G.arcs[i][j].info);//若弧含有相关信息，则输入G.arcs[j][i]=G.arcs[i][j];//置v1,v2的对称弧v2,v1}ReturnOK;}2)voidnarrate70321()/*说明函数*/{k=0;printf(\n\t\t***************欢迎使用校园导游程序*************\n);printf(\n\t\t*******************石**家**庄**经**济**学**院************************\n);printf(\n\t\t制作者：信息工程学院410109070321颜建学！！！欢迎您使用！！！\n);printf(\n\t\t__________________________________________________________________\n);printf(\t\t\t\t\t景点名称\t\t\n);printf(\t\t__________________________________________________________________\n);for(i=0;iNUM;i++){printf(\t\t(%2d)%-15s\t\t,i,G.vex[i].sight);if(i%2==((NUM-1)%2))printf(\n);//奇数编号景点在右边，偶数编号景点在左边k=k+1;}7printf(\t\t_________________________________________________________________\n);}3)voidShortestPath70321(intnum){//用迪杰斯特拉算法求G的v0顶点到其余顶点的最短路径P[v]及其带权长度D[v]//若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点//final[v]为TRUE当且仅当v属于S，即已经求得从v0到v的最短路径for(v=0;vG.vexnum;++v){Final[v]=FALSE;D[v]=G.arcs[v0][v];For(w=0;wG.vexnum;++w)P[v][w]=FALSE;If(D[v]INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;}}//forD[v0]=0;final[v0]=TRUE;//开始主循环，每次求得v0到某个顶点的最短路径，并加v到S集For(i=1;iG.vexnum;++i){Min=INFINITY;For(w=0;wG.vexnum;++w)If(!final[w])If(D[w]min){v=w;min=D[w];}Final[v]=TRUE;For(w=0;wG.vexnum;++w)If(!final[w]&&(min+G.arcs[v][w]D[w])){D[w]=min+G.arcs[v][w];P[w]=P[v];P[w][w]=TRUE;}//if}//for}//ShortestPath4)voidoutput70321(intsight1,intsight2)/*输出函数*/{if(sight2!=sight1)/*如果景点二不和景点一输入重合，则进行...*/8{printf(从G.vex[sight1].sight到G.vex[sight2].sight的最短路径是:);/*输出提示信息*/printf(D[a]);/*输出sight1到sight2的最短路径长度，存放在D[]数组中*/printf(G.vex[sight1].sight);/*输出景点一的名称*/d=sight1;/*将景点一的编号赋值给d*/for(c=0;cNUM;++c){P[a][sight1]=0;for(b=0;bNUM;b++){if(G.arcs[d][b].adj20000&&P[a][b])/*如果景点一和它的一个临界点之间存在路径且最短路径*/{printf(G.vex[b].sight);/*输出此节点的名称*/q=q+1;/*计数变量加一，满8控制输出时的换行*/P[a][b]=0;d=b;/*将b作为出发点进行下一次循环输出，如此反复*/if(q%8==0)returnOK;}}}}5)voidmain()/*主函数*/{CreateUDN70321(NUM,11);do{switch(Menu()){case'1':narrate70321();scanf(v0);scanf(v1);ShortestPath70321(v0);/*计算两个景点之间的最短路径*/Output70321(v0,v1);/*输出结果*/break;9case