公园导游图课设1

1、海前N科冬陇课程设计报告课程名称数据结构课题名称公园导游图专业.计算机科学与技术班级计算机0702学号200703010235姓名蔡鄂湘指导教师陈淑红李杰君李珍辉2009年10月26日湖南工程学院课程设计任务书课程名称数据结构课题公园导游图专业班级计算机0702学生姓名蔡鄂湘学号200703010235指导老师陈淑红李杰君李珍辉审批任务书下达日期2009年10月8日任务完成日期2009年11月8日1设计内容与设计要求1.1 设计内容1.1.9公园导游图给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，

2、最后回到出口(出口就在入口旁边)。要求用图示展示最佳路径。1.2 选题方案：所选题目根据学号确定，学号模9加1,即(学号9+1)。如你的学号为12,则所选题目号为：12%9+1=(题目4)。注意，所有的课题都要求用图形方式演示步骤和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法，但要预先告知老师，经过审批，方可确定课题。1.3 设计要求：1.3.1 课程设计报告规范(1)需求分析a.程序的功能。b.输入输出的要求。(2)概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些

3、数据是什么样的结构，它们之间有什么关系等。(3)详细设计a.采用C语言定义相关的数据类型。b.写出各模块的类C码算法。c.画出各函数的调用关系图、主要函数的流程图。(4)调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。(5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。(6)书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体，二级标题用四号宋体加粗，正文用小四号宋体；行距为22。(7)附录a.源程序清单(带

4、注释)1.3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：(1)平时出勤(占10%)(2)系统需求分析、功能设计、数据结构设计及程序总体结构合理与否(占10%)(3)程序能否完整、准确地运行，个人能否独立、熟练地调试程序(占40%)(4)设计报告(占30%)注意：不得抄袭他人的报告(或给他人抄袭)，一旦发现，成绩为零分。(5)独立完成情况(占10%)。1.3.3 课程验收要求(1)运行所设计的系统。(2)回答有关问题。(3)提

5、交课程设计报告。(4)提交软盘(源程序、设计报告文档)。(5)依内容的创新程度，完善程序情况及对程序讲解情况打分。2进度安排1 .需求分析11.1 课程设计内容和要求11.2 输入输由的要求12 .概要设计22.1 主要程序功能模22.2 课题涉及的数据结构和数据库结构23 .详细设计43.1 C语言定义的相关数据类型43.2 各模块的类C码算法43.3 各函数的调用关系图、主要函数的流程图74 .调试分析以及设计体会114.1 测试数据114.2 程序调试中遇到的问题以及解决问题的方法154.3 经验教训、心得体会155 .使用说明166 .附录171需求分析1.1 课程设计内容和要求。程序

6、要能够显示出地图，要能够查找出地图中任意两点间的最短距离，以及不重复遍历全图的最短路径，并且在查找及遍历的每个过程都在图中显示出暂时的结果，以便演示整过过程。1.2 输入输出的要求。程序执行要求有描述地图的两个文件，并放到相应位置。其中一个文件存放有描述地图各个景点之间距离的矩阵，另一个文件存有地图中各景点在显示器上显示的位置。两个地图文件不允许有错误。执行相应功能前要求先选择。查找任意两点间的最短距离，要求输入要查找最短路径的两点。在运行各个小过程后要求输出暂时结2概要设计2.1 程序模块程序共有主模块、查找两点最短路径并输出具体过程、寻找不重复遍历全图图路径并输出遍历过程、三个模块。主模块

7、包含、载入地图、显示地图、功能选择与调用三部分。查找两点最短路径并输出具体过程模块中的输出具体过程为显示地图模块模块结构如图：图2.12.2 课题涉及的数据结构和数据库结构程序主要用了图和栈两种数据结构，采用矩阵来保存图形结构的地图，用栈保存遍历时经过的结点用以遍历的回溯，以及存储最终路径。图的抽象数据类型：ADTGraph数据对象:D=ai|1<iqnn>0数据关系：R=<ai,a>|a,aCD,1<j<n,10网退个元素可以有零个或多个前驱，可以有零个或多个后继基本运算：LoadImg(*g)：从相应文件中载入图数据初始化图g。OutputImg(*g)

8、把图输出到屏幕。bestpath()不重复遍历图。Floyed()计算图中所有点的两两最短路径。栈的抽象数据类型：ADTList数据对象：D=ai|1<in>Q数据关系：R=<ai,a>|a,a+iCD,i=1,，n-1基本运算：push(*s,e)：进栈：将元素e查到栈s中作为栈顶元素。pop(*s,*e)：出栈：从栈s中退出栈顶元素，并将其值赋予e。copsta(*s1,*s)：把栈s中的内容复制到栈s1o3详细设计3.1 采用C语言定义相关的数据类型。图的定义：typedefstructintedgesMAXMAX;intn;/*n顶点数*/inte;/*e边数*

9、/MGraph;栈的定义：typedefstructintbodyMAX;inttop;Stack;3.2 写出各模块的类C码算法。，图结构体g及顶点位置3.2.1 读取地图：把保存在文件中的地图数据载入到程序中相应的数据结构数组vl2中voidLoadImg(intvl2,MGraph*g)(fp=fopen("g.g2","r");fscanf(fp,"%d",&(g->n);for(i=0;i<g->n;i+)fscanf(fp,"%d%d",&vli0,&vli1)

10、;fclose(fp);fp=fopen("g.g1","r");for(i=0,g->e=0;i<g->n;i+)for(j=0;j<g->n;j+)fscanf(fp,"%d",&(g->edgesij);fclose(fp);3.2.2 显示地图：把地图以图形方式输出到显示器。voidOutputImg(intvl2,MGraph*g)for(i=0,g->e=0;i<g->n;i+)for(j=0;j<g->n;j+)if(g->edgesij!=

11、INF&&i<j)g->e+;画两点间路径；for(i=0;i<g->n;i+)画景点；3.2.3 不重复遍历全图的最短路径：寻找从起点开始不重复走完所有景点的路径，如果该路径不存在，将提示。如果存在将会最终找出符合要求的最短路径。Step1：if(没遍历完)if(向前有一景点没访问过)往下走；6else(回溯到上一景点点(原景点之后景点变为没访问过)；if(遍历到起点且访问其以后景点必然与以前的试探路径相同)/说明路径不再存在；若以前找到过遍历路径则输出最佳结果结束；else到Stepl开始下一步搜索；)else若比以前有的结果更好，则输出结果并继续试

12、探更好的遍历方法；3.2.4 两点间最短路径：采用弗洛伊德算法，求出每点间的最短路径，并在计算过程中输出用户所求两点问的暂时计算出的最短路径。voidFloyed(MGraph*g,intAMAX,intpathMAX,intvl2)for(i=0;i<g->n;i+)/*置初值*/for(j=0;j<g->n;j+)Aij=g->edgesij;pathij=-1;)输入两景点；for(k=0;k<g->n;k+)for(i=0;i<g->n;i+)for(j=0;j<g->n;j+)if(Aik!=INF&&

13、Akj!=INF&&Aij>(Aik+Akj)Aij=Aik+Akj;pathij=k;)输出0到k号顶点被考虑作为中间节点时两景点的最短路径图；)3.3 各函数的调用关系图、主要函数的流程图3.3.1 函数调用关系图：图3,1函数调用关系图3.3.2 主函数流程图:开始图3.2主函数流程图3.3.3查找两点最短路径函数Floyed()流程图:10图3.3查找两点最短路径函数流程图3.3.4不重复遍历景点函数bestpath()11开始图3.4不重复遍历景点函数4调试分析以及设计体会124.1测试数据：程序中的测试数据主要为景点地图相关的数据，景点个数、景点间距离、显示景

