大数据结构课程设计报告材料

1、实用文案西安郵電大學数据结构课程设计报告书系部名称计算机学院学生姓名高丹计算 计算机科学与技术技术专专业名称业标准文档实用文案班级科 11106学号04111196指导教师衡 衡霞2012年12月15日至时间2012年12月21日实验题目延安市旅游导游系统一、实验目的1加深对数据结构这一课程所学内容的进一步理解与巩固2通过完成课程设计，逐渐培养自己的编程能力；3培养给出题目后，构建框架，用计算机解决的能力；4通过调试程序积累调试C 程序设计的经验；二、实验内容编写一个延安市旅游导游系统，其中有平面图，有景点列表，可以查询景点简介，也可以查询两个景点间的最短路径，中转次数最少路径以及所有路径，其

2、中要用到数据结构中的图的部分的知识。三、需求分析1.开发系统功能描述（ 1）菜单类函数void MenuShow()主界面菜单函数标准文档实用文案void MenuShow0()输出延安市旅游景点平面图void MenuShow1()延安市简介void MenuList()旅游景点列表void S_Menu()查询菜单（ 2）查询两点间最短路径 .（权值最小）Shortroad(MGraph*G) 弗洛伊德法来查询两点间最短路径（ 3）查询两点间所有路径Depsearch(MGraph*G,int v,int w)allroads(MGraph *G)利用深度优先遍历图，递归的思想来完成所有路

3、径的查找（ 4） .查询中转次数最少的路径int IsEmpty(LinkQueue *Q)判断队是否为空函数int InitQueue(LinkQueue *Q)初始化队列函数int EnterQueue(LinkQueue *Q,int x)进队函数int DeleteQueue(LinkQueue *Q,int *x)出队函数int NextAdjVertex(MGraph *G,int w,int v)求当前顶点的前一个顶点函数void BFS(MGraph *G,int vi,int vj)void Reseach(MGraph *G)广度优先遍历图， 递归思想完成查询中转次数最少的

4、功能（ 5） .确定顶点位置函数int LocateVertex(MGraph * G, char v)确定当前顶点所在矩阵位置函数标准文档实用文案（ 6） .查询景点简介函数void Search_K (MGraph * G)按景点名称查询void Search_N (MGraph * G)按景点编号查询（ 7） .文件保存以及读出函数int read_info(MGraph *G)文件保存函数int save_info (MGraph * G)文件读出函数（ 8） .平面图的创建函数MGraph * CreatUDN(MGraph *G)平面图创建函数，若们有文件，则重新建立文件并保存（

5、9） .主函数void main(void)四、概要设计1、方案设计整个程序要实现的功能是导游功能， 平面图如果文件里面有存储的话便从文件读出，如果没有存储便创建文件存储。其中可以实现的功能为： 按景点名称查询， 按景点编号查询， 查询两点间的所有路径，查询两点间的最短路径， 查询两点间中转次数最少的路径。 按景点名称查询和按景点编号查询在此不做赘述，重要介绍其他三种查询方式。查询两点间所有路径： 该查询方法应用的是深度优先遍历平面图的方法， 其中定义两个数组， visit 用来标记已遍历过的结点， path 用来存储已找到景点的编号，利用递归的思想一层一层向下遍历， 最后打印出 path 数

6、组便可完成该功能。查询两点间最短路径： 该查询方法应用的是弗洛伊德算法，定义的两个二维数组 D 和 Q, 其中 Q 数组是用来存储查询到最短路径的景点矩阵的，D 数组是用来比较每两个景点之间的权值， 每得到一个最小值便将 D 数组刷新一次，将最后结果存入 Q 数组。查询两点间中转次数最少的路径：利用广度优先思想遍历平面图。其中应用的队列的知识。先将最后一个顶点入队，然后利用NextAdjVertex函数求它的标准文档实用文案上一个结点，利用递归思想一直找到最开始的一个结点。景区图：延安市主要景点平面图北延安杨家岭革命旧址延安大学清凉山景区人民公园二道街中国抗日军政大学延河大桥百米大道凤凰山景区

7、宝塔山火车站万花山景区2.数据结构说明typedef struct ArCellint adj; /*路径长度*/ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;邻接矩阵typedef struct /*图中顶点表示主要景点,存放景点的编号、名称、简介等信息 , */标准文档实用文案char nameMAX;景点名称int num;景点编号char introduction1000;/*简介 */infotype;typedef structinfotype vexsMAX_V

8、ERTEX_NUM;存储景点信息的数组AdjMatrix arcs;存储邻接矩阵的权值int vexnum;/图中的顶点数int arcnum; /图中的弧数MGraph;/ 队列的结构体typedef struct Nodeint date; 队列元素的值，在该程序中用来存储景点编号struct Node *next;LinkQueueNode;队中的每个结点typedef structLinkQueueNode *front;队头指针LinkQueueNode *fear;队尾指针标准文档实用文案LinkQueue;int visitMAX;用来存储景点是否被访问，访问标做1 ，未访问标做

