第五次实验题目与报告书-软件111-112.docVIP

淮海工学院计算机科学系

实验报告书

课程名：《数据结构》

题目：图形数据结构实验

班级：

学号：

姓名：

评语：

评语：

成绩：指导教师：

批阅时间：年月日

《数据结构》实验报告 -PAGE1-

图形数据结构实验报告要求

1目的与要求:

1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；

2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现（预习）；

3）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；

4）认真书写实验报告,并按时提交（第12周周一提交）。

2实验内容或题目

题目：一、图形数据结构实验——图的建立与遍历。

内容：

使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结构。

在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。

图1

图1无向图

V1

V2

V4

V5

V3

V7

V6

V8

V1

V1

V2

V4

V5

V3

V7

V6

V8

例2有向图

3实验步骤与源程序

（学生自己填写）

4测试数据与实验结果（可以抓图粘贴）

（学生自己填写）

5结果分析与实验体会

（学生自己填写）

2.版面格式：

（1）各级标题：黑体，小四，段前/段后：6磅

（2）正文内容：宋体、五号，行间距1.25倍；

（3）程序代码：宋体、五号，单倍行间距；

（4）A4纸，上、下、左、右边距：2厘米

注：蓝色字体部分为注释，正式报告中将其删除。

举例：使用邻接矩阵创建图形结构

本次实验有向网

/*头文件

#includestdlib.h

#includestdio.h

#defineMAX_VERTEX_NUM10/*最多顶点个数*/

#defineINFINITY32768/*表示极大值，即∞*/

#defineTrue1

#defineFalse0

#defineError-1

#defineOk1

typedefenum{DG,DN,UDG,UDN}GraphKind;/*图的种类：DG表示有向图,DN表示有向网,UDG表示无向图,UDN表示无向网*/

typedefcharVertexData;/*假设顶点数据为字符型*/

typedefstructArcNode

{

intadj;/*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/

}ArcNode;

typedefstruct

{

VertexDatavexs[MAX_VERTEX_NUM];/*顶点向量*/

ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接矩阵*/

intvexnum,arcnum;/*图的顶点数和弧数*/

GraphKindkind;/*图的种类标志*/

}AdjMatrix;/*(AdjacencyMatrixGraph)*/

intLocateVertex(AdjMatrix*G,VertexDatav)/*求顶点位置函数*/

{

intj=Error,k;

for(k=0;kG-vexnum;k++)

if(G-vexs[k]==v)

{

j=k;

break;

}

return(j);

}

头文件结束/

创建程序如下

intCreateDN(AdjMatrix*G)/*创建一个有向网*/

{

inti,j,k,weight;

VertexDatav1,v2;

printf(输入图的弧数和顶点数\n);

fflush(stdin);

scanf(%d,%d,G-arcnum,G-