数据结构课程设计报告学校导游系统

1、西安郵電學院数据结构课程设计报告题 目： 校 园 导 游 系 统院系名称：计算机学院 专业名称：计算机科学与技术班 级： 学生姓名： 学号（8位）： 指导教师： 设计起止时:一. 设计目的1学会图的存储、图的保存与读取。2学会图的深度遍历和广度遍历。3学会图的查找。4学会找图的最短路径、转折点最少的路径和所有路径。二. 设计内容 1界面。 2图的存储、保存、及读取。 3图的查找。 4找图重量景点之间的最短路径、转折点最少的路径和所有路径。三概要设计界面游客登录管理员登陆学院地图学院各景点的序号表景点查找查找两景点的所有路径两景点间的最短路径查找两景点间的转折点最少路径输入密码创建图文件读取保存

2、文件四详细设计1创建图 createudn(*g)开始输入顶点数和弧的个数i定点数 j定点数i,j两顶点间的权值赋值无穷大i+i=0i=0i+j+输入定点名i定点数输入简介i弧的个数结束输入第一个顶点名输入点二个顶点名输入两景点间的权值i=0 j=0i+否否否否调用函数 locatevertex() 2查找景点 getvertex(*g)输入定点名开始i=0i定点数 景点名与第i个定点名相同输出定点名输出该定点名的简介是否继续结束否是i+否调用函数 map() 3查找最短路径 zdload(g*)开始初始化pathij,distij用弗洛伊德算法计算最小路径输入两景点名输出最短路径结束y yn

3、distik+distkjvexnum,&g-arcnum); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-arcsij.adj=infinity; for(i=0;ivexnum;i+) printf(输入第%d个顶点信息,i+1);printf(地点名:);scanf(%s,g-);flushall();printf(简介:);scanf(%s,g-vertexi.jianjie);flushall(); printf(*n); for(k=0;karcnum/2;k+) printf(输入第%d条弧的两定点的地点名n,k);

