logo资料库

数据结构课程设计-图的存储与遍历.doc

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.26M 资料格式：doc 举报 版权申诉
第1页 / 共22页
第2页 / 共22页
第3页 / 共22页
第4页 / 共22页
第5页 / 共22页
第6页 / 共22页
第7页 / 共22页
第8页 / 共22页
资料共22页，剩余部分请下载后查看
    第一章 课程设计目的
    第二章 课程设计内容和要求
    2.1课程设计内容
    2.1.1图的邻接矩阵的建立与输出
    2.1.2图的邻接表的建立与输出
    2.1.3图的遍历的实现
    2.1.4 图的顶点的度
    2.2 运行环境
    第三章 课程设计分析
    3.1图的存储
    3.1.1 图的邻接矩阵存储表示
    3.1.2 图的邻接表存储表示
    3.2 图的遍历
    3.2.1 图的深度优先遍历
    3.2.2 图的广度优先遍历
    3.3图的顶点的度
    第四章 算法（数据结构）描述
    4.1 图的存储结构的建立。
    4.1.1 定义邻接矩阵的定义类型
    4.1.2定义邻接表的边结点类型以及邻接表类型
    4.1.3初始化图的邻接矩阵
    4.1.4 初始化图的邻接表
    4.2 图的遍历
    4.2.1 深度优先遍历图
    4.2.2 广度优先遍历图
    4.3 main函数
    4.4 图的大致流程表
    第五章 源代码
    第六章 测试结果
    第七章 思想总结
    第八章 参考文献
    摘 要 图（Graph）是一种复杂的非线性结构。图可以分为无向图、有向图。若将 图的每条边都赋上一个权，则称这种带权图网络。在人工智能、工程、数学、物 理、化学、计算机科学等领域中，图结构有着广泛的应用。在图结构中，对结点 （图中常称为顶点）的前趋和后继个数都是不加以限制的，即结点之间的关系是 任意的。图中任意两个结点之间都可能相关。图有两种常用的存储表示方法：邻 接矩阵表示法和邻接表表示法。在一个图中，邻接矩阵表示是唯一的，但邻接表 表示不唯一。在表示的过程中还可以实现图的遍历（深度优先遍历和广度优先遍 历）及求图中顶点的度。当然对于图的广度优先遍历还利用了队列的五种基本运 算（置空队列、进队、出队、取队头元素、判队空）来实现。这不仅让我们巩固 了之前学的队列的基本操作，还懂得了将算法相互融合和运用。 1
    目 录 第一章 课程设计目的 ...................................................................................................................... 3 第二章 课程设计内容和要求 ..........................................................................................................3 2.1 课程设计内容 ..................................................................................................................... 3 2.1.1 图的邻接矩阵的建立与输出 .................................................................................3 2.1.2 图的邻接表的建立与输出 .....................................................................................3 2.1.3 图的遍历的实现 .....................................................................................................4 2.1.4 图的顶点的度 ........................................................................................................4 2.2 运行环境 ............................................................................................................................ 4 第三章 课程设计分析 ...................................................................................................................... 4 3.1 图的存储 ............................................................................................................................. 4 3.1.1 图的邻接矩阵存储表示 ......................................................................................4 3.1.2 图的邻接表存储表示 ............................................................................................5 3.2 图的遍历 ............................................................................................................................ 5 3.2.1 图的深度优先遍历 ................................................................................................5 3.2.2 图的广度优先遍历 ................................................................................................6 3.3 图的顶点的度 ..................................................................................................................... 7 第四章 算法（数据结构）描述 ......................................................................................................7 4.1 图的存储结构的建立。 ....................................................................................................7 4.1.1 定义邻接矩阵的定义类型 ....................................................................................7 4.1.2 定义邻接表的边结点类型以及邻接表类型 .........................................................7 4.1.3 初始化图的邻接矩阵 .............................................................................................8 4.1.4 初始化图的邻接表 ................................................................................................8 4.2 图的遍历 ............................................................................................................................ 8 4.2.1 深度优先遍历图 ....................................................................................................8 4.2.2 广度优先遍历图 ....................................................................................................9 4.3 main 函数........................................................................................................................... 9 4.4 图的大致流程表.............................................................................................................. 10 第五章 源代码 ................................................................................................................................ 10 第六章 测试结果 ............................................................................................................................ 20 第七章 思想总结 ............................................................................................................................ 21 第八章 参考文献 ............................................................................................................................ 22 2
    第一章 课程设计目的 本学期我们对《数据结构》这门课程进行了学习。这门课程是一门实践性非常强的课程， 为了让大家更好地理解与运用所学知识，提高动手能力，我们进行了此次课程设计。数据结 构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中 都要用到各种数据结构。这次课程设计不但要求学习者掌握《数据结构》中的各方面知识， 还要求学习者具备一定的 C 语言基础和编程能力。具体说来，这次课程设计主要有两大方面 目的： 一是让学习者通过学习掌握《数据结构》中的知识。对于《图的存储与遍历》这一课题 来说，所要求掌握的数据结构知识主要有：图的邻接矩阵存储、图的邻接表存储、队列的基 本运算实现、邻接矩阵的算法实现、邻接表的算法实现、图的广度优先遍历算法实现、图的 深度优先遍历算法实现。 二是通过学习巩固并提高学习者的 C 语言知识，并初步了解 Visual C++的知识，提高 其编程能力与专业水平。 2.1 课程设计内容 第二章 课程设计内容和要求 该课题要求以邻接矩阵和邻接表的方式存储图，输出邻接矩阵和邻接表，并要求实现 图的深度、广度两种遍历及顶点的度。 2.1.1 图的邻接矩阵的建立与输出 对任意输入顶点数和边数的图，若对无向图进行讨论，根据邻接矩阵的存储结构建立 图的邻接矩阵并输出。要求输出的格式是矩阵形式，这样便于直观的了解。 2.1.2 图的邻接表的建立与输出 对任意给定的图（顶点数和边数可以宏定义），若对无向图进行讨论，根据邻接表的存 储结构建立图的邻接表并输出。 3
    2.1.3 图的遍历的实现 图的遍历包括图的广度优先遍历与深度优先遍历。对于广度优先遍历应利用队列的五种 基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从 初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。 对于深度优先遍历则采用递归算法来实现。当然，若存储图的表示不一样，进行两种遍历的 方式也不一样。 2.1.4 图的顶点的度 在图中，可以求顶点的度。在无向图用邻接矩阵表示，Vi 顶点的度即是该矩阵第 i 行或 第 j 列中非 0 元素的个数之和。若无向图用邻接表表示，顶点 Vi 的度则是第 i 个边表中的 结点个数。 2.2 运行环境 该程序的运行环境为 Windows xp 系统，Microsoft Visual C++6.0 版本。 第三章 课程设计分析 3.1 图的存储 图的存储表示方法很多，但常用的是：图的矩阵表示和邻接表表示。至于在遇到问题具 体选择哪一种表示法，主要取决于具体的应用和欲施加的操作。 3.1.1 图的邻接矩阵存储表示 本课题有邻接矩阵存储表示，邻接矩阵是表示顶点之间相邻关系的矩阵。设 G=（V，E） 是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下性质的 n 阶方阵：A[i,j]=1：若（Vi，Vj） 是 E（G）中的边；A[i,j]=0：若（Vi，Vj）不是 E(G)中的边。用邻接矩阵表示法表示图， 除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表存储顶点信息。 因此，我们就要进行定义数据类型。由于无向图的邻接矩阵是对称的，故采用压缩存储方式， 仅存储上三角阵（不包括对角线上的元素）中的元素即可。显然，邻接矩阵表示法的空间杂 4
    度 S（n）=O（n^2）。 开始进行类型定义，用输入的方式来控制图的顶点数和边数，并对邻接矩阵进行初始 化 ， 将 G->arcs[i][j]=0 ， 再 从 键 盘 上 获 得 顶 点 信 息 ， 建 立 顶 点 表 ， 在 此 同 时 G->arcs[i][j]=1，G->arcs[j][i]=1，最后输出邻接矩阵，用两层 for 循环语句来控制。 3.1.2 图的邻接表存储表示 另外还有邻接表的存储表示。邻接表是一种链式的存储结构，在邻接表中，对图中每 个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 Vi 的边。每个结点由 2 个 域组成，其中邻接点域（adjvex）指示与顶点 Vi 邻接的点在图中的位置，链域（next）指 示下一条边的结点。 所以一开始必须先定义邻接表的边结点类型以及邻接表类型，并对邻接表进行初始化， 然后根据所输入的相关信息，包括图的顶点数、边数以及各条边的起点与终点序号，建立图 的邻接表。对于无向图，一条边的两的个顶点，互为邻接点，所以在存储时，应向起点的单 链表表头插入一边结点，即终点。同时将终点的单链表表头插入一边结点，即起点。对于邻 接表的输出，采用 for 语句输出各结点。 3.2 图的遍历 和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有的顶点 各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图的所有 顶点。图的遍历比树的遍历复杂得多，这是因为图中的任一顶点都可能和其余顶点相邻接， 故在访问了某个顶点之后，可能顺着某条回路又回到了顶点。为了避免重复访问同一个顶点 必须记住每个顶点是否被访问过。为此，可设置一个布尔向量 visited[n]，它的初始值为 0， 一旦访问了顶点 Vi，便将 visited[i-1]置为 1。 根据搜索路径的方向不同，有两种常用的遍历图的方法：深度优先遍历和广度优先遍 历。 3.2.1 图的深度优先遍历 假设给定图 G 的初态是所有顶点未曾被访问，在 G 中任选一顶点 Vi 为初始出发点，则 5
    深度优先遍历可定义如下：首先，访问出发点 Vi，并将其标记为已访问过，然后，依次从 Vi 出发搜索 Vi 的每一个邻接点 Vj，若 Vj 未曾访问过，则以 Vj 为新的出发点继续进行深度 优先遍历。显然这是一个递归的过程，它的特点是尽可能先对纵深方向进行搜索，故称之为 深度优先遍历。在实现深度优先遍历的过程中必须递归调用深度优先搜索函数。 具体过程应为：先访问初始点 Vi，并标志其已被访问。此时定义一指向边结点的指针 p， 并建立一个 while（）循环，以指针所指对象不为空为控制条件，当 Vi 的邻接点未被访问 时，递归调用深度优先遍历函数访问之。然后将 p 指针指向下一个边结点。这样就可以完成 图的深度优先遍历了。 对图进行深度优先遍历时，按访问顶点的先后顺序所得到的顶点序列，称为该图的深度 优先遍历序列，简称 DFS 序列。一个图的 DFS 序列不唯一，它与算法、图的存储结构以及初 始出发点有关。在 DFS 算法中，当从 Vi 出发搜索时，是在邻接矩阵的第 i 行中从左至右选 择下一个未曾访问的邻接点作为新的出发点，若这种邻接点多于一个，则选中的是序号较小 的那一个。因为图的邻接矩阵表示是唯一的，故对于指定的初始出发点，有 DFS 算法所得的 DFS 序列是序列是唯一的。 3.2.2 图的广度优先遍历 广度优先搜索遍历类似于树的按层次遍历的过程。设图 G 中某顶点 Vi 出发，在访问了 Vi 之后访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻 接点的邻接点”被访问，直到图中所有已被访问的顶点的邻接点都被访问到。若此时图中尙 有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所 有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以 Vi 为起始点，由近及 远，依次访问和 Vi 有路径相通且路径长度为 1，2，……的顶点。 所以要实现算法必须先建立一个元素类型为整型的空队列，并定义队首与队尾指针，同 时也要定义一个标志数组以标记结点是否被访问。同样，也是从初始点出发开始访问，访问 初始点，标志其已被访问，并将其入队。当队列非空时进行循环处理。当结点被访问时对其 进行标志，并入队列。通过 while（）循环，并以是否被访问为控制条件，访问所有结点， 完成图的广度优先遍历。 和定义图的 DFS 序列类似，我们可将广度优先遍历图所得到的顶点序列，定义为图的广 6
    度优先搜索遍历序列，简称 BFS 序列。一个图的 BFS 序列也是不唯一的，它与算法、图的存 储结构以及初始出发点有关。 3.3 图的顶点的度 若无向图用邻接矩阵表示，Vi 顶点的度即是该矩阵第 i 行或第 j 列中非 0 元素的个数之 和。若无向图用邻接表表示，Vi 的度分为出度和入度。出度即是表结点的个数，入度即是 逆邻接表的出度。 第四章 算法（数据结构）描述 4.1 图的存储结构的建立。 4.1.1 定义邻接矩阵的定义类型 typedef int datatype; typedef struct { char vexs[max]; int arcs[max][max]; int vexsnum,arcsnum; }graph; /* 顶点个数及边的个数 */ 4.1.2 定义邻接表的边结点类型以及邻接表类型 typedef char vextype; typedef struct node { int adjvex; /* 邻接点域 */ struct node *next; /* 链域 */ 7
    /* 边表结点 */ }enode; typedef struct { vextype vertex; /* 顶点信息 */ enode *link; /* 边表头指针 */ }vnode; /* 顶点表结点 4.1.3 初始化图的邻接矩阵 for(i=0;ivexsnum;i++) G->vexs[i]=getchar(); for(i=0;ivexsnum;i++) for(j=0;jvexsnum;j++) G->arcs[i][j]=0; 4.1.4 初始化图的邻接表 需建立一个邻接表初始化函数对图的邻接表进行初始化。即建立一个所有边结点都为空 的邻接表。 for(i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料