数据结构-无向图的操作-课程设计-实验报告

《数据结构-无向图的操作-课程设计-实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计设计题目：无向图的操作学生姓名：专业班级：指导教师：完成时间：17课题名称无向图的操作院系年级专业学号姓名成绩课题设计目的与设计意义1、课题设计目的：一、熟悉图的两种常用的存储结构，邻接矩阵。二、建立有向图，用邻接表存储结构存储。三、在邻接表存储结构上实现深度优先遍历。2、课题设计意义：一、能够熟悉关于无向图邻接矩阵和无向图邻接表的输出建立等操作。二、能够理解关于无向图的基本操作有何目的与意义。三、将以上的理解加以运用与操作。指导教师：年月日17目录第一章课程设计的目的与意义1第二章课程设计的内容与要

2、求12.1课程设计的内容12.1.1定义12.1.2操作22.2课程设计的要求2第三章需求分析23.1原理23.2要求33.3系统总框架33.4运行环境33.5程序的输入（包含输入的数据格式和说明）43.6开发工具4第四章算法与描述44.1图的深度优先遍历44.2具体过程应为4第五章源程序5第六章运行结果12第七章结束语17第八章参考文献1817第一章课程设计的目的与意义图是一种复杂的非线性结构。在人工智能、工程、数学、物理、化学、计算机科学等领域中，图结构有着广泛的应用。在线性结构中，结点之间的关系是线性关系，除开

3、始结点和终端结点外，每个结点只有一个直接前趋和直接后继。在树形结构中，结点之间的关系实质上是层次关系，除根结点之外，每个结点都只能有一个双亲（前趋），但每个结点可以有零个或多个孩子（后继）。因此，层次关系是非线性的。但是，它在树的结点之间建立了一个层次结构；同层次上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根节点除外）。然而在土结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。邻接表(Adjac

4、encyList)是图的一种顺序存储与链式存储结合的存储方法，类似于树的孩子链表表示法。由于它只考虑非零元素,因而节省了零元素所占的存储空间。它对于无向图和有向图都适用。本学期我们学了很多图的存储结构，有邻接矩阵。邻接表等。其中邻接矩阵和邻接表为图的主要存储结构。图的邻接矩阵存储结构的主要特点是吧图的边信息与链式存数相结合的存储方法。从空间性能上说，图越洗漱邻接表的空间效率也相应的越高。从时间性能上来说，邻接表在图的算法中时间代价较邻接矩阵要第。本课程设计主要是实现使用邻接表存储结构存储一个图，并在所存储的图中实现深

5、度优先和广度优先遍历以及其链表结构的输出。通过实习巩固并提高我的C语言知识，并初步了解VisualC++的知识，提高编程能力与专业水平。第二章课程设计的内容与要求2.1课程设计的内容2.1.1定义有向图与无向图：图是一种复杂的非线性结构。图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集。通常，也将图G的顶点集和边集分别记为V（G）和E（G）。E（G）可以是空集，若E（G）为空，则图G只有顶点而没有边。若图G中的每条边都是有方向的，则称G为有向图；若图G中的每

6、条边都是没有方向的，则称G为无向图。邻接矩阵：邻接矩阵是表示定点之间相邻关系的矩阵。17邻接表：对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个单链变，这个单链表就成为顶点vi的邻接表。2.1.2操作熟悉掌握关于无向图邻接表和邻接矩阵的运用以及操作，包括：无向图邻接矩阵的建立、无向图邻接矩阵的输出、无向图邻接表的建立、无向图邻接表的输出、无向图邻接表的深度遍历、无向图邻接矩阵的深度遍历、无向图邻接表的广度遍历、无向图邻接矩阵的广度遍历。2.2课程设计的要求一、能够熟悉关于无向图邻接矩阵和无向图邻接表

7、的输出建立等操作。二、能够理解关于无向图的基本操作有何目的与意义。三、将以上的理解加以运用与操作。第三章需求分析3.1原理本课题要求采取邻接表的存储结构。邻接表是一种链式的存储结构，在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点Vi为尾的弧）。每个结点由3个域组成，其中邻接点域（adjvex）指示与顶点Vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。所以一开始必须先定义邻接表的边结点类型

8、以及邻接表类型，并对邻接表进行初始化，然后根据所输入的相关信息，包括图的顶点数、边数、是否为有向，以及各条边的起点与终点序号，建立图的邻接表。此时要分两种情况：有向图与无向图。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。对于有向图，只能向起点的单