9、 0int pathMAX;用来存储所有访问路径int top=-1;/*记录路径的长度 */int DMAXMAX,用来比较最短路径，不断刷新数组值int QMAXMAX;用来存储最短路径的邻接矩阵五、详细设计及运行结果1.各函数之间的调用关系图主菜单平面图浏延安市简景点列表查询功能览介MenuList()菜单MenuShoMenuShoS_Menu()w0()w1()void Search_N (MGraph*按景点编号查询G)LocateVertex(MGraph * G, char v)按景点名称查询void Search_K (MGraph * G)标准文档实用文案查询功能查询两点间

10、所有路径Depsearch(MGraph *G,int v,int w)菜单allroads(MGraph *G)S_Menu()查询两点间最短路径Shortroad(MGraph *G)NextAdjVertex(MGraph *G,int w,int查询两点间中转次数最v)少路径BFS(MGraph *G ,int vi,int vj)Reseach(MGraph *G)2.各模块流程图创建函数开始是否存在文件是否read_info(MGraphCreatUDN(MGraph *G)save_info (MGraph * G)结束查询所有路径标准文档实用文案Depsearch(G,j,w)

11、;Nv=wPathivisitv=1G-arcsvj.adjINFINITY & !visitjDepsearch(G,j,w);Yivexnum结束查询中转次数最少的路径标准文档实用文案开始广度遍历图求出中转最少的路径输入 vi,vjNvi,vj 合理Y权值小于无穷YNvi,vj 直接到达Yvi=vjN递归调用BFS输出中转最少的路径结束查询带权值最小路径标准文档实用文案开始初始化 Dij,Qij用弗洛伊德算法计算最小路径输入 vi,vjNvi,vj 合理YDtik+Dkjvexnum,&G-arcnum);for (i=1;ivexnum;i+)/G 的初始化邻接矩阵）for (j=1;j

12、vexnum;j+)G-arcsij.adj=INFINITY;printf(n请输入景点的编号 :、名称、简介 :n);for(i=1;ivexnum;i+)printf(n景点编号 :);scanf(%d,&G-vexsi.num);printf(n景点名称 :);scanf(%s,G-);printf(n景点简介 :);scanf(%s,G-roduction);for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)G-arcsij.adj=INFINITY;标准文档实用文案printf(n请输入每条路径长度 :n);for(k

13、=1;karcnum;k+)printf( 第 %d 条边 :n,k);printf(n连接的景点名称为 :n);scanf(%s,v1);scanf(%s,v2);printf(n该路径长度为 :n);scanf(%d,&w);i=LocateVertex(G,v1);j=LocateVertex(G,v2);if(i=1&j=1)G-arcsij.adj=w;G-arcsji=G-arcsij;return G;查询所有路径Depsearch(MGraph*G,int v,int w)标准文档实用文案int j,i;top+;pathtop=v;visitv=1;if(v=w)for(i=

14、0;i,G-);printf(bbn);visitv=0;top-;return ;for( j=1;jvexnum;j+)if(G-arcsvj.adjINFINITY & !visitj)Depsearch(G,j,w);visitv=0;top-;allroads(MGraph *G)标准文档实用文案int v,w,i;char c=y;while(c=y)printf( 请输入起始和终点的景点编号:);scanf(%d,%d,&v,&w);top=-1;for(i=0;iMAX;i+)visiti=0;Depsearch(G,v,w);printf(n是否继

15、续查询最短路径 (y/n):);fflush(stdin);c=getchar();printf(n);查询权值最小路径Shortroad(MGraph*G)/n 是顶点数 ,D 是权值 ,Q 是最短路径int i,j,k,v,w;char c=y;标准文档实用文案while(c=y)for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)if(G-arcsij.adj!=INFINITY)Qij=j;/j 是 i 的后继elseQij=0;Dij=G-arcsij.adj;/ 路径长度for(k=1;kvexnum;k+)/ 做 k 次迭代，每次均试图将顶点 k 扩充到当

