校园导游系统课程设计报告

《校园导游系统课程设计报告》由会员分享，可在线阅读，更多相关《校园导游系统课程设计报告（29页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计-校园导游系统 夏凤 040830201南京航空航天大学数据结构课程设计报告校 园 导 游 系 统 目录一、 需求分析2二、 程序的主要功能2三、 程序运行平台2四、 数据结构2五、 算法设计思想及时间复杂度2六、 测试用例及结果5七、 存在的不足与对策及编程体会6八、 程序源代码6一、需求分析南航学生家长及入学新生很需要一个导游程序，来引领他们参观和了解南航。二、程序的主要功能1、查询各景点的相关信息 2、查询任意两景点间的所有路径 3、查询任意两景点间的最短路径 1、增加景点4、推荐参观路线 2、删除景点5、更新导游信息（操作需管理员密码） 3、更新道路信息 6、对景点联通

2、性的浏览（2阶矩阵表示） 4、更新景点信息 7、学校全景一览 5、修改管理员密码三、程序运行平台Microsoft Visual C+ 6.0四、数据结构图的邻接矩阵存储表示，栈的顺序存储表示五、算法设计思想及时间复杂度主要函数介绍：1、求两点间的所有路径：a)相关函数：void dfs(MGraph G,SqStack path,int *used,int u,int w);/深度优先遍历b)主要算法思想：栈的相关操作+深度优先搜索创建一个空栈保存路径，一个空数组保存已标记节点，首先让起点进栈，并标记为已访问，然后调用深度优先搜索，如果该顶点的相邻顶点（即与其有直接通路的顶点）未被访问过就标

3、记为已访问，进栈，然后对它调用深度优先搜索，依次类推，直到获得所有到指定终点的路径。c)时间复杂度：O（VE），其中V为图的顶点数目，E为图中边的数目。2、求两点间的最短路径：a)相关函数：void ShortestPath(MGraph G,int v0,int PNmax,int *D);/查询任意两景点间的最短路径void PrintShortest(MGraph G,int v1,int v2,int PNmax,int *D); /输出最短路径b)主要算法思想：迪杰斯特拉算法假设起点为v0，S为已找到的从v0出发的最短路径的终点的集合，其初始状态为空集。而vj为当前求得的从v0出发的

4、最短路径的终点，则将j加到集合S中去，然后修改从v0出发到集合S的补集上任一顶点vk可达的最短路径的长度。重复上两步共n-1次即可。c)时间复杂度：O(V*V*V)，V表示图中的顶点数目。3、推荐参观路径：a)相关函数：void RecommentPath(MGraph G);/推荐参观路线void NextValue(int k,int n);/生成下一个顶点void Hamiltonian(int k,int n);/搜索所有的回路b)主要算法思想：回溯法求哈密顿回路。c)时间复杂度：O（E），其中E为图中边的数目。4、更改导游信息a)相关函数：void MakeChange(MGraph

5、 &G,char *pass);/更新导游信息（操作需管理员密码）void ChangeText(MGraph G,char *pass);/更新文本内容b)主要算法思想：第一个函数操作需要有管理员权限，初始密码为：1234，不然信息的安全性无法保证。修改后的信息会通过上面第二个函数写入文件，保证下次运行是修改后了的信息。特色函数介绍：1、验证密码正确性及修改密码函数int ConfirmPassword(char *pass);/验证密码是否正确void ChangePassword(char *pass);/修改管理员密码用户输入密码时，程序会自动输出“*”符号，以保证密码不被其他人看到。

6、修改密码时，程序提示用户输入两遍，以验证密码的正确性。所以只有拥有密码的管理员才能够更新导游信息和修改密码。初始密码为：1234.2、验证输入有效性的函数int ConfirmChoice(int low,int high);/验证输入是否合法，是,则返回用户的选择如果输入不合法，则程序输出出错信息，并提示用户重新输入选择。六、测试用例及结果以下是程序部分功能运行结果的截图：七、存在的不足与对策及编程体会存在的不足：1、我的程序中有一个功能是为用户推荐游览路径，我的主要思想就是用回溯法在图中搜索哈密顿回路。即只要沿着该条简单回路，能不重复地游遍全校的景点，就把它当做推荐路线。2、程序功能还不够

