课程设计(软件类)报告内容模版(参考).doc

《课程设计(软件类)报告内容模版(参考).doc》由会员分享，可在线阅读，更多相关《课程设计(软件类)报告内容模版(参考).doc（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 西 安 邮 电 大 学 （计算机学院）数据结构设计报告题 目： 校园导游系统 专业名称： 软件工程班 级： 软件1205 学生姓名： 吴晗学号（8位）： 指导教师： 邓万宇设计起止时间： 2013年 12月16日2.13年12月27日一. 设计目的通过设计一些复杂的问题，是我们对课堂上所学的东西加深理解，更考验了我们对问题思考的逻辑结构和思维方法，学会在程序中应用和理解，提高我们思考问题和分析问题的能力， 逐步使我们提高自己的编写程序的能力。二. 设计内容用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要

2、求能够回答有关景点介绍、游览路径等问题。游客通过终端可询问：（1）从某一景点到另一景点的最短路径。 （2）游客从大门进入，选取一条最佳路线。 （3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。基本要求（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路， 边上的权值表示距离为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择浏览路线。 （3）画出景点分布图于屏幕上。 实现提示（1）构造一个无向图G并用邻接矩阵来存储。（2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组pi来记录，最短路径长度就用一维数组di存放

3、；i的范围：020。（3）一维数组pre是用来记录最短路径出现顶点的顺序。 （4）根据起点和终点输出最短路径和路径长度三概要设计程序设计的基本结构为：1. 先是设计一个欢迎界面，然后进入登录界面，加一个密码保护.2. 然后进入菜单界面显示逐条实现的功能。3. 最后是退出。 开始1 功能模块图； 定义变量 Void main() void Welcome() Switch() 选择功能增加 和删除景点两景点最短距离 显 示 景 点 平 面 图两景点间转折最少两景点间所有路径退出 结束2 各个模块详细的功能描述。.浏览校园全景：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出开始定义变量浏览

4、校园全景查看景点信息景点查询：可以进行按名称查询，如果你你输入非法，系统会自动提醒你你所查询的地点不存在，功能齐全。路径查询：可以查询两景点间的所有路径，最短路径和中转次数最少的路径。功能满足很多游客的要求。校园平面图显示：简单地显示校园的粗略布局。修改地图： 可以进行图的初始化、景点的插入、景点的删除（删除路线）、路径的插入。在修改后它会提示你要保存到文件中。四详细设计1 功能函数的调用关系图main（） Main（）Welcome（）Picture（）Pas swad（）游客登录管理员登陆最短路径最短连通路径显示路径所有路径中转次数最少的路径删除查找2各功能函数的数据流程图1.浏览校园全景

5、：采用深度遍历遍历图进行所有景点浏览，将遍历景点信息输出开始定义变量浏览校园全景查看景点信息某一景点到其余景点两景点最短距离退出系统VoidMenu()进入菜单Switch()选择功能结束2. 查看所有游览路线：用户输入一个景点，采用迪杰斯特拉算法将从该景点起所有路径查出并输出在屏幕上3.选择出发点和目的地：用户输入一个出发点和一个目的地编号，采用prim算法求出发点到目的地的最短路径4.查看景点信息：直接用景点名进行单个景点查询。3 重点设计及编码采用迪杰斯拉算法求各景点间的最短路径void Dijkstra(AdjMatrix *G , int start, int end , int d

6、ist ,int pathMAXVEX)/int mindist,i,j,k,t=1;for (i=1 ; ivexnum ; i+)/初始化disti=G-arcsstarti;if (G-arcsstarti!=INFINITY)pathi1=start;pathstart0=1;for (i=2 ; ivexnum ; i+)/寻找各条路线最短路线mindist=INFINITY;for (j=1 ; jvexnum ; j+)/选择权值最小的路线if (!pathj0&distjmindist)k=j;mindist=distj;if (mindist=INFINITY)return