16、前求得的从i 到 j 的最短路径 pij 上for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)if(Dik+D,G-);elseprintf(顶点%s到终点%s的最短路径为 :n %s,G-,G-,G-); while(k!=w)printf(-%s,G-);/ 输出后继结点k=Qkw;/ 继续找下一个后继结点printf(-%s,G-);/ 输出终点 wprintf(路径长度 : %dn,Dvw);printf(n是否继续查

17、询最短路径 (y/n):);标准文档实用文案fflush(stdin);c=getchar();printf(n);查询中转次数最少路径void BFS(MGraph *G,int vi,int vj)int visitedMAX;int i,num;intw;LinkQueue *Q;int v;Q=(LinkQueue*)malloc(sizeof(LinkQueue);if(vi=vj)return;for(i=1;ivexnum;i+)visitedi=FALSE;visitedvi=TRUE;InitQueue(Q);EnterQueue(Q,vi);while(Q-front!=Q

18、-fear)标准文档实用文案DeleteQueue(Q,&v);num=v;for(i=1;ivexnum;i+)if(G-arcsnumi.adj!=INFINITY|G-arcsinum.adj!=INFINITY)w=i;/* 求出当前节点的第一个邻接点（求出序号）*/while(w!=-1)if(visitedw=FALSE)if(w=vj)BFS(G,vi,num);printf(%s-,G-);return;visitedw=TRUE;EnterQueue(Q,w);标准文档实用文案w=NextAdjVertex(G,w,v);/W 是求的得第一个邻接点，

19、V 是相对 w 下一个邻接点(求出下一个邻接点的序号)break;六、调试情况，设计技巧及体会1 按景点编号查询和按景点名称查询标准文档实用文案2.查询所有路径3.查询带权值最小路径标准文档实用文案4.查询中转次数最少的路径标准文档实用文案2、对调试中主要问题进行总结这次程序中遇到的问题也挺多，首先在写所有路径查询时运行不出结果，加断点法时有几个数据没有值， 后来发现是自己数组的下标有问题，自己写时是从1 开始，而用深度查询时是从0 开始的，所以出错了。其次在写广度优先搜索时没有理解递归出口的条件， 所以写出来的是死循环， 后来让同学帮忙改正才得以正确运行，也加深了我对广度优先遍历的理解。第三

20、就是文件存储和读取方面自己很薄弱，刚开始根本无法下手写，后来把上学期C 语言课本文件部分再认真看了一遍，也是在同学的帮助下完成了文件的存储和读取，总之写的是磕磕绊绊，不过这样也加深的了理解。3、对自己设计进行评价，指出合理和不足之处，提出改进的方案这次设计的导游系统， 可以完成老师指定的功能， 我觉得其中的两点是深度优先遍历那里，没有完全按照课本上的编码来写， 是根据自己的思路定义了数组，讲栈的思想用进数组， 这样输出时比较容易理解， 不足之处就是在编写菜单时有标准文档实用文案些疏忽，导致在查询功能完成退出后直接进入主菜单，而不是查询的子菜单， 这样比较麻烦，而且有点浪费时间，还有就是用邻接矩

21、阵写的图，没法进行插入，这样就减弱了其实用性。4、在设计过程中的感受刚开始是在不知道怎么开始， 只是创建了个图然后就不知道怎么办了， 后来在网上查询了很多资料， 也看了许多别人的代码和思想， 才敢对自己的程序下手，编写过程中也不是一帆风顺的，遇到各种困难，主要是对课本上的知识了解不够熟悉， 浪费了大量时间去熟悉课本。 对知识太过死板，不会灵活利用。但同时也更好地理解了广度优先和深度优先，刚就到了弗洛伊德算法思想很精辟。源代码：#define INFINITY 32767#define MAX_VERTEX_NUM 40#define MAX 40#include#include#include

22、#include#define FALSE 0#define TRUE 1typedef struct ArCellint adj; /*路径长度*/ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /*图中顶点表示主要景点,存放景点的编号、名称、简介等信息, */char nameMAX;int num;char introduction1000;/*简介 */infotype;typedef structinfotype vexsMAX_VERTEX_NUM;标准文档实用文案AdjMatrix arcs;int vexn

23、um;/图中的顶点数int arcnum; /图中的弧数MGraph;/ 队列的结构体typedef struct Nodeint date;struct Node *next;LinkQueueNode;typedef structLinkQueueNode *front;LinkQueueNode *fear;LinkQueue;int visitMAX;/* 访问标志 */int pathMAX;/* 路径 */int top=-1;/*记录路径的长度*/int DMAXMAX,QMAXMAX;void MenuShow()system(cls);printf(n);printf(n);

24、printf(n);printf(n);printf(t*欢迎使用延安市主要景点导航系统*n);printf(n);printf(n);printf(n);printf(n);printf(n);printf(tt请按键选择： n);printf(tt0:进入平面图浏览 n);printf(tt1:查看延安市简介 n);printf(tt2 ：查看景点列表 n);printf(tt3:查询功能 n);标准文档实用文案printf(tt4: 退出 n);void MenuShow0()system(cls);printf(延安市主要景点平面图n);printf(北 n); printf(n);p

25、rintf(延安杨家岭革命旧址延安大学n);printf(n);printf(清凉山景区n);printf(n);printf(人民公园 n);printf(二道街n);printf(n);printf(中国抗日军政大学旧址n);printf(n);printf(延河大桥n);printf(百米大道n);printf(n);printf(凤凰山景区n);printf(宝 塔 山n);标准文档实用文案printf(n);printf(火车站n);printf(n);printf(n);printf(万花山景区n);printf(tt按任意键返回上一层n);getchar();void MenuS

26、how1()system(cls);printf(n);printf(n);printf(n);printf(n);printf(n);printf(延安古称延州，历来是陕北地区政治、经济、文化和军事中心。n);printf(城区处于宝塔山、清凉山、凤凰山三山鼎峙，延河、汾川河二水交汇之处的位置，成为兵家必争之地，n);printf(有“塞上咽喉” 、“军事重镇”之称，被誉为“三秦锁钥，五路襟喉。n);printf(延安之名，始出于隋。延安是国务院首批公布的全国24个历史文化名城之一。n);printf(n);printf(n);printf(n);printf(n);printf(n);pr

27、intf(tt按任意键返回上一层n);getchar();void MenuList()system(cls);标准文档实用文案printf(n);printf( 市内主要景点列表：n);printf(1:延安杨家岭革命旧址n);printf(2:延安大学n);printf(3:二道街n);printf(4:人民公园n);printf(5:中国抗日军政大学n);printf(6:延河大桥n);printf(7:凤凰山景区n);printf(8:宝塔山n);printf(9:清凉山景区n);printf(10:百米大道n);printf(11:火车站n);printf(12:万花山景区n);pr

28、intf(t 按任意键继续 n);getchar();void S_Menu()printf(n);printf(n);printf(n);printf(n);printf(n);printf(t请按键选择： n);printf(t 1:按景点编号进行查询n);printf(t 2:按景点名称进行查询n);printf(t 3:查询任意两个景点间所有路径n);printf(t 4:查询景点间最短路径n);printf(t 5:查询两点间中转次数最少的路径n);int IsEmpty(LinkQueue *Q)if(Q-front=Q-fear)return(1);elsereturn(0);标

29、准文档实用文案int InitQueue(LinkQueue *Q)/队的初始化函数的定义Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);if(Q-front!=NULL)Q-fear=Q-front;Q-front-next=NULL;return(TRUE);elsereturn(FALSE);int EnterQueue(LinkQueue *Q,int x)/入队函数的定义LinkQueueNode *NewNode;NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode);i

