《图的建立与遍历》数据结构课程设计

1、届课程设计图的建立与遍历图的建立与遍历课程设计论文课程设计论文学生姓名 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机 指导教师 教师职称 讲师 塔里木大学教务处制塔里木大学信息工程学院课程设计第 1 页 共 10 页目录目录前言前言.1正文正文.11.1 课程设计的教学目的和任务.11.2 课程设计的主要内容.11.3 课程设计报告的要求 .22.1.问题描述及基本要求.22.2.算法思想.22.3 模块划分.32.3.1 深度优先搜索.32.3.2 广度优先搜索法.42.3.3 分析与探讨.42.3.4 图的存储.52.4 测试数据.82.5 测试情况 .8总总

2、结结 .1010参考文献：参考文献： .1010附附 录录 .1111课程总结课程总结 .1414塔里木大学信息工程学院课程设计第 0 页 共 10 页前言前言图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。 由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面: 在图结构中，没有一个自然的首结点，图中任意一个顶点都可作为第一个被访问的结点。 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有

3、顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。正文正文1.1 课程设计的教学目的和任务(1) 使学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。(2) 使学生初步掌握软件开发过程的问题分析、设计、编码、测试等基本方法和基本技能。(3) 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。(4) 使学生能用系

4、统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计的主要内容(1) 问题分析和任务定义。根据题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？(2) 逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明） ，各个主要模块的算法，并画出模块之间的调用关系图。(3) 物理设计。定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰

5、、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。(4)程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。(5) 程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。(6) 结果分析。程序运行结果包括正确的输入及其输出结果和含有错

6、误的输入及其输出结果。算法的时间、空间复杂性分析。塔里木大学信息工程学院课程设计第 1 页 共 10 页(7) 撰写课程设计报告。1.3 3 课程设计报告的要求课程设计报告要求规范书写。应当包括如下内容： 问题描述：描述要求编程解决的问题。 基本要求：给出程序要达到的具体的要求。 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。 算法思想：描述解决相应问题算法的设计思想。 模块划分：描述所设计程序的各个模块（即函数）功能。 数据结构：给出所使用的基本抽象数据类型，所定义的具体问题的数据类型，以及新定义的抽象数据类型。 源程序：给出所有源程序清单，要求程序有

7、充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。 测试情况：给出程序的测试情况，并分析运行结果。 算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；经验和体会等。 参考文献：列出参考的相关资料和书籍。2.1.2.1.问题描述及基本要求利用深度优先搜索和广度优先搜索完成出具的排序。/要求建立一个菜单，菜单包含 4个菜单项供选择：1、建立图的邻接矩阵；2、建立图的邻接表； 3、对图进行深度优先遍历；4、对图进行广度优先遍历。要求从键盘输入无向有权图的顶点数、边数、每条边的起始顶点序号、终点序号、权值，将每条边的信息存入到邻接矩阵和邻接表中。从键盘输入

8、深度优先遍历和广度优先遍历图时初始出发的顶点的序号，要求在遍历过程中输出访问过的结点序号。2.2. 算法思想遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点 v 的所有边都已被探寻过，搜索将回溯到发现结点 v 有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行

9、直到所有结点都被发现为止。深度优先搜索基本算法如下递归算法：PROCEDURE dfs_try(i);FOR i:=1 to maxr DOBEGINIF 子结点 mr 符合条件 THENBEGIN产生的子结点 mr 入栈；IF 子结点 mr 是目标结点 THEN 输出ELSE dfs_try(i+1);栈顶元素出栈;塔里木大学信息工程学院课程设计第 2 页 共 10 页END;END; 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta 单源最短路径算法和 Prim 最小生成树算法都采用了与宽度优先搜索类似的思想。宽度优先

10、搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点，如此依次扩展，直到发现目标结点为止。宽度优先搜索基本算法如下：list1:=source; 加入初始结点，list 为待扩展结点的表head:=0; 队首指针foot:=1; 队尾指针REPEAThead:=head+1;FOR x:=1 to 规则数 DOBEGIN根据规则产生新结点 nw;IF not_appear(nw,list) THEN 若新结点队列

11、中不存在，则加到队尾BEGINfoot:=foot+1;listfoot:=nw;listfoot.father:=head;IF listfoot=目标结点 THEN 输出；END；END；UNTIL headfoot; 队列为空表明再无结点可扩展2.32.3 模块划分2.3.1 深度优先搜索深度优先搜索深度优先搜索法是树的先根遍历的推广，它的基本思想是:从图 G 的某个顶点 v0 出发，访问 v0，然后选择一个与 v0 相邻且没被访问过的顶点 vi 访问，再从 vi 出发选择一个与vi 相邻且未被访问的顶点 vj 进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到