14、点时在屏幕上的位置，由于数据量比较大，所以把数据保存到文件，在程序运行时从文件中输入数据。从文件1中输入景点个数和在景点屏幕上的显示位置数据，每对坐标按顺序对应相应编号的景点：10（景点个数为10）300100200150300150400150250200350200450200200250300250400250从文件2中输入以下的景点间距离数据到程序，32767表示两景点间没有路径，数据的行数和列数分别对应第一个顶点和第二个顶点的编号。相对于主对角线对称的两点表示的是同一条路径，所以必须相等。050203232767327673276732767327673276750032767327

15、671032767327674332767327672032767015327673276732767327673276732767323276715032767313276732767327673276710332767032327676932767327673276733320363276754163276732767327671327673603276732767243276743327673276763276732767018327673276732767327673276795432767180213276732767327673276732767162432767210在键盘输入数

16、据主要为功能选择类输入,卜面图中调试用的景点号为0、9。和查找两景点间距离数时输入的景点号码13运行后得到如下结果:图4.1:选择功能界面图4.2:遍历图运行中14图4.3:遍历图完成选才i2后系统提示输入两点:图4.4:选才i2后系统提示输入两点图15ollerskatinootanica1gardenspleasenumberourbernutihernumberniUfiberioooootuooooo01234eeeeehhhhhtttttddddd自足&e0rrrrreeeeetttttnnnnnii士eaeeeittita口aaHJnodesnod已与nodesnodesn