30、f(NewNode!=NULL)NewNode-date=x;NewNode-next=NULL;Q-fear-next=NewNode;Q-fear=NewNode;return(TRUE);elsereturn(FALSE);int DeleteQueue(LinkQueue *Q,int *x)/出队函数的定义LinkQueueNode *p;if(Q-front=Q-fear)return(FALSE);标准文档实用文案p=Q-front-next;Q-front-next=p-next;if(Q-fear=p)Q-fear=Q-front;*x=p-date;free(p);retu

31、rn(TRUE);Depsearch(MGraph*G,int v,int w)int j,i;top+;pathtop=v;visitv=1;if(v=w)for(i=0;i,G-);printf(bbn);visitv=0;top-;return ;for( j=1;jvexnum;j+)if(G-arcsvj.adjINFINITY & !visitj)Depsearch(G,j,w);visitv=0;top-;allroads(MGraph *G)int v,w,i;char c=y;while(c=y)printf(请输入起始和终点的景点编号:);标准文

32、档实用文案scanf(%d,%d,&v,&w);top=-1;for(i=0;iMAX;i+)visiti=0;Depsearch(G,v,w);printf(n是否继续查询最短路径(y/n):);fflush(stdin);c=getchar();printf(n);Shortroad(MGraph*G)/n是顶点数 ,D 是权值 ,Q 是最短路径int i,j,k,v,w;char c=y;while(c=y)for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)if(G-arcsij.adj!=INFINITY)Qij=j;/j 是 i 的后继elseQij=0;D

33、ij=G-arcsij.adj;/ 路径长度for(k=1;kvexnum;k+)/ 做 k 次迭代， 每次均试图将顶点k扩充到当前求得的从i 到 j 的最短路径pij 上for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)if(Dik+D,G-);elseprintf(顶点%s到终点%s的最短路径为:n %s,G-,G-,G-); while(k!=w)printf(-%s,G-);/ 输出后继结点k=Qkw;/ 继续找下一个后继结点printf

34、(-%s,G-);/ 输出终点 wprintf(路径长度 : %dn,Dvw);printf(n是否继续查询最短路径(y/n):);fflush(stdin);c=getchar();printf(n);int NextAdjVertex(MGraph *G,int w,int v)int i,j;for(i=w+1;ivexnum;i+)if(G-arcsvi.adj!=INFINITY)j=i;return(j);return (-1);标准文档实用文案/*广度优先遍历*/void BFS(MGraph *G,int vi,int vj)int visitedMAX;int i,num;