7、强大，比如可以增加一个功能是：允许游客输入大于等于两个景点，程序自动生成若干条路径来指引游客。对策：对于1：我想可以事先设置各景点的参数，这个参数描述的是该景点的可观赏价值。然后找出若干条观赏价值很高而路径长度又比较短的简单回路，然后推荐给游客。对于2：用深度或广度优先搜索算法搜索，直至路径中包含所有待观赏的景点即可。编程体会：这次课程设计花了我不少的时间和精力，但是我认为很值得！因为在编程过程中我的知识得到了进一步的巩固，也积累了一点小小的经验，我想会对我以后的工作很有帮助的。我记得上C+第一课的时候，郑洪源老师就给我们说了“不求甚解”的问题。而数据结构的课上，相对于具体的程序实现，秦小麟老

8、师则更注重算法思想的讲解。所以我想，在做一个比较大的程序的时候，关键在于把握总体的算法思想，要有一个宏观的视角，一个整体的思路，而不是急于下手去写几行代码。这次数据结构课设，我就是先考虑了程序的主要功能和实现方法，写出了一个整体的函数框架，然后再一步步填充具体代码实现的。 我感觉写程序时还是要更认真一些的，因为通过这次的调试，我发现很多错误往往都是源于粗心。而这个缺点是很致命的，它会耗费你很大的精力与时间。我这次就吃了粗心的亏了。八、程序源代码以下为map.txt的内容：1234921北门就是南航北边的那个门啊！博园学生宿舍，主要住的女生。怡园学生宿舍，住的主要是男生。艺术馆一些组织的办公所在

9、地，还有多功能厅体育馆这是篮球馆，羽毛球馆等体育用地。一号楼这是南航的主要教学楼哦！三号楼模电、数电实验室都在这栋楼里呢！砚湖南航的情侣胜地哦，景色还不错啦！西门就是南航西边的那个门啦！034200200002000020000200002000020000340300500550200002000020000990200300055060020000880800100020000500550050200200002000060020000550600500200200002000050020000200002000020020001005002002000020000880200002000

10、0100020000150200002000080020000200005002000002000020000990100060050020015020000 0#include#include#include#include #include#define Nmax 30#define Max 20000typedef int ElemType;/*栈的顺序存储表示*/#define Stack_init_size 100#define Stack_increment 10typedef structElemType *base;ElemType *top;/栈顶指针int stacksiz

11、e;SqStack;/栈的顺序存储表示结束/*图的数组（邻接矩阵）存储表示*/typedef struct /边int adj;ArcCell;typedef struct /顶点char name20;char info200;VexType;typedef struct/图VexType vexsNmax;ArcCell arcsNmaxNmax;int vexnum,arcnum;MGraph;/图的邻接矩阵表示结束/*相关函数声明*/int InitStack(SqStack &s);/构造空栈int DestroyStack(SqStack &s);/销毁栈int GetTop(Sq

12、Stack s,ElemType &e);/返回栈顶元素值int Push(SqStack &s,ElemType e);/插入新的元素ElemType Pop(SqStack &s);/删除栈顶元素void Print(SqStack s);/输出栈里的元素 void InitGraph(MGraph &G,char *pass);/对该无向网进行初始化int ConfirmChoice(int low,int high);/验证输入是否合法，是,则返回用户的选择int ShowMenu();/显示主菜单int ShowDoMenu(void);/显示更新导游信息的菜单int ShowMen

13、u1(void);/显示修改景点的菜单void GetInfo(MGraph G);/获取景点的相关信息void ShowAllPlace(MGraph G);/显示所有景点的名字和序号int ConfirmPassword(char *pass);/验证密码是否正确void ChangePassword(char *pass);/修改管理员密码void AllPath(MGraph G);/查询任意两景点间的所有路径void dfs(MGraph G,SqStack path,int *used,int u,int w);/深度优先遍历void ShortestPath(MGraph G,i

14、nt v0,int PNmax,int *D);/查询任意两景点间的最短路径void RecommentPath(MGraph G);/推荐参观路线 void MakeChange(MGraph &G,char *pass);/更新导游信息（操作需管理员密码）void NextValue(int k,int n);/生成下一个顶点 void Hamiltonian(int k,int n);/搜索所有的回路 void Print(MGraph G);/用二阶矩阵显示景点的连通性void Browser(MGraph G); /全景浏览void ChangeText(MGraph G,char

15、*pass);/更新文本内容void PrintShortest(MGraph G,int v1,int v2,int PNmax,int *D); /输出最短路径/函数声明结束/*/*主函数*/void main()int choice,i,j,DNmax,PNmaxNmax;MGraph G;char pass33;/pass存储密码 InitGraph(G,pass); /对该无向网进行初始化 dochoice=ShowMenu();switch(choice)case 1:GetInfo(G);break;case 2:AllPath(G);/查询两点间的所有路径break;case

