C语言校园导游程序设计报告

课程设计：校园导游系统石家庄铁道大学校园导游系统设计报告班级：计0801-2姓名：盖龙飞学号：20082514完成日期：2010-9-13课程设计：校园导游系统1.需求分析：此次课程设计的主要内容是校园导航系统，所谓系统其实也不尽然，只不过是个小小的提示，为来访的客人提供各种信息查询服务。主要包括：①查看学校的全景图②各个景点的简介③学校主要景点的分布④查看某一景点到其它所有景点的最短路径⑤查询任意两个景点之间的最短路径。一些约定：⑴对于功能①的输入形式是没什么要求的，主要就是根据菜单的提示输入相应的数字选择相应的功能；对于功能②的输入形式的要求也比较简单，要查询某一景点的简介直接输入其对应的编号即可；对于功能③的输入形式的要求同功能①；对于功能④只需要输入想要查看的起始景点的编号即可；对于功能⑤只需要输入起始景点和目的景点的编号即可。此程序在输入形式上都没什么特殊的要求只是一些简单的数字就可以搞定一切。⑵功能①③就是输出由字符构成的一幅简易图，形式比较单一；景点的简介方面输出景点的简单信息就可以了；要查询最短路径的话输出的自然是从起始景点到目的地的最短路径中所途经的各个景点及距离。⑶本程序所能达到的功能就是前面所提到的①—⑤中的功能。2.概要设计：抽象数据类型的定义：课程设计：校园导游系统ADTGraph{数据对象V:V具有相同特性的数组元素的集合，称为顶点集。数据关系R：R={VR}VR={v,w|v,w∈V且P(v,w),v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义或信息}基本操作P：CreateGraph(&G,V,VR);初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DistroyGraph(&G)初始条件：图G存在操作结果：销毁图GLocateVex(G,u);初始条件：图G存在，u和G中顶点有相同的特征。操作结果：若存在顶点u,则返回该顶点在图中的位置；否则返回其他信息。GetVex(G,u);课程设计：校园导游系统初始条件：图G存在，u是图中的顶点。操作结果：返回u的值。InsertVex(&G,v);初始条件：图G存在，v和图中的顶点有相同的特性。操作结果：在图G中新增顶点v.InsertArc(&G,v,w);初始条件：图G存在,v和w是图中的顶点。操作结果：在图G中增添弧v,w,若是无向图，还增添弧w,v。｝ADTGraph主程序流程（各函数之间的调用关系）：Main();//主函数Initview();//景点信息的初始化InitLength();//各个景点之间距离的初始化log();//登录时的头部showmenu();//登录后的菜单browser();//全景图的浏览browse_view_info();//景点简介的查询browse_view_distribute();//主要景点的分布onetoall();//某一景点到其它所有景点的最短路径课程设计：校园导游系统onetoone();//查询任意两个景点之间的最短路径调用关系如下：(函数内部没什么调用关系)3.详细设计：⑴图的结构：typedefstructview//点的结构{intno;//景点编号charname[100];//景点名称charbriefinfo[1000];//景点简介}view;typedefstructedge//边的结构{intlength;//两个景点之间的距离chardirection[4];//方向}edge;MainInitLength()Showmenu()Initview()Browser()Browse_vew_info()Browse_vew_distribute()onetoall()onetuone()log()课程设计：校园导游系统⑵各个函数的伪代码如下Initview()、InitLength()、log()、showmenu()、broser()、browse_view_distribute()、browse_view_info()等都是一些初始化或者即时显示，此处不再写其伪代码，在附录中给出。Main(){path=(edge**)malloc(MAX*sizeof(edge));for(v=0;vMAX;v++)path[v]=(edge*)malloc(1000*sizeof(edge));TD=(view*)malloc(MAX*sizeof(view));D=(DistancMatrix)malloc(MAX*sizeof(DistancMatrix));P=(PathMatrix)malloc(MAX*sizeof(PathMatrix));for(v=0;vMAX;++v)P[v]=(int*)malloc(MAX*sizeof(int*));Initview(TD);InitLength(path);//初始化system(modecon:cols=140lines=130);log();while(1){showmenu();//菜单printf(请选择：\n);scanf(%d,&k);switch(k){case1:browser();system(cls);break;case2:browse_view_info(TD);system(cls);break;case3:browse_view_distribute();system(cls);break;课程设计：校园导游系统case4:onetoall(P,D,TD,path);system(cls);break;case5:onetoone(P,D,TD,path);system(cls);break;case0:exit(0);}}}Voidonetoone(PathMatrixP,DistancMatrixD,view*TD,edge**path)｛//迪杰斯特拉算法while(flag){printf(请输入一个起始景点编号)；scanf(v0);if(v00||v0MAX){printf(景点编号不存在!请重新输入景点编号:);scanf(v0);}if(v0=0&&v0MAX)flag=0;}flag=1;while(flag){printf(请输入一个目的地景点编号:);scanf(%d,&v1);if(v10||v1MAX){printf(景点编号不存在!请重新输入景点编号:);scanf(%d,&v1);}if(v1=0&&v1MAX)课程设计：校园导游系统flag=0;}for(v=0;vMAX;v++){final[v]=0;D[v]=path[v0][v].length;for(w=0;wMAX;w++)P[v][w]=0;if(D[v]INFINITY){P[v][v0]=1;P[v][v]=1;}}D[v0]=0;final[v0]=1;for(i=1;iMAX;i++){min=INFINITY;for(w=0;wMAX;w++)if(!final[w])if(D[w]min){v=w;min=D[w];}final[v]=1;for(w=0;wMAX;w++)if(!final[w]&&(min+path[v][w].lengthD[w])){D[w]=min+path[v][w].length;for(x=0;xMAX;x++)P[w][x]=P[v][x];P[w][w]=1;}}v=v1;w1=v0;课程设计：校园导游系统printf(%s,TD[v0].name);do{flag=0;min=INFINITY;for(w=0;wMAX;w++){if(P[v][w]&&w!=v0){flag=1;if(D[w]min){j=w;min=D[w];}}}if(flag){//输出部分printf(向%s走%dm,path[w1][j].direction,path[w1][j].length);printf(--%s,TD[j].name);w1=j;P[v][j]=0;}elsebreak;}while(1);printf(\n总路线长%dm\n\n,D[v]);printf(完毕，按任意键继续!\n);getch();｝onetoall()与onetoone()函数用的是相同的算法这里不再赘述。4调试分析：(1)设计过程中遇到的问题：调试过程中难免会遇见这样或者那样的问题，一个很低级的错误就是在字符串的赋值上居然还会出错，本来是不可以像int型数据那样直接用等于号赋值的，可是刚开始由于失误却犯了这样低级的错误课程设计：校园导游系统结果导致出现102个错误，当时确实有点慌了，等冷静下来一想才把问题想明白，字符串的赋值必须用strcpy函数。看来基本功还是相当的重要的。剩下的就是最主要的问题也可以说是99%的问题，都在迪杰斯特拉算法上了，迪杰斯特拉算法是我们重点学习的一个算法当时学习时就感觉很吃力，不过当时也确实弄明白了，只可惜都过去好长一段时间了所以有所遗忘，算法确实是按照书上所写的抄到了程序中。最短路径确实也存到了数组P[v0][v]中，可是在输出相应的景点名称时总不能输出正确，感觉是很不可思议的问题，后来才明白数组P中的存储是按照一定的顺序存储的但是并不一定是路径中所途经的景点的顺序，所以最后选择在求最短路径过程中将其输出。回顾讨论和分析：迪杰斯特拉算法其实放在这里多少有些不合适，因为不管在求任意两个景点之间的最短路径还是求某一景点到其它景点的最短路径时都要完全的执行一遍算法时间复杂度是很高的，当时在实现时也确实考虑到了这个问题只是后来感觉要是实现时间复杂度的降低不是很简单也就暂时放弃了，也就选择了将这个算法直接搬了过来，这里是一点败笔，尚需要改进。(2)算法的时空分析和改进设想：主要还是迪杰斯特拉算法的时空分析：在计算到剩下的MAX-1个顶点的最短距离时第一个for循环时时间复杂度是O（n），每进行一次第二个for循环的时间复杂度都是O（n），第三个for循环也就是存储途经顶点时用的循环而不是书中算法所用的只是个地址的赋课程设计：校园导游系统值，所以时间复杂度也是O（n），这样总的时间复杂度就是O(n3)。改进设想主要就是给用户一个浏览路线的推荐本来在程序设计初期是计划要实现这个功能的，但是由于时间和能力问题没有去实现，因为它涉及到汉密尔顿路的实现，目前感觉还比较复杂所以暂时放弃了，日后如果有机会一定将这个功能完善。（3）经验和体会：经验吧说实在的也谈不上什么就一点信息越全才能使你的程序功能越完善。至于体会嘛，细心加耐心再加细节就等于成功！5.用户使用说明：程序刚运行时显示主要景点及其编号；菜单。⑴输入1显示校园的全景图；⑵输入2查询各个景点的简介范围0-49；⑶输入3显示主要景点的分布图；⑷输入4查询某一景点到所有景点的最短路径；⑸输入5查询任意两个景点之间的最短路径；⑹输入0退出系统；6.测试结果：2：请输入您想要查看的景点的编号：2输出：第四教学楼，此教学楼不是很了解貌似是建筑艺术学院专有的教学楼,上课教室都是固定的。2：请输入您想要查看的景点的编号：18输出：工程训练中心，机械院的学生实习的场所，其他院工业认课程设计：校园导游系统知实习时也会在此。里面有个很出名的风功能研究中心。请按任意键继续！5请输入一个起始景点编号:52景点编号不存在!请重新输入景点编号:3请输入一个目的地景点编号:13输出：第三栋宿舍楼（含医院）向东走10m--第二栋宿舍楼向北走60m--大礼堂总路线长70m完毕，按任意键继续!5请输入一个起始景点编号:8请输入一个目的地景点编号:27输出：第十二栋宿舍楼向西走40m--春晖楼向北走20m--泽园向西走40m--大礼堂向北走10m--教学实验楼（建设中）总路线长110m完毕，按任意键继续!7.附录：#includestdio.h#includestdlib.h#includestri