《大大数据结构课程设计导航图》由会员分享，可在线阅读，更多相关《大大数据结构课程设计导航图（51页珍藏版）》请在金锄头文库上搜索。
1、word 西 安 邮 电 大 学 计算机学院数据结构设计报告题目： 导航图专业名称：软件工程班 级：班 学生某某：学号8位：指导教师：设计起止时间： 2014年12月15日2014年12月26日一. 设计目的1.数据结构课程设计是让学生综合运用数据结构课程中学到的几种典型数据结构，以与程序设计语言C语言，自行实现一个较为完整的应用系统的设计与开发2.通过课程设计，使学生通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用 。3.学会将知识应用于实际的方法，提高分析和解决问题的能力，增加综合能力二. 设计内容我设
2、计的是旅游查询系统，是用于校园的，任何景区都可以用。对于游客来说，游客可以查询要游览的景点，可以显示出该景点的相关信息，景点等级。也可以输入起点和终点，找到一条最短路径，或者这两点之间所有路径。或者输入起点，自动生成一个全程最短的游览路线。当然游客也可以查看校园的平面图。对于管理员来说，管理员可以增，删，改景点和道路信息。三概要设计1功能模块图；旅游查询系统系统管理两点之间所有路线最优全景路线查询最短行程查询浏览全景显示所有景点和路线2各个模块详细的功能描述。显示校园的平面图，让游客大概的了解校园的形貌，以与各个景点的位置。将所有景点和路线以列表的形式显示出来，包括景点名称，景点等级，景点描述
3、；路线也有道路名称，道路距离，道路的起点终点。输入起点，显示该起点到其它所有景点的最短路径。 输入起点，生成一个最小联通路径，这样游客便能以最少的行程来游览所有景点。 输入起点和终点，显示出这两点之间的所有路线供游客选择。四详细设计Map()Mian()showall()1功能函数的调用关系图bestroad ()System ()seekspotmin ()pathall ()prim()init_SeqStack ()Dijkstra ()pop ()creatgrahp ()DFS ()push()del()changel ()add()changes ()2各功能函数的数据流程图Map
4、()Mian()showall()bestroad ()seekspotmin ()System ()pathall ()prim()init_SeqStack ()Dijkstra ()pop ()creatgrahp ()DFS ()push()changel ()del()add()changes ()3重点设计与编码用DFS得出两点之间所有路线，首先输入起点和终点名称，找到其名称的下标，以起点下标开始进展深度优先遍历，每遍历到下一个邻接点让其进栈，并判断其下标是否和终点下标一样，如果一样如此输出栈内所有元素，并将栈顶出栈，假如不一样，继续遍历。直至找完所有的路线。在这里栈的作用是存储将
5、要找到的路线。五测试数据与运行结果1正常测试数据和运行结果六调试情况设计技巧与体会在求两点之间所有路径和最小联通路径的算法中，需要将邻接表转化为矩阵去做。对于prim算法所得出的结果并不是游客所要按照的走法，只是单纯的最小生成树，假如要得到一个节省的且能游览所有的景点的走法，那么需要遍历所得到的最小生成树，但并没有一个普遍的遍历方法去得到，完全需要游客自己主观的去判断怎样走才最短。在系统管理这一功能中，只有管理员才能使用，所以必须设置密码，这样就防止了游客的操作。对于邻接表要存储无向图，我们需要该顶点的邻接点个数，输完该顶点，再输入这些邻接点。那么输入以某个邻接点为顶点时，之前已经输过的顶点就
6、是它的邻接点，我们又要去输一遍它，这样太麻烦了。那么有什么方法呢？经过我的思考和研究，我们再输入完一个顶点和它携带的邻接点后，加一个算法，让这些邻接点和这个顶点关系一并接到这些以邻接点为顶点的邻接表上。具体处理如下：for(p=a-vertexi.head;p!=NULL;p=p-next)/*无向图在邻接表中相互指向*/ if(p-adjvexi) if(a-vertexp-adjvex.head=NULL) q=a-vertexp-adjvex.head=(anode *)malloc(sizeof(anode); else for(q=a-vertexp-adjvex.head;q-ne
7、xt!=NULL;) q=q-next; q-next=(anode *)malloc(sizeof(anode); q=q-next; q-next=NULL; q-adjvex=i; strcpy(q-rname,p-rname); q-weight=p-weight; 七、源代码与相关文件主程序代码：#include#include#include#define infinity 32767#define maxsize 50 typedef structint stackmaxsize;int top;SeqStack;typedef struct arode/邻接表结构体 char
8、rname20;/*路名*/int adjvex;/*相邻景点序号*/int weight;/*路长*/struct arode *next;anode;typedef struct vertexnode int visit;/*访问标志*/ char vexdata20;/*景点名称*/ char lv10;/*景点等级*/ char discribe100;/*景点描述*/ int in;/*入度*/ int out;/*出度*/ anode *head;vnode;typedef struct vnode vertexmaxsize; int vexnum;/*景点数*/ int aru
9、m;/*路数*/adjlist;typedef structint arcsmaxsizemaxsize;char spotnamemaxsize100;/景点名称int vexnum;/景点数adjmartrix; void establish(adjlist *a)/把创建的图写入文件，放到creatgrahp(adjlist *a)中int i,j;anode *p;FILE *sfp,*rfp; sfp=fopen(school.txt,wt);/创建新景点文件 rfp=fopen(road.txt,wt); fprintf(sfp,%d %dn,a-vexnum,a-arum);/*
10、景点数和路数写到school中*/for(i=1;ivexnum;i+) fprintf(sfp,%s %s %s %d %dn,a-vertexi.vexdata,a-vertexi.lv,a-vertexi.discribe,a-vertexi.out,a-vertexi.in);for(i=1;ivexnum;i+)/*道路信息写到road中*/p=a-vertexi.head;if(a-vertexi.out!=0) fprintf(rfp,%s %d %dn,p-rname,p-adjvex,p-weight); p=p-next; for(j=1;jvertexi.out;j+)
11、fprintf(rfp,%s %d %dn,p-rname,p-adjvex,p-weight); p=p-next; fclose(sfp);/关闭文件 fclose(rfp);/关闭文件void churudu(adjlist *a)/*计算出度和入度*/ int i,n; anode *p; for(i=1;ivexnum;i+)/*计算出度*/问题 p=a-vertexi.head;if(p!=NULL) n=1; p=p-next;elsen=0;while(p!=NULL)n+;p=p-next;a-vertexi.out=n; for(i=1;ivexnum;i+) a-vert
12、exi.in=0;/*在调用churudu()之前，原有景点入度变为0*/for(i=1;ivexnum;i+)/*计算入度*/p=a-vertexi.head;while(p!=NULL)a-vertexp-adjvex.in=a-vertexp-adjvex.in+1;/*入度自增1*/p=p-next;void creatgrahp(adjlist *a)/*创建图*/ int i,n,j; int flag=1; anode *p,*q; while(flag) printf(请输入景点数，路线数:n); scanf(%d %d,&a-vexnum,&a-arum); if(a-arum (a-vexnum-1)*a-vexnum/2|a-arum=0)/*判断输入的景点数和路线数是否能构成一个图*/ printf(输入有误，请重新输入:n); else flag=0; flag=1; getchar(); for(i=1;ivexnum;i+)/*输入景点*/ printf(请输入第%d个景点名称:n,i); scanf(%s,a-vertexi.vexdata); printf(请输入该景点等级:n); scanf(%s
