图的存储与遍历课程设计实验报告

《图的存储与遍历课程设计实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计设计题目：图的邻接表存储及其应用2课题名称图的邻接表存储及其应用院系年级专业学号课题设计目的与设计意义1、课题设计目的：一、是让我们通过实习掌握《数据结构》中的知识。对于《图的遍历》这一课题来说，所要求掌握的数据结构知识主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索、图的深度优先搜索算法实现。二、是通过实习巩固并提高实习者的C语言知识，并初步了解C++的知识，提高编程能力与专业水平。2、课题设计意义：一、通过对邻接表表示图及深广度优先遍历程序的编写，对

2、数据结构的理解更为加深。二、培养了我们独立设计程序与解决问题的能力，培养了我们团队协作集成程序模块及调试能力。三、培养了学生初步的软件设计及软件测试的能力。指导教师：年月日2目录第一章课程设计目的１第二章课程设计内容和要求１2.1课程设计内容１2.1.1图的邻接表的建立与输出１2.1.2图的遍历的实现１2.2运行环境１第三章课程设计分析２3.1图的存储２3.2图的遍历２3.2.1图的深度优先遍历２3.2.2图的广度优先遍历２第四章算法（数据结构）描述３4.1图的存储结构的建立。３4.1.1定义邻接表的边

3、结点类型以及邻接表类型３4.1.2初始化图的邻接表３4.1.3建立并输出图的邻接表３4.2图的遍历５4.2.1深度优先遍历图的邻接表５4.2.2广度优先遍历图的邻接表６第五章源代码７第六章运行结果分析１３第七章结束语１７第八章参考文献１９１９第一章课程设计目的本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程，为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计实习。这次课程设计不但要求实习者掌握《数据结构》中的各方面知识，还要求实习者具备一定的C语言基础和

4、编程能力。具体说来，这次课程设计主要有两大方面目的。一是让实习者通过实习掌握《数据结构》中的知识。对于《图的遍历》这一课题来说，所要求掌握的数据结构知识主要有：图的邻接表存贮结构、队列的基本运算实现、邻接表的算法实现、图的广度优先搜索周游算法实现、图的深度优先搜索周游算法实现。二是通过实习巩固并提高实习者的C语言知识，并初步了解VisualC++的知识，提高其编程能力与专业水平。第二章课程设计内容和要求2.1课程设计内容该课题要求以邻接表的方式存储图，输出邻接表，并要求实现图的深度、广度两种遍历。2.1

5、.1图的邻接表的建立与输出对任意给定的图（顶点数和边数自定），并且对有向图与无向图都应进行讨论，根据邻接表的存储结构建立图的邻接表并输出之。尽量用图形化的方式输出邻接表。2.1.2图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。对于深度优先遍历则采用递归或非递归算法来实现。2.2运行环境该程序的运行环境

6、为Windowsxp系统，MicrosoftVisualC++6.0版本。１９第三章课程设计分析3.1图的存储本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的在图中的位置，链域（nextarc）指示下一条弧）。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，

7、如权值等。所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。此时要分两种情况：有向图与无向图。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。对于有向图，只能向起点的单链表的表头插入一个边结点，即终点。但不能反过来。至于邻接表的输出，由于不了解C++中的绘图操作，故采用for语句输

8、出各结点，并配合一些符号完成邻接表的输出。3.2图的遍历3.2.1图的深度优先遍历假设初始状态是图中所有顶点未曾被访问，深度优先遍历可以从图的初始点出发，访问初始点，然后依次从v未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时仍有顶点未被访问到，则从另一个未被访问的顶点出发，重复上述过程，直至所有点都被访问到为止。这是一个递归的过程。所以在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。而且在深度