4、printf(第一个顶点名:); scanf(%s,name1);flushall(); printf(第二个顶点名:); scanf(%s,name2);flushall();printf(权值:);scanf(%d,&weight);printf(*n);i=locatevertex(g,name1);j=locatevertex(g,name2); g-arcsij.adj=weight;g-arcsji.adj=g-arcsij.adj; return 1;/合并线性表seqlist joinlist(seqlist q,seqlist p) int i; for(i=1;i=p.la

5、st;i+) q.last+; q.aq.last=p.ai; return q;/两景点的最短路径void zdload(adjmatrix *g) int distmax_vertex_nummax_vertex_num,i,j,k,p,q; seqlist pathmax_vertex_nummax_vertex_num; char name130,name230; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) / initlist(&pathij); pathij.last=-1; distij=g-arcsij.adj; if(distijinfin

6、ity) addlist(&pathij,i); addlist(&pathij,j); for(k=0;kvexnum;k+) for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) if(distij(distik+distkj) distij=distik+distkj; pathij=joinlist(pathik,pathkj); do biao(); printf(请输入要查找的开始地点:); scanf(%s,name1); flushall(); printf(请输入要查找的结束地点:); scanf(%s,name2); flushall(); p=l

7、ocatevertex(g,name1); q=locatevertex(g,name2); for(k=0;k,g-); printf(endn); map(); printf(是否继续查找? 1是 2否n请选择:); scanf(%d,&i); sleep(1000); system(cls);while(i=1);五测试数据及运行结果1正常测试数据数据1运行结果数据2运行结果数据3运行结果2非正常测试数据（2组）及运行结果。数据1运行结果运行结果数据3运行结果 六调试情况，设计技巧及体会 上机前应知道上机的内容，认真地把书上相关的内容弄懂，上机时应

8、细心，不要犯一些小错误，因为一些小错误在实验中很难发现，实验中会影响时间，例如:在scanf语句中忘记加、语句后忘加“；”、struct类型弄错误。同时也要看自己申请的空间，防止空间申请过大，程序无法运行。该程序实现了规定的必须要完成的功能，除此之外，还实现了其他的一些功能，例如：将邻接矩阵打印输出，增加新的景点和路线等等。在今后的程序设计中，我会尽量使自己的程序更加完美。刚开始看到课程设计的题目时，我感觉没有思路，很茫然。后来从图书馆里翻阅了相关资料和查看课本，才慢慢的理清头绪。在编程的时候遇到了一些较难的问题后，通过认认真真的把图章节的内容复习了一遍及问同学，对一些经典的算法有了更深的理解

9、，最后克服难题。 最后，谢谢老师这周来对我们的认真指导，给我们释疑解惑，耐心的解答我们提出的问题，老师，谢谢您，您辛苦了！七参考文献1.c语言程序设计（第二版），王曙燕等，科学出版社，20082.数据结构c语言描述，耿国华，高等教育出版社2011八附录：源代码（电子版）#include#include#include #include#include#define max_vertex_num 15#define infinity 32768int bmax_vertex_num ;int visitedmax_vertex_num;typedef struct vexnode char na

10、me30; char jianjie150;vexnode;typedef struct arcnode int adj;arcnode;typedef struct vexnode vertexmax_vertex_num; arcnode arcsmax_vertex_nummax_vertex_num; int vexnum,arcnum;adjmatrix;typedef struct int amax_vertex_num; int top;list;typedef struct seqlist int amax_vertex_num; int last;seqlist;/*void

11、 initlist(seqlist *l) l-last=-1;*/int addlist(seqlist *l,int x) if(l-last=max_vertex_num-1) return 0; l-last+; l-al-last=x; return 1;/void tuichu();/void exit();void initstack(list *s) s-top=-1;int push(list *s,int x) if(s-top=max_vertex_num-1) return 0; s-top+; s-as-top=x; return 1;int pop(list *s)

12、 if(s-top=-1) return 0; else s-top-; return 1; /退出界面void tuichu() sleep(1000); system(cls); printf(nnnnnttn); printf(tt n); printf(tt * n); printf(tt * * n); printf(tt * * * * n); printf(tt * 导航结束 ￥ * n); printf(tt * * * n); printf(tt * * n); printf(tt * * * * n); printf(tt * ￥ 谢谢使用 * n); printf(tt

13、* * * n); printf(tt * * n); printf(tt * n); printf(tt n); printf(ttn);/地图void map() printf(n); printf( n); printf( 行政楼 大学生 体育场 学生公n); printf( 活动中心 寓区1 n); printf( 体育馆 n); printf( 图书馆 n); printf( 喷泉 n); printf(正 n); printf( 旭日苑n); printf( n); printf(门 n); printf( n); printf( n); printf( 篮 土 n); print

14、f( 教学楼实验楼 球 操 学生公n); printf( 场 场 寓区2n); printf( n); printf( 东 n); printf( 北南 美食 n); printf( 西 澡堂 广场 n); printf( n); printf(n);/各地点的序号void biao() printf( n); printf( 1正门 2行政楼 n); printf( n); printf( 3喷泉 4教学楼 n); printf( n); printf( 5大学生活动中心 6实验楼 n); printf( n); printf( 7图书馆 8澡堂 n); printf( n); printf

15、( 9体育场与体育馆 10土操场与篮球场 n); printf( n); printf( 11美食广场 12学生公寓区1 n); printf( n); printf( 13旭日苑 14学生公寓区2 n); printf( n);/求顶点位置int locatevertex(adjmatrix *g,char name30) int j=0,k; for(k=0;kvexnum;k+) if(strcmp(g-,name)=0) j=k; break; return (j);/用邻接矩阵存储结构创建图int createudn(adjmatrix *g) int i,j

16、,k,weight; char name130,name230; printf(请输入定点数和弧数:); scanf(%d %d,&g-vexnum,&g-arcnum); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) g-arcsij.adj=infinity; for(i=0;ivexnum;i+) printf(输入第%d个顶点信息,i+1);printf(地点名:);scanf(%s,g-);flushall();printf(简介:);scanf(%s,g-vertexi.jianjie);flushall(); printf

