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

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

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

3、查找(4) .查询中转次数最少的路径int lsEmpty(Li nkQueue *Q)判断队是否为空函数int Ini tQueue(Li nkQueue *Q)初始化队列函数int En terQueue(Li nkQueue *Q,i nt x) 进队函数int DeleteQueue(Li nkQueue *Q,i nt *x) 出队函数int NextAdjVertex(MGraph *G,i nt w,i nt v)求当前顶点的前一个顶点函数void BFS(MGraph *G,i nt vi,i nt 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) .文件保存以及读出函数in t readn fo(MGraph *G)文件保存函数int savenfo (MGraph * G) 文件读出函数(8) .平面图的创建函数MGraph * CreatUDN(MGraph *G)平面图创建函数，若们有文件，则重新建立文件并保存(9) 主

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

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

7、 struct ArCellint adj; /*路径长度*/ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;邻接矩阵typedef struct /*图中顶点表示主要景点，存放景点的编号、名称、简介等信息，*/char nameMAX;景点名称int num; 景点编号char in troductio n1000;/*简介 */in fotype;typedef structin fotype vexsMAX_VERTEX_NUM;存储景点信息的数组AdjMatrix ar

8、cs;存储邻接矩阵的权值in t vex num;/ 图中的顶点数int arcnum; / 图中的弧数MGraph;/队列的结构体typedef struct Nodeint date;队列元素的值，在该程序中用来存储景点编号struct Node *n ext;Li nkQueueNode;队中的每个结点typedef structLin kQueueNode *front;队头指针Lin kQueueNode *fear;队尾指针Lin kQueue;int visitMAX;用来存储景点是否被访问，访问标做1，未访问标做0in t pathMAX;用来存储所有访问路径int top=-

9、1;/*记录路径的长度*/in t DMAXMAX,用来比较最短路径，不断刷新数组值in t QMAXMAX;用来存储最短路径的邻接矩阵五、详细设计及运行结果1.各函数之间的调用关系图标准文档2.各模块流程图创建函数查询所有路径查询中转次数最少的路径查询带权值最小路径程序设计过程及编码创建函数/初始化图形，接受用户输入MGraph * CreatUDN(MGraph *G)int i,j,k,w;char v120,v220;printf(n请输入地图所有景点的数目，以及所有路径的数目：);scanf(%d %d,&G-vex num,&G-arcnum);for (i=1;ivexnum;i

10、+)/G 的初始化邻接矩阵)for (j=1;jvex nu m;j+)G-arcsij.adj=INFINITY;printf(n请输入景点的编号：、名称、简介:n);for(i=1;ivex nu m;i+)printf(n 景点编号:);scan f(%d,&G-vexsi. nu m);printf(n 景点名称:);scan f(%s,G-vexsi. name);printf(n 景点简介:);sca nf(%s,G-vexsi.i ntroducti on);for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)G-arcsij.adj=INFINI

11、TY;printf(n请输入每条路径长度:n);for(k=1;karc nu m;k+)printf(第%d 条边:n,k);printf(n 连接的景点名称为:n);sca nf(%s,v1);sca nf(%s,v2);printf(n 该路径长度为:n);sca nf(%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,i nt v,i nt w)int j,i;top+;patht