12、已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点 w，从 w 出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下: Boolean visitedMAX_VERTEX_NUM; /访问标志数组 Status (*VisitFunc)(int v); /VisitFunc 是访问函数，对图的每个顶点调用该函数 void DFSTraverse (Graph G, Status(*Visit)(int v) VisitFunc = Visit; for(v=0; vG.vexnum; +v) visitedv = FALSE; /访问标志数组初始化 for(v=0; v=0

13、; w=NextAdjVex(G,v,w) /FirstAdjVex 返回 v 的第一个邻接顶点，若顶点在 G 中没有邻接顶点，则返回空(0)。 /若 w 是 v 的邻接顶点，NextAdjVex 返回 v 的(相对于 w 的)下一个邻接顶点。 /若 w 是 v 的最后一个邻接点，则返回空(0)。 if(!visitedw) DFS(G, w); /对 v 的尚未访问的邻接顶点 w 调用 DFS 2.3.2 广度优先搜索法图的广度优先搜索是树的按层次遍历的推广，它的基本思想是:首先访问初始点 vi，并将其标记为已访问过，接着访问 vi 的所有未被访问过的邻接点 vi1,vi2, vi t，并均

14、标记已访问过，然后再按照 vi1,vi2, vi t 的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点 vi 有路径相通的顶点都被访问过为止。其非递归算法如下: Boolean visitedMAX_VERTEX_NUM; /访问标志数组 Status (*VisitFunc)(int v); /VisitFunc 是访问函数，对图的每个顶点调用该函数 void BFSTraverse (Graph G, Status(*Visit)(int v) VisitFunc = Visit; for(v=0; vG.vexnum, +v) visit

15、edv = FALSE; initQueue(Q); /置空辅助队列 Q for(v=0; v=0; w=NextAdjVex(G,u,w) if(!Visitedw) /w 为 u 的尚未访问的邻接顶点 Visitedw=TRUE; VisitFunc(w); EnQueue(Q, w); 2.3.3 分析与探讨目录结构是一种典型的树形结构，为了方便对目录的查找，遍历等操作，可以选择孩子兄弟双亲链表来存储数的结构。程序中要求对目录的大小进行重新计算，根据用户的输入来建立相应的孩子兄弟双亲链表，最后输入树形结构。可以引入一个 Tree 类，将树的构造，销毁，目录大小的重新计算（reSize）

16、，建立树形链表结构（parse） ，树形结构输出（outPut）等一系列操作都封装起来，同时对于每一个树的借点，它的私有变量除了名称（Name） ，大小（Size）和层数（Depth）之外，根据孩子兄弟双亲链表表示的需要，还要设置三个指针，即父指针（Tree*parent）,下一个兄弟指针（Tree*NextSibling）和第一个孩子指针（Tree*Firstchild） 。下面是几个主要函数的实现。1.建立树形链表结构的函数 parse()根据输入来确定树形关系是，首先读取根借点目录/文件名和大小值，并根据这些信息建立塔里木大学信息工程学院课程设计第 4 页 共 10 页一个新的节点；然后

17、读入后面的各行信息，对于同一括号中的内容，即具有相同父节点的那些节点建立兄弟关联。这个函数实际上是采用层数遍历建立树形链表结构。定义一个Tree*类型的数组 treeArray ，用来存放目录的节点信息，并定义两个整型变量 head 和rear，head 值用来标记当前节点的父节点位置，每处理完一对括号，head 需要增加 1,即下一对待处理括号的父节点在 treeArray 中要往后移一个位置。如果当前处理的节点是目录类型，则将它放在 treeArray 数组中，rear 是 treeArray 的下标变量，加入一个树的节点，并和 head 所指的父节点建立关联，但是不用放入 treeArr

18、ay 中。2.目录大小重新计算函数reSize()输入数据中对目录大小的初始化值一般为 1，而目录的真正大小应该是自身的大小和它包含的所有文件及子目录的大小之和。因此，在计算目录大小的时候，需要遍历它下面所有的文件和子目录，可以采用递归嵌套的后序遍历方式。另外要注意，采用孩子兄弟双亲链表表示时，父目录下的所有子目录和子文件都在该父目录的左子树上（右字数第一个节点是该目录的兄弟节点） ，所以遍历的时候只需要遍历目录的左字数即可。3.输出树形结构的函数 outPut()输出是一个线序遍历的过程。为完成对树形的输出，兄弟目录之前需要相同的缩进，用|上下相连，而斧子目录或父目录和子文件之间需要设定正确

19、的缩进，子目录或子文件要比父目录向右缩进 8 个空格。设置一个标志数组 flag11（每个目录下最大层次数为 10） ，当前 Tree*temp 指针所指的节点如果有兄弟节点，则置 flag 数组值为 1，否则置为 0；并由此节点反复查询它的祖先节点的情况，知道根节点位置。输出时，遇到flag =1 时，屏幕输出“| ” ，表明是兄弟节点；遇到 flag =0 时则输出“ ” ，这样就可以保证兄弟节点之间有相同的缩进，而子节点总比父节点享有缩进 8 个空格。2.3.4 图的存储图的存储图的深度优先遍历假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从

20、 v 未被访问的邻接点出发深度优先遍历图，直至图中所有和 v 有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。具体过程应为：先访问初始点 Vi，并标志其已被访问。此时定义一指向边结点的指针 p，并建立一个 while（）循环，以指针所指对象不为空为控制条件，当 Vi 的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将 p 指针指向下一个边结点。这样就可以完成图的深度优先遍

21、历了。图的广度优先遍历：广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点 v 出发，在访问了 v 之后访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尙有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以 v 为起始点，由近及远，依次访问和 v 有路径相通且路径长度为 1，2，的顶点。所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组以标记结点是否

22、被访问。同样，也是从初始点出发开始访问，访问初始点，标志其已被访问，并将其入队。当队列非塔里木大学信息工程学院课程设计第 5 页 共 10 页空时进行循环处理。当结点被访问时对其进行标志，并入队列。通过 while（）循环，并以是否被访问为控制条件，访问所有结点，完成图的广度优先遍历。定义邻接表的边结点类型以及邻接表类型：struct edgenodeint adjvex; /该弧所指向的顶点的位置 edgenode * next; /指向下条条弧的指针; /定义邻接表的边结点类型typedef edgenode * * adjlist; /定义邻接表类型初始化图的邻接表：需建立一个邻接表初始

23、化函数对图的邻接表进行初始化。即建立一个所有边结点都为空的邻接表。void InitGAdjoin(adjlist&GL,int n)/初始化图的邻接表GL=new edgenode*n;for(int i=1;i=n;i+)GLi=NULL;建立并输出图的邻接表首先必须输入图的相关信息，包括图的顶点数、边数、各条边的起点和终点，为保证输入数据的正确性，我在程序中设计了一个判断所输结点是否越界的函数 check（）当所输的顶点序号超出序号的范围时则报错，并要求重新输入。还有就图是否有向，此时可定义一变量，图的是否有向，可用变量的值来表示。此处定了变量 m，当图为无向时，m 等于 0。图

24、为有向时 m 等于 1。用 if（）语句判断 m 的值，就可将图分有向和无向两种情况来进行分析了。对于无向图，各条边的起点和终点互为邻接点。所以必须把起点添加到终点的邻接点域中，并把终点添加到起点的邻接点域中。而对于有向图，只能是将弧头添加到弧尾的邻接点域中。最后是输出邻接表，即对于每个顶点，输出其邻接点。由于不了解 C+中绘图函数的用法，所以利用一些符号来达到图形化的效果。邻接表输出的相关代码如下：cout图的邻接表为:endl;for(i=1;i=n;i+)edgenode*p=GLi;couti-1 |Vnext)cout|adjvex;cout|;塔里木大学信息工程学院课程设计第 6

25、页 共 10 页coutendl; /输出邻接表图的遍历图的遍历深度优先遍历图的邻接表：假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从 v 未被访问的邻接点出发深度优先遍历图，直至图中所有和 v 有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度优先搜索函数中必须设一标志数组以标记结点是否被访问。具体过程应为：在深度优先遍历函数的参数中定义一个标志数组 bool*& visit

26、ed，当某结点已被访问时，标志数组的值为关键字 ture，未被访问时其值为关键字 false。先访问初始点 Vi，并标志其已被访问。此时定义一指向边结点的指针 p，并建立一个 while（）循环，以指针所指对象不为空为控制条件，当 Vi的邻接点未被访问时，递归调用深度优先遍历函数访问之。然后将 p 指针指向下一个边结点。这样就可以完成图的深度优先遍历了。深度优先遍历的相关代码如下：void dfsAdjoin(adjlist GL,bool*& visited,int i,int n)/从初始点出发深度优先搜索邻接表 GL 表示的图coutiadjvex; /j 为 Vi 的一个邻接点

27、的序号if(!visitedj)dfsAdjoin(GL,visited,j,n);p=p-next; /使 p 指向 Vi 单链表的下一个边结点广度优先遍历图的邻接表广度优先遍历图的邻接表：图的广度优先遍历是从初始点出发，访问初始点，再访问初始点的邻接点。当初始点的所有邻接点都被访问过时，再依次访问各邻接点的邻接点。如此循环下去。算法的实现必须依靠辅助队列，结点被访问后，对其进行标记，并将结点入队列。所以要实现算法必须先建立一个元素类型为整形的空队列，并定义队首与队尾指针，同时也要定义一个标志数组 bool*& visited 以标记结点是否被访问。塔里木大学信息工程学院课程设计第

28、7 页 共 10 页同样，也是从初始点 Vi 出发开始访问，访问初始点，标志其已被访问，并将已访问过的初始点序号 i 入队。当队列非空时进行循环处理，删除队首元素，第一次执行时 k 的值为 i，即 front=(front+1)%MaxLength。然后取 Vk 邻接表的表头指针 int k=qfront; edgenode* p=GLk。当边结点指针 p 不为空时，通过while（）循环，并以 p 是否为空为控制条件，依次搜索 Vk 的每一个结点。若Vj 没有被访问过则进行处理。访问完后，将 p 指向 p-next。其中的 while 循环部分的代码如下：while(p!=NULL) /依次

29、搜索 Vk 的每一个结点int j=p-adjvex; /Vj 为 Vk 的一个邻接点if(!visitedj) /若 Vj 没有被访问过则进行处理coutjnext;这样就可以访问所有结点，完成图的广度优先遍历2.4 测试数据输入顶点数和弧数:8 9 输入 8 个顶点. 输入顶点 0:a 输入顶点 1:b 输入顶点 2:c 输入顶点 3:d 输入顶点 4:e 输入顶点 5:f 输入顶点 6:g 输入顶点 7:h 输入 9 条弧. 输入弧 0:a b 1 输入弧 1:b d 1 输入弧 2:b e 1 输入弧 3:d h 1 输入弧 4:e h 1 输入弧 5:a c 1 输入弧 6:c f

30、1 输入弧 7:c g 1 输入弧 8:f g 1 塔里木大学信息工程学院课程设计第 8 页 共 10 页2.5 测试情况输入数据后出现的效果：图图 1 1 编译初始界面编译初始界面塔里木大学信息工程学院课程设计第 9 页 共 10 页图图 2 2 编码界面编码界面小小 结结通过该题目的设计过程,对数据结构以及二叉树的逻辑结构,存储结构的理解,对树的数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意自己各个方面的能力的协调发展。在课程设计时我遇到

31、了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。参考参考文献：文献：1谭浩强编著.C+课程设计.北京：清华大学社，20042S.B.Lippman，J.Lajoie 著.潘爱民译.C+Primer（3rd Edition）中文版.北京：中国电力出版社，20023H.M.Deitel，Paul James Deitel 著.薛万鹏译.C+程序设计教程.北京：机械工业出版社，20004Stephen R.Savis 著.C+ For Dummies 4th edition，IDG Books World

32、wide，Inc.，20025Harvey M.Deitel .Jack W.Davidson 著.邱仲潘译.C+大学教程（第二版）.北京：电子工业出版社，20026James P.Cohoon.Jack W.Davidson 著.刘瑞挺等译.C+程序设计（第三版）.北京：电子工业出版社 塔里木大学信息工程学院课程设计第 10 页 共 10 页附附 录录#include /#include #define INFINITY 32767 #define MAX_VEX 20 /最大顶点个数 #define QUEUE_SIZE (MAX_VEX+1) /队列长度 using namespace

33、std; bool *visited; /访问标志数组 /图的邻接矩阵存储结构 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; vo

34、id DeQueue(int &e) e=basefront; front=(front+1)%QUEUE_SIZE; public: int *base; int front; int rear; ; /图 G 中查找元素 c 的位置 int Locate(Graph G,char 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,temp; printf(输入顶点数和弧数:); sc

35、anf(%d%d,&G.vexnum,&G.arcnum); temp=getchar(); /接收回车 G.vexs=(char *)malloc(G.vexnum*sizeof(char); /分配顶点数目 printf(输入%d 个顶点.n,G.vexnum); for(i=0;iG.vexnum;i+) /初始化顶点 printf(输入顶点%d:,i); scanf(%c,&G.vexsi); 塔里木大学信息工程学院课程设计第 11 页 共 10 页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=0;i=0 & i=0 & jG.vexnum) /i,j 合理 fo