还剩26页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
淮海工学院计算机工程学院课程设计报告设计名称数据结构课程设计选题名称校园导游咨询名:李晨学号专业班级2022122663系(院)计算机工程学院设计时间
2022.
12.23~
2022.
1.3设计地点软件工程实验室、教室指导教师评语:成绩:签名://初始化顶点属于集合final[num]=1;num S//开始主循环,每一次求得到某个顶点的最短路径,并将其加入到集合num S//其余个顶点//当前所知离顶点的最近距离for i=0;iNUM;++i G.vexnumTmin=Max;numforw=0;wNUM;++w〃顶点在中if!final[w]w v-s〃顶点离顶点更近if D[w]min w num v=w;min=D[w];//离顶点更近的加入到集合final[v]=l;num vs〃更新当前最短路径极其距离for w=0;wNUM;++w不在集合,并且比以前所找到的路径都短就更新当前路径if[final min+G.arcs[v][w].adjD[w]//sD[w]=min+G.arcs[v][w].adj;for t=0;tNUM;t++P[w][t]=P[v]Et];P[w][w]=l;void outputint sightl,int sight2//输出函数int a,b,c,d,q=0;//将景点二赋值给a=sight2;a//如果景点二不和景点一输入重合,则进行・・・if a!=sightl{〃从%至的最短路径是〃,〃输出提示信息printf\n\tsU%s G.vex[sightl].sight,G.vex[sight2].sight;〃最短距离为%〃//输出到的最短路径长度,存放在口数组中printf\t dm.\n\n\t,D[a];sightl sight2D//输出景点一的名称printf G.vex[sightl].sight;二//将景点一的编号赋值给d sightl;dforc=0;cNUM;++c//标号,可以作为语句跳转的位置gate:;gotoP[a]Esightl]=O;forb=0;bNUM;b++//如果景点一和它的一个临界点之间存在路径且最短路径ifG.arcs[d][b].adj20000P[a][b]printfz/一>%s,/,G.vex[b].sight;//输出此节点的名称//计数变量加一,满控制输出时的换行q=q+1;8P[a][b]=0;//将作为出发点进行下一次循环输出,如此反复〃〃d=b;b ifq%8==0printf\n;goto gate;函数的调用关系
4.ShortestPath seirch SearchpathlOutputSearchMenu disppathmainpath四设计与调试分析.考虑到该程序时导游咨询系统,因此直接将景点及景点信息静态输入,并以邻接矩阵的方式存储,便1于程序中的调用.由于导游程序在实际执行时,需要根据用户的暂时输入求最短路径因此用迪杰斯特拉算法虽然其2时间复杂度比弗洛伊德算法低,但是每求一条最短路径时都需要重新搜索一遍,在频繁查询时会导致查询效率降低,而弗洛伊德算法只要计算一次,即可以求得每一对顶点之间的最短路径,虽然时间复杂度为但以后每次查询都只要查表即可但是,由于对弗洛伊德算法,并不熟练,所以程序中运用的仍0M3,是迪杰斯特拉算法五用户手册.进入演示程序后首先进入的是主菜单界面,要求选择所需要的功能120dongmen学校主门,大门进去是升旗广场1tushuguan借阅书籍2zhulou教室,校内最高建造3jisuanjilou满足学生上机需要4dahuo学生活动场所5tiyuguan室内体育馆6wentonglou7ershitang教室,楼分别立千两侧饭菜口味重,量多提示A,B8yishitang信息9nanfangchaoshi口味清淡,量少10nanyuan校内超市校内饭店11wenyulou校内宾馆12ximen在校门东侧有新建的停车场六测试成果操作命令为“1”始点东门;终点西门;最短路径东门®图书馆®主楼麴文通楼®二食堂@—食堂£南方超市®文宇楼@西门最短距离键入操作为1110命令符口*C:\Docuent sand5ettinss\student\J^3l\Debug\Cpp
1.exe择W0I馆机T05^生动育xXX馆楼堂雪馆乐II堂超楼主书竽连内筑建要I门书口清超饭楼愦悬苜上最都宾门f『普室通食食场是生内宝菜方园千馆两味内内卷E门I东于皿语教通干重图主计立别多分量少字教正口大体文市号量三一西在i南文西年场京二钟一占一至二电二呵I径径自格信有点占防旦算问洵询点出门杳杳票退IX M■CXZXZWX11M■3210M210987654MM”“,,,AM1MMN,18^^*IR,C:\Docuent sand5ett incs\student\Debug\Cpp
1.exevjx景点名称I生动倭市馆机怖楼育心袤堂堂超楼门用雪馆乐愦笄何通食I主书内筑食方园宇门东图主计去文三孕整建要上一丙再文西口清超场正香ii药室是馆量分量生内室少吗量重荽味内内裳F询询点出杳查4T景退一X占X防Ld,r*C:XDocuaent3and Settincs\student\^9$\Debug\Cppl.exe*******欢迎使用校园导游程字一《«»««««景点名称lW动育景点描述蜃雪楼市馆机陆楼仅乐f二,大门世去是升旗广场堂堂的楼门书十学宜w通食食方园牛东图王口清超内筑计大体文三一饭兵f金西南文西商甘克生值内室变味高需最内内裳重分量比番葱教少接饭口一量在]W*MM•■■•21W987654321WZV210987A543210KZCZKZXZXZX/111^0321a,,.^^]I,;R,B,i1•起室读侑新楼在英口】味,商计?倒矶恬内大楼?立育—内唐所体楼通曹文宾建食一育三门量更亘机一有自馆百临教室叫宇东两楼饭足再歹门堂口生「上建西■堂内学场,
1.exe°I主书竽涯口清超饭教内筑宾门f上建要堂辐室足生场堂味馆两教内内殳立重正利多讣量少腰基口在格信有点占防里算同三询询点出I材杳番票退I退出请输入您的迭择.3欢迎使月校园导游程序xxxn.m.景点描述门书楼舁生动育活育诵食福褛馆的乐食方园宇内门东图机教一书筑建要主计大体上半文三二南里南文西I速口场宰X气市清超饭馆不我宾门利多介两款堂济瞽室足重量堂超生内室樱口楼其味内量在内裳I至所X与刚X自X出:MMMAd«11103212109R765432192*0MM~lli3MMMlM,,—•H.A,£•MMR,,B.M1MEMIai”,M/IRf T-,*C:\Docuaent sandSett incs\st udent\Debut\Cpp
1.exe*(«通楼心矍星馆那多-hn口清超《三百支禊饭宾门
一一、一壹堂<9董味内内・<9)亘万超市卷教饭门在《》由园10文〒楼<1<>i2sn:12卿养鹤大话-〉体育馆文通楼-〉三食堂一食堂方n->第1条蒯:有蠢蠢加机楼—g三食堂--宿-〉2支宇楼用-_____________…__________________—条市->第琰:东门书馆-》主褛7文诵褛第仔主门书憧-〉主桂-》文逋楼三食堂->一食堂-》南方超市-〉文字楂-酒-洒门楼-〉富庶:左园i讨尊机楼->太哲->休可保->文逸楼三食堂->一食堂->南方愈市-〉->文字楼二南第条:东门一主楼-〉计算机楼->大活->体耳沱丁〉文通楼->三食堂-〉一食堂->西方6超市文楼>西门0-》南园》文宁喽>西第而东「桂桂〉文通1-门文平楼西第条宓门-食堂->南方‘18起•¥^^Llrz3nD*输出两点之间所有路径第条:东门,图书馆->主楼,计算机楼,大活,体育馆,文通楼,二食堂,一食堂,南超1n市,南园->文宇楼,西门第条冻门,图书馆,主楼,计算机楼,大活,体育馆>文通楼,二食堂,一食堂,南超2n-市,文宇楼,西门第条:东门,图书馆,主楼,文通楼->二食堂->一食堂,南方超市,南园,文宇楼->西3门第条:东门,图书馆,主楼,文通楼,二食堂,一食堂,南方超市,文宇楼,西门4第条:东门,主楼,计算机楼,大活,体育馆>文通楼,二食堂,一食堂,南方超市,园,5n-文宇楼,西门第条:东门,主楼,计算机楼->大活,体育馆>文通楼,二食堂,一食堂,南方超市,宇6n-楼,西门第条:东门,主楼〉文通楼,二食堂,一食堂,南方超市,南园,文宇楼,西门7第条:东门,主楼,文通楼,二食堂,一食堂,南方超市,文宇楼,西门8七附录源程序清单include string.hinclude stdio.hinclude stdio.h#include malloc.hinclude stdlib.h#includeiostream.h#define Max20000#define NUM13typedef structArcCell/*相邻接的景点之间的路程★/int adj;/*定义边的类型*/}ArcCell;typedef structVertexType/*景点编号*/int number;/*景点名称*/char*sight;景点描述*/char*description;/*/*定义顶点的类型*/}VertexType;typedef struct图中的顶点,即为景点*/VertexType vex[NUM];//图中的边,即为景点间的距离*/ArcCell arcs[NUM][NUM];/*顶点数,边数int vexnum,arcnum;//7/*定义图的类型*/}MGraph;/*把图定义为全局变量*/MGraph G;//全局数组,用来存放路径上的顶点*/int P[NUM][NUM];/*辅助变量存储最短路径长度*/long intD[NUM];标志数组*/int x
[13]={0};/*造图函数*/void CreatellDNint v,int a;/*/*说明函数*/void narrate;最短路径函数*/void ShortestPathint num;/*输出函数*/void outputint sight1,int sight2;/*/*主菜单*/char Menu;/*查询景点信息*/void search;/*查询子菜单*/char SearchMenu;void Searchpath1MGraph G;全局变量,用来记录每对顶点之间的所有路径的条数*/全局数组,int a=0;/*int visited[NUM];/*用来记录各顶点被访问的情况*/主函数*/void main/*int v0,v1;char ck;CreateUDNNUM,13;dock=Menu;switch ckcase*1char s;narrate;while1printfn\n\n\t\t\t请选择起点景点0^12”;scanfn%du,vO;printfn\t\t\t请选择终点景点0〜12;%scanf”d”,v1;/*计算两个景点之间的最短路径*/ShortestPathvO;/*输出结果*/outputvO,v1;请按任意键继续…;printf\n\n\t\t\t\t\n“getchar;getchar;继续查询?或者printf yn:H;scanfH%sH,s;ifs==N,||s==n,break;break;case2:search;break;case3:narrate;查询景点间的遨游路径*/SearchpathlG;/*break;};}whileck!=e;/*主菜单*/char Menuchar c;int flag;do{flag=1;narrate;printfn\n\t*********************************\nH;printfH\t
1、查询景点路径W;、查询景点信息printf\t2\n;、景点间所有路径printf\t3\nprintfH\t、退出\n”;e★★★★★★★★★★printf\t************\nH;★★★★★★★★★★请输入您的选择”;printf”\t scanfH%cn,c;Wc==1||c==2||c==3||c==e flag=O;whileflag;return c;char SearchMenu/*查询子菜单*/char c;int flag;doflag=1;narrate;printf H\n\t***************************、n*•printfn\tprintfn\t、按照景点编号查询1\nprintfn\t printf、按照景点名称查询2\n;、返回***★★★e★★★*★★*★*★*******\*n*n*;请输入您的选择”;printf”\t scanfH%c,c;ifc==1|||c==2|||c==,e,flag=O;whileflag;return c;/*查询景点信息*/void searchintnum;int i;char c;char name
[40];doc=SearchMenu;switch ccase,1narrate;请输入您要查找的景点编号”;printf\n\n\t\t%scanf”d”,num;fori=0;iNUM;i++ifnum==G.vex[i].number您要查找景点信息如下:;printf\n\n\t\t\tprintf^n\n\t\t\t%-25s\n\nH,G.vex[i].description;按任意键返回…printfn\n\t\t\tgetchar;getchar;break;}}ifi NUM==没有找到!;printf”\n\n\t\t\t按任意键返回…printf\n\n\t\t\tgetchar;getchar;}break;case2:narrate;请输入您要查找的景点名称”;printfH\n\n\t\t%scanf s”,name;』for0;ivNUM;i++将赋值给if!strcmpname,G.vex[i].sight/*G.vex[i].sight name*/您要查找景点信息如下:;printf\n\n\t\t\tprintf^n\n\t\t\t%-25s\n\n,,G.vex[i].description;按任意键返回…printfM\n\t\t\tgetchar;getchar;break;}}』二if NUM没有找到!;printf”\n\n\t\t\t按任意键返回…printf”\n\n\t\t\tgetchar;getchar;break;}}whilec!=e*;造图函数*/void CreateUDNint vjnt a/*int ij;/*初始化结构中的景点数和边数*/G.vexnum=v;G.arcnum=a;初始化每一个景点的编号*/fori=0;iG.vexnum;+4-i G.vex[i].number=i;/*/*初始化没一个景点名及其景点描述*/⑼』冻门”;G.vex.sight学校主门,大门进去是升旗广场”;G.vex
[0].description=“图书馆”;G.vex
[1].sight=”借阅书籍”;G.vex
[1].description=主楼”;G.vex
[2].sight=、「就教室,校内最高建造”;63*
[2].€^54|1=”计算机楼”;G.vex
[3].sight=”满足学生上机需要”;G.vex
[3].description=大活”;G.vex
[4].sight=体口学生活动场所”;63*
[4].^$:011=”、忖=体育馆”;66*
[5]9室内体育馆”;G.vex
[5].description=⑹文通楼”;G.vex.sight-⑹教室,楼分别立于两侧”;G.vex.description=A,B三食堂”;G.vex
[7].sight=饭菜口味重,量多”;G.vex
[7].description=、忖=一食堂”;66*
[8]9⑻口味清淡,量少”;G.vex description3南方超市”;G.vex
[9].sight=校内超市”;G.vex
[9].description=南园”;G.vex
[10].sight=校内饭店”;G.vex
[10].description=文宇楼”;G.vex
[11].sight=校内宾馆”;G.vex[11[description-西门”;G.vex
[12].sight=、刈前阿门=”在校门东侧有新建的停车场”;6012]650/*这里把所有的边假定为含义是这两个景点之间是不可到达*/20000,tori=0;iG.vexnum;++iforj=0;jG.vexnum;++jG.arcs[i][j].adj=Max;下边是可直接到达的景点间的距离,由于两个景点间距离是互相的,所以要对图中对称的边同时赋值G.arcs
[0]
[1].adj=G.arcs
[1]
[0].adj=150;G.arcs
[0]
[2].adj=G.arcs
[2]
[0].adj=200;G.arcs
[1]
[2].adj=G.arcs
[2]
[1].adj=40;G.arcs
[2]
[3].adj=G.arcs
[3]
[2].adj=180;G.arcs
[2]
[6].adj=G.arcs
[6]
[2].adj=300;G.arcs
[3]
[4].adj=G.arcs
[4]
[3].adj=80;G.arcs
[5]
[6].adj=G.arcs
[6]
[5].adj=50;G.arcs
[5]
[4].adj=G.arcs
[4]
[5].adj=50;G.arcs
[6]
[7].adj=G.arcs
[7]
[6].adj=20;G.arcs
[7]
[8].adj=G.arcs
[8]
[7].adj=10;G.arcs
[8]
[9].adj=G.arcs
[9]
[8].adj=50;G.arcs
[9]
[10].adj=G.arcs
[10]
[9].adj=100;G.arcs
[10]
[11].adj=G.arcs
[11]
[10].adj=100;G.arcs
[9]
[11].adj=G.arcs
[11]
[9].adj=140;G.arcs
[11]
[12].adj=G.arcs
[12]
[11].adj=400;说明函数*/void narrate/*int i,k=0;欢迎使用校园导游程序**printf\n\t********************\n;printf(H\t景点名称\t|\t景点描述\n“);printfn\t*fori=0;iNUM;i++输出景点列表*/printfH\t%2d%-10s:%-25s\nn,i G.vex[i].sight,G.vex[i].description;/*k=k+1;5printf H\t*}迪杰斯特拉算法最短路径函数为入口点的编号*/void ShortestPathintnum/*num;、和为计数变量*/intv,w,i,t/*i w vint final[NUM];int min;forv=0;vNUM;v++/*假设从顶点到顶点没有最短路径*/final[v]=0;num v将与之相关的权值放入中存放*/D[v]=G.arcs[num][v].adj;/*D设置为空路径*/forw=0;wNUM;w++/*P[v][w]=0;/*存在路径★/ifD[v]20000存在标志置为一*/P[v][num]=1;/*自身到自身*/P[v][v]=1;/*}}D[num]=O;/*初始化顶点属于集合*/final[num]=1;num S/*开始主循环,每一次求得到某个顶点的最短路径,并将其加入到集合*/num S/*其余个顶点fori=0;iNUM;++i G.vexnum-17/*当前所知离顶点的最近距离*/min=Max;numforw=0;wNUM;++w顶点在中*/if!final[w]/*w v-s顶点离顶点更近*/ifD[w]min/*wnum v=w;min=D[w];}/*离顶点更近的加入到集合*/final[v]=1;num vs/*更新当前最短路径极其距离*/forw=0;wNUM;++w不在集合,并且比以前所找到的路径都短就更新当前路径N!final[w]min+G.arcsM[w].adjvD[w]/*s*/D[w]=min+G.arcs[v][w].adj;fort=0;tNUM;t++P[w][t]=P[v][t];P[w][w]=1;}}/*输出函数*/void outputint sightl,int sight2;int a,b,c,d,q=0/*将景点二赋值给a=sight2;a*/⑴/*如果景点二不和景点一输入重合,则进行…*/Wa!=sigh从%$到%$的最短路径是”,输出提示信息*/printf\n\t G.vex[sight1].sight,G.vex[sight2].sight;/*最短距离为/*输出到的最短路径长度,存放在口数组中*/printf”\t%dm.\n\n\tn,D[a];sightl sight2D/*输出景点一的名称*/printfM\t%sn,G.vex[sight1].sight;/*将景点一的编号赋值给d=sight1;d*/forc=0;cNUM;++c/*标号,可以作为语句跳转的位置*/gate:;goto P[a][sight1]=0;forb=0;bNUM;b++如果景点一和它的一个临界点之间存在路径且最短路径*/ifG.arcs[d][b].adj20000P[a][b]/*/*输出此节点的名称*/printfH-%sn,G.vex[b].sight;;/★计数变量加一,满控制输出时的换行*/q=q+18P[a][b]=O;/*将作为出发点进行下一次循环输出,如此反复*/d=b;bifq%8==0printf,,\n^^;goto gate;}}为要查询是起始点,为要查询的终点,相当于深度优先遍历*//★确定void pathMGraph GJnt ijntj,int k/*i j路径上第个顶点的序号卜初始值为0*1k+1ints;讦找到一条路径,初始x[k]==j/*x
[0]=i*/路径的条数值加a++;/*1*/第%条—printf da;・输出一条路径*/fors=0;sv=k1;s++/*printfn%s-H,G.vex[x[s]].sight;printf,%s\n,,,G.vex[x[s]].sight;s=0;whilesG.vexnum保证找到的是简单路径*/Hs!=i/*ifG.arcs[x[k]][s].adj!=20000visited[s]==0/*当与之间有边存在且未被访问过*/vk vsvs/置访问标志位为即已访问的*/visited[s]=11,将顶点加入到数组中,在以为起点找下一个顶点★/x[k+1]=s;/*S XS/递归调用之*/pathG,i,j,k+1;/止重置访问标志位为即未访问的,以便该顶点能被重新使用*/vis ed[s]=0;/*0,S+4-;}void disppathMGraphGJnt ijntjint k;数据结构课程设计报告x
[0]^fork=0;kG.vexnum;k+4-让初始化各顶点的访问标志位,即都为未访问过的*/vis ed[k]=O;/*初始化路径的条数*/a=0;/*★通过调用函数,找到从至的所有路径并输出*/pathG,i,j,O;/path viU vj查询两个景点间的所有路径*/void SearchpathlMGraphG/*int ij;char s;⑴提供循环查询,当输入为或者时可,结束循环*/while/*N h选择出发景点:;printfcin»i;选择目地景点”;printfcin»j;从%$到%$的所有遨游路径有:输出出发景点和printfn\n\t\n”,G.vex[i].sight,G.vex[j].sight;/*目地景点的名称*/调用函数,用来输出两个景点间的所有路径*/disppathGjJ;/*disppath继续查询?或者printf yn:H;scanfH%s,s;网s==N||s==nbreak;.课程设计心得4通过这次课程设计,本人了解到自己的不足,有不少东西还是不了解,本人分析原因本人上课不够认真听得不明白下课又没有及时问老师同学;还有由于没有时常锻炼虽然课程设计之前做了好多准备但还是不够,感觉到自己还有好多东西要学我想我会以这次课程设计为起点好好系统学习、和以C C++后教的语言这次的课程设计让我感触颇多不仅有对编程基础好、设计做的棒的同学的佩服和羡慕,更重要的是从中认识到自己的不足,以及对数据结构这门课程的知识点有了进一步的了解这次课程设计中我遇到了不少问题由于基础知识掌握不牢靠,编程能力有限,从算法的设计,到语句的格式都浮现了大大小小的错误和问题,解决这些问题的过程中,又将课本和数据结构课本涉及C++课程设计的知识点巩固了一遍,也请教了一些同学,感觉脑袋里含糊的知识点也更加清晰了但还有一些问题还是没有搞明白,完成课程设计后还得进一步的巩固这次课程设计值得欣慰的是,在程序编译后浮现不少错误,但经过上几次的训练,这次我并没有像前几次那样,看到这么多错误就抛却了,既不敢也没有耐心找下去了,很深刻的记着大一老师的话“错误越多越好,说明错误很简单,很容易找出来,要耐心的找下去!”这次我很耐心的查找、修改自己的错误,直到没有错误,从中也找到了一点自信心这次的课程设计中,我相信“功夫不负苦心人”,只要我用心,我一定会会更上一层楼,虽然这次有点来不及了,但在以后的学习和工作中一定会有不少用到文件的地方我感觉对于我们计算机专业的同学来说,实践能力的培养至关重要但实践能力在平时的课堂上的培养是远远不够的,而课程设计就为实践能力的培养提供了很好的平台我们每一个学生都应该珍惜,同时也要注重平时的课外编程能力的训练,提高自己的实践能力,为以后的工作和学习奠定良好的基础所以,以后我会多看一些关于编程方面的书籍,多动手编写一些程序,提高自己的实践能力希翼经过在以后的努力,可以提高自己的编程能力,让自己的专业更好的发挥,保证以后找到一个好工作,让自己觉得没有白学这个专业,虽说以前在高中语言学的还不错,可是到了大学由于对自己要求的降低,多以导致c自己的成绩越来越不像话,通过这次的课程设计我发现暂时抱佛脚有很大的问题存在,因为真的不是很容易的事情,特别是在要考试的时候,一大堆的事情要忙,还有课程设计,蓦地间就会感觉时间很少,然后很慌张,什么事情都做不好,所以我觉得下学期要改变自己的学习方法,要从一开始抓起,好好的学习每一个课程,让自己不需要到考试的时候有慌张的心理,这样什么事情都做不好,然后就是做事情要认真子细,这样的话编程过程中也会浮现很少的语句错误,对自己编程的速度也会有所提高
1.课程设计目的**********A*^****************«»**«*******«*****^»*«*««*^»**«^»**««*«*««******«*^»*««^»***««*^»«**^»«*^»*««i**«*^^***«**^»***^»**^»***^»***^»******^»***^»**^»***^»***^»******^»****»W****^»***************»*****^»*»»^»««**********«»******«
0、训练学生灵便应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求1解指定问题
2.初步掌握软件开辟过程的问题分析、系统设计、程序编码、测试等基本方法和技能;
3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力;
4.训练用系统的观点和软件开辟普通规范进行软件开辟,巩固、深化学生的理论知识,提高编程水平,并在此过程中培养他们严谨的科学态度和良好的工作作风
5.课程设计任务与要求任务根据教材《数据结构-语言描述》(耿国华主编)和参考书《数据结构题集(语言版)》(严蔚敏、C C吴伟民主编)选择课程设计题目,要求通过设计,在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用设计题目从任务书所列选题表中选取,每班每题不得超过人2学生自选课题学生原则上可以结合个人爱好自选课题,要求课题有一定的深度与难度,有一定的算法复杂性,能够巩固数据结构课程所学的知识学生自选课题需在周前报课程设计指导教师批准方可生效18要求、在处理每一个题目时,要求从分析题目的需求入手,按设计抽象数据类型、构思算法、通过设计1实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目,最终写出完整的分析报告前期准备工作完备与否直接影响到后序上机调试工作的效率在程序设计阶段应尽量利用已有的标准函数,加大代码的重用率、.设计的题目要求达到一定工作量(行以上代码),并具有一定的深度和难度
2300、程序设计语言推荐使用程序书写规范,源程序需加必要的注释;3C/C++,、每位同学需提交可独立运行的程序;
4、每位同学需独立提交设计报告书(每人一份),要求编排格式统
一、规范、内容充实,不少于510页(代码不算);、课程设计实践作为培养学生动手能力的一种手段,单独考核
66.课程设计说明书******..■•■■■■■■■..*********..«*^»****..***********^»***^»******^»***^»***^»*«^»***^»**«^»**^****^»«*****^»***^^******^»***^»***^»**^***^***^»**^»***^»******^»*»*^»***^»***.♦.********...****^»***...********...*****■■■■.•■■■,一需求分析用无向网表示淮海工学院的校园景点平面图,图中顶点表示主要景点,存放景点编号、名称、简介等信息,图中边表示景点间的道路,存放路径长度信息[基本要求]查询各景点的相关信息;1查询图中任意两个景点间的最短路径2查询图中任意两个景点间的所有路径3淮海工学院的平面图上选取个具有代表性的景点,抽象成一个无向带权图.以图中顶点表示校
1.13内各景点,存放景点名称,代号,简介等信息;以边表示路径,存放路径长度等信息本程序的目的是为用户提供路径咨询.根据用户指定的景点输出景点信息
2.根据用户指定的始点和终点输出相应的路径,即查询任意两个景点之间的一条最短的简单路径
3..测试数据.4二概要设计抽象数据类型图的定义如下书上页
1.157ADT Graph{数据对象是具有相同特性的数据元素的集合,称为顶点集V V数据关系RR={VR}表示和之间存在路径}VR={v,w v,w£V,v,wvw基本操作PCreateUNDV,VR初始条件:是图的顶点集,是图中边的集合.v a操作结果:按和的定义构造图v aG.outputV,W初始条件图存在,和中顶点G V W操作结果若输入的和不重合且存在最短路径,则返回两顶点之间的最短路径;否则返V W回其他信息SearchpathlG初始条件图存在G操作结果以为起点遍历输出所有可以到达点的路径V WpathG,V,,W,K初始条件图存在,和是中顶点,且为起始点,为要查询的终点,是路G VW,K G VWK径上的顶点序号操作结果确定路径上个顶点序号K+1disppathG,V,W初始条件图存在,是图中顶点G V,W操作结果通过调用函数,找到从至的所有路径并输出path VWShortestPathV初始条件图存在,是中一条边的顶点GVG操作结果若存在路径,则返回以努为入口点的一条最短路径,否则返回其他信息V}ADT Graph主程序
2.void main初始化;接受命令输入景点信息或者输出最短路径;处理命令;do{“命令”!二“退出”;}hvhile.本程序惟独两个模块,调用关系简单3主程用莫块带权无向超模块三详细设计重点设计每一个功能模块的实现算法和数据库关系表的结构定义等图的基本操作
1.void CreateUDNintv,int a;//造图函数路径类型typedef structArcCell{//相邻接的景点之间的路程int adj;//定义边的类型}ArcCell;//景点编号//景点名称景点描述typedef structVertexType{int number;char*sight;char*description;//〃定义顶点的类型}VertexType;typedef struct{图中的顶点,即为景点VertexType vex[NUM];//图中的边,即为景点间的距离顶点数,边数ArcCell arcs[NUM][NUM];//int vexnum,arcnum;////定义图的类型}MGraph;相关的基本操作有void SearchpathlMGraphG〃输出两个顶点之间的所有路径void pathMGraphG,int i,int j,int k〃为要查询是起始点,为要查询的终点,相当于深度优先遍历i j//确定路径上第个顶点的序号,初始值为k+1k0void disppathMGraphG,int i,int j〃找到从到的所有路径并输出其中部份操作的伪代码如下vi vj为要查询是起始点,为要查询的终点,相当于深度优先遍历void pathMGraphG,int i,int j,int k//i j〃确定路径上第个顶点的序号,初始值为k+1k0ints;〃找到一条路径,初始ifx[k]=j x[O]=i〃路径的条数值加a++;1〃第%条:〃,printf da;〃输出一条路径for s=0;s=k-l;s++〃〉〃,printf%s-G.vex[x[s]].sight;〃〃printf%s\n,G.vex[x[s]].sight;}s=0;whilesG.vexnum〃保证找到的是简单路径if s!=iifG.arcs[x[k]][s].adj!=20000visited[s]==0〃当与之间有边存在且未被访问过vk vsvs{置访问标志位为即已访问的visited[s]=l;/*1,〃将顶点加入到数组中,在以为起点找下一个顶点x[k+l]=s;s xs〃递归调用之pathG,i,j,k+1;〃重置访问标志位为即未访问的,以便该顶点能被重新使用visited[s]=O;0,s++;void disppathMGraphG,int i,int jintk;x
[0]=i;fork=0;kG.vexnum;k++丫五〃初始化各顶点的访问标志位,即都为未访问过的1$61[]=0;〃初始化路径的条数a=0;〃通过调用函数,找到从到的所有路径并输出pathG,i,j,0;path vivj〃查询两个景点间的所有路径void Searchpath1MGraphGint i,j;char s;〃提供循环查询,当输入为‘或者时可,结束循环while1N n〃选择出发景点〃;printfcini;〃选择目地景点;printfcin»j;数据结构课程设计报告printf,z\n\t从%s到%s的所有游览路径有\n〃,G.vex[i].sight,G.vex[j].sight;〃输出出发景点和目地景点的名称〃调用函数,用来输出两个景点间的所有路径disppathG,i,j;disppath〃继续查询?或者〃;〃%〃printf yn:scanf s,s;ifs=N||s=,nbreak;主程序和其他伪代码
3.void main{〃主函数do主菜单;//计算两个景点之间的最短路径ShortestPathvO;//输出结果output vO,vl;search;SearchpathlG;〃查询景点间的遨游路径}whileck!=,e;}//main}char Menu{//主菜单char c;int flag;do{flag=l;system,,cls,/;narrate;显示指示图;〃请输入您的选择〃;〃%〃printf\t\t\t\t scanfc,c;if c-r||c—7||c-3||c—eflag=0;}whileflag;return c;void search//查询景点信息intnum;int i;charc;char name
[40];do{system〃cls〃;c=SearchMenu;switch ccaser:system,,cls,/;narrate;〃请输入您要查找的景点编号〃;〃%〃printf\n\n\t\tscanf d,num;fori=0;iNUM;i++ifnum==G.vex[i].numberprintf Cz\n\n\t\t\t您要查找景点信息如下:〃;printf〃\n\n\t\t\t%-25s\n\n〃,G.vex[i].description;printf,z\n\t\t\t按任意键返回...;getchar;getchar;break;}ifi=NUMprintf〃\n\n\t\t\t没有找到!〃;printf z,\n\n\t\t\t按任意键返回・・・〃;getchar;getchar;}break;case2’:〃〃system cls;narrate;〃请输入您要查找的景点名称〃;〃〃,printf\n\n\t\t scanf%s name;fori=0;iNUM;i++{〃将赋值给您要查找景点信息如if!strcmpname,G.vex[i].sight G.vex[i].sight nameprintf Cz\n\n\t\t\t下:〃;〃一〃printf\n\n\t\t\t%25s\n\n,G.vex[i].description;printf,z\n\t\t\t按任意键返回・・・〃;getchar;getchar;数据结构课程设计报告break;ifi==NUMprintfz,\n\n\t\t\t没有找到!〃;printf,z\n\n\t\t\t按任意键返回...;getchar;getchar;break;}whilec!=,e;说明函数void narrate//int i,k=0;〃欢迎使用校园导游程序*〃printf\n\t*********************\n;〃〃printf\t******************************************\n;printfz,\t景点名称\t|\t景点描述\n〃;〃〃printf\t****************|*****************\n;fori=0;iNUM;i++〃输出景点列表printf\t%2d%T0s:%-25s\n”,i,G.vex[i].sight,G.vex[i].description;/**/k=k+1;〃〃printf\t************************************\n;迪杰斯特拉算法最短路径函数为入口点的编号}void ShortestPathintnum//num、和为计数变量intv,w,i,t;//i wv intfinal[NUM];int min;forv=0;vNUM;v++//假设从顶点到顶点没有最短路径final[v]=0;numv将与之相关的权值放入中存放设置为空路径D[v]=G.arcs[num][v].adj;//D forw=0;wNUM;w++//P[v][w]=0;//存在路径ifD[v]20000存在标志置为一P[v][num]=l;//自身到自身P[v][v]=l;//D[num]=0;。