数据结构图的建立与输出课程设计

1、计算机工程学院数据结构课程设计报告题 目： 图的建立与输出 姓 名： 学 号： 专业班级： 指导教师： 设计时间： 目录1 课题任务与计划32 设计方案及原理32.1 图有两种主要的存储结构 32.2 图的邻接表存储表示42.3 有向图的十字链表存储表示法52.4无向图的邻接多重表存储表示52.5 邻接矩阵表示法 62.6 邻接表表示法 93 各功能的程序流程103.1函数功能的实现 103.2变量的定义 12 4 主函数程序流程125 实验数据分析136 附源代码167 参考书目19一 课题任务与计划建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够

2、输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。数据结构课程设计是学习数据结构课程的一个重要环节。能巩固和加深课堂教学内容，提高学生实际工作能力，培养科学作风，为学习后续课程和今后的系统开发奠定基础。通过课程设计，使学生熟练掌握数据结构课程中所学的理论知识，并实际应用，通过综合运用数据结构的基本知识来解决实际问题，加强学生分析和解决问题的能力。 除了广义表和树以外，都可以有两类不同的存储结构，它们是由不同的映像方法（顺序映像和链式映像）得到的。由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序映像

3、的存储结构，但可以借助数组的数据类型表示元素之间的关系。另一方面，用多重链表表示图是自然的事，它是一种最简单的链式映像结构，即以一数据域和多个指针域组成的结点表示图中一个顶点，其中数据域存储该顶点的信息，指针域存储指向其邻接点的指针，如图所示，有向图G1和无向图G2的多重链表。但是，由于图中各个结点的度数不同，最大度数和最小度数可能相差很多，因此，若按度数最大的顶点设计结点结构，则会浪费很多存储单元；反之，若按每个顶点自己的度数设计不同的结点结构，又会给操作带来不便。因此，和树类似，在实现应用中不宜采用这种结构，而应该根据具体的图的需要进行的操作，设计恰当的结点结构和表结构。常用的就有我们熟悉

4、的邻接表、邻接多重表和十字链表。所以，我们打算采用邻接表的方法设计图的存储结构，包括图的建立与存储。二 设计方案及工作原理1 图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法。设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edgenn，用来存放顶点的信息和边或弧的信息。（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。 （2） 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 行 1 的个数可得顶点j 的入度。在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i的度。图的邻接表（Adjacency L

5、ist）存储表示法 邻接表是图的一种链式存储结构，它对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧），每个结点由三个域组成：邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置，链域(nextarc)指示下一条边或弧的结点，数据域（info）存储和边或弧相关的信息（如权值）。每个链表上附设一个表头结点,包含数据域（data）和链域(firstarc)指向链表中的第一个结点，这些表头结点通常以顺序结构的形式存储， 以便随机访问任一顶点的链表。 在无向图的邻接表中，顶点vi的度等于第i个链表中的结点数；在有向图的邻接表中，顶点vi的出度

6、等于第i个链表中的结点数，求入度必须遍历整个邻接表，为便于求vi的入度需建立有向图的逆邻接表（是以顶点vi为头的弧所建立的邻接表）。 2 图的邻接表存储表示： #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode; typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条

7、依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph; 3 有向图的十字链表存储表示法 十字链表（Orthogonal List）是有向图的另一种链式存储结构，可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。 #define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex, headvex; / 该弧的尾和头顶点的位置 s

8、truct ArcBox *hlink, *tlink; / 分别指向下一个弧头相同和弧尾相同的弧的指针域 InfoType *info; / 该弧相关信息的指针 ArcBox; typedef struct VexNode VertexType data; ArcBox *firstin, *firstout; / 分别指向该顶点第一条入弧和出弧 VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; / 表头向量 int vexnum, arcnum; / 有向图的当前顶点数和弧数 OLGraph; 4 无向图的邻接多重表存储表示 #def

