在邻接表存储结构上实现图的遍历0

《在邻接表存储结构上实现图的遍历0》由会员分享，可在线阅读，更多相关《在邻接表存储结构上实现图的遍历0（24页珍藏版）》请在装配图网上搜索。

1、大 连 科 技 学 院数据结构课程设计题 目 在邻接表存储结构上实现图的遍历 学生姓名 李楠 专业班级 网络工程13-1 指导教师 郭文书 职 称 副教授 所在单位 信息科学系 教学部主任 王立娟 完成日期 2015年1月11日课程设计报告单学号23姓名李楠专业班级网络工程13-1考 核 项 目评分备注1平时工作态度及遵守纪律情况（10分）2掌握基本理论、关键知识、基本技能的程度和阅读参考资料的水平（10分）3独立工作能力、综合运用所学知识分析和解决问题能力及实际工作能力提高的程度（20分）4完成课程设计说明书及软件的情况与水平（小组分工情况、规范性、整洁清楚、叙述完整性、思路清晰程度、工作量

2、及实际运行情况和创新性）（60分）总评成绩综 合 评 定：（优、良、中、及格、不及格） 指导教师签字：2015年1月11日数据结构课程设计任务书一、任务及要求：1. 设计（研究）任务和要求研究内容：在邻接表存储结构上实现图的遍历任务和要求：（1）学习数据结构基础知识，掌握数据结构典型的算法的使用。（2）对指导教师下达的题目进行系统分析。（3）根据分析结果完成系统设计。（4）编程：在计算机上实现题目的代码实现。（5）完成对该系统的测试和调试。（6）提交课程设计报告。要求完成课程设计报告3000字以上(约二十页)。完成若干综合性程序设计题目，综合设计题目的语句行数的和在100行语句以上。2.原始依

3、据结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3.参考题目：二、工作量2周（10个工作日）时间三、计划安排第1个工作日：查找相关资料、书籍，阅读示例文档，选择题目。第2个工作日第3个工作日：设计程序结构、模块图。第4个工作日第9个工作日：完成程序的编码，并且自己调试、测试。穿插进行课程设计报告的撰写。第10个工作日：上交课程设计报告，由教师检查软件测试效果、检查课程设计报告，给出学生成绩。

4、指导教师签字： 2014年 12月 28日目 录1 需求分析11.1 系统概述11.2 系统运行环境11.3 功能需求描述12 总体设计22.1 开发与设计的总体思想22.2 系统模块结构22.3 系统总体流程33 详细设计43.1 数据类型43.2 邻接表创建模块53.3 邻接表输出模块63.4 输出DFS遍历模块83.5 输出BFS遍历模块94 系统测试11总 结13参考文献14附 录15 大连科技学院2013级数据结构课程设计报告1 需求分析1.1 系统概述邻接表是图的一种存储结构。邻接表中的每个顶点表结点应包含两个区域：一个是顶点域，用来存放顶点的信息；另一个是指针域，用来存放与顶点相

5、关联的所有边链接成的边表头指针。图的遍历是从图的某一顶点出发，沿着某条搜索路径对图的每个顶点都访问一次且仅访问一次。根据搜索路径方向的不同，有两种常用的图的遍历方法：深度优先搜索和广度优先搜索。1.2 系统运行环境1. 硬件环境处理器： Inter Pentium 166 MX 或更高内存： 32M硬盘空间：1GB显卡： SVGA显示适配器2. 软件环境操作系统：Windows 98/ME/2000/XP/WIN7开发语言：Visual C+1.3 功能需求描述图是一种较线性表和树更为复杂的数据结构.图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关.因此,在研究有关图

6、的问题时,要考虑图中每个顶点的信息,访问图中的各顶点,而访问图中各顶点的操作过程就是图的遍历. 当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。2 总体设计2.1 开发与设计的总体思想由于图形结构比树形结构逻辑特征更复杂，所以图的遍历比树的遍历也要复杂得多。因为图中人一个顶点都可能与其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条搜索路径有回到了该顶点上。为了避免某一顶点被重复访问，在图的遍历过程中，必须采取某种方法来记录每个顶点是否被访问过。为此，可以设一个辅助数组，数组的初始值均设为“假”，一旦某个顶点被访问过，则将辅助数组中相应的值置为“真”。所

