《数据结构图的建立与输出课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构图的建立与输出课程设计.doc（19页珍藏版）》请在金锄头文库上搜索。
1、计算机工程学院数据结构课程设计报告题 目： 图的建立与输出 姓 名： 学 号： 专业班级： 指导教师： 设计时间： 2目录1 课题任务与计划32 设计方案及原理32.1 图有两种主要的存储结构 32.2 图的邻接表存储表示42.3 有向图的十字链表存储表示法52.4 无向图的邻接多重表存储表示52.5 邻接矩阵表示法 62.6 邻接表表示法 93 各功能的程序流程103.1 函数功能的实现 103.2 变量的定义 12 4 主函数程序流程125 实验数据分析136 附源代码167 参考书目193一 课题任务与计划建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类
2、型） ，能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。数据结构课程设计是学习数据结构课程的一个重要环节。能巩固和加深课堂教学内容，提高学生实际工作能力，培养科学作风，为学习后续课程和今后的系统开发奠定基础。通过课程设计，使学生熟练掌握数据结构课程中所学的理论知识，并实际应用，通过综合运用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。除了广义表和树以外，都可以有两类不同的存储结构，它们是由不同的映像方法（顺序映像和链式映像）得到的。由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没
3、有顺序映像的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示图是自然的事，它是一种最简单的链式映像结构，即以一数据域和多个指针域组成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针，如图所示，有向图 G1 和无向图 G2 的多重链表。但是，由于图中各个结点的度数不同，最大度数和最小度数可能相差很多，因此，若按度数最大的顶点设计结点结构，则会浪费很多存储单元；反之，若按每个顶点自己的度数设计不同的结点结构，又会给操作带来不便。因此，和树类似，在实现应用中不宜采用这种结构，而应该根据具体的图的需要进行的操作，设计恰当的结点结构和表结构。
4、常用的就有我们熟悉的邻接表、邻接多重表和十字链表。所以，我们打算采用邻接表的方法设计图的存储结构，包括图的建立与存储。二 设计方案及工作原理1 图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法。设图 4A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edgenn，用来存放顶点的信息和边或弧的信息。（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。 （2） 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 行 1 的个数可得顶点 j 的入度。在无向图中, 统计第 i 行 (列) 1 的个数可得顶点 i的度。图的邻接表
5、（Adjacency List ）存储表示法 邻接表是图的一种链式存储结构，它对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 vi 的边（对有向图是以顶点 vi 为尾的弧） ，每个结点由三个域组成：邻接点域(adjvex)指示与顶点 vi 邻接的点在图中的位置，链域(nextarc) 指示下一条边或弧的结点，数据域（info ）存储和边或弧相关的信息（如权值） 。每个链表上附设一个表头结点,包含数据域（data）和链域(firstarc)指向链表中的第一个结点，这些表头结点通常以顺序结构的形式存储， 以便随机访问任一顶点的链表。 在无向图的邻接表中，顶点 vi 的度等于第
6、 i 个链表中的结点数；在有向图的邻接表中，顶点 vi 的出度等于第 i 个链表中的结点数，求入度必须遍历整个邻接表，为便于求 vi 的入度需建立有向图的逆邻接表（是以顶点 vi 为头的弧所建立的邻接表） 。 2 图的邻接表存储表示： #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; typedef struct VNode VertexType d
7、ata; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; typedef struct 5AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph; 3 有向图的十字链表存储表示法 十字链表（Orthogonal List）是有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。 #define MAX_VERTEX_NUM 20 typedef struct ArcBo
8、x int tailvex, headvex; / 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType *info; / 该弧相关信息的指针 ArcBox; typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧 VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; / 表头向量 int vexnum, arcnum; / 有向图
9、的当前顶点数和弧数 OLGraph; 4 无向图的邻接多重表存储表示 #define MAX_VERTEX_NUM 20 typedef emnu unvisited, visited VisitIf; typedef struct Ebox 6VisitIf mark; / 访问标记 int ivex, jvex; / 该边依附的两个顶点的位置 struct EBox *ilink, *jlink; / 分别指向依附这两个顶点的下一条边 InfoType *info; / 该边信息指针 EBox; typedef struct VexBox VertexType data; EBox *fi
10、rstedge; / 指向第一条依附该顶点的边 VexBox; typedef struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; / 无向图的当前顶点数和边数 AMLGraph; 5 邻接矩阵表示法设 G=(V,E)是一个图，其中 V=V1,V2,V3,Vn。G 的邻接矩阵是一个他有下述性质的 n 阶方阵：1，若(Vi,Vj)E 或 E；Ai,j=0，反之图 5-2 中有向图 G1 和无向图 G2 的邻接矩阵分别为 M1 和 M2:M1= 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 7M2= 0 1 1
11、1 1 0 1 0 1 1 0 1 1 0 1 0 注意无向图的邻接是一个对称矩阵，例如 M2。用邻接矩阵表示法来表示一个具有 n 个顶点的图时，除了用邻接矩阵中的n*n 个元素存储顶点间相邻关系外，往往还需要另设一个向量存储 n 个顶点的信息。因此其类型定义如下：const vnum=;图的顶点数 type adj=0.1;adjmatrix=arry1.vnum,1.vnumof adj;邻接矩阵 graph=recordvexs:array1.vnumof vextype;顶点向量 arcs:adjmatrix;邻接矩阵 end;若图中每个顶点只含一个编号 i(1ivnum)，则只需一个
12、二维数组表示图的邻接矩阵。此时存储结构可简单说明如下：type adjmatrix=array1.vnum,1.vnumof adj;利用邻接矩阵很容易判定任意两个顶点之间是否有边（或弧）相联，并容易求得各个顶点的度。对于无向图，顶点 Vi 的度是邻接矩阵中第 i 行元素之和，即nnD(Vi) Ai,j （或Ai,j）j=1 i=1对于有向图，顶点 Vi 的出度 OD(Vi)为邻接矩阵第 i 行元素之和，顶点 Vi的入度 ID(Vi)为第 i 列元素之和。即nnOD(Vi) Ai,j， OD(Vi)Aj,i）8j=1 j=1 用邻接矩阵也可以表示带权图，只要令Wij, 若或(Vi,Vj)Ai,
13、j , 否则。其中 Wij 为 或 (Vi,Vj)上的权值。相应地，网的邻接矩阵表示的类型定义应作如下的修改： adj:weightype ; weightype 为权类型图 5-6 列出一个网和它的邻接矩阵。 (a)网 (b)邻接矩阵图 5-6 网及其邻接矩阵对无向图或无向网络，由于其邻接矩阵是对称的，故可采用压缩存贮的方法，仅存贮下三角或上三角中的元素(但不含对角线上的元素)即可。显然，邻接矩阵表示法的空间复杂度 O(n2)。无向网邻接矩阵的建立方法是：首先将矩阵 A 的每个元素都初始化成。然后，读入边及权值(i,j,wij),将 A 的相应元素置成 Wij。无向网邻接矩阵的建立算法如下：
14、procedure build-graph(var ga:graph); 建立无向网的邻接矩阵 beginfor i:=1 to n do read(ga.vexsi)； 读入 n 个顶点的信息for i:=1 to n dofor j:=1 to e doga.arcsi,j:=maxint；将邻接矩阵的每个元素初始化成 maxint,计算机内用最大事数 maxint 表示for k:=1 to e do e 为边的数目9 read(i,j,w) 读入边和权ga.arcsi,j:=w; ga.arcsj,i:=w end；该算法的执行时间是 O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是 O(n2),而 e和。 注意： n 个顶点 e 条边的有向图，它的邻接表表示中有 n 个顶点表结点和 e 个边表结点。 4） 有向图的逆邻接表