9、ine MAX_VERTEX_NUM 20 typedef emnu unvisited, visited VisitIf; typedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex; / 该边依附的两个顶点的位置 struct EBox *ilink, *jlink; / 分别指向依附这两个顶点的下一条边 InfoType *info; / 该边信息指针 EBox; typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox; typedef

10、struct VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; / 无向图的当前顶点数和边数 AMLGraph; 5 邻接矩阵表示法设G=(V,E)是一个图，其中V=V1,V2,V3,Vn。G的邻接矩阵是一个他有下述性质的n阶方阵： 1，若(Vi,Vj)E 或<Vi,Vj>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 M2= 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 注意无向图的邻接是一个对

11、称矩阵，例如 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)，则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下： type adjmatrix=a

12、rray1.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） j=1j=1用邻接矩阵也可以表示带权图，只要令Wij, 若<Vi,Vj>或(Vi,Vj)Ai,j , 否则。其中Wij为<Vi,Vj>或(Vi,Vj)上的权值。相应地，网的

13、邻接矩阵表示的类型定义应作如下的修改： adj:weightype ; weightype为权类型图5-6列出一个网和它的邻接矩阵。 (a)网(b)邻接矩阵图5-6 网及其邻接矩阵对无向图或无向网络，由于其邻接矩阵是对称的，故可采用压缩存贮的方法，仅存贮下三角或上三角中的元素(但不含对角线上的元素)即可。显然，邻接矩阵表示法的空间复杂度O(n2)。无向网邻接矩阵的建立方法是：首先将矩阵A的每个元素都初始化成。然后，读入边及权值(i,j,wij),将A的相应元素置成Wij。 无向网邻接矩阵的建立算法如下：procedure build-graph(var ga:graph); 建立无向网的邻接矩

14、阵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为边的数目 read(i,j,w) 读入边<i,j>和权ga.arcsi,j:=w; ga.arcsj,i:=w end；该算法的执行时间是O(n+n2+e),其中消耗在邻接矩阵初始化操作上的时间是O(n2),而e<n2，所以上述算法的时间复杂度是O(n2)。图的邻接矩阵

15、存储表示： #define INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 / 最大顶点个数 typedef enum DG, DN, AG, AN GraphKind; /有向图,有向网,无向图,无向网 typedef struct ArcCell VRType adj; / VRType是顶点关系类型。对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct

16、 VertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧(边)数 GraphKind kind; / 图的种类标志 MGraph; 6、邻接表表示法邻接表是图的一种链式存储结构为，类似于树的孩子链表表法。在邻接表中，对图中每个顶点建立一个单链表，n个顶点，就要建n个链表。对于无向图，第i个单链表中的结点表示依赖于顶点vi的边。对于有向图是以顶点vi为尾的弧，这个单链表称为顶点vi的单链表(即Vi的邻接表)。单链表中每一个结点称为表结点，应包括两个域:邻接点域，用以存

17、放与vi相邻接的顶点序号；链域用以指向民vi邻接的下一个结点。另外，每一个单链表设一个表头结点。每一个表头结点有两个域，一个用来存放顶点vi的信息；另一个域用来指向vi的邻接表中的第一个结点(见图5-7)。为了便于管理和随机访问任一顶点的单链表，将所有单链表的头结点组织成一个一维娄组。若一个无向图有n个顶点，e条边，则它的邻接表需n个头结点和2e个表结点。显然，在边稀疏（e<<n(n-1)/2）的情况下，用邻接表表示比用邻接矩阵节省存储空间。若一个有向图有n个顶点，e条边，则它的邻接表需n个头结点和e个表结点。下面讨论在邻接表上如何求顶点的度。无向图中顶点vi的度恰为第i个单链表中