17、ode5pathpathpathpaththaooaoc门nnn七t七七txxxxxeQIeea图4.5:选才22输入0、9后运行截图nunbernumbernumbernuiMlbernumbernuMbeirnunbernumbernumbernumberInlsmJSls导5SW5wamaa白maaa日t0123456789U0000000000olO18DOODDDDOnunber«0theintermedi日上心th隹interHcliatetheintemediatetheiintermediate(theinterHeciiatethejnternedi3tethein

18、termediatheiniterirteciiatetheinteriniedtheintemediategnodesnode与nodesnodesnode&nodes,nodesnode&nodesnodes%5SS.Sii-lii,hlhlnlhnHJ日a-a日Mxxxxpppppeeeeefffff0000000000nnnnnhhhhhhhhhhttttttttttnnnnnwwaeeeeeppppIMlln图4.6:选才22输入09后运行完成截图161.2 程序调试中遇到的问题以及解决问题的方法。程序调试中遇到了各种各样的问题，大部分是输入错误以及局部的逻辑混乱，或

19、者某些地方考虑不周造成。输入错误主要有等于写成赋值、缺少分号、符号，写成了减号-以及字符忘加引号等。输入错误在编译时一般可以排除，编译时还没排除的错误以及逻辑错误一般要在调试运行时排除。排除错误主要是通过在程序中加入大量输出函数，输出运行状态，然后根据输出结果定位出错位置，找出出错原因并解决问题。但在中途还遇到过一些奇怪的问题，如函数执行完毕之后不能正常跳出。我实在是找不到错在哪里，后来我改变了函数的结构，及程序的组织方式，问题终于没有了。我自己觉得应该是对语言或编译环境的细节还了解得不够造成了这类问题不能解决。1.3 经验教训、心得体会。两周的课程设计中，碰到过许多问题。首先，上课时听的理论

20、知识，各种算法似乎很容易理解，但是在真正的运用过程中,并不能把理论知道很好的和实践结合起来。在平时做实验时，尤其是这次课程设计，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。其次，通过这次课程设计，对自己的逻辑思维能力是一个很大的锻炼，加强了我们的系统思考问题的能力，在编程方面，我们开始从整体的角度来考虑问题了，而不再像以前一样的，没有一个总体的概念。也就是因为这种习惯，使自己在课程设计过程中浪费了不少的时间。程序设计是一个毅力的考验过程。有时候往往只是一个小小的错误，却要费很多的时间来解决。在这个过程不能过于急躁，并且要很有耐心才行程序需要反

21、复调试，其过程很可能相当令人头疼，有时花很长时间设计出来还是需要重做，那时心中未免有点灰心，有时还特别想放弃，此时更加需要静下心，查找原因。在课程设计中，感谢老师的耐心指导，让我能能能够顺利写出程序并把程序更快的调试正确，我从中也学到了许多新的方法和知识。感谢在做课程设计帮助自己的一些同学，是他们给我的意见和建议，让我的程序能够更加完善。175 .使用说明把地图文件放到与程序文件相同的目录，然后运行程序，程序会提供地图的图形显示，以及两个供选择的功能，选择相应编号或即可完成对应功能，并在图上看到其完成过程。186 .附录#include"stdio.h"#include&q

22、uot;Conio.h"#include"graphics.h"#include"Dos.h"#defineclosegrclosegraph#defineMAX12#defineINF32767/*定义图结构*/typedefstructintedgesMAXMAX;intn,e;/*n顶点数e边数*/MGraph;/*定义栈结构*/typedefstructintbodyMAX;inttop;Stack;intpush(Stack*s,intn)if(s->top=MAX-1)return0;s->top+;s->body

23、s->top=n;return1;intpop(Stack*s,int*n)if(s->top=-1)return0;*n=s->bodys->top;s->top-;return1;voidcopsta(Stack*s1,Stack*s)inti;19s1->top=s->top;for(i=0;i<=s->top;i+)s1->bodyi=s->bodyi;)voidInitgr(void)/*BGI初始化*/(intgd=DETECT,gm=0;/*和gd=VGA,gm=VGAHI是同样效果*/registerbgidri

24、ver(EGAVGA_driver);initgraph(&gd,&gm,"");)/*从文件中读取图形到程序*/voidLoadImg(intvl2,MGraph*g)/*vl顶点在显示器中显示时的坐标值*/FILE*fp;inti,j;fp=fopen("g.g2","r");fscanf(fp,"%d",&(g->n);for(i=0;i<g->n;i+)fscanf(fp,"%d%d",&vli0,&vli1);fclose(fp

25、);fp=fopen("g.g1","r");for(i=0,g->e=0;i<g->n;i+)for(j=0;j<g->n;j+)fscanf(fp,"%d",&(g->edgesij);fclose(fp);)/*在屏幕显示上图形*/voidOutputImg(intvl2,MGraph*g)charjd1025="enter","flowergarden","Zoo","Rollerskating",&qu

26、ot;Teahouse","Barbecue","AmusementPark","verandah","buffet","Botanicalgardens",;intradius=10;inti,j;chars50='0'setlinestyle(0,0,2);for(i=0,g->e=0;i<g->n;i+)for(j=0;j<g->n;j+)if(g->edgesij!=INF&&i<j)g->e+;l

27、ine(vli0,vli1,vlj0,vlj1);sprintf(s,"%d",g->edgesij);setcolor(RED);20outtextxy(vli0+vlj0)/2,(vli1+vlj1)/2+5,s);setcolor(WHITE);)for(i=0;i<g->n;i+)setfillstyle(SOLID_FILL,GREEN),f川ellipse(vli0,vli1,radius,radius),sprintf(s,"%d",i),setcolor(RED),outtextxy(vli0-3,vli1-3,s),s