12、op=v;visitv=1;if(v=w)for(i=0;i,G-vexspathi. name);prin tf(bbn);visitv=0;top-;return ;for( j=1;jvex nu m;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(请输入起始和终点的景点编号:);scan f(%d,%d,&v,&w);top=-1;for(i=0;iMAX;i+)visiti=O;Depse

13、arch(G,v,w);printf(n是否继续查询最短路径(y/n):);fflush(stdi n);c=getchar();prin tf(n);查询权值最小路径Shortroad(MGraph *G)n是顶点数，D是权值,Q是最短路径int i,j,k,v,w;char c=y;while(c=y)for(i=1;ivex nu m;i+)for(j=1;jv=G-vex nu m;j+)if(G-arcsij.adj!=INFINITY)Qij=j；j 是 i 的后继elseQij=0;Dij=G-arcsij.adj;/ 路径长度for(k=1;kvexnum;k+)/ 做 k 次

14、迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径pij上for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)if(Dik+Dkjvexsv. name,G-vexsw. name);elseprintf( 顶点 %s 到终点 s 的最短路径为:n %s,G-vexsv. name,G-vexsw. name,G-vexsv. name);while(k!=w)printf(-%s,G-);/ 输出后继结点k=Qkw;/继续找下一个后继结点printf(-%s,G-);/ 输出终点 wprintf(路径长度：%dn

15、,Dvw);printf(n是否继续查询最短路径(y/n):); fflush(stdi n);c=getchar();prin tf(n);查询中转次数最少路径void BFS(MGraph *G,i nt vi,i nt vj)in t visitedMAX;int i,num;int w;Lin kQueue *Q;int v;Q=(Li nkQueue*)malloc(sizeof(Li nkQueue); if(vi=vj)return;for(i=1;ivex nu m;i+)visitedi=FALSE;visitedvi=TRUE;Ini tQueue(Q);En terQue

16、ue(Q,vi);while(Q-fro nt!=Q-fear)DeleteQueue(Q,&v);num=v;for(i=1;ivex nu m;i+)if(G-arcs nu mi.adj!=INFINITY|G-arcsi nu m.adj!=INFINITY)w=i;/*求出当前节点的第一个邻接点(求出序号)*/while(w!=-1)if(visitedw=FALSE)if(w=vj)BFS(G,vi, nu m);prin tf(%s-,G-vexs nu m. name);return;visitedw=TRUE;En terQueue(Q,w);实用文案w=NextAdjVer

17、tex(G,w,v);W 是求的得第一个邻接点，V是相对w下一个邻接点(求出下一个邻接点的序号)break;六、调试情况，设计技巧及体会1 按景点编号查询和按景点名称查询V.标准文档 C：LfeerspcDektopgd DebugXGu i de SYSTEVfxe区 区续 暑旦靈 山大建建 一早车花意 清员万-C據賢示|询询 售WIi请钿人您要查旬的景点编号= 以下是您所查询的信息：编号4?其行政偻为朕北卷色建筑窑洞2椅曲諮实用文案标准文档朗CLfeer&p 必需_一区区- & 1 27 8 9 1 11一 区续 景景道ul 山山山懸 咼聚车花意 M睪百火万任 按有 所 電间g 进进工茁

18、选A点生日两 ，矍宣乐询谕询查 谙4.查询中转次数最少的路径啾C ：LfeerpDesktopXgd DebugGu i de SYSTEM.exeJSL8：请按挺逸择：費蛊声有路径I-漏次蝕最少的琵径请输入您要查询的起点编号和终点编号 :应堑家嵯早命P址到中国抗日至政大里中转次数最少的路径为: 诰岭拿喬|BM-道缶-时国吭日军改大学2、对调试中主要问题进行总结这次程序中遇到的问题也挺多，首先在写所有路径查询时运行不出结果，力卩 断点法时有几个数据没有值，后来发现是自己数组的下标有问题，自己写时是从 1开始，而用深度查询时是从0开始的，所以出错了。其次在写广度优先搜索时 没有理解递归出口的条件

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

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

21、define MAX 40#in clude#in clude#in clude#in clude#define FALSE 0#defi ne TRUE 1typedef struct ArCellint adj; /* 路径长度 */ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /*图中顶点表示主要景点，存放景点的编号、名称、简介等信息，*/char nameMAX;int num;char in troductio n1000;/*简介 */in fotype;typedef structin fotype vex

22、sMAX_VERTEX_NUM;AdjMatrix arcs;in t vex nu m;图中的顶点数int arcnum; / 图中的弧数MGraph;/队列的结构体typedef struct Nodeint date;struct Node *n ext;Lin kQueueNode;typedef structLin kQueueNode *front;Lin kQueueNode *fear;Lin kQueue;int visitMAX;/* 访问标志 */int pathMAX;/* 路径 */int top=-1;/* 记录路径的长度*/ int DMAXMAX,QMAXMAX

23、;void Me nu Show()system(cls); prin tf(n); prin tf(n); prin tf(n); prin tf(n);prin tf(t*欢迎使用延安市主要景点导航系统*、n”);prin tf(n); prin tf(n); prin tf(n); prin tf(n);prin tf(n); prin tf(tt prin tf(tt prin tf(tt prin tf(ttprin tf(tt请按键选择：n);0:进入平面图浏览n);1：查看延安市简介n);2 :查看景点列表n);3:查询功能n);printf(tt4:退出 n);void Men

24、 uShowO()system(cls);prin tf(延安市主要景点平面图n);printf(”北 n);printf(n);printf(延安杨家岭革命旧址printf(n);printf(n);printf(n);printf(园 n);printf(n);printf(n);prin tf(中国抗日n);printf(n);printf(n);printf(n);printf(n);printf(n);printf(延安大学n);清凉山景区人民公二 道 街 军政大学旧址 延河大桥百米大道凤凰山景区宝塔山n);printf(”n);prin tf(火车站n);printf(n);pri

25、ntf(n);prin tf(万 花 山 景 区n);prin tf(tt按任意键返回上一层n);getchar();void Men uShow1()system(cls);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);printf(”延安古称延州，历来是陕北地区政治、经济、文化和军事中心。n);prin tf(城区处于宝塔山、清凉山、凤凰山三山鼎峙，延河、汾川河二水交汇之处的位置，成为兵家必争之地，n);printf(”有“塞上咽喉”、“军事重镇”之称，被誉为“三秦锁钥，五路襟喉。n);printf(”延安之名，始出于隋。延安

26、是国务院首批公布的全国24个历史文化名城之一。n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(tt按任意键返回上一层n);getchar();void Men uList()system(cls);prin tf(n);printf(市内主要景点列表：n “)；printf(”1:延安杨家岭革命旧址n);printf(”2:延安大学n “)；printf(”3:二道街n);printf(”4:人民公园n);printf(5:中国抗日军政大学n “);printf(”6:延河大桥n);printf(”7:凤凰山景

27、区n);printf(”8:宝塔山n);printf(”9:清凉山景区n);printf(”10:百米大道n “)；printf(”11:火车站n);printf(”12:万花山景区n);printf(”t按任意键继续n);getchar();void S_Me nu()prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(n);prin tf(t请按键选择：n);prin tf(t 1:按景点编号进仃查询n);prin tf(t 2:按景点名称进行查询n);prin tf(t 3:查询任意两个景点间所有路径n “)；prin tf(t 4:查

28、询景点间最短路径n);prin tf(t 5:查询两点间中转次数最少的路径n)int lsEmpty(L in kQueue *Q) if(Q_fro nt=Q-fear)return(1);elsereturn(O);int Ini tQueue(L in kQueue *Q)队的初始化函数的定义Q-fro nt=(Li nkQueueNode *)malloc(sizeof(L in kQueueNode);if(Q-fro nt!=NULL)Q-fear=Q-fro nt;Q-fro nt- next=NULL;return(TRUE);elsereturn(FALSE);int En

29、terQueue(L in kQueue *Q,int x)入队函数的定义Lin kQueueNode *NewNode;NewNode=(Li nkQueueNode *)malloc(sizeof(Li nkQueueNode); if(NewNode!=NULL)NewNode-date=x;NewNode- next=NULL;Q-fear- n ext=NewNode;Q-fear=NewNode;return(TRUE);elsereturn(FALSE);出队函数的定义int DeleteQueue(L in kQueue *Q,i nt *x) Lin kQueueNode *

30、p;if(Q-fro nt=Q-fear)return(FALSE);p=Q_fr ont-n ext;Q-front-n ext=p-n ext;if(Q_fear=p)Q-fear=Q-fro nt;*x=p_date;free(p);return(TRUE);Depsearch(MGraph *G,i nt v,i nt w)int j,i;top+;pathtop=v;visitv=1;if(v=w)for(i=0;i,G-vexspathi. name);prin tf(bbn ”);visitv=0;top-;return ;for( j=1;jvex nu m;j+)if(G-a

31、rcsvj.adjINFINITY & !visitj)Depsearch(G,j,w);visitv=0;top-;allroads(MGraph *G)int v,w,i;char c=y;while(c=y)printf(请输入起始和终点的景点编号:);scan f(%d,%d，&v,&w);top=-1;for(i=0;iMAX;i+)visiti=O;Depsearch(G,v,w);prin tf(n是否继续查询最短路径(y/n):);fflush(stdi n);c=getchar();prin tf(n ”);Shortroad(MGraph *G)n是顶点数，D是权值，Q是最

32、短路径int i,j,k,v,w;char c=y;while(c=y)for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)if(G-arcsi j.adj!=INFINITY)Qij=j;/j 是 i 的后继elseQij=0;Dij=G-arcsij.adj;/ 路径长度for(k=1;kvexnum;k+)/做k次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径pij上for(i=1;ivex nu m;i+)for(j=1;jvex nu m;j+)if(Dik+Dkjvexsv. name,G-vexsw. name);elseprintf(

33、 顶点为:n %s,G-vexsv. name,G-vexsw. name,G-vexsv. name);%s的最短路径while(k!=w)prin tf(-%s,G-vexsk. name);/继续找下一个后继结点k=Qkw;prin tf(-%s,G-vexsw. name); printf(”路径长度:%dn,Dvw);prin tf(n是否继续查询最短路径(y/n):);fflush(stdi n);c=getchar();prin tf(n);int NextAdjVertex(MGraph *G,i nt w,i nt v)int i,j;for(i=w+1;ivex nu m;

34、i+)if(G-arcsvi.adj!=INFINITY)return(j);return (-1);/输出后继结点/输出终点w广度优先遍历*void BFS(MGraph *G,i nt vi,i nt vj)in t visitedMAX;int i,num;int w;Lin kQueue *Q;in t v;Q=(L in kQueue*)malloc(sizeof(L in kQueue); if(vi=vj)return;for(i=1;ivex nu m;i+)visitedi=FALSE;visitedvi=TRUE;Ini tQueue(Q);En terQueue(Q,vi

35、);while(Q-fro nt!=Q-fear)DeleteQueue(Q,&v);num=v;for(i=1;ivex nu m;i+)if(G-arcs numi.adj!=INFINITY |G-arcsi num.adj!=INFINITY)w=i;/*求出当前节点的第一个邻接点(求出序号) */while(w!=-1)if(visitedw=FALSE)if(w=vj) BFS(G,vi, num);prin tf(%s-,G-vexs nu m. name); return;visitedw=TRUE;En terQueue(Q,w);w=NextAdjVertex(G,w,v)

36、;W 是求的得第一个邻接点，V是相对w下一个邻接点(求出下一个邻接点的序号)break;/* 求任意两个地 点之间中转次数最少 的路径(广度遍历*/void Reseach(MGraph *G)int vi,vj;printf(请输入您要查询的起点编号和终点编号(1-12):n);scan f(%d, %d,&vi,&vj);if(G-arcsvivj.adj!=INFINITY)无 需 中 转，可 直 接 到中转次数最少 的路径/求顶点位置函数prin tf( 从 %s 到 %s 达!n ,G-vexsvi. name,G-vexsvj. name);if(G-arcsvivj.adj=IN

37、FINITY)prin tf( 从 %s 到 %s 为:n ,G-vexsvi. name,G-vexsvj. name);BFS(G,vi,vj);prin tf(%sn,G-vexsvj. name);int LocateVertex(MGraph * G, char v) int j=0,k;for (k=1;kvex nu m;k+)if (strcmp(G-vexsk. name,v)=0)j=k;break;return (j);/名称查找void Search_K (MGraph * G)char n ame10;int i=1;prin tf(n请输入您要查询的景点名称：);s

38、ca nf(%s, name);prin tf(n以下是您查询的信息:n);for (i=1;ivex nu m;i+)if (strcmp(G-vexsi. name ,n ame)=0)简介n);%st,G-vexsi. nu m,G-vexsi. naprintf(编号t名称tprintf( %dt%stme,G-vexsi.i ntroduct ion);getchar();void Search_N (MGraph * G)/ 编号查找int num=0;prin tf(n请输入您要查询的景点编号：”)；scan f(%d,&n um);prin tf(n以下是您所查询的信息:n);

39、printf(编号t名称tt简介n);printf(%dt%st%st,G-vexs nu m. nu m,G-vexs numn ame,G-vexs nu m.i ntroductio n);getchar();int read_info(MGraph *G)FILE *fp;int i=O,j;if (fp=fopen(E:/ 旅游图.txt,rt)=NULL)prin tf(n库存文件不存在，请创建 );return 0;while (!feof(fp)fscan f(fp,%d,&G-vex nu m);for (i=1;ivex nu m;i+)for (j=1;jvex nu m

40、;j+)fsca nf(fp,%d%s%d%d%s,&G-vexsi. nu m,G-vexsi. name,&G-arcsi j,&j,G-vexsi.i ntroduct ion);fclose (fp);return 1;int save_info (MGraph * G)/文件的保存景点信息FILE *fp;int i,j;j.adif (fp=fopen(E:/旅游图.txt,wt)=NULL)printf(n读取文件错误.按任意键退出！);return 0;fprin tf(fp,%dn,G-vex nu m);for (i=1;ivex nu m;i+)for (j=1;jvex nu m;j+)fprin tf(fp,%d%s%d%d%sn ,G-vexsi. nu m,G-vexsi. name,G-arcsij.adj,j,G-vexsi.i ntroducti on);fclose(fp);return 1;MGraph * CreatUDN(MGraph *G)/初始化图形，接受用户输入int i,j,k,w;char v120,v220;prin tf(n请输入地图所有景点的数目，以及所有路径的数目：”)；sca n