17、(*n); for(k=0;karcnum/2;k+) printf(输入第%d条弧的两定点的地点名n,k);printf(第一个顶点名:); scanf(%s,name1);flushall(); printf(第二个顶点名:); scanf(%s,name2);flushall();printf(权值:);scanf(%d,&weight);printf(*n);i=locatevertex(g,name1);j=locatevertex(g,name2); g-arcsij.adj=weight;g-arcsji.adj=g-arcsij.adj; return 1;/保存图save_i

18、nf(adjmatrix *g)int i,j;file *fp;if(fp=fopen(学校导游系统.txt,wt)=null)printf(n写文件出错,按任意键退出!);getch();exit(1);fprintf(fp,%d %dn,g-arcnum,g-vexnum);for(i=0;ivexnum;i+)fprintf(fp,%s %sn,g-,g-vertexi.jianjie); for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) fprintf(fp,%d ,g-arcsij.adj);printf(n文件已保存，按任意键

19、返回!); getch();fclose(fp);/从制定磁盘中读取信息并存入图gadjmatrix *read_inf()adjmatrix *g;int i,j;file *fp;fp=fopen(学校导游系统.txt,rt);if(fp=null)printf(n读文件出错,按任意键退出!);getch();exit(1);g=(adjmatrix *)malloc(sizeof(adjmatrix); fscanf(fp,%d %d,&g-arcnum,&g-vexnum); for(i=0;ivexnum;i+) fscanf(fp,%s %s,g-,g-ve

20、rtexi.jianjie);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+) fscanf(fp,%d,&g-arcsij.adj);fclose(fp);printf(n文件已读出,按任意键返回!);getch();return g;/景点查找void getvertex(adjmatrix *g) char name30; int i,p=0; biao(); printf(输入要查找的地点名:); scanf(%s,name); flushall(); for(i=0;ivexnum;i+) if(strcmp(g-,name)=0)