7、以要根据搜索路径方向的不同，则有两种常用的图的遍历方法：深度优先搜索遍历和广度优先搜索遍历。2.2 系统模块结构在邻接表存储结构上实现图的遍历邻接表创建模块输出DFS遍历模块输出BFS遍历模块邻接表输出模块退出结束程序图2-1 系统模块结构图2.3 系统总体流程在邻接表存储结构上实现图的遍历输入顶点个数建立邻接表输入边的信息输入边的个数输入顶点信息邻接表建立成功输入2输入3输入4输入0输出邻接表输出DFS遍历输出BFS遍历结束程序输入1图2-2 系统总流程图3 详细设计3.1 数据类型本系统中主要采用结构数据类型实现图的深度和广度两种遍历。本系统中定义typedef char VexType结

8、构体类型用于定义图的顶点，typedef int AdjType;结构体类型用于定义权值，ypedef intDataType结构体类型用于定义队列。格式如下：typedef char VexType;typedef int AdjType;typedef intDataType;typedef structDataType dataMAXSIZE;int rear,front;SeQueue;SeQueue * sq;typedef struct nodeint adjvex;struct node * next;EdgeNode;typedef structVexType vertex;E

9、dgeNode * link;3.2 邻接表创建模块V1V3V2V4V5V8V6V7图3-1无向图首先需要建立顶点表。顶点表的vertex域存入顶点信息，并将各个边表的头指针置空。然后依次读入各条边，当读到某一条边的顶点对序号（i，j）时，先在顶点vi的边表中用头插法插入一个adjvex域的值为j的边表结点，然后在顶点vj的边表中用头插法插入一个adjvex域的值为i的边表结点。显然，对应无向图中的一条边，需要在邻接表中建立两个边表结点。图3-2建立的邻接表代码：void creatAdjList() int i,j,k,M,H; EdgeNode*s;printf(请输入顶点个数);scan

