数据结构课程设计作业(校园导游).docx

数据结构课程设计CourseDesignofDataStructure计算机科学与技术082姓名：*学号：08422137指导老师：*2010年7月9日1 .需求分析说明2 .概要设计说明3 .详细设计说明4 .调试分析5 .课程设计总结6 .参考书目7 .致谢需求分析说明随着高校校园的逐渐扩展，来访校园的人士逐渐增多，随着校园透明度的提高，各界人士对学术气氛的追求，越来越多的人走进了大学校园，走进了象牙塔，这片静土也以它崭新的面貌，迎接着所有的到来者，以前封闭以及半封闭的校园状况随之改变，派生的是它积极的迎接挑战的状态。高等院校，历来以其悠久的历史、深厚的文化底蕴、优美的自然和人文景观吸引着人们的目光。高校校园旅游在掀起“羞答答的头盖“后，正悄然走向市场，当今高校在确立了旅游的市场可行性之后，随之而来的导游系统是势在必行，高校的旅游可以让人陶冶情操，也可以让人对学术产生浓厚的兴趣。那么如何更好的更科学的更科学的组织好高校导游，如何更方便更便捷的把高校的校园展示给世人，就成为了一个需要解决的问题。利用计算机建立一个自动的导游系统，可以很好的解决这个问题。当客人来访时，系统可以根据客人指定的景点给予相关的信息，游客可以方便的了解到每个景点的详细信息，同时可以通过系统找到起始点和终点的多条路径，通过系统的分析后,能得出一条最短路径。各个景点的全景图、局部图可以在景点浏览中找到，付予语音、图片以及相关文字说明，让游客轻轻松松掌握景点信息。概要设计说明用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求实现以下功能：(1)查询各景点的相关信息。(2)查询图中任意两个景点间的最短路径。(3)查询图中任意两个景点间的所有路径。用图的结点代表景点，用图的边代表景点意见的路径，首先设计一个图类，结点值代表景点的信息，边的权值代表景点之间的距离，结点值及边的权值用顺序表存储，所以需要设计一个顺序表类，本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个编号，用结构体类型来实现。计算路径长度和最短路线是可以用DijkStra(迪杰斯特拉)算法实现,在主函数中用switch选择语句执行浏览景点信息或查询最短路径tyedefstructArCell(intadj;路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstruct图中顶点表示主要景点，存放景点的编号、名称、简介等信息，(charname30;intnum;charintroduction200;/简介infotype;typedefstruct(infotypevexsMAX_VERTEX_NUM;景点AdjMatrixarcs;路径数组intVeXnUm,arcnum;/景点数，路径长度记录MGraph;voidCmd(VOid);在主函数中用来调用其他应用子函数的函数声明MGraphInitGraPh(VOid);用来构造学校地图的子函数返回MGraph类型voidMenU(Void);/菜单函数；voidBrowser(MGrah*G);调用MGraph类型的地址，进行voidShortestPath_DIJ(MGraph*G);/迪杰斯特拉算法求最短路径的子函数voidFloyd(MGraph*G);佛洛伊德算法voidSearch(MGraph*G);寻找要查询的景点，并输出该景点的信息intLocateVex(MGraph*Gchar*v);定点位置MGraph*CreatUDN(MGraph*G);/初始化图形，接受用户输入voidprint(MGraph*G);打印输出子函数详细设计说明#defineINHNITY10000/*无穷大*/#defineMAX_VERTEX_NUM40#defineMAX40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>typedefstructArCell(intadj;路径长度ArCeII,AdjMatrix(MAX_VERTEX_NUM(MAX_VERTEX_NUM;typedefstruct图中顶点表示主要景点，存放景点的编号、名称、简介等信息，(charname30;intnum;charinlroduclion200;简介infbtype;typedefstruct(infolypevexsMAX_VERTEX_NUM;景点AdjMatrixarcs;路径数组intVeXnUm,arcnum;景点数，路径长度记录MGraph;MGraphb;全局变量VOidCmd(Void);在主函数中用来调用其他应用子函数的函数声明MGraphInilGraPh(VOid);用来构造学校地图的子函数返回MGraph类型voidMenU(Void);菜单函数：voidBrowser(MGraph*G);调用MGraph类型的地址，进行voidShOrteSlPalh_DIJ(MGraPh*G);迪杰斯特拉算法求最短路径的子函数voidFloyd(MGraPh*G);佛洛伊德算法voidSearch(MGraph*G)H寻找要查询的景点，并输出该景点的信息intLocateVex(MGraph*G,char*v);定点位置MGraph*CreatUDN(MGraph*G);初始化图形，接受用户输入voidprint(MGraph*G);打印输出子函数/*/voidmain(void)(SyStem("colorS);设置调试窗口背景和字体颜色SySIem("modecon:cols=140IineS=I30");设置调试窗口的大小Cmd();/用该函数来调用其他需要用到的函数)/*/voidCmd(VOid)用来调用其他需要用到的函数的子函数(inti;b=InilGraph();“构造校园地图MenU();调用菜单函数scanf("%d",i);while(i!=5)(switch(i)(casel:system("cls");Browser(&b);Menu();break;case2:system("cls");ShortestPath_DIJ(&b);Menu();break;case3:system("cls");Floyd(&b);Menu();break;case4:system("cls");Search(&b);Menu();break;case5:exit(l);break;default:break;scanf("%d",i);*MGraphInilGraPh(Void)构造校园地图(MGraphG;intij;Gvexnum=10;景点数量GarCnUm=I4;路径数量fbr(i=O;i<Gvexnum;i+)Gvexsi.num=i;对景点进行对应编号/*对对应的景点编号进行命名，输入简介*/StrCPy(GVeXS.name,"行政楼")；SIrCPy（GVeXS.introduction,"学校的行政机构"）；StrCPy（Gvexs1.name,”图书馆”）；StrcPy（GVeXSl.introduction,"藏书200万册,设施良好,环境幽雅"）；StrCPy（Gvexs2.name,"新理科楼"）；StrCPy（GVeXS.Elroduclion,"学校最气派的教学楼，里面的设施比拟好"）；SlrCPy（GVeXS3.name,"川味府"）；StrcPy（GVeXS3.introduction,"里面有南方各种美食,就餐环境幽雅"）；StrCPy（GVeXS4.name,"洗浴中心"）；StrcPy（GVeXS4.introduction,"学校唯一的澡堂，在川味府旁边"）；StrCPy（GVeXS5.name,”中心体育场”）；StrCPy（GVeXS5.introduclionJ化塑胶跑道,人造草坪,适宜锻炼身体的场所"）；StrCPy（GVeXS6.name,"会堂"）；StrcPy（GVeXS6.in（roduciionJ学校有大型的晚会都在这里举行"）;StrCPy（GVeXS.name,”钟楼广场”）；StrcPy（Gvexs7.introduction,"是连大学子展现才华的地方,旁有邮局"）;StrCPy（GVeXS8.name,"新文科楼"）；StrcPy（GVeXS8introduction,“里面包含几个学院StrCPy（GVeXS9.name,"清缘超市"）；StrCPy（GVeXS9.iniroduclion,"学校最大的超市，里面有很多学生使用的商品"）；对有路的各景点之间的路径长度进行设置,没路的设置为无穷大for（i=0;i<Gvexnum;i+）fbr（j=0j<Gvexnumj+）Garcsij.adj=INFINITY;Garcs0l.adj=100;Garcs02.adj=150;Garcs06.adj=2;Garcsl7.adj=150;Garcs2J3.adj=50;Garcs36.adj=50;Garcs34.adj=20;Garcs45.adj=2;Garcs4J9.adj=150;Garcs59.adj=350;Garcs6J7.adj=60;Garcs69.adj=80;Garcs78.adj=50;Garcs8J9.adj=20;无向图的路径是相互的for（i=0i<Gvexnum;i+）fbr（j=0j<Gvexnumj+）Garcsji.adj=Garcsij.adj;returnG;InitGraphend*菜单函数，打印出导游工程菜单voidMenu（）printf("nprintf("大连大学校园导游图n"）；II'l三hprintf("IL浏览校园全景In");printf("I2.查看所有游览路线I11");printf("I3.选择出发点和目的地I心;printf("I4.查看景点信息In");printf("I5.退出系统I吟;printf("printf("Option-I点*点*输出所有景点信息voidBrowser(MGraph*G)(intv;printf("I111n")：printf("I编号I景点名称I简介In");for(v=0;v<G->vexnumjv÷+)printf("I%-4d|%-16s%-58sn",G->vexsv.num,G->vexsv.name,G->vexsv.introduction);printf("1111n");/迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v为起点voidShOrteStPalh_DIJ(MGraPh*G)(intv,w,i,min,t=O,x,flag=1,v0；intfinal(20,D20,p(2020:while(flag)(Prinlf("请输入一个起始景点编号:“)；scanf("%d",vO);if(vO<Ov()Xj->vexnum)(Prinlf("景点编号不存在!请重新输入景点编号:")；scanf("%d"vO);if(vO>=O&&vO<G->vexnum)flag=O;fbr(v=0;v<G->vexnum;v+)finalv=0;Dv=G->arcsvOv.adj;fbr(w=O;w<G->vexnum;w+)pvw=O;if(Dv<INFINITY)(p(vvO=l;pvv=l:DvO=O;final(vO=l;for(i=l;i<G->vexnum;i+)(min=INFINITY;fbr(w=O;w<G->vexnum;w+)if(!finalw)if(Dw<min)v=w;min=Dw;final(v=l;fbr(w=O;w<G->vexnum;w+)if(!finalw&&(min+G->arcsvw.adj<Dw)(Dw=min+G->arcsvw.adj;for(x=0;x<G->vexnum;x+)pwx=pvx;p(wjw=l;fbr(v=O;v<G->vexnum;v+)(if(v!=v)printf("%s",G->vexsvO.name);fbr(w=O;w<G->vexnum;w+)(if(pvw&4&w!=v0)printf("->%s",G->vexsw.name);t+；if(t>G->vexnum-l&&vO!=v)printf("总路线长dmnn”,Dv);ShOrteStPalh_DIJend*voidFloyd(MGraph*G)(intv,u,i,w,kj,flag=l,p101010,DI0J10;fbr(v=O;v<G->vexnum;v+)for(w=O;w<G->vexnum;w+)Dvw=G->arcsvw.adj;fbr(u=O;u<G->vexnum;u+)pvwu=O;if(Dvw<INFINITY)(pvwv=1；pvww=1;for(u=O;u<G->vexnum;u+)ft)r(v=O;v<G->vexnum;v+)fbr(w=O;w<G->vexnum;w+)if(Dvu+Duw<Dvw)(Dvw=Dvu+Duw;fbr(i=O;i<G->vexnum;i+)pvwi=pvuipuwi;while(flag)(PrinlfC请输入出发点和目的地的编号:")；scanf("%d%d",k,j);if(k<()kXj->vexnumlj<OHj>G->vexnum)(PrinIf("景点编号不存在!请重新输入出发点和目的地的编号:")；scanf("%d%d",&k,&j)；if(k>=O&&k<G->vexnum&&j>=O&&j<G->vexnum)flag=O;printf("%s",G->vexsk.name);fbr(u=O;u<G->vexnum;u+)if(pk|ju&&k!=u&&j!=u)printf("->%s",G->vexsuJ.name);printf("->%s",G->vexsj.name);Prinlfr总路线长dmn",Dk皿)；/Floydend*寻找要查询的景点，并输出该景点的信息voidSearch(MGraph*G)(intk,flag=1;while(flag)Printf（"请输入要查询的景点编号:"）;scanf("%d",&k);if(k<()kXj->vexnum)(Prinlf("景点编号不存在!请重新输入景点编号:")；scanf("%d",&k);if(k>=O&&k<G->vexnum)flag=O;rintf('I111n");printf("I编号I景点名称I简介In");printf("I%-4<l|%-16s%-56sn",G->vexsk.num,G->vexsk.name,G->vexsk.introduction);printf("1111n");/Searchend*intLocateVex(MGraph*Qchar*v)(intc="l,i;fbr(i=O;i<G->vexnum;i+)ifstrcmp(v,G->vexsi.name)=O)c=i;break;returnc;)*MGraph*CreatUDN(MGraph*G)初始化图形，接受用户输入(intij,k,w;charvl20,v220;Printf("请输入图的顶点数,弧数scanf("%d%d",&G->vexnum,&G->arcnum);PrinIfC请输入景点的编号:、名称、简介M");fbr(i=O;i<G->vexnum;i+)(Primf("景点编号scanf("%d",<feG->vexs->num);PrinIf("景点名称:")；scanf("%s",G->vexsi.name);Printf("景点简介scanf("%s",G->vexs->introduction);for(i=O;i<G->vexnum;i+)for(j=Oj<G->vexnumj+)G->arcs(ij.adj=INFINITY;Primf("请输入路径长度:f);for(k=0;k<G->arcnum;k+)Prinlf("第d条边:n",k+1);PrimfC景点对(x,y)巧;scanf("%s',vl);scanf("%s'',v2);PrintfC路径长度:");scanf("%d",<few);i=LocateVex(G,v1);j=LocateVex(G,v2);if(i>=0&&j>=0)(G->arcsij.adj=w;G->arcsUi=G->arcs(ij;returnG;)*voidprint(MGraph*G)(intv,w,t=0;for(v=O;v<G->vexnum;v+)fbr(w=O;w<G->vexnum;w+)(if(G->arcsvw.adj=INFINITY)printf("");elseprintf("%-7d",G->arcsvw.adj);t+；if(t%G->vexnum=O)printf("n");)*调试分析yUsersnpDesktopDebug最近.exe'大连大学校园导游图ption>：大连大学校园导游图斡和息 全游点信 园有誉统 筹出荽 薯醇出 浏查选查退_ 12 3 4 5 -tion：2 "CzUsersnpDesktopUebugSb.exe*请领人一个起始景点编号：4洗着中心一 > 行政楼一渐理科楼一训味府总路线长220m洗浴中心一图书馆一 >川味府一 > 会堂一 > 钟楼广场总路线长28加酰浴中心一新理科楼一11味府总路线长70m洗浴巾心一>川味府总路线长28e洗浴中心一） 中心体育场总路线长2。时洗浴中心一11味府一> 会堂总路线长70m洗浴中心一 > 川味府一> 会堂一潮楼广场总路线长13M洗浴中心一 > 新文科楼一青绿超市总路线长17队酰浴中心一 > 清绿超市总路线长150n大连大学校园导游图旦法利息 露点信统 落出第 出 浏查选杳退跖目地 线的 , *CUsersnpDesktopDebugifi.e×eiji的第号：2 8会翼一>清缘超市一>新文科楼总路线长200m大连大学校园导游图地线的路目豆蓝和息全游点信园疏禽出景系骞年出嚼.嗫12 3 4 5ption：4V：v>cf>npcwpWDgg3Uw睛输入要查询的景点编号：7萝节赢崎融大学子展现才华的地方，旁有邮局大连大学校园导游图地 路目 Bl蓝利息 翕占猾M适鎏.1 12 3 4 5Option>：5争号髓慈I拿大学子展现才华的地方，旁有邮局大连大学校园导游图路目和息 霜点信 园有售统 臀出景系 襄善出 浏查选查退 12 3 4 5Option->：5Pressanykeytocontinue课程设计总结通过本次课程设计实验，使我更能熟练地掌握数据结构以及C语言等知识的综合应用。当然在课程设计期间，也遇到了大大小小的一些问题，也看到了自己的缺乏之处，使我认识到在以后的学习中要善于发现自己的缺乏，找到自己的薄弱环节，以便能够更好的去稳固所学。本次设计中要求求最短路径，就必须要理解求最短路径的算法：Dijkstra算法或者是Floyd算法。在拿到题目值，通过查找相关的资料才回忆起这两种算法的具体实现，比拟着两种算法的复杂度，尽量选用复杂度小的算法，当然任何程序都不可能完美，往往会牺牲程序的空间来换取时间，或者牺牲时间类换取足够大的空间，这就需要根据程序的具体要求来设计算法。在选用存储方法时，要尽量选用时间复杂度较小的算法,这样能够节省程序执行时间，提高查询效率。课程设计中所使用的计算机语言其使用范围比拟广阔，在很多编程中都可以用到，所以无论以后我们从事计算机编程，软件设计还是硬件，网络等领域，都应该学会，学精一门编程语言，这对我们以后学习和工作有很大的帮助。测试结果参考书目口数据结构C语言版，严蔚敏，吴伟民编著，一北京：清华大学出版社数据结构（习题与解析），李春葆编著，清华大学出版社致谢首先感谢我的指导老师高秀娥胡老师，他在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术。感谢我的数据结构老师汤老师和C语言老师在以往的根底课学习中为我打下良好的根底，这是我这次课程设计能够顺利完成的前提。我的同学在设计完成后对程序的测试，没有他们，也许就难以发现一些潜在的错误，在此一并表示感谢。