7、;pathk0=1;for (j=1 ; jvexnum ; j+)/修改路线if (!pathj0&G-arcskjarcskjarcskj;t=1;while(pathkt!=0)/记录新路线pathjt=pathkt;t+;pathjt=k;pathjt+1=0;for (i=1 ; ivexnum ; i+)if (i=end)break; printf (%s-%s的最短路线为: 从%s,G-vexstart.name,G-vexend.name,G-vexstart.name);for (j=2 ; pathij!=0 ; j+)printf (-%s,G-vexpathij.na

8、me);printf (-%s,距离为%dkmn,G-vexend.name,disti);采用深度遍历算法求两点间的所有路径int dfs(int g1515,int vexnum,int cur,int path,int vis,int end,AdjMatrix *G)if(pathcur-1=end)int i=1;for(i=1;ivexpathi.name);printf(n);elseint i;for(i=1;iarcs,G-vexnum,2,path,vis,end,G);return 0;五测试数据及运行结果1正常测试数据和运行结果以上三个都是运行错误的2异常测试数据及运行

9、结果 导游图中的地点数目和路线数目: 5 6导游图中的地点及地点名: 1 A2 B3 C4 D5 E导游图中的路线: BA: 5kmCA: 6kmDB: 3kmDC: 6kmEC: 3kmED: 3km六调试情况，设计技巧及体会每当写完一个函数的时候，一编译会出现很多错误，当时的信息一下就没了，但怎么样还得继续做下去，就这样坚持着改错误，慢慢的发现其实很多是由于自己粗心造成的，别的错误改多了就习惯了。1改进方案总体还是比较满意的，比较上一学期进步了不少，但是程序还是有很多不足，需要改进，出现了很多问题都不会解决，还是找同学帮忙，还感觉自己对这门课程的学习程度还不是很深，对于自己的程序应该查阅资

10、料再进行改正，直到完美为止！2体会经过几周的课程设计，我学到了很多东西：巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和实验结果，正确绘制系统和程序框图。通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。同时，通过这次课程设计我发现，我的数据结构基础不够扎实，有很多地方还需要继续努力。课程设计是把我们所学的理论知识进行系统的总结并应

11、用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。在这次课程设计中我遇到许多问题和麻烦，得到了老师的帮助和指导，才能够使得这次课程设计顺利的进行下去，另外，在程序编写和调试过程中，也得到很多同学的帮助，给我及时指出错误，提出许多宝贵意见。此对老师和同学们表示感谢！七 参考文献王曙燕 王春梅 数据结构与算法王曙燕 王小银 C语言程序设计八附录：#include#include#include#include#includewindows.h#define MAXVEX 15

12、#define INFINITY 32768#define max_vexnum 200int visitedmax_vexnum;int bmax_vexnum;int premax_vexnum;typedef structint NO;/景点编号号char name20;/景点名char produce200;/景点介绍Vextype;typedef structint arcsMAXVEXMAXVEX;/所有路径Vextype vexMAXVEX;/所有景点int vexnum;/景点数目int arcnum;/路径条数AdjMatrix;typedef structint amax_

13、vexnum;int top;List;void InitStack(List *s) /初始化一个空栈s-top=-1;int push(List *s,int x) /入栈if(s-top=max_vexnum-1)return 0; s-top+;s-as-top=x;return 1;int pop(List *s) /出栈if(s-top=-1)return 0;else s-top-;return 1;/根据校园景点名确定景点编号int Locate(AdjMatrix *G,char name)int i;for(i=1;ivexnum;i+)if(!strcmp(name,G-

14、vexi.name)return i;return -1;void save_file(AdjMatrix *G)FILE *fp;int i,j;char filename10;printf(请输入要保存的文件名:);scanf(%s,filename);if(fp=fopen(filename,wt)=NULL)printf(打开文件错误!,任意键退出! n);getchar();exit(1); fprintf(fp,%d %dn,G-vexnum,G-arcnum);for(i=1;ivexnum;i+) fprintf(fp,%d %s %sn,G-vexi.NO,G-vexi.na

15、me,G-vexi.produce); for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) fprintf(fp,%6dn ,G-arcsij); printf(文件已保存!任意键返回); /getchar(); fclose(fp);/采用邻接矩阵创建学校景点无向图void Create(AdjMatrix *G)/创建图 int i,j; G-vexnum=10; G-arcnum=19; for(i=1;ivexnum;i+) G-vexi.NO=i; strcpy(G-vex1.name,男生宿舍); strcpy(G-vex1.produce,我们居住的地

16、方，共有8栋，里面水电齐全，舒适居住，东暖夏凉!); strcpy(G-vex2.name,旭日苑); strcpy(G-vex2.produce,旭日苑是学校的另一食堂;共分三层,饭菜种类繁多,可品尝到各种美味!); strcpy(G-vex3.name,女生宿舍); strcpy(G-vex3.produce,女神们栖息的地方，西邮的饭菜养人，更是产美女的地方。这栋楼的美女特别多!);strcpy(G-vex4.name,操场); strcpy(G-vex4.produce,体育场是举行大型赛事的地点，平时主要各种足球训练、比赛使用;也是同学们跑步健身的好场所!); strcpy(G-ve

17、x5.name,体育馆); strcpy(G-vex5.produce,体育馆是一个室内的小型体育场;内设有篮球场，羽毛球场及乒乓球场等); strcpy(G-vex6.name,篮球场); strcpy(G-vex6.produce,篮球场是同学们篮球课程及锻炼球技的地方,也是篮球比赛的重要场所!);strcpy(G-vex7.name,图书馆); strcpy(G-vex7.produce,图书馆内设多种书库,有几百万的丰富藏书!平时这里学习氛围浓重、是知识的天堂!); strcpy(G-vex8.name,实验楼); strcpy(G-vex8.produce,学校实验楼乃是学校各项重大

18、成果诞生的地方、共有三栋可供不同专业、不同兴趣的学生丰富自己的知识、拓展自己的视野!); strcpy(G-vex9.name,大学生活动中心); strcpy(G-vex9.produce,大学生活动中心是我校专为学生设计、展现自己各种特长才艺的地方!每周这里都会有非常精彩的活动、晚会;乃才艺高人的聚集地!); strcpy(G-vex10.name,教学楼); strcpy(G-vex10.produce,教学楼是学生学习上课的地方,分A、B两栋); for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) G-arcsij=INFINITY; G-arcs12=G-

