《图的遍历的实现课程设计.doc》由会员分享，可在线阅读，更多相关《图的遍历的实现课程设计.doc（25页珍藏版）》请在三一办公上搜索。
1、精选优质文档-倾情为你奉上学 号： 课 程 设 计题 目图的遍历的实现学 院计算机科学与技术学院专 业软件工程班 级姓 名指导教师2013年12月23日 课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位：计算机科学与技术学院 题 目: 图的遍历的实现初始条件：理论：学习了数据结构课程，掌握了一种计算机高级语言。实践：计算机技术系实验中心提供计算机及软件开发环境。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、系统应具备的功能：1)先任意创建一个图；2)图的DFS,BFS的递归或非递归算法的实现3)要求用有向图或无向图分别实现4)要求用邻接矩阵、邻
2、接表多种结构存储实现2、数据结构设计；3、主要算法设计；4、编程及上机实现；5、撰写课程设计报告，包括：（1）设计题目；（2）摘要和关键字（中文和英文）；（3）正文，包括引言、需求分析、数据结构设计、算法设计、有关技术的讨论、设计体会等；（4）结束语；（5）参考文献。时间安排： 2013年12月16日-25日12月19日 查阅资料12月20日 系统设计12月21日-22日 编程并上机调试12月23日 撰写报告12月24日 验收程序，提交设计报告书 指导教师签名： 2013年12月14日系主任（或责任教师）签名： 年 月 日图的遍历的实现摘要 本课程设计主要目的在于更深一步的了解图的遍历的问题，
3、图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图分别实现图的遍历，广度优先遍历和深度优先遍历的实现，用邻接矩阵和邻接表等多种结构存储存储图。在课程设计中，程序设计设计语言采用Visual C，程序运行平台为Windows 98/2000/XP。在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。程序最终通过调试运行，初步实现了设计目标。关键词 程序设计；数据结构；有向图；无向图；存储结构；邻接矩阵；递归算法Abstract The purpose of this course
4、 design is to further understand the problem of graph traversal, figure DFS and BFS recursive and non-recursive algorithms of implementation, using directed graph and undirected graph, graph traversal is implemented, breadth-first traversal and the realization of the depth-first traversal, using adj
5、acency matrix and adjacency list and so on the many kinds of structure to store.In curriculum design, using Visual C programming design language, application platform for Windows XP / 98/2000.In programming is given a figure I mainly solve how to use a variety of methods to complete graph traversal
6、problems, including how to create a figure, depth-first traversal and breadth-first traversal a figure, the method of recursive and non-recursive traversal graph.Program debugging and running, ultimately through preliminary design goal is realized. Keywords program design;Data structure;Directed gra
7、ph;Undirected graph.Storage structure;Adjacency matrix目录1.引 言 数据结构是计算机科学与技术专业的一门核心专业基础课程，是一门理论性强、思维抽象、难度较大的课程。在软件工程专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力。我认为学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，我们应该能从中抽象出一个适当的数学模型，该数学模型在计
8、算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。 图是一种非常重要的数据结构，在数据结构中也占着相当大的比重。这个学期的数据结构课程中，我们学习了很多图的存储结构，有邻接矩阵、邻接表、十字链表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是把图的边信息存储在一个矩阵中，是一种静态存储方法。图的邻接表存储结构是一种顺序存储与链式存储相结合的存储方法。从空间性能上说，图越稀疏邻接表的空间效率相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要低。 本课程设计主要是实现使用邻接表存储结构存储一个图，并在所
9、存储的图中实现深度优先和广度优先遍历以及其链表结构的输出。 2. 需求分析2.1 原理当图比较稀疏时，邻接表存储是最佳的选择。并且在存储图的时候邻接表要比邻接矩阵节省时间。在图存储在系统中后，我们有时还需要对图进行一些操作，如需要添加一个顶点，修改一个顶点，或者删除一个顶点，而这些操作都需要一图的深度优先及广度优先遍历为基础。本系统将构建一个图，图的结点存储的是int型数据。运行本系统可对该图进行链式结构输出、深度优先及广度优先遍历。控制方法如下： 表2-1 控制键的功能 控制键 1 2 3 功能 广度优 先遍历 深度优 先遍历 退出 程序 2.2要求 (1)先任意创建一个图； (2)图的DF
10、S,BFS的递归或非递归算法的实现 (3)要求用有向图或无向图分别实现 (4)要求用邻接矩阵、邻接表多种结构存储实现2.3 运行环境 (1)WINDOWS 7系统 (2)C+ 编译环境2.4 开发工具C+语言3.数据结构分析本课程设计是针对于图的，程序中采用邻接表进行数据存储。在计算机科学中，邻接表 描述一种紧密相关的数据结构，用于表征图。在 邻接表的表示中，对于图中的每个顶点，我们将保存所有其它与之相连的顶点（即 “邻接表”）。 邻接表是一种顺序存储与链式存储相结合的存储方法，该存储方式在图比较稀疏是相对于图的邻接矩阵存储有明显优势。设计实现了图的邻接表结构输出、深度有新遍历和广度优先遍历操
11、作的实现。 3.1邻接表的结构：（1） 、头结点结构firstarcdata Firstarc：结点的指针域（2） 、邻接点的结构nextarcadjvex Adjvex：邻接点的数据域； Nextarc：邻接点的指针域，指向下一个邻接点；在该程序中，除了邻接表结构以外，还有到了一个mark数组，它是用来标记结点Vi是否被访问。若Vi被访问，则marki=1，否则为0；它是一个比较简单的一维数组。（注：在每次对图进行遍历之前mark都会被清零）3.2图的深度优先访问： 从图中每个顶点V出发，访问此顶点，然后依次从V的未访问邻接点出发深度优先遍历图，直至所有与V有通路的顶点被访问，否则选择另外未
12、访问点作为起点，重复上述过程。3.3图的广度优先遍历： 从图中每个顶点V出发，访问此顶点，然后依次访问V的 未访问邻接点，并保证先被访问的结点的邻接点先于后被访问的结点，直至所有与V有通路的顶点被访问，否则选择另外未访问点作为起点，重复上述过程。4. 算法设计4.1结构体定义及函数的声明（1）首先，要定义头文件，在头文件中定义邻接点point、图的基本结点graph以及在广度优先搜索中会用到队列queue。具体如下：struct point int n; /邻接点的序号point *next; /指向下一条弧节点的地址;struct graphint data; /表接点的数据struct p
13、oint *f; /结点的指针域，给出自该结点发出的第 一弧节点的地址;struct queueint elemd; /队列的容量int front; /front为首指针，指向第一个元素int rear; /rear为最后一个元素，指向队尾元素的下一个位置q; 其次，在头文件中还需定义邻接表存储结构下图的抽象数据类型定义。 （2）编写源文件，进行图的初始化，首先要输入顶点信息，初始化顶点表，在输入点v的值时，同时构造v的邻接点。输入邻接点的序号，最后生成一个邻接点链表。子函数功能：1.void creatgraph(int m) /n表示节点的个数 构造图的链表结构，在此函数中要输入图结点的
14、值，邻接点的序号。2.void print(struct graph a,int m) 将图a的链表结构打印出来,m为结点个数3.void dpv(struct graph a,int v) 对图进行深度优先遍历。先访问指定的顶点v，从该顶点的未被访问的邻接点中选取一个顶点p,从p出发进行深度优先遍历。重复以上的步骤，直至图中所有和v有路径相通的顶点都被访问到。4.void wdv(struct graph a,int v,queue &Q) 从v点开始广度优先遍历a是连通图或是连通分量），先访问顶点v，依次访问v的各个未被访问的邻接点v1,v2,vk,分别从,v1,v2,vk出发依次访问它们
15、未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问的顶点”被访问，直至图中所有与顶点v有路径相通的顶点都被访问到。5.void enqueue(queue &Q,int e) e入队列Q的队尾。 6.void delqueue(queue &Q,int &e) 删除队列Q的对首元素。7.int queueempty(queue &Q) 判断队列Q是否为空。（3）编写主函数。用数组存放图结点。输入所要进行的操作的序号，并设置每次只能选择一种功能，调用相应的函数，输出相应的结果。4.2 主要模块的算法描述（1）、深度优先遍历算法，利用递归void dpv(graph a,vtxptr v
16、0) /从点v开始进行深度访问 /a为连通图或非连通图的一个连通分量visit（v0）； /访问v结点markv0=1; /标记为已访问 w=v0的第一个邻接点；while(当邻接点w存在时1)if(w未访问)dpv(a,w);w=下一个邻接点；/dpv（2）、广度优先遍历算法，利用队列先入先出void wdv(graph a,vtxptr v)/从v点开始广度优先，a是连通图或是连通分量visit（v）； /访问点vmarkv=1; /并标记为以访问 initqueue（Q)；enqueue(Q,v);/v进队列while(!queueempty(Q)delqueue(Q,v1);w=v1的
17、第一个邻接点；while(当邻接点w存在时)if(w为访问)visit（w）； markw=1; enqueue(Q,w);w=下一个邻接点； /wdv4.3 函数调用图5. 程序实现及测试5.1 创建工程并建立文件（1）启动Microsoft Visual C+ 6.0。（2）新建工程名为“课程设计” 的Win32控制台应用程序。（3）建立头文件“邻接表.cpp”，在其中定义图的创建函数creategraph()、深度优先遍历的函数dpv()、广度优先遍历的函数wdv()、输出函数print（）以及main（），通过main （4）调用其他函数来实现对图的操作。6. 心得体会通过这次课程设计
18、，我受益颇多：首先，上课时听的理论知识，似乎很容易接受，以及各种算法都能够比较轻松的理解，但是在真正的运用过程中，并不能把理论知道很好的和实践结合起来。感觉自己有点眼高手低，有些知识点的应用只有在实践中才能慢慢体会，在平时做实验时，总感到有些无从下手。因此，在学知识的过程中，一定要多动手、动脑，将所学的知识熟练掌握，自如运用。其次，通过这次课程设计，对我的逻辑思维能力是一个很大的锻炼，再有，它还加强了我的系统思考问题的能力，在编程方面，我开始从整体的角度来考虑问题了，而不再像以前一样的，胡乱动手。也就是因为先前的这种编程习惯，使得我在课程设计过程中浪费了不少的时间，尝到了教训。通过这次课程设计
19、，我学习了很多平时很少关注的知识点，比如循环链，递归的应用，也增强了自己的实践能力和编写程序的能力。图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。用邻接矩阵作为图的数据存储结构很好地解决了图的结构难点， 借助于邻接矩阵容易判定任意两个顶点之间是否有边(或弧)相连，并容易求得各个顶点的度。该程序通俗易懂且实用性强，并且该程序清单详细具体、全面、具有很强的可读性；系统整体上比较完美，可以从键盘获取输入元素，并且可以根据用户输入进行选择性地输出；整体输出画面效果整洁、大方。 7.结束语 经过几天的努力，黄天不负苦心人，我的课
20、程设计终于完成了。本课程设计主要运用数据结构知识和C+程序设计完成了用邻接表存储结构实现对图的操作。该系统的主要功能为：图的链式结构输出、深度优先遍历、广度优先遍历。 在这次数据结构的课程设计中，曾遇到过一些问题，但是经过查找资料都已经得到解决，也正是因为这些问题引发的思考给我带了收获。所以我认为只要我们有耐心和信心，我们一定能解决问题。再次对给过我帮助的所有同学和各位指导老师表示忠心的感谢！没有你们的帮助我想我是不能这么好的完成这项工作的。参考文献1 严蔚敏、吴伟民著.数据结构（C语言版）.-北京清华大学出版社2 谭浩强著， C程序设计，-3版，-北京：清华大学出版社3 薛超英著.数据结构（
21、第二版）用Pascal语言、C+语言对照描述算法. -武汉：华中科技大学出版社4 李陶深、赵文静著. 面向对象程序设计与方法. -武汉：武汉理工大学出版社附源程序清单和运行结果/ 程序名称：TUDEBIANLI.C/ 程序功能：采用递归和非递归算法，有向图和无向图，邻接矩阵和邻接表等多种结构存储实现图的遍历。#includestdio.h#includestdlib.h#define INFINITY 32767 #define MAX_VEX 20 /最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) /队列长度 bool *visited;/访问标志数组 int z
22、=1; /图的邻接矩阵存储结构 typedef struct char *vexs; /顶点向量 int arcsMAX_VEXMAX_VEX; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 Graph; class Queue /队列类 public: void InitQueue() base=(int *)malloc(QUEUE_SIZE*sizeof(int); front=rear=0; void EnQueue(int e) baserear=e; rear=(rear+1)%QUEUE_SIZE; void DeQueue(int &e) e=bas
23、efront; front=(front+1)%QUEUE_SIZE; int *base; int front; int rear; ; int Locate(Graph G,char c) /图G中查找元素c的位置for(int i=0;iG.vexnum;i+) if(G.vexsi=c) return i; return -1; void CreateUDN(Graph &G) /创建无向网int i,j,w,s1,s2; char a,b,c,temp; printf(输入顶点数和弧数:); scanf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(
24、); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf(输入%d个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化顶点 scanf(%c,&G.vexsi); temp=getchar(); /接收回车 for(i=0;iG.vexnum;i+) /初始化邻接矩阵 for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; printf(输入%d条弧.n,G.arcnum); for(i=0;i=0 & kG.vexnum) /k合理 for(int i=
25、0;i=0 & i=0 & jG.vexnum) /i,j合理 for(int k=j+1;kG.vexnum;k+) if(G.arcsik!=INFINITY) return k; return -1; /深度优先遍历 void DFS(Graph G,int k) int i; if(k=-1) /第一次执行DFS时,k为-1 for(i=0;i %c,G.vexsk); +z;/访问第k个顶点 if(z-1)%G.vexnum=0) z=1;for(i=FirstVex(G,k);i=0;i=NextVex(G,k,i) if(!visitedi) DFS(G,i); /对k的尚未访问
26、的邻接顶点i递归调用DFS /广度优先遍历 void BFS(Graph G) int k; Queue Q; /辅助队列Q Q.InitQueue(); for(int i=0;i=0;w=NextVex(G,k,w) if(!visitedw) /w为k的尚未访问的邻接顶点 visitedw=true; printf(- %c ,G.vexsw); Q.EnQueue(w); printf(n 请继续选择:n); void choose(Graph G)/对输入选项调用相应的函数执行操作int i,m; visited=(bool *)malloc(G.vexnum*sizeof(bool
27、);scanf(%d,&m);switch(m)case 1: printf(广度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; BFS(G); choose(G); printf(n);break;case 2:printf(深度优先遍历: ); for(i=0;iG.vexnum;i+) visitedi=false; DFS(G,-1); printf(n 请继续选择:n);choose(G);break; case 3:printf(程序结束.); break;default : printf( 输入错误!n请在1-3中选择:n); cho
28、ose(G); /主函数 void main() int i,m; Graph G; CreateUDN(G); printf(有如下选项供选择：n);printf(*n);printf(|*| 1:广度优先遍历 2:深度优先遍历 3:退出本程序！|*|n);printf(*n);printf(请选择(1-3):n);choose(G); 运行结果（截图）程序运行如图3所示：图3 输入图的顶点数和弧数 图4 输入各个顶点和各条弧 图5 选择图的遍历方式 本科生课程设计成绩评定表姓 名性 别专业、班级课程设计题目： 课程设计答辩或质疑记录：成绩评定依据：最终评定成绩（以优、良、中、及格、不及格评定）指导教师签字： 年 月 日专心-专注-专业
