校园导游咨询系统课程设计报告.doc

福建农林大学计算机与信息学院计算机类课程设计报告课程名称：数据结构课程设计题目：校园导游咨询系统姓 名：系：计算机专 业：计算机科学与技术年 级：07级学 号：指导教师：职 称：副教授2008年 06月 30日目 录一、需求分析3二、概要设计4三、详细设计6四、设计和调试分析10五、用户手册11六、测试结果121操作命令符为s/S,122操作命令符为v/V,133操作符为v/V,134操作符为e/E,135综上可以查得：14七、附录14参考文献15校园导游咨询系统一、需求分析1从福建农林大学的平面图中选取28个有代表性的景点，抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地间的距离。2本程序的目的是为了用户提供路径咨询，根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。3测试数据（附后）。二、概要设计1.抽象数据类型图的定义如下： ADT struct arcnode int v; int w; struct arcnode *next;struct node int degree; struct arcnode *first;adjlist28;2.主程序 Void mian() 初始化临接矩阵 windows(); / /初始化串口 getch();3. 函数定义的变量#define infi 32767 #define MAX 28int M,N; /无向图中的顶点M，无向图的变数int adjmatrixMAXMAX; / 保存临接矩阵的2唯数组char *schoolIfoMAX+1= /此数组用于界面显示信息 null,东台-dt,金1-j1,金2-j2,金3-j3,金4-j4,食堂-st,田径场-tjc,校大门-xdm,创业园-cyy,校医院-xyy,图书馆-tsg,映辉桥-yhq,观音湖-gyh, 成教楼-cjl,生物楼-swl,博学楼-bxl,创新楼-cxl,明德楼-mdl, 拓荒广场-thgc,南区公寓-nqgy,田家炳楼-tjbl,农大新区-ndxq,中华广场-zhgc, 905终点站-zdz,蜂疗医院-flyy,研究生公寓-yjsgy,昌融学生街-crxsj,北区学生公寓-bqxsgy; char *charcd2MAX= /用于显示最短路径时走向的数组 校大门,金1,昌融学生街,创业园,东台,金2,田径场, 拓荒广场,南区公寓,校医院,食堂,成教楼,创新楼, 田家炳楼,农大新区,观音湖,金3,映辉桥,金4,明德楼,中华广场, 905终点站,蜂疗医院,生物楼,博学楼,图书馆,研究生公寓,北区学生公寓;char *charcdMAX= /用于用户输入起始点与终止点时对应的数组 xdm,j1,crxsj,cyy,dt,j2,tjc, thgc,nqgy,xyy,st,cjl,cxl, tjbl,ndxq,gyh,j3,yhq,j4,mdl,zhgc, zdz,flyy,swl,bxl,tsg,yjsgy,bqxsgy ;char *inforMAX= /介绍景点信息数组 校大门:n 占不提供介绍,金1:n 指金山大道的一处,由图可知,昌融学士街:n 农大的小吃一条街,来农大一定要来尝尝!, 创业园:n 农大创业有志者的孵化地,东台:n 农大老师所住之处,金2:n 金山大道的第二处有图可看出, 田径场:n 农大的运动场地,拓荒广场:n 大礼堂就在此处,南区公寓:n 顾名思意,学生公寓,校医院:n 希望你不要来, 食堂:n 学校八九十食堂都在这,不错蛮好吃的。,成教楼:n 成人教育教学大楼,创新楼:n 教学处, 田家炳楼:n 教学楼,农大新区:n 此处景点很多,由于时间不多.占不介绍。你自己看看,不错的., 观音湖:n 来农大必到之处,口碑也非常好，来了就一定要去,金3:n 金山大道第三处分叉口,映辉桥:n 情人之桥美丽而烂漫,值得留恋, 金4:n 金山大道第四处分叉口,明德楼:n 学校的最高建筑,中华广场:n 学校最好的照相之处,那是相当漂亮哦, 终点站,你离开农大再来我这吧!,蜂疗医院:n 学校特色，其他学校可没有,生物楼:n 搞研究的,博学楼:n 搞化学方面的, 图书馆:n 不错,可以来看看,研究生公寓:n 不要介绍了吧,北区学生公寓:n 不要说你不懂哦;void windows(); /主界面窗口void ReadCommand(char cmd); /读取用户需要的操作码void Interpret(char cmd); /执行正确的用户输入操作码void Shortpath(); /得到用户想要计算的起点与终点void getshortpath(int v0,int v1); /计算两点间的最短路径及走向void getinformation();4.本程序仅有三个模块 主程序模块带权无向图模块 三、详细设计 void CreatGraph() /创建学校平面图 /采用邻接矩阵为存储结构 FILE *fp2; int i=0,j=0,k; int vi=0,vj=0,w=0; fp2=fopen(D:TCtcworkGraph.txt,r); if(!fp2)printf(Open Graph file error.); fscanf(fp2,%d %d,&M,&N); for(i=0; iM; i+) for(j=0; jM; j+) if(i=j) adjmatrixij=0; else adjmatrixij=infi; for(k=0;kN;+k) fscanf(fp2, %d %d %d,&vi,&vj,&w); i=vi; j=vj; adjmatrixij=adjmatrixji=w; /* CreatGraph */void windows()int i;char cmd;printf(*n);printf(*Scenic Information-s Visited Path-v Exit-e *n);printf(*n);for(i=1;i=MAX;i+)printf(%d)%s ,i,schoolIfoi); if(i!=0&i%4=0)printf(n);printf(n);printf(*n);printf(*Enter a operationcode: s/S v/V e/E *n); printf(*n); printf(Operation :-n); /提示用户输入操作码scanf(%c,&cmd);ReadCommand(cmd);void ReadCommand(char cmd) /判断用户输入操作码 while(1)if(cmd=s|cmd=S|cmd=v|cmd=V|cmd=q|cmd=Q)Interpret(cmd);fflush(stdin); printf(Operation :-n); /提示用户输入操作码 scanf(%c,&cmd);if(cmd=e|cmd=E)exit(0);else fflush(stdin);printf(您输入的操作码不正确,请重新输入:n);scanf(%c,&cmd);if(cmd=e|cmd=E)exit(0);void Interpret(char cmd) /处理用户希望的操作char m;switch(cmd)case s:case S:while(1)getinformation();printf(n是否继续了解其他景点 Y&N: );scanf(%c,&m);if(m=n|m=N)break;break;case v:case V:while(1) Shortpath(); printf(n是否继续 Y&N: ); scanf(%c,&m); if(m=N|m=n)break; break;case e:case E:exit(0);break;void Shortpath() /得到用户要求的起点和终点的对应下标int i,j;int v0=0;int v1=0;char add180;char add280;printf( (使用地点的字母输入如：校大门 输入为 xdm)n);while(1)fflush(stdin);printf(起点:);gets(add1);printf(终点:);gets(add2);for(i=0;iMAX;i+)if(strcmp(charcdi,add1)=0) /判断起点对应的数组下标v0=i;break;for(j=0;jMAX;j+)if(strcmp(charcdj,add2)=0)v1=j;break;if(i=MAX)printf(没有你要的起点n); if(j=MAX)printf(没有你输入的终点n); else break;getshortpath(v0,v1);void getshortpath(int v0,int v1) int reverceMAX; int markMAX,distMAX,pathMAX; int i,j,k,l=1; int min,sum=0; for(i=0;iMAX;i+) marki=2; disti=adjmatrixv0i; pathi=v0; markv0=1; for(i=1;iMAX;i+) min=32767; for(j=0;jMAX;j+) if(markj=2&distjmin) min=distj; k=j; markk=1; for(j=1; j(double)distk+(double)adjmatrixkj) distj=distk+adjmatrixkj; pathj=k; if(v0!=v1) j=v1; /revercel+=v1; while(j!=v0) j=pathj; revercel+=j; sum+; for(i=sum;i0;i-) k=revercei; printf(%s-,charcd2k); printf(%sn,charcd2v1); printf(此路路程最短为:%dn,distv1); void getinformation() /显示景点信息int i;char value40;fflush(stdin);printf(输入景点:n);gets(value);for(i=0;iMAX;i+)if(strcmp(charcdi,value)=0) printf(infori);2.函数的调用关系图 getinformationgetshortpathShortpathInterpretReadCommandwindowsCreatGraphmain四、设计和调试分析 1，考虑道路网多是稀疏网，故采用邻接多重表做存储结构，其空间复杂度为O(e).构建邻接多重表的时间复杂度为O(n+e),输出路径的时间复杂度为O(n).由此，本导游程序的时间复杂度为O(n+e). 2，调试过程中头文件的引用也出现过报错如：warning C4013: exit undefined; assuming extern returning int改正为：#include stdlib.h由于程序需要经常从键盘中得到数据，所以在接收时，要时常注意刷新缓冲区。否则也将运行出错如：当用户输入操作码不正确时，提示用户重新输入出现两句。问题出现在 else printf(您输入的操作码不正确,请重新输入:n);scanf(%c,&cmd);if(cmd=e|cmd=E)exit(0);这句中，因为为使用函数fflush(stdin)；所以读取了一个空字符，造成两次循环。4.有些调试，都属于逻辑错误，在思考后都给予了解决。五、用户手册1本程序的运行环境为DOS操作系统，执行文件为： GraphTest.exe;2程序已经给了数据文件，若想改变数据文件，在文件夹data下将Graph.dat替代；3进入系统后，显示如下用户界面： 第一行：Scenic Information代表得到景点的信息 Visited Path 计算两景点的最短路径 Exit 退出系统框内显示28个景点及其英文名第三行表示，用户输入的操作码大小写均可4进入“查询景点信息（s/S）”的命令后，即提示以输入景点的名称，接受输入之后即显示该景点的信息；5进入“查询路径信息（v/V）”的命令后，即提升输入起始点和终止点的名称，在接受用户的输入之后即显示两点之间的一条最短路径。六、测试结果1操作命令符为s/S,2操作命令符为v/V,3操作符为v/V,4操作符为e/E,5综上可以查得：七、附录 原程序文件名清单 GraphTest.C /主程序 Graph.dat /数据文件 注释： 校园数据文件格式： 28 30 0 1 50 1 2 40 1 3 40 1 4 100 1 5 200 5 6 50 5 7 50 7 8 40 8 9 50 8 10 3010 11 50 10 16 245 11 12 30 12 13 10 13 14 20 12 19 80 19 20 10 5 15 20 1