19、arcs21=2; G-arcs13=G-arcs31=6; G-arcs14=G-arcs41=1; G-arcs23=G-arcs32=3; G-arcs25=G-arcs52=5; G-arcs26=G-arcs62=7; G-arcs36=G-arcs63=2; G-arcs35=G-arcs53=10; G-arcs45=G-arcs54=2; G-arcs49=G-arcs94=15; G-arcs57=G-arcs75=5; G-arcs56=G-arcs65=6; G-arcs58=G-arcs85=6; G-arcs68=G-arcs86=9; G-arcs79=G-arcs

20、97=1; G-arcs78=G-arcs87=6; G-arcs810=G-arcs108=8; G-arcs89=G-arcs99=12; G-arcs910=G-arcs109=20; save_file(G);void read_file(AdjMatrix *G)int i,j;FILE *fp;char filename40;printf(n请输入要打开的的文件名:);scanf(%s,filename);if(fp=fopen(filename,rt)=NULL)printf(读文件出错，按任意键退出!);getchar();exit(1);fscanf(fp,%d %d,&G-

21、vexnum,&G-arcnum); for(i=1;ivexnum;i+)fscanf(fp,%d %s %s,&G-vexi.NO,G-vexi.name,G-vexi.produce); for(i=1;ivexnum;i+) for(j=1;jvexnum;j+) fscanf(fp,%d,&G-arcsij);/fread(G,sizeof(AdjMatrix),1,fp);fclose(fp);printf(n文件以正确读出，按任意键返回!);getchar();/显示校园平面图信息void print(AdjMatrix *G)int i,j;printf(n校园平面图情况为:n

22、);for(i=1;ivexnum;i+)for(j=1;jarcsij!=INFINITY)printf(%s%s:%6dkmn,G-vexi.name,G-vexj.name,G-arcsij);/校园平面图信息查询void search(AdjMatrix *G)char views20;int NO,i,j;printf(n请输入需要查询的地点名称:);scanf(%s,views);NO=Locate(G,views);printf(%s的简介:,views);for(i=1;ivexnum;+i)if(i=NO)printf(%s,G-vexi.produce);printf(终止

23、地点:n);for(i=1;ivexnum;i+) if(i=NO) for(j=1;jvexnum;j+)if(G-arcsij!=INFINITY)printf(%s-%s:%6dkmn,G-vexNO.name,G-vexj.name,G-arcsij); /添加新的景点及路线void Add(AdjMatrix *G)char views20,str100;int start,end,weight,i;printf(n请输入增加路线的起始地点:);scanf(%s,views);start=Locate(G,views);printf(景点信息:);gets(str);save_fil