16、3:ShowAllPlace(G);printf(nt请输入起点序号：);scanf(%d,&i);if(iG.vexnum) printf(t景点编号不存在!请重新输入景点编号:); scanf(%d,&i); printf(t请输入终点序号：);scanf(%d,&j);if(jG.vexnum) printf(t景点编号不存在!请重新输入景点编号:); scanf(%d,&j); i-;j-; ShortestPath(G,i,P,D);PrintShortest(G,i,j,P,D);break;case 4:RecommentPath(G);break;case 5:/printf(

17、mimashi:%s,pass);if( ConfirmPassword(pass)=0)/密码正确才能执行该操作printf(nt对不起，您的密码错误，无权执行该操作！n);elseprintf(nt恭喜您，密码正确！您可以继续进行下面的操作！n); MakeChange(G,pass);break;case 6:Print(G);/用二阶矩阵显示景点的连通性break;case 7: Browser(G); /全景浏览 break;while(choice!=8);/主函数实现结束/*相关子函数实现*/*以下为栈操作函数的实现*/int InitStack(SqStack &s)/构造空栈

18、s.base=(ElemType *)malloc(Stack_init_size*sizeof(ElemType);if(s.base=NULL)exit(0);s.top=s.base;s.stacksize=Stack_init_size;return 1;int DestroyStack(SqStack &s)/销毁栈s.top=s.base=NULL;return 1;int GetTop(SqStack s,ElemType &e)/返回栈顶元素值if(s.base=NULL)return 0; e=*(s.top-1); return 1; int Push(SqStack &s

19、,ElemType e)/插入新的元素if(s.top-s.base=s.stacksize)/栈满，追加空间s.base=(ElemType *)realloc(s.base,(s.stacksize+Stack_increment)*sizeof(ElemType); if(s.base=NULL) return 0; s.top=s.base+s.stacksize; s.stacksize+=Stack_increment; *s.top+=e; return 1;ElemType Pop(SqStack &s)/删除栈顶元素ElemType e;if(s.top=s.base) re

20、turn 0; e=*-s.top; return e;void Print(SqStack s)/输出栈里的元素 ElemType *p=s.base;int i;for(i=1;i=s.top-s.base;i+) printf(%dt,*p); p+;printf(n);/*/*以下为菜单显示函数*/int ShowMenu()/显示主菜单 int c;printf(ntt 南京航空航天大学导游系统 n);printf(tt 主菜单 ); printf(ntt *n); printf(tt n); printf(tt 1、查询各景点的相关信息 n); printf(tt 2、查询任意两景

21、点间的所有路径 n); printf(tt 3、查询任意两景点间的最短路径 n); printf(tt 4、推荐参观路线 n); printf(tt 5、更新导游信息（操作需管理员密码） n); printf(tt 6、对景点联通性的浏览（2阶矩阵表示） n); printf(tt 7、学校全景一览 n); printf(tt 8、退出 n); printf(tt n); printf(tt *n); c=ConfirmChoice(1,8); return c;int ShowDoMenu()/显示更新导游信息的菜单 int c;printf(ntt 南京航空航天大学导游系统 n); pri

22、ntf(tt 更新导游信息菜单 ); printf(ntt *n); printf(tt n); printf(tt 1、增加景点 n); printf(tt 2、删除景点 n); printf(tt 3、更新道路信息 n); printf(tt 4、更新景点信息 n); printf(tt 5、修改管理员密码 n); printf(tt 6、退出 n); printf(tt n); printf(tt *n); c=ConfirmChoice(1,6); return c; int ShowMenu1()/显示修改景点的菜单 int c; printf(ntt 南京航空航天大学导游系统 n)

23、; printf(tt 修改景点信息菜单 ); printf(ntt *n); printf(tt n); printf(tt 1、修改景点名称 n); printf(tt 2、修改景点信息 n); printf(tt 3、退出 n); printf(tt n); printf(tt *n); c=ConfirmChoice(1,3); return c; /*/*以下为密码相关函数*/int ConfirmPassword(char *pass)/验证密码是否正确 printf(nn请输入密码(密码只能包含字母和数字，否则不接受输入):); char pwd33; /保存密码的数组，最长支持

24、32位，第33位保存结束符。 short int index=-1; /密码数组下标，数据范围-1,32。 char ic=getch(); while(ic!=13&index=A&ic=a&ic=0&ic-1) /退格符处理 printf(b b); pwdindex- = 0;/修正字符串结束符位置 ic=getch();/读取下一个输入字符 if(strcmp(pwd,pass)=0) return 1; else return 0; void ChangePassword(char *pass)/修改管理员密码 printf(nn请输入新的密码(密码只能包含字母和数字，否则不接受输入

25、):); char pwd33,pwd133; /保存密码的数组，最长支持32位，第33位保存结束符。 short int index=-1; /密码数组下标，数据范围-1,32。 char ic=getch(); while(ic!=13&index=A&ic=a&ic=0&ic-1) /退格符处理 printf(b b); pwdindex- = 0;/修正字符串结束符位置 ic=getch();/读取下一个输入字符 printf(nt为了保证密码修改的正确性，请按照提示再输入一次：n);strcpy(pwd1,pwd);if(ConfirmPassword(pwd1)=1) strcpy

26、(pass,pwd);printf(nt恭喜您，密码修改成功！n);elseprintf(nt对不起，密码修改失败！n);/*/*以下为与导游图有关的操作函数*/int ConfirmChoice(int low,int high)/验证输入是否合法，是则返回用户的选择 int c;printf(tttt请输入您的选择：); scanf(%d,&c);getchar(); while(chigh) printf(编号不存在!请重新输入您的选择:); scanf(%d,&c); getchar(); return c;void InitGraph(MGraph &G,char *pass) /对

27、该无向网进行初始化 int i,j; FILE *fp; char p33;if(fp = fopen(map.txt,r) = NULL) /打开文件 printf(文件打开错误！n); exit(0); fscanf(fp,%sn,&p); /读入密码 fscanf(fp,%d %d,&G.vexnum,&G.arcnum); /读入景点个数和边数 for(i = 0; i G.vexnum; +i) /读入景点名称和详细介绍信息 fscanf(fp,%s %sn,&G.vexsi.name,&G.vexsi.info);for(i = 0; i G.vexnum; +i)for(j =

28、0; j G.vexnum; +j)fscanf(fp,%d,&G.arcsij.adj); fclose(fp); strcpy(pass,p);void ShowAllPlace(MGraph G) /显示所有景点的名字和序号int i,j=0;printf(ntt*南京航空航天大学*n);for(i=0;iG.vexnum;i+)if(j%3=0)printf(n);printf(%d: %st,i+1,G.vexsi.name);void ChangeText(MGraph G,char *pass)/更新文本内容 int i,j; FILE *fp;if(fp = fopen(map

29、.txt,w) = NULL) /打开文件 printf(文件打开错误！n); exit(0); fprintf(fp,%sn,pass); /写入密码 fprintf(fp,%dt%d,G.vexnum,G.arcnum); /写入景点个数和边数 fprintf(fp,n); for(i = 0; i G.vexnum; +i) /写入景点名称和详细介绍信息 fprintf(fp,%stt%sn,G.vexsi.name,G.vexsi.info); for(i = 0; i G.vexnum; +i)/写入边的权值 for(j = 0; j G.vexnum; +j)fprintf(fp,

30、%dt,G.arcsij.adj); fprintf(fp,n); fclose(fp);void GetInfo(MGraph G)/获取景点的相关信息int n;ShowAllPlace(G);n=ConfirmChoice(1,G.vexnum);printf(nt%s 的信息如下：n,G.vexsn-1.name);printf(t%s,G.vexsn-1.info);void ShortestPath(MGraph G,int v0,int PNmax,int *D)/查询景点v0到任意景点的最短路径int v,w,i,t,min,*final; final=(int*)malloc

31、(G.vexnum+1)*sizeof(int); if(final=NULL) printf(t*内存分配失败！*n); exit(0); for(v=0;vG.vexnum;v+) finalv=0; Dv=G.arcsv0v.adj; for(w=0;wG.vexnum;w+) Pvw=0; if(DvMax) Pvv0=1; Pvv=1; Dv0=0; finalv0=1; for(i=0;iG.vexnum;+i) min=Max; for(w=0;wG.vexnum;+w) if(!finalw) if(Dwmin) v=w; min=Dw;finalv=1; for(w=0;wG

32、.vexnum;+w) if(!finalw&(min+G.arcsvw.adj)Dw) Dw=min+G.arcsvw.adj; for(t=0;tG.vexnum;t+) Pwt=Pvt; Pww=1; void PrintShortest(MGraph G,int v1,int v2,int PNmax,int *D) /输出最短路径if(v1=v2)printf(起点和终点不能相同！n);return ; int i,j,k; printf(nt从%s到%s的最短距离为 %dm.)nn,G.vexsv1.name,G.vexsv2.name,Dv2); printf(t最短路径是%s,

33、G.vexsv1.name); k=j=0; for(i=0;iG.vexnum;+i) Pv2v1=0; while(j=Max|Pv2j=0) j+; if(G.arcsv1j.adj%s,G.vexsj.name); k+; Pv2j=0; v1=j; if(k%6=0) printf(n); void MakeChange(MGraph &G,char *pass)/更新导游信息（操作需管理员密码）int choice,i,j,n,c; do choice=ShowDoMenu(); switch(choice)case 1:printf(tt请依据向导准确填写相关信息,谢谢合作！n)

34、;printf(t请输入要增加的景点名称:);scanf(%s,&G.vexsG.vexnum.name);printf(t请输入对该景点的介绍:);scanf(%s,&G.vexsG.vexnum.info);for(i=0;iG.vexnum;i+)G.arcsiG.vexnum.adj=Max;G.arcsG.vexnumi.adj=Max; G.arcsG.vexnumG.vexnum.adj=0;G.vexnum+;ChangeText(G,pass);printf(tt*已成功增加该景点！*n);break;case 2:if(G.vexnum1) printf(nt导游图中已经没

35、有景点了，不能继续进行删除操作！tn); exit(0); printf(ntt请依据向导准确填写相关信息,谢谢合作！n);ShowAllPlace(G);i=ConfirmChoice(1,G.vexnum); i-; printf(nt您确定要删除该景点吗？请输入您的选择：（1：是；2：否）); scanf(%d,&c); if(c=2) break;for(j=0;j0&G.arcsij.adjMax)G.arcnum-;for(;iG.vexnum-1;i+)for(j=0;jG.vexnum;j+) G.arcsij=G.arcsi+1j; G.arcsji=G.arcsi+1j;G

36、.vexnum-; ChangeText(G,pass);printf(tt*已成功删除该景点！*n);break;case 3: ShowAllPlace(G); printf(tt请依据向导准确填写相关信息,谢谢合作！n); printf(t请输入该条道路的起点序号:); scanf(%d,&n);if(nG.vexnum) printf(n景点编号不存在!请重新输入景点编号:); scanf(%d,&n); i=n-1;printf(t请输入该条道路的终点序号:);scanf(%d,&n);if(nG.vexnum) printf(n景点编号不存在!请重新输入景点编号:); scanf(

37、%d,&n); j=n-1; n=G.arcsij.adj; printf(kaishi de %dn,n);printf(t请输入对该条道路的新长度(若该路不存在了，则输入%ld):,Max);scanf(%d,&G.arcsij.adj);G.arcsji.adj=G.arcsij.adj;printf(houlaide de %dn,G.arcsji.adj);if(n=Max&G.arcsij.adjMax)/本来没路，现在有路了G.arcnum+;else if(n=Max)/本来有路，现在没路了G.arcnum-;ChangeText(G,pass);printf(tt*已成功修改

38、该道路的情况！*n);break;case 4:ShowAllPlace(G);printf(ntt请依据向导准确填写相关信息,谢谢合作！n);i=ConfirmChoice(1,G.vexnum); c=ShowMenu1( ); if(c=1)printf(t请输入该景点的新名称:n);scanf(%s,&G.vexsi-1.name);ChangeText(G,pass);printf(tt*已成功修改该景点的名称！*n);else if(c=2)printf(t请输入对该景点的介绍:n);scanf(%s,&G.vexsi-1.info);ChangeText(G,pass);prin

39、tf(tt*已成功修改该景点的信息！*n); break;case 5:ChangePassword(pass);ChangeText(G,pass);break;while(choice!=6);void NextValue(MGraph G,int *x,int k,int n)/生成下一个顶点 /*X(1),X(k-1)是一条有k-1个不同结点的路径。若X(k)0，则表示再无结 点可分配给X（k）。若还有与X(1),X(k-1)不同且与X(k-1)有边相连接的结 点，则将其中标数最高的结点置于X(k)。若k=n，则还需要与X(1)相连接*/doxk=(xk+1)%(n+1); if(xk=0) return;if(G.arcsxk-1-1xk-1.adj0&G.arcsxk-1-1xk-1.adjMax)for(int j=1;j=k-1;j+)if(xj=xk) break;if(j=k)if(k0&G.arcsxn-10.adjMax)return;while(1);void Hamiltonian(MGraph G,int *x,int k,int n)/搜索所有的回路 doNextValue(G,x,k,n);if(xk=0) return;if(k=n) for(int i=1;i ,G.vexsxi-1.name);