28、etcolor(WHITE),outtextxy(vli0+10,vli1-10,jdi);)/*遍历*/*/*显示整个路径*/voiddisbestpath(Stack*psta,intvl2)inti,k;chars5=""intradius=10;outtextxy(120,300,"bestpathisthat");pop(psta,&i);setlinestyle(0,0,3);while(pop(psta,&k)setcolor(YELLOW);line(vlk0,vlk1,vli0,vli1);setcolor(RED);s

29、etlinestyle(0,0,2);setfillstyle(SOLID_FILL,GREEN),f川ellipse(vlk0,vlk1,radius,radius),setfillstyle(SOLID_FILL,GREEN),f川ellipse(vli0,vli1,radius,radius),setlinestyle(0,0,3);sprintf(s,"%d",k),outtextxy(vlk0-3,vlk1-3,s),sprintf(s,"%d",i),outtextxy(vli0-3,vli1-3,s);i=k;setcolor(WHITE)

30、;setlinestyle(0,0,2);21intbestpath(MGraph*g,intk,intvl2)/*k起点编号*/(inti,n,length2=0,INF,k1;/*n为已访问顶点数*/intverstFlagMAX=0;/*该顶点下一条可访问边对应的另一顶点号*/intverFlagMAX=0;/*顶点数被访问标志*/Stacksta3;/*保存路径的栈sta0随时更新、sta1保存前一条最短路径、sta2直接用于显示(显示是栈会清空)*/intcount;intradius=10;intstarMAX=0;/*star1指示起点与第i个顶点间的路径是否可以作为起点路径初始

31、为(可以作为起点路径)当试探过一次或作过遍历路径最后一段时将为(不可再作为起点路径)*/intns=0;/*还可以作为起点路径的边数*/chars5=""for(i=0;i<g->n;i+)if(g->edgeski!=INF&&i!=k)ns+;sta0.top=-1;sta1.top=-1;verFlagk=1;k1=k;push(&sta0,k1);n=1;bestpathloop1:for(i=verstFlagk1;i<(g->n);i+)verstFlagk1+;if(g->edgesk1i!=INF&

32、amp;&i!=k1&&verFlagi=0&&verstFlagk1<=g->n)if(k1=k)ns-;if(stari=1)continue;verFlagi=1;length0+=g->edgesk1i;push(&sta0,i);setlinestyle(0,0,3);setcolor(YELLOW);line(vlk10,vlk11,vli0,vli1);setcolor(WHITE);setlinestyle(0,0,2);setfillstyle(SOLID_FILL,GREEN),22f川ellipse(vlk

33、10,vlk11,radius,radius),setfillstyle(SOLID_FILL,GREEN),f川ellipse(vli0,vli1,radius,radius),setcolor(RED),sprintf(s,"%d",k1),outtextxy(vlk10-3,vlk11-3,s),sprintf(s,"%d",i),outtextxy(vli0-3,vli1-3,s),setcolor(WHITE);for(count=0;count<3;count+)delay(32767);+n;if(n=g->n&&

34、;g->edgesik!=INF&&verstFlagk<=i)ns-;stari=1;if(length0<length1)copsta(&sta1,&sta0);copsta(&sta2,&sta0);push(&sta2,k);disbestpath(&sta2,vl);outtextxy(300,300,"now");for(count=0;count<20;count+)delay(32767);length1=length0;verstFlagi=0;if(ns=0)outt

35、extxy(350,300,"finally");push(&sta1,k);disbestpath(&sta1,vl);return;setlinestyle(0,0,3),setcolor(BLACK),line(vlk0,vlk1,vli0,vli1),setcolor(WHITE),setlinestyle(0,0,2),line(vlk0,vlk1,vli0,vli1);setfillstyle(SOLID_FILL,GREEN),fillellipse(vlk0,vlk1,radius,radius),setfillstyle(SOLID_FIL

36、L,GREEN),f川ellipse(vli0,vli1,radius,radius),setcolor(RED),sprintf(s,"%d",k),outtextxy(vlk0-3,vlk1-3,s),sprintf(s,"%d",i),outtextxy(vli0-3,vli1-3,s),23setcolor(WHITE);for(count=0;count<20;count+)delay(32767);break;k1=i;i=verstFlagi-1;if(pop(&sta0,&i)=0|pop(&sta0,&am

37、p;k1)=0)if(sta1.top=-1)outtextxy(100,300,"pathnotexit");return;push(&sta1,k);outtextxy(250,300,"finally");disbestpath(&sta1,vl);return;setlinestyle(0,0,3),setcolor(BLACK),line(vlk10,vlk11,vli0,vli1),setcolor(WHITE),setlinestyle(0,0,2);line(vlk10,vlk11,vli0,v皿1);sefillstyl

38、e(SOLID_FILL,GREEN),f川ellipse(vlk10,vlk11,radius,radius),setfillstyle(SOLID_FILL,GREEN),f川ellipse(vli0,vli1,radius,radius),setcolor(RED),sprintf(s,"%d",k1),outtextxy(vlk10-3,vlk11-3,s),sprintf(s,"%d",i),outtextxy(vli0-3,vli1-3,s),setcolor(WHITE);for(count=0;count<4;count+)dela

39、y(32767);length0-=g->edgesk1i;verFlagi=0;verstFlagi=0;push(&sta0,k1);n-;i=verstFlagk1;gotobestpathloop1;I*两点最短路径*/voidPpath(intpathMAX,intvl2,inti,intj,Stack*psta)intk;k=pathij;24if(k=-1)return;Ppath(path,vl,i,k,psta);/*printf("%d",k);*/push(psta,k);Ppath(path,vl,k,j,psta);)voidFDis

40、Path(intpathMAX,intAMAX,intvl2,inti,intj,intk)短路径*/(intpre;Stacksta;char*a=""sta.top=-1;if(Aij=INF)outtextxy(400,310+8*k,"pathnoexit!");return;sprintf(a,"lenthofpathis%d",Aij);outtextxy(400,310+8*k,a);push(&sta,i);Ppath(path,vl,i,j,&sta);push(&sta,j);if(pop(

41、&sta,&i)=0)return;while(pop(&sta,&j)setcolor(YELLOW),line(vli0,vli1,vlj0,vlj1),setcolor(WHITE);setcolor(RED),sprintf(a,"%d",j),outtextxy(vlj0-3,vlj1-3,a),sprintf(a,"%d",i),outtextxy(vli0-3,vli1-3,a),setcolor(WHITE);i=j;/*使用弗洛伊德算法*/voidFloyed(MGraph*g,intAMAX,intpathMAX,intvl2)inti,j,k;chari12=0,j12=0;char*a="intcount;/*显示两点间最;25for(i=0;i<g->n;i+)/*置初值*/for(j=0;j<g->n;j+)(Aij=g->edgesij;pathij=-1;)outtextxy(80,300,"pleaseinputtwonumber:");while(1)*i1=getch();if(*i1-'0'<g->n&&*i1-'0'>=0