21、 p=1; break; if(p=0) map(); printf(抱歉,您查找的地址不存在!); else map(); printf(地点名:%sn简介:%s,g-,g-vertexi.jianjie) ; printf(nnnn*); printf(n是否继续查找? 1是 2否n请选择:); scanf(%d,&i); if(i=1) sleep(10000); system(cls); getvertex(g); /密码登录void mima() adjmatrix g; int i; char m7; printf(请输入六位数的密码:); for(i=0;

22、i6;i+) mi=getch(); printf(*); m6=0; sleep(1000); if(strcmp(m,123456)=0) printf(nnnnntt (-) ); printf(ntt ) - - (); printf(ntt / (o _ o) ); printf(ntt ( 0 ) /); printf(ntt -._=_.-_); printf(ntt /;#.-.#; ); printf(ntt_) 密码#正确(_/ ); printf(ntt #. # ); printf(ntt #.欢迎进入 !.# ); printf(ntt / #. .# ); prin

23、tf(ntt _ #. .#/ /_ ); printf(ntt (_) # (_) ); sleep(1000); system(cls); printf(n); printf( * n); printf( * * n); printf( * 是否创建导游图? * n); printf( * 1是 2否 * n); printf( * * n); printf( * n); printf(n); printf(请选择:); scanf(%d,&i); if(i=1) createudn(&g); save_inf(&g); else sleep(1000); system(cls); tui

24、chu(); else sleep(1000); system(cls); printf(nnntt|/ ); printf(ntt.-.-/ ); printf(ntt (.) ); printf(ntt+-oooo-(_)-oooo-+); printf(ntt| |); printf(ntt| 密码输入错误! 请重新输入! |); printf(ntt| |); printf(ntt+-oooo-+n); mima(); /求离第二个景点最近的点list *second(adjmatrix *g,int i,int j,list *l2 ) int visitmax_vertex_num

25、 ,p,k; list *l1,*l3; l1=(list*)malloc(sizeof(list); initstack(l1); l3=(list*)malloc(sizeof(list); initstack(l3); for(k=0;kvexnum;k+) visitk=infinity; if(i=j) push(l2,i); return l2; p=i; visitp=p; for(k=0;kvexnum;k+) if(g-arcspk.adjtop!=-1) push(l3,l1-al1-top); pop(l1); push(l1,k); while(l3-top!=-1)

26、push(l1,l3-al3-top); pop(l3); /* if(k=j)push(l2,j);push(l2,i);return l2;*/ while(1) p=l1-al1-top;l1-top-;for(k=0;kvexnum;k+)if(g-arcspk.adjtop!=-1)push(l3,l1-al1-top);pop(l1);push(l1,k);while(l3-top!=-1)push(l1,l3-al3-top);pop(l3);if(k=j)push(l2,p);return l2;/求两景点间转折点最少的路径void zzdload(adjmatrix *g)

27、list *l2; int i,j; char v130,v230; l2=(list*)malloc(sizeof(list);initstack(l2); biao(); printf(输入第一个景点名:); scanf(%s,v1); flushall(); printf(输入第二个景点名:); scanf(%s,v2); flushall(); i=locatevertex(g,v1); j=locatevertex(g,v2); push(l2,j); l2=second(g,i,j,l2); while(l2-al2-top!=i)l2=second(g,i,l2-al2-top,

28、l2); printf(最少转折点的路径:); for(l2-top;l2-top-1;l2-top-) i=l2-al2-top; printf(%s-,g-); printf(endn); map(); printf(n*n); printf(是否继续查找? 1是 2否n请选择:); scanf(%d,&i); if(i=1) sleep(1000); system(cls); zzdload(g); /路径输出void fond(adjmatrix *g,int v0,int v1,int j,int k)int n;visitedk=1;if(g-arcsbjv

29、1.adj!=infinity)for(n=0;); printf(%st,g-);printf(nnn);return;for(n=0;nvexnum;n+)if(g-arcsbjn.adj!=infinity&visitedn=0)visitedn=1; bj+1=n;fond(g,bj+1,v1,j+1,k); visitedn=0;/两景点间的所有路径void allload(adjmatrix *g) int bmax_vertex_num,j,v0,v,i,k,visitedmax_vertex_num;char name130

30、,name230;biao(); printf(输入地一个地点:);scanf(%s,name1);flushall();printf(输入第二个地点:);scanf(%s,name2);flushall(); v0=locatevertex(g,name1);v=locatevertex(g,name2);/int pmaxsize;/for(i=0;ivexnum;i+)/visitedi=0;b0=v0;j=0;for(i=0;ivexnum;i+)visitedi=0;visitedv0=1;i=g-arcsv0v.adj;k=v0;if(g-arcsv0v.adj!=infinity

31、)printf(%st,g-);printf(%st,g-); printf(nnn);i=g-arcsv0v.adj; g-arcsbjv.adj=infinity;fond(g,bj,v,j,k); g-arcsv0v.adj=i;printf(是否继续? 1是 2否n);scanf(%d,&i);sleep(1000);system(cls);if(i=1)allload(g);/合并线性表seqlist joinlist(seqlist q,seqlist p) int i; for(i=1;i=p.last;i+) q.last+;

32、q.aq.last=p.ai; return q;/两景点的最短路径void zdload(adjmatrix *g) int distmax_vertex_nummax_vertex_num,i,j,k,p,q; seqlist pathmax_vertex_nummax_vertex_num; char name130,name230; for(i=0;ivexnum;i+) for(j=0;jvexnum;j+) / initlist(&pathij); pathij.last=-1; distij=g-arcsij.adj; if(distijinfinity) addlist(&pathij,i); addlist(&pathij,j); for(k=0;kvexnum;k+) for(i=0;ivexnum;i+) for(j=0;jve