数据结构图的邻接表的建立实验指导书.pdfVIP

实验五图的邻接表的建立

一、实验目的

1．理解图的数据结构；

2．掌握图的邻接表的存储结构，建立邻接表的算法。

二、实验内容

图，是一种比树和表要复杂得多的数据结构。在线性表中，数据元素之间只有线性关

系，每一个数据元素只有一个直接前驱和直接后继；在树形结构之中，树元素之间有着明显

的层次关系，并且每上一层的数据元素可能和下一层的多个数据元素相关，但只能和上一层

的一个数据元素相关；而在图形结构中，结点之间的关系可以是任意的。图中的任意结点之

间的两个数据元素都可以相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗

透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支里。

图有多种存储方式，邻接表是一链式存储结构。在邻接表中，对图中的每一个结点都

建立一个单链表，第一个单链表表示依附于顶点VI的边。每一个结点由三个域组成，其邻

接点域指示与顶点VI邻接的点图中的位置，链域指示下一条边或弧的结点，数据域存储和

边或弧的相关信息，如权值等。

每个链表附设一表头结点。如下图所示：

表结点头结点

数据域链域

邻接点域链域数据域

本实验是对下图做邻接表：

12

3

45

邻接表应为实验程序输出所示。

三、实验步骤

1．读懂实验原理，参照参考程序编写上机程序并调试、运行。

2．按上图输入数据验证结果。

3．完成思考题。

四、程序流程图

开始

生成表

头

I=

VTXNUM?

建立邻接表

置表头结点为空生成空的

表头结点

做REPEAT循环生成

其它结点,直到输入

的邻接点为零为止

做VETNUM次循环输

出邻接表,若表头为空则

输出空邻接表;否则输出

邻接表直到遇到空指针

为止

结束

五、实验参考程序

#includestdio.h

#includestdlib.h

#definevtxnum5

#definenull0

structarcnode

{intadjvex;

structarcnode*next;

};

structvexnode

{i