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