10、f(%d,&M);printf(请输入每个顶点信息:,M);getchar();for(i=1;i=M;i+) adjlisti.vertex=getchar(); adjlisti.link=NULL;printf(请输入条的边数);scanf(%d,&H);printf(请输入%d条边的信息:n,H);for(k=1;kadjvex=j;s-next=adjlisti.link;adjlisti.link=s;s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=i;s-next=adjlistj.link;adjlistj.link=s;3.3邻接表

11、输出通过creatAdjList()来建立图3-1的邻接表，由于建立每个边表对应的单链表时采用的头插法，个遍表中的邻接点序号一定是从大到小排序的，从而得到图3-3样式的运行输出邻接表。1-3-22-5-4-13-7-6-14-8-25-8-26-7-37-6-38-5-4图3-3邻接表程序输出样式代码：SeQueue*initSeQueue()SeQueue*q;q=(SeQueue*)malloc(sizeof(SeQueue);q-front=MAXSIZE-1;q-rear=MAXSIZE-1;return q;int emptySeQueue(SeQueue*sq)if(sq-fron

12、t=sq-rear)return 1;else return 0; int enSeQueue(SeQueue*sq,DataType x) if(sq-rear+1)%MAXSIZE=sq-front) printf(队满);return 0; elsesq-rear=(sq-rear+1) % MAXSIZE; sq-datasq-rear=x; return 1; DataType deSeQueue (SeQueue * sq)if (emptySeQueue (sq)printf(列队为空); return 0;elsesq-front=(sq-front+1)%MAXSIZE;re

13、turn sq-datasq-front;3.4输出DFS遍历模块 实现深度优先搜索遍历算法，首先访问出发点vi，置访问标记为1，然后找到vi的一个邻接的未被访问过的点vj，从vj出发继续进行深度优先搜索。图的深度优先搜索过程是递归的，当找不到vi邻接的未被访问过的点时，递归返回它的特点是尽可能先对图从纵深方向进行搜索，生成DFS遍历序列和与之对应的DFS生成树。V1V3V2V4V5V8V6V7图3-4 DFS生成树代码：void DFSL(int i)EdgeNode *p;printf(%c,adjlisti.vertex);visitedi=1;p=adjlisti.link;while

14、(p)if(!visitedp-adjvex)DFSL(p-adjvex);p=p-next;3.5输出BFS遍历模块 实现广度优先搜索遍历算法，除了需要记录图中的顶点是否被访问过以外，还要保存顶点访问的序列，并且此序列在广度优先搜索遍历的过程中是按照先进先出的原则使用的，也就是说，在图的广度优先搜索遍历过程中需要用一个队列来辅助实现（相当于图的深度优先搜索遍历过程中栈的作用）。实现广度优先搜索遍历时，按照访问顶点的次序也可以得到BFS序列和与之对应的BFS生成树。V1V3V2V4V5V8V6V7图3-5 BFS生成树代码：void BFSL(int k)int i;EdgeNode * p;

15、sq=initSeQueue();printf(%c,adjlistk.vertex);visitedk=1;enSeQueue(sq,k);while(!emptySeQueue(sq) i=deSeQueue(sq);p=adjlisti.link;while (p!=NULL)if(!visitedp-adjvex)printf(%c,adjlistp-adjvex.vertex);visitedp-adjvex=1;enSeQueue(sq,p-adjvex);p=p-next;4系统测试程序调试成功，运行结果如下：图4-1程序主菜单 邻接表建立过程，输入顶点个数根据无向图3-1输入8

16、enter，根据提示输入顶点信息12345678enter。根据提示继续输入边的个数9enter，根据提示继续输入9条边的信息，输入方法“头空尾enter”输入边的数目达到设定个数，邻接表建立成功。如图4-2所示。图4-2建立邻接表程序邻接表输出过程，根据creatAdjList()运行得出邻接表。如图4-3所示。图4-3邻接表输出程序 DFS遍历序列输出，通过DFSL(int i)成功输出DFS便利序列：13762584 。如图4-4所示。图4-4 DFS遍历输出程序 DFS遍历序列输出，通过void BFSL(int k)成功输出BFS便利序列：13276584 。如图4-5所示。图4-5

17、 BFS遍历输出程序总 结两周的课程设计终于成功的收尾了,虽然有些疲惫但是收获还是蛮多的,我巩固了所学到的知识,之前的学习只是停留在理论的基础上现在自己动手实践后才会真正的理解和运用。数据结构也学了近一年,很多知识也是似懂非懂,通过平时的上机操作自己也了解一些,但让我有更深的理解和更好的认识则是在这个课程设计上,之前的困惑也了解决了很多,虽然不能够全面的理解,但是有进步还是挺开心的。在课程设计之前有在电脑上调试程序的经验,了解写程序代码是很重要的,因为当你把代码输进去以后,并编译让其运行,发现通过不了,在来检查是那里出现的错误是非常麻烦的,因此分析和规划代码是非常重要。通过本次课程设计,进一步

18、的了解了课程设计的流程,学会了怎么去借鉴别人方法和经验,知道了如何整理材料是设计最快的完成这为以后设计毕业论文打下了基础,更让我高兴的是一份成功的喜悦,带领团队结合每个人不同的特点来分配任务,尽量的发挥小组每个人的力量,是课程设计圆满完成任务。在本次课程设计我也认识到了自己的不足,缺乏经验,没能够熟练的使用word的基本工具。所以在以后还是要加倍的努力,这次课程设计成为以后的基础和经验,我将再接在力,把以后的课程设计和毕业论文做的更加完美。参考文献1 严蔚敏.吴伟民著.数据结构(C语言版). 北京：清华大学出版.1999年第一版2 陈一华等编.数据结构(C 语言). 北京：电子科技大学出版社.

19、1998年第一版3 谭浩强.C语言程序设计（第二版）.北京：高等教育出版社.20024 布鲁志著. 吴丹等译面向对象的软件工程构建复杂且多变的系统北京：清华大学出版社2002.10 5 李瑞. 徐克圣. 刘月凡. 戚海英. C程序设计基础M. 北京：清华大学出版社. 2009.76 薛圆圆C语言开发手册. 北京：电子工业出版社. 2011.4 附 录#include#include#define MAXSIZE 1024#define N 8#define E 9typedef char VexType;typedef int AdjType;typedef intDataType;typed

20、ef structDataType dataMAXSIZE;int rear,front;SeQueue;SeQueue * sq;typedef struct nodeint adjvex;struct node * next;EdgeNode;typedef structVexType vertex;EdgeNode * link;VexNode;int visitedN+1;VexNode adjlistN+1;void creatAdjList() int i,j,k,M,H; EdgeNode*s;printf(请输入顶点个数);scanf(%d,&M);printf(请输入每个顶点

21、信息:,M);getchar();for(i=1;i=M;i+) adjlisti.vertex=getchar(); adjlisti.link=NULL;printf(请输入条的边数);scanf(%d,&H);printf(请输入%d条边的信息:n,H);for(k=1;kadjvex=j;s-next=adjlisti.link;adjlisti.link=s;s=(EdgeNode*)malloc(sizeof(EdgeNode);s-adjvex=i;s-next=adjlistj.link;adjlistj.link=s;SeQueue*initSeQueue()SeQueue*

22、q;q=(SeQueue*)malloc(sizeof(SeQueue);q-front=MAXSIZE-1;q-rear=MAXSIZE-1;return q;int emptySeQueue(SeQueue*sq)if(sq-front=sq-rear)return 1;else return 0; int enSeQueue(SeQueue*sq,DataType x) if(sq-rear+1)%MAXSIZE=sq-front) printf(队满);return 0; elsesq-rear=(sq-rear+1) % MAXSIZE; sq-datasq-rear=x; retu

23、rn 1; DataType deSeQueue (SeQueue * sq)if (emptySeQueue (sq)printf(列队为空); return 0;elsesq-front=(sq-front+1)%MAXSIZE;return sq-datasq-front;void DFSL(int i)EdgeNode *p;printf(%c,adjlisti.vertex);visitedi=1;p=adjlisti.link;while(p)if(!visitedp-adjvex)DFSL(p-adjvex);p=p-next;void BFSL(int k)int i;Edge

24、Node * p;sq=initSeQueue();printf(%c,adjlistk.vertex);visitedk=1;enSeQueue(sq,k);while(!emptySeQueue(sq) i=deSeQueue(sq);p=adjlisti.link;while (p!=NULL)if(!visitedp-adjvex)printf(%c,adjlistp-adjvex.vertex);visitedp-adjvex=1;enSeQueue(sq,p-adjvex);p=p-next;void main()/主函数/int i,m;EdgeNode *p;while(1)p

25、rintf(n*n);printf(* 输入1：建立邻接表 *n);printf(* 输入2：输出邻接表 *n);printf(* 输入3：输出DFS遍历 *n);printf(* 输入4：输出BFS遍历 *n);printf(* 输入0：退出程序 *n);printf(*n);printf(*请选择要执行的操作: *n);scanf(%d,&m);switch(m)case 1: creatAdjList();printf(邻接表建立成功!n);break;case 2:for(i=1;i,adjlisti.vertex); p=adjlisti.link; while(p) printf(%c,adjlistp-adjvex.vertex); if(p-next)printf(-); p=p-next; printf(n); break;case 3:printf(nDFS遍历序列：); DFSL(1); for(i=1;i=N;i+) visitedi=0;/将标志数组清零/ break;case 4:printf(nBFS遍历序列：); BFSL(1); for(i=1;i=N;i+) visitedi=0;/将标志数组清零/ break;case 0:return;default:printf(请重新选择!);55break;20