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

1、届课程设计?图的建立与遍历?课程设计论文学生姓名 学 号 所属学院 信息工程学院 专 业 计算机科学与技术 班 级 计算机 指导教师 教师职称 讲师 塔里木大学教务处制目录前言1正文11.1 课程设计的教学目的和任务11.2 课程设计的主要内容12222.3 模块划分334452.4 测试数据8 测试情况8总 结10参考文献：10附 录11课程总结14前言图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种根本操作，图的许多其它操作都是建立在遍历操作的根底之上。 由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面: 在图结构中，没有一个自然的首结点，图中任意一个顶点都可作为第一个被访问的结点。 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶

2、点访问过后，存在如何选取下一个要访问的顶点的问题。正文1.1 课程设计的教学目的和任务(1) 使学生进一步理解和掌握所学的各种根本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。(2) 使学生初步掌握软件开发过程的问题分析、设计、编码、测试等根本方法和根本技能。(3) 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的根本能力。(4) 使学生能用系统的观点和软件开发一般标准进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计的主要内容(1) 问题分析和任务定义。根据题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？(2) 逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原那么划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义包括数据结构的描述和每个根本操作的功能说明，各个主要模块的算法，并画出模块之间的调用关系图。(3) 物理设计。定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简

3、单和易于调试，抽象数据类型的实现尽可能做到数据封装，根本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和根本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。(4)程序编码。把详细设计的结果进一步求精为程序设计语言程序。同时参加一些注解和断言，使程序中逻辑概念清楚。(5) 程序调试与测试。采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。(6) 结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。(7) 撰写课程设计报告。1.3课程设计报告的要求课程设计报告要求标准书写。应当包括如下内容： 问题描述：描述要求编程解决的问题。 根本要求：给出程序要到达的具体的要求。 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。 算法思想：描述解决相应问题算法的设计思想。 模块划分：描述所设计程序的各个模块即函数功能。 数据结构

4、：给出所使用的根本抽象数据类型，所定义的具体问题的数据类型，以及新定义的抽象数据类型。 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。 测试情况：给出程序的测试情况，并分析运行结果。 算法的时空分析(包括根本操作和其他算法的时间复杂度和空间复杂度的分析)和改良设想；经验和体会等。 参考文献：列出参考的相关资料和书籍。2.1.问题描述及根本要求利用深度优先搜索和广度优先搜索完成出具的排序。/要求建立一个菜单，菜单包含4个菜单项供选择：1、建立图的邻接矩阵；2、建立图的邻接表； 3、对图进行深度优先遍历；4、对图进行广度优先遍历。要求从键盘输入无向有权图的顶点数、边数、每条边的起始顶点序号、终点序号、权值，将每条边的信息存入到邻接矩阵和邻接表中。从键盘输入深度优先遍历和广度优先遍历图时初始出发的顶点的序号，要求在遍历过程中输出访问过的结点序号。2.2. 算法思想遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。深度优先搜索所遵循的搜索策略是尽可能“深地

5、搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，那么选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。深度优先搜索根本算法如下递归算法：PROCEDURE dfs_try(i);FOR i:=1 to maxr DOBEGINIF 子结点 mr 符合条件 THENBEGIN产生的子结点mr入栈；IF 子结点mr是目标结点 THEN 输出ELSE dfs_try(i+1);栈顶元素出栈;END;END; 宽度优先搜索算法又称广度优先搜索算法是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，假设没有，再用产生式规那么将所有第一层的结点逐一扩展，得到第二层结点，并

6、逐一检查第二层结点中是否包含目标结点。假设没有，再用算符逐一扩展第二层所有结点，如此依次扩展，直到发现目标结点为止。宽度优先搜索根本算法如下：list1:=source; 参加初始结点，list为待扩展结点的表head:=0; 队首指针foot:=1; 队尾指针REPEAThead:=head+1;FOR x:=1 to 规那么数 DOBEGIN根据规那么产生新结点nw;IF not_appear(nw,list) THEN 假设新结点队列中不存在，那么加到队尾BEGINfoot:=foot+1;listfoot:=nw;listfoot.father:=head;IF listfoot=目标结点 THEN 输出；END；END；UNTIL headfoot; 队列为空说明再无结点可扩展2.3 模块划分深度优先搜索法是树的先根遍历的推广，它的根本思想是:从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，那么退回到已被访问的顶点序列中最

7、后一个拥有未被访问的相邻顶点的顶点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; 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 图的广度优先搜索是树的按层次遍历的推广，它的根本思想是:首先访问初

8、始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, vi t，并均标记已访问过，然后再按照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) visitedv = 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); 目录结构是一种典型的树形结构，为了方便对目录的查找，遍历等操作，可以选择孩子兄弟双亲链表来存储数的结构。程序中要求对目录的大小进行重新计算，根据用户的输入来建立相应的孩子兄弟双亲链表，最后输入树形结构。可以引入一个Tree类，将树的构造，销毁，目录大小的重新计算r

《《图的建立与遍历》数据结构课程设计》由会员枫**分享，可在线阅读，更多相关《《图的建立与遍历》数据结构课程设计》请在金锄头文库上搜索。