24、e(G);printf(n终止地点:);scanf(%s,views);end=Locate(G,views);printf(景点信息:);gets(str);save_file(G);printf(距离:);scanf(%d,&weight);G-arcsstartend=weight;G-arcsendstart=weight;printf (是否继续？ 1.是 2.否n);scanf (%d,&i);if (i=1)Add(G);/撤销路线void Del(AdjMatrix *G)int i;char views20;int start,end;printf(请输入需要撤销路线的起点景

25、点:);scanf(%s,views);start=Locate(G,views);printf(终点景点:);scanf(%s,views);end=Locate(G,views);G-arcsstartend=INFINITY ;G-arcsendstart=INFINITY ;printf (是否继续？ 1.是 2.否n);scanf (%d,&i);if (i=1) Del(G);/采用算法求得起点景点到各景点的最短路径void Dijkstra(AdjMatrix *G , int start, int end , int dist ,int pathMAXVEX)int mindi

26、st,i,j,k,t=1;for (i=1 ; ivexnum ; i+)disti=G-arcsstarti;if (G-arcsstarti!=INFINITY)pathi1=start;pathstart0=1;for (i=2 ; ivexnum ; i+)mindist=INFINITY;for (j=1 ; jvexnum ; j+)if (!pathj0&distjmindist)k=j;mindist=distj;if (mindist=INFINITY)return ;pathk0=1;for (j=1 ; jvexnum ; j+)if (!pathj0&G-arcskja

27、rcskjarcskj;t=1;while(pathkt!=0)pathjt=pathkt;t+;pathjt=k;pathjt+1=0;for (i=1 ; ivexnum ; i+)if (i=end)break; printf (%s-%s的最短路线为: 从%s,G-vexstart.name,G-vexend.name,G-vexstart.name);for (j=2 ; pathij!=0 ; j+)printf (-%s,G-vexpathij.name);printf (-%s,距离为%dkmn,G-vexend.name,disti);/寻找最短路线void Shortcut

28、(AdjMatrix *G)char univer20;int start,end,i;int distMAXVEX,pathMAXVEXMAXVEX=0;printf(请输路线的起点位置：);scanf(%s,univer);start=Locate(G,univer);printf(请输入终点位置：);scanf(%s,univer);end=Locate(G,univer);Dijkstra(G,start,end,dist,path);printf (是否继续？ 1.是 2.否n);scanf (%d,&i);if (i=1)Shortcut(G);/采用prim算法求最短连通路径vo

29、id prim(AdjMatrix*G,int start)struct int adjvex;int lowcost;closedgeMAXVEX;int i,e,k,m,min;closedgestart.lowcost=0;for(i=1;ivexnum;+i)if(i!=start)closedgei.adjvex=start;closedgei.lowcost=G-arcsstarti;for(e=1;evexnum-1;e+)/ 选择权值最小的路径min=INFINITY;for(k=1;kvexnum;+k)if(closedgek.lowcost!=0&closedgek.lo

30、wcostvexclosedgem.adjvex.name,G-vexm.name,closedgem.lowcost);closedgem.lowcost=0;/标志顶点v0加入到生成树中，灯泡亮！/当V0加入到生成树中，更新closedge数组信息for(i=1;ivexnum;+i)if(i!=m&G-arcsmiarcsmi;closedgei.adjvex=m;/查询最短连通路线void MinspanTree(AdjMatrix *G)char views20;int start;printf(请输入起点景点:);scanf(%s,views);start=Locate(G,vie

31、ws);prim(G,start);/求离第二个景点最近的点List *second(AdjMatrix *G,int i,int j,List *L2)int visitmax_vexnum,p,k;List *L1,*L3;L1=(List *)malloc(sizeof(List);InitStack(L1);L3=(List *)malloc(sizeof(List);InitStack(L3);for(k=1;kvexnum;k+)visitk=INFINITY;if(i=j)push(L2,i);return L2;p=i;visitp=p;for(k=1;kvexnum;k+)if(G-arcspktop!=-1)push(L3,L1-aL1-top);pop(L1);push(L1,k);while(L3-top!=-1)push(L1,L3-aL3-top);pop(L3);whi