数据结构课程设计报告(含代码).doc

西安郵電學院数据结构课程设计报告题 目： 校园导航系统院系名称： 计算机学院 专业名称： 计算机科学与技术班 级： 学生姓名： 学号（8位）： 指导教师： 设计起止时间：2011年12月11日2011年12月15日一. 设计目的1.通过本次课程设计巩固数据结构中所学的内容；2.提高自己上机编程以及调试能力。二. 设计内容1.设计所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 2.为来访客人提供图中任意景点相关信息的查询。 3.为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 三概要设计1功能模块图；主程序景点信息介绍输入各个景点的遍历校园平面图显示图的建立与修改景点信息路径查询 文件的读取与保存密码退出程序2各个模块详细的功能描述。 1. 可以手动创建一个校园图。 2. 可以直接从文件读取校园各个景点的信息。 3. 可选择从任意个景点作为起点进行遍历。 4. 输入景点序号查询该景点相关信息。 5. 输入两个景点查询两个景点的最短，最佳及其所有的路径。 6. 将校园图信息保存入文件。4 详细设计1功能函数的调用关系图判断密码显示menu调用相应函数返回主菜单密码3次错误密码正确输入密码具体分函数退出程序 开始管理系统程序是否退出？执行函数相应的操作 main() readvernum()arcnumfile() readarcnum()vernumfile()search()shortload()findvernum()creatdn()creatvisited()locatevertex()depthfirstsearch()floyd()2各功能函数的数据流程图1. Adjmatrix *g即结构体对象在main()中被创建在其他子函数中进行参数传递。2. 全局变量visited数组depthfirstsearch()creatvisited()visitedvisited数组在creatvisited()中被初始化，然后再在depthfirstsearch()中用。3. 全局变量shorest,path 在floyd()中被赋值来分别记录vi-vj最短路径和 vi-vj所经过景点。3重点设计及编码两景点最短距离 弗洛伊德算法void floyd(adjmatrix *g) int i,j,k;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)shortestij=0;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)shortestij=g-arcsij.adj;pathij=0;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)for(k=0;kvexnum;k+)if(shortestij(shortestik+shortestkj) shortestij=shortestik+shortestkj;pathij=k;pathji=k;五测试数据及运行结果1正常测试数据和运行结果要求提供3组正常测试数据和运行结果2(遍历功能)1(起始景点序号)1 校门 呈长方形,校训:爱国、求实、奋进2 喷泉 呈鸽子形状,喷射出水花3 教学楼 传授知识和学习知识4 实验楼 供学生进行课程实验和教师办公5 洗浴中心 供学生洗澡,内设单人间和双人间6 美食广场 仅一层,快餐味道不错7 图书馆 共七层,存储大量书籍供学生查阅和学习8 旭日苑 共三层,主要的就餐场所9 体育馆 内设篮球场,羽毛球场和观看席10 宿舍 休息的场所5(查询景点信息)2(景点序号)2 喷泉 呈鸽子形状,喷射出水花6(查询两景点最短路径)1 9(两景点序号)1-2-7-91-9 最短距离:570米2异常测试数据及运行结果要求提供2组异常测试数据和运行结果9 无此功能模块请重新输入5(功能模块)11(景点序号)无此景点请重新输入六调试情况，设计技巧及体会1改进方案1. 可将景点文件，边文件及账户密码合并为一个文件。2. 可设管理员，是管理员才能进行创建和修改，而客户只能进行查询。3. 可选用更好的算法，提升查询路径的速度。2体会回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。七参考文献数据结构 杨剑 主编 清华大学出版社数据结构(C语言版) .严蔚敏_吴伟民.主编 清华大学出版社八附录：源代码（电子版）#include#include#include#include#define maxsize 40 /最大景点数#define infinity 32768 /两景点不可到距离长度int visitedmaxsize; int pathmaxsizemaxsize;int shortestmaxsizemaxsize;typedef struct int top;char infomaxsize;char introducemaxsize;data;typedef struct node int adj;node;typedef struct data vertexmaxsize;node arcsmaxsizemaxsize;int vexnum,arcnum;adjmatrix;void Cipher ()FILE *fp;char user020, user120, cipher010, cipher110, ch;int i;fp = fopen(Cipher.txt,r);if(fp=fopen(Cipher.txt,r)=NULL)printf(no user message!n);exit(1);fscanf(fp, %s %s, user0, cipher0);fclose(fp);printf(nttn);printf(tt XIAN UNIVERSITY OF POSTS & TELLCOMUNICATIONS n);printf(tt * School Yard Guidebook * n);printf(ttn);printf(tt input users name:t);scanf(%s, user1);printf(tt intput cipher:t);for (i = 0; i10; i+)ch = getch();if (ch = 13)break;printf(*);cipher1i = ch;cipher1i = 0;printf(n);if(strcmp(user0, user1) != 0)system(cls);/*清屏*/printf(error users name!n);main();if(strcmp(cipher0, cipher1) != 0)system(cls);/*清屏*/printf(error cipher!n);main();elsesystem(cls);/*清屏*/printf(nntt Welcome to The School Yard Guidebook! %s.nn, user1);void Browser()system (color 0F);printf( 西安邮电学院平面图图 );printf(n);printf( 正门 );printf(n);printf( / | );printf(n);printf( / | 行政楼 =);printf(n);printf( / 喷泉 | | );printf(n);printf( 基础教学楼 | | | );printf(n);printf( | | | | );printf(n);printf( | | | | );printf(n);printf( | | | | );printf(n);printf( 实验楼 | 大学生活动中心 | );printf(n);printf( | | | | );printf(n);printf( | | | | );printf(n); printf( | = = 图书馆 = 人工湖 | );printf(n); printf( | | | );printf(n);printf( | | | );printf(n);printf( | | | );printf(n);printf( | |=东门 );printf(n);printf( | );printf(n);printf( | );printf(n);printf( 操场 =体育馆 );printf(n);printf( | );printf(n);printf( | );printf(n);printf( | );printf(n);printf( | );printf(n);printf( | );printf(n);printf( | );printf(n);printf( | );printf(n);printf( =食 堂 );printf(n);printf( | );printf(n);printf( | );printf(n);printf( |=宿舍 ); printf(n);void PlaceList()system (color 0A);printf(ttn);printf(tt 已存文件景点一览表 n);printf(ttn);printf(tt1.学校正门 2.喷泉 n);printf(ttn);printf(tt3.教学楼 4.实验楼 n);printf(ttn);printf(tt5.洗浴中心 6.美食广场 n);printf(ttn);printf(tt7.图书馆 8.旭日苑 n);printf(ttn);printf(tt9.体育馆 10.宿舍 n);printf(ttn);int locatevertex(adjmatrix *g,int v) int j,k;for(k=0;kvexnum;k+)if(g-vertexk.top=v) j=k;break;return(j);void creatdn(adjmatrix *g) int i,j,k,weight;data v1,v2;printf(请输入景点数和边数:n);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(请输入该景点的序号,名称:n);scanf(%d,&g-vertexi.top);gets();printf(请输入景点的信息:n);gets(roduce);for(k=0;karcnum;k+) printf(请输入第%d条边关联的两个景点:n,k+1);scanf(%d %d,&v1.top,&v2.top);printf(请输入距离:n);scanf(%d,&weight);i=locatevertex(g,v1.top);j=locatevertex(g,v2.top);g-arcsij.adj=weight;g-arcsji.adj=weight;void creatvisited(adjmatrix *g) int i;for(i=0;ivexnum;i+)visitedi=0;void depthfirstsearch(adjmatrix *g,int v) int k;visitedv=1;printf(景点序号:%d 名称:%sn,g-vertexv.top,);for(k=0;kvexnum;k+)if(!visitedk&g-arcsvk.adj!=infinity)depthfirstsearch(g,k);int patmaxsize,visitedmaxsize;int top=0;void Depsearch(adjmatrix *G,int num1,int num2) int v,i;top+;pattop=num1;visitednum1=1;if(num1=num2)for(i=0;i,G-);printf(bb n);visitednum1=0;top-;return ;for(v=0;vvexnum;v+)if(G-arcsnum1v.adjinfinity & !visitedv) Depsearch(G,v,num2);visitednum1=0;top-;void allways(adjmatrix *G)int num1,num2,i; char c=y;while(c=y)printf(请输入起始和终点的景点编号:);scanf(%d,%d,&num1,&num2);top=-1;for(i=0;imaxsize;i+)visitedi=0;Depsearch(G,num1,num2);printf(n是否继续查询最短路径(y/n):);/system(cls);scanf(%c,&c);c=getchar(); printf(n);void search(adjmatrix *g) int i,n;creatvisited(g);for(i=0;ivexnum;i+)printf(%dt%sn,g-vertexi.top,);printf(请输入遍历的起点序号:(1-%d)n,g-vexnum);scanf(%d,&n);depthfirstsearch(g,n-1);void vernumfile(adjmatrix *g) FILE *fp;int i;fp=fopen(vernum.txt,wt);for(i=0;ivexnum;i+)fprintf(fp,%d %s %sn,g-vertexi.top,,roduce);fclose(fp);void arcnumfile(adjmatrix *g) FILE *fp;int i,j;fp=fopen(arcnum.txt,wt);for(i=0;iarcnum;i+)for(j=0;jarcnum;j+)if(g-arcsij.adj!=infinity) fprintf(fp,%d %d %dn,g-vertexi.top,g-vertexj.top,g-arcsij.adj); fclose(fp);void readvernum(adjmatrix *g) FILE *fp;int i=0;fp=fopen(vernum.txt,rt);while(fscanf(fp,%d %s %s,&g-vertexi.top,,roduce)!=EOF) printf(景点序号:%d 名称:%sn,g-vertexi.top,);printf(景点信息:%sn,roduce);printf(n);i+;g-vexnum=i;fclose(fp);void readarcnum(adjmatrix *g) FILE *fp;int i=0,j=0,k=0;for(i = 0 ; i vexnum ; i+)for(j = 0 ; j vexnum ; j+)g-arcsij.adj = infinity;fp=fopen(arcnum.txt,rt);while(fscanf(fp,%d %d %d,&i,&j,&k)!=EOF) g-arcsi-1j-1.adj=k;fclose(fp);void findvernum(adjmatrix *g) int i,n,a;char choice;for(i=0;ivexnum;i+)printf(%dt%sn,g-vertexi.top,);printf(请选择查询方式的种类:n);printf(1.按序号n);printf(2.按名称n);scanf(%d,&a);doprintf(请输入要查询的景点序号(1-%d):n,g-vexnum);scanf(%d,&n);printf(景点名称:%sn,);printf(景点信息:%sn,roduce);printf(n);printf(是否继续查询:(y/n):n);flushall();scanf(%c,&choice);while(choice=Y|choice=y);void floyd1(adjmatrix *g) int i,j,k;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)shortestij=0;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)shortestij=g-arcsij.adj;pathij=0;for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)for(k=0;kvexnum;k+)if(shortestij(shortestik+shortestkj) shortestij=shortestik+shortestkj;pathij=k;pathji=k;void shortload(adjmatrix *g) int i,j,a,b;PlaceList();floyd1(g);printf(请输入起始景点和终止景点(1-%d):n,g-vexnum);scanf(%d%d,&i,&j);a=i;b=j;i=i-1;j=j-1;if(ij) printf(%d,b);while(pathij!=0)printf(-%d,pathij+1);if(ij)j=pathij; else i=pathji;printf(%d 距离是:%d米nn,a,b,shortesta-1b-1);else printf(%d,a);/while(pathij!=0)printf(-%d,pathij+1);if(i%d,b);printf(nn);printf(%d-%d 最短距离是:%d米nn,a,b,shortesta-1b-1); void suoyou(adjmatrix *g) int i,j,a;printf(请输入起始景点和终止景点(1-%d):n,g-vexnum);scanf(%d%d,&i,&j);a=j-i;for(;a0;a-)printf(-%d,i+1);meun()char choice;adjmatrix *g;g=(ad