18、的结点数。对有向图，第i个单链表中的结点个数只是顶点vi的出度。为了求入度，必须遍历整个邻接表。在所有单链表中，其邻接点域的值为i的结点的个数是顶点vi的入度。 显然，上述算法的时间复杂度是O(n+e)。值得注意的是，一个图的邻接矩阵表示是唯一的，而其邻接表表示则不唯一。这是因为邻接表表示中各表结点的链接顺序取决于建立邻接表的算法以及各边的输入次序。在邻接表中要判定任意两个顶点vi和vj之间是否有边或弧相连，需要遍历第i个或第j个单链表，不象邻接矩阵那样能方便地对顶点进行随机访问。因此，对于图来说使用邻接矩阵或邻接表作存储结构各有其利弊。 构造一个具有n个顶点和e条边的无向网的时间复杂度为O（

19、n2+e*n），其中O（n2）用于对邻 接矩阵初始化。 三 各功能的程序流程1函数功能的实现1）图的建立及输出图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点v i ，该方法把所有邻接于v i 的顶点v j 链成一个带头结点的单链表，这个单链表就称为顶点v i 的邻接表(Adjacency List)。 1 邻接表的结点结构 （1）表结点结构 adjvex next 邻接表中每个表结点均有两个域: 邻接点域adjvex 存放与vi相邻接的顶点v j 的序号j。 链域next ，将邻接表的所有表结点链在一起。 注意： 若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。

20、（2）头结点结构 vertex firstedge 顶点v i 邻接表的头结点包含两个域： 顶点域vertex 存放顶点v i 的信息 指针域firstedge 存放v i 的邻接表的头指针。 注意： 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。 2）无向图的邻接表 对于无向图，v i 的邻接表中每个表结点都对应于与v i 相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。 【例】对于无向图G 5 ，其邻接表表示如下面所示，其中

21、顶点v 0 的边表上三个表结点中的顶点序号分别为1、2和3，它们分别表示关联于v 0 的三条边(v 0 ，v 1 )，(v 0 ，v 2 )和(v 0 ，v 3 )。注意： n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。 3）有向图的邻接表 对于有向图，v i 的邻接表中每个表结点都对应于以v i 为始点射出的一条边。因此，将有向图的邻接表称为出边表。 【例】有向图G 6 的邻接表表示如下面(a)图所示，其中顶点v 1 的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v 1 射出的两条边(简称为v 1 的出边)：<v 1 ，v 0 >和<v

22、 1 ，v 4 >。 注意： n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。 4）有向图的逆邻接表 在有向图中，为图中每个顶点v i 建立一个入边表的方法称逆邻接表表示法。 入边表中的每个表结点均对应一条以v i 为终点(即射入v i )的边。 【例】G 6 的逆邻表如上面(b)图所示，其中v 0 的人边表上两个表结点1和3分别表示射人v 0 的两条边(简称为v 0 的入边)：<v 1 ，v 0 >和<v 3 ，v 0 >。 n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。 图的存储表示方法很多本节介绍两种最常用的方

23、法邻接矩阵表示法和领接表表示法。2 变量的定义AdjvexInt该弧所指向顶点的位置NextracStruct ArcNode 指针指向下条弧的指针InfoInt该弧的权值DataInt顶点信息FirstarcStruct ArcNode 指针指向第一条依附该顶点的弧的指针VexnumInt图当前的顶点数ArcnumInt 图当前的弧数四 主函数的程序流程 菜单主函数图的建立图的输出终 止退 出五 实验数据分析实验数据分析：首先，正常进入程序执行界面，显示输出如下： = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1、创建邻接表

24、图 = = = = = = = = = = = =2、输出邻接表图 = = = = = = = = = = = 3、退出 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 请选择操作：为了建立邻接表图，在此我们选择“1”，出现以下提示：请正确创建邻接表图：请输入图的顶点数目：为了执行方便，我们输入一个顶点数目为4的邻接表。之后便会提示“请输入图的弧的数目：”，我们也输入4。定义时，我们有typedef struct ArcNode/ int adjvex;/struct ArcNode *nextarc;int in

