数据结构课程设计校园导游系统Word文档下载推荐.docx

1、char name30;int num;char introduction100;/简介infotype;Prim算法：void prim（MGraph *G） FILE *fp; fp=fopen（D:sight.txt,at+）; if（fp=NULL） printf（fail to open!n else int v,u,i,w,k,j,flag=1,p101010,D1010; for（v=0;vvexnum;v+） for（w=0;warcsvw.adj; for（u=0;uu+） pvwu=0; if（DvwINFINITY） pvwv=1;pvww=1; if（Dvu+DuwDv

2、w） Dvw=Dvu+Duw; for（i=0;ii+） pvwi=pvui|puwi; while（flag） printf（请输入出发点和目的地的编号: scanf（%d%d,&k,&j）; if（kvexnum|jvexnum）景点编号不存在!请重新输入出发点和目的地的编号: if（k=0&kjvexsk.name）; if（pkju&k!=u&j!=u）-vexsu.name）;vexsj.name）; 总路线长%dmn,Dkj）; fclose（fp）;迪杰斯特拉算法：void ShortestPath_DIJ（MGraph * G）approach.txtFail to openn

3、 int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020;请输入一个起始景点编号: scanf（%dv0）; if（v0 printf（请重新输入景点编号: scanf（ if（v0v0arcsv0v.adj; for（w=0; pvw=0; if（Dv pvv0=1;pvv=1; Dv0=0;finalv0=1; for（i=1; min=INFINITY; if（!finalw） if（Dwarcsvw.adj for（x=0;xvexnum-1&v0! 总路线长%dmnn,Dv）; /endfor /endif /ShortestPa

4、th_DIJ end五测试数据及运行结果1正常测试数据和运行结果2异常测试数据及运行结果六调试情况，设计技巧及体会1改进方案对于我的设计，合理之处是对每一次查询都以文件的形式进行了存储，其次，校园的平面图比较好的展现了我们学校的风貌。不足之处是使用prim算法的时候，若终点输入不合法，程序会陷入，死循环。这是致命的错误，我的改进方法是若输入字符不合法，则跳出循环，再次输入，直到合法为止。利用迪杰斯特拉算法在计算到剩下的顶点的最短距离时第一个for循环时时间复杂度是O（n），每进行一次第二个for循环的时间复杂度都是O（n），第三个for循环也就是存储途经顶点时用的循环而不是书中算法所用的只是个

5、地址的赋值，所以时间复杂度也是O（n），这样总的时间复杂度就是O（n3）。改进设想主要就是给用户一个浏览路线的推荐本来在程序设计初期是计划要实现这个功能的，但是由于时间和能力问题没有去实现，因为它涉及到汉密尔顿路的实现，目前感觉还比较复杂所以暂时放弃了，日后如果有机会一定将这个功能完善。2体会调试过程中难免会遇见这样或者那样的问题，一个很低级的错误就是在字符串的赋值上居然还会出错，本来是不可以像int型数据那样直接用等于号赋值的，可是刚开始由于失误却犯了这样低级的错误结果导致出现102个错误，当时确实有点慌了，等冷静下来一想才把问题想明白，字符串的赋值必须用strcpy函数。看来基本功还是相当

6、的重要的。此外，迪杰斯特拉算法其实放在这里多少有些不合适，因为不管在求任意两个景点之间的最短路径还是求某一景点到其它景点的最短路径时都要完全的执行一遍算法时间复杂度是很高的，当时在实现时也确实考虑到了这个问题只是后来感觉要是实现时间复杂度的降低不是很简单也就暂时放弃了，也就选择了将这个算法直接搬了过来，这里是一点败笔，尚需要改进。七参考文献数据结构 严蔚敏 吴为民C语言程序设计（第三版） 谭浩强 八附录：源代码（电子版）#define INFINITY 10000 /*无穷大*/#define MAX_VERTEX_NUM 40#define MAX 40#includestdio.hconi

7、o.hstring.htypedef struct ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structinfotype 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 P

8、rim（MGraph *G）;void Search（MGraph *G）;int LocateVex（MGraph *G,char* v）;MGraph * CreatUDN（MGraph *G）;void print（MGraph *G）;void map（）;/*/void main（void） system（mode con: cols=100 lines=30 cmd（）;void cmd（void） int i; b=InitGraph（）; Menu（）;i）; while（i!=6） switch（i） case 1:Browser（&b）;Menu（）;break; case

9、 2:map（）; case 3:ShortestPath_DIJ（& case 4:Floyd（& case 5:Search（& case 6:exit（1）; default:MGraph InitGraph（void） MGraph G; int i,j; G.vexnum=10; G.arcnum=14;G.vexnum; G.vexsi.num=i; strcpy（G.vexs0.name,旭日苑 strcpy（G.vexs0.introduction,难吃,洗过的筷子上面都是菜叶子 strcpy（G.vexs1.name,校医院 strcpy（G.vexs1.introducti

10、on,校医院，名副其实的校（shou）医（yi）院（yuan） strcpy（G.vexs2.name,大学生活动中心 strcpy（G.vexs2.introduction,又名大活,举办一些没什么卵用的晚会 strcpy（G.vexs3.name,美食广场 strcpy（G.vexs3.introduction,吃货的天堂,完爆旭日苑 strcpy（G.vexs4.name,图书馆 strcpy（G.vexs4.introduction,Warning学霸出没 strcpy（G.vexs5.name,足球场 strcpy（G.vexs5.introduction,国足的未来.2333333

11、3 strcpy（G.vexs6.name,水煮鸽子 strcpy（G.vexs6.introduction,然而他并不能吃 strcpy（G.vexs7.name,东区教学楼 strcpy（G.vexs7.introduction,又名尼伯龙根,进去就不要想出来 strcpy（G.vexs8.name,狗男女湖 strcpy（G.vexs8.introduction,湖边时常回荡着单身狗的哀嚎 strcpy（G.vexs9.name,澡堂 strcpy（G.vexs9.introduction,洗个澡,压压惊 for（j=0;j+） G.arcsij.adj=INFINITY; G.arcs

12、01.adj=100; G.arcs02.adj=200; G.arcs06.adj=400; G.arcs17.adj=300; G.arcs23.adj=120; G.arcs36.adj=220; G.arcs34.adj=100; G.arcs45.adj=300; G.arcs49.adj=250; G.arcs59.adj=350; G.arcs67.adj=60; G.arcs69.adj=200; G.arcs78.adj=50; G.arcs89.adj=20; G.arcsji.adj=G.arcsij.adj; return G;/InitGraph endvoid Me

13、nu（） n 西安邮（mei）电（dian）大学n n 1.校园景点介绍 n 2.校园平面图 n 3.查看所有游览路线（jiandan） n 4.选择出发点和目的地（zuiduan） n 5.查看景点信息 n 6.退出系统 n nOption-:void Browser（MGraph *G） int v;n编号景点名称 简介 n%-4d%-16s%-56snvexsv.num,G-vexsv.name,G-vexsv.introduction）;n/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点请稍候.n文件已经成功地保存至D:/approach.txt!void Searc

14、h（MGraph *G） int k,flag=1;请输入要查询的景点编号:k）;nvexsk.num,G-vexsk.name,G-vexsk.introduction）;n/Search endint LocateVex（MGraph *G,char* v） int c=-1,i; if（strcmp（v,G-vexsi.name）=0） c=i; return c;void print（MGraph *G）int v,w,t=0;for（v=0; if（G-arcsvw.adj=INFINITY） else printf（%-7darcsvw.adj）; if（t%G-vexnum=0）void Prim（MGraph *G）G