25、fo; ArcNode;数据域包括三个域，除了结点和弧外还有弧的权值域，所以定义函数时定义了弧的权值，之后的提示就会有“请确认是否输入权值<y/n>：”在此我们选择Y，以后输入结点信息完之后输入弧的权值，接下来输入结点和弧的信息。提示如下：请输入弧尾1，4：请输入弧头1，4：请输入弧的权值：在此我们输入（1 2 5），（1 3 6），（3 4 7 ），（4 1 8 ）。接下来，程序会出现创建图成功的标志“Create ALGraph success！”。到此为止，图的创建完成。此外，如果在输入结点和弧信息不合法的时候，程序不会继续往下执行，会要求用户再次输入结点信息和弧的信息，直到

26、用户输入完全正确为止。接下来进入第二阶段，重新选择操作。根据程序开始的提示，现在我们输入2，来查看我们的程序执行结果：输出该邻接矩阵图如下：= = = = = = = = = = = = = = = = = = = = = =0 1 1 00 0 0 00 0 0 11 0 0 0该图输出完毕！= = = = = = = = = = = = = = = = = = = = = =请选择操作： 程序执行到此，又进入主菜单进行选择，图的输出流程到此完毕。按3键可退出程序，按1键可再次进入建立图的程序流程，按2键可输出建立的图。 程序运行图如图1-1和图1-2：图 1-1 图的建立图1-2 图的输出

27、六 附源代码#define max 20#include<malloc.h>#include<iostream>using namespace std;typedef struct ArcNode/定义表结点int adjvex;/该弧所指向顶点的位置struct ArcNode *nextarc;/指向下一条弧的指针int info;/该弧的权值ArcNode;typedef struct VNode/定义头结点int data;/顶点信息ArcNode *firstarc;/指向第一条依附该顶点的弧的指针VNode,AdjListmax;typedef struct

28、/定义ALGraphAdjList vertices;int vexnum,arcnum;/图的当前顶点数和弧数int kind;/图的种类标志ALGraph;void CreateDG(ALGraph &G)/创建邻接表的图int k,i,j;char tag;cout<<"请输入图的顶点数目:"<<endl;/输入顶点数目cin>>G.vexnum; cout<<"请输入图的弧的数目:"<<endl;/输入弧的数目cin>>G.arcnum; cout<<&q

29、uot;请确认是否输入弧的权值(y/n):"<<endl;cin>>tag;for(i=1;i<=G.vexnum;+i)G.verticesi.data=i;/初始化顶点值G.verticesi.firstarc=NULL;/初始化指针 cout<<"请输入弧的相关信息arc(V1->V2)"<<endl;/构造弧for(k=1;k<=G.arcnum;+k)cout<<endl<<"请输入弧尾"<<"1,"<<

30、;G.vexnum<<":"cin>>i; cout<<"请输入弧头"<<"1,"<<G.vexnum<<":"cin>>j; while(i<1|i>G.vexnum|j<1|j>G.vexnum)/如果弧头或弧尾不合法,重新输入cout<<endl<<"请再次输入弧尾"<<"1,"<<G.vexnum<<&

31、quot;:"cin>>i;cout<<"请再次输入弧头"<<"1,"<<G.vexnum<<":"cin>>j; ArcNode *p;p=(ArcNode*)malloc(sizeof(ArcNode);/分配内存if(!p)cout<<"Overflow!"/如果没有足够的空间,则退出p->adjvex=j;/对弧结点的弧顶点数据域赋值p->nextarc=G.verticesi.firstarc;/对弧

32、结点下一条弧指针域赋值p->info=0; / 对弧结点相关信息指针域赋值G.verticesi.firstarc=p; / 将弧结点插入到对应的单链表if(tag='y')cout<<"请输入弧的权值:"cin>>p->info; void ShowMGraph(ALGraph G)int *a,i,k;ArcNode *p;a=(int*)malloc(G.vexnum*G.vexnum+1)*sizeof(int);for(i=1;i<=G.vexnum*G.vexnum;i+)ai=0;for(i=1;i<=G.vexnum;i+)for(p=G.verticesi.f