数据结构实验图的基本操作复习过程.docx

数据结构实验图的基本操作复习过程.docx

《数据结构实验图的基本操作复习过程.docx》由会员分享，可在线阅读，更多相关《数据结构实验图的基本操作复习过程.docx（27页珍藏版）》请在冰点文库上搜索。

数据结构实验图的基本操作复习过程

浙江大学城市学院实验报告

课程名称数据结构

实验项目名称实验十三/十四图的基本操作

学生姓名专业班级学号

实验成绩指导老师（签名）日期2014/06/09

一.实验目的和要求

1、掌握图的主要存储结构。

2、学会对几种常见的图的存储结构进行基本操作。

二.实验内容

1、图的邻接矩阵定义及实现：

建立头文件test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。

同时建立一个验证操作实现的主函数文件test13.cpp（以下图为例），编译并调试程序，直到正确运行。

2、图的邻接表的定义及实现：

建立头文件test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。

同时在主函数文件test13.cpp中调用这些函数进行验证（以下图为例）。

3、填写实验报告，实验报告文件取名为report13.doc。

4、上传实验报告文件report13.doc到BB。

注:

下载p256_GraphMatrix.cpp（邻接矩阵）和p258_GraphAdjoin.cpp（邻接表）源程序，读懂程序完成空缺部分代码。

三.函数的功能说明及算法思路

（包括每个函数的功能说明，及一些重要函数的算法实现思路）

四.实验结果与分析

（包括运行结果截图、结果分析等）

5.心得体会

程序比较难写，但是可以通过之前的一些程序来找到一些规律

（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。

）

【附录----源程序】

256:

//p-255图的存储结构以数组邻接矩阵表示,构造图的算法。

#include

#include

#include

#include

typedefcharVertexType;//顶点的名称为字符

constintMaxVertexNum=10;//图的最大顶点数

constintMaxEdgeNum=100;//边数的最大值

typedefintWeightType;//权值的类型

constWeightTypeMaxValue=32767;//权值的无穷大表示

typedefVertexTypeVexlist[MaxVertexNum];//顶点信息，定点名称

typedefWeightTypeAdjMatrix[MaxVertexNum][MaxVertexNum];//邻接矩阵

typedefenum{DG,DN,AG,AN}GraphKind;//有向图,有向网,无向图,无向网

typedefstruct{

Vexlistvexs;//顶点数据元素

AdjMatrixarcs;//二维数组作邻接矩阵

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

GraphKindkind;//图的种类标志

}MGraph;

voidCreateGraph（MGraph&G,GraphKindkd）//采用数组邻接矩阵表示法，构造图G

{//构造有向网G

inti,j,k,q;

charv,w;

G.kind=kd;//图的种类

printf（"输入要构造的图的顶点数和弧数：

\n"）;

scanf（"%d,%d",&G.vexnum,&G.arcnum）;

getchar（）;//过滤回车

printf（"依次输入图的顶点名称ABCD...等等：

\n"）;

for（i=0;i

getchar（）;//过滤回车

for（i=0;i

for（j=0;j

if（kd==DN||kd==AN）

G.arcs[i][j]=MaxValue;//网，初始值为无穷大

else

G.arcs[i][j]=0;//图，初始为0

if（kd==DN||kd==AN）

printf（"按照：

尾顶点名->头顶点名，权值输入数据:

如A->B,23\n"）;

else

printf（"按照：

尾顶点名->头顶点名输入数据:

A->B\n"）;

for（k=0;k

if（kd==DN||kd==AN）

scanf（"%c->%c,%d",&v,&w,&q）;//输入弧的两个定点及该弧的权重

else

scanf（"%c->%c",&v,&w）;

getchar（）;

for（i=0;i

if（G.vexs[i]==v）break;//查找出v在vexs[]中的位置i

if（i==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）;}

for（j=0;j

if（G.vexs[j]==w）break;//查找出v在vexs[]中的位置j

if（j==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）;}

if（kd==AN）//无向网

{

G.arcs[i][j]=q;//邻接矩阵对应位置置权值

G.arcs[j][i]=q;//无向图为对称矩阵

}

elseif（kd==DN）//有向网

G.arcs[i][j]=q;

elseif（kd==AG）//无向图

{

G.arcs[i][j]=1;//对称矩阵

G.arcs[j][i]=1;

}

else//有向图

G.arcs[i][j]=1;

//getchar（）;

}

}//CreateGraph

/*注意输入格式,按以下方式输入

构造有向网

输入要构造的网的顶点数和弧数：

4,5

依次输入网的顶点名称ABCD...等等：

abcd

按照：

尾顶点名->头顶点名，权值输入数据:

如A->B,23

a->b,5

a->c,8

c->b,7

a->d,4

d->c,3

输出邻接矩阵

∞|5|8|4|

∞|∞|∞|∞|

∞|7|∞|∞|

∞|∞|3|∞|

Pressanykeytocontinue

*/

voidPrintMGraph（MGraph&G）

{

inti,j;

switch（G.kind）

{

caseDG:

for（i=0;i

{

for（j=0;j

printf（"%2.d|",G.arcs[i][j]）;

printf（"\n"）;

}

break;

caseDN:

for（i=0;i

{

for（j=0;j

if（G.arcs[i][j]!

=MaxValue）printf（"%2.d|",G.arcs[i][j]）;

elseprintf（"∞|"）;

}

printf（"\n"）;

}

break;

caseAG:

for（i=0;i

{

for（j=0;j

printf（"%2.d|",G.arcs[i][j]）;

}

printf（"\n"）;

}

break;

caseAN:

//********完成构造无向网****************

/*请模仿编写无向网*/

for（i=0;i

{

for（j=0;j

if（G.arcs[i][j]!

=MaxValue）printf（"%2.d|",G.arcs[i][j]）;

elseprintf（"∞|"）;

}

printf（"\n"）;

}

break;

}

}

//*****************完成函数**********************************

voidcountdig（MGraphG）//请完成计算图的入度或初度

{

if（G.kind==DG||G.kind==DN）

{

//计算有向图或网的各个顶点的入度与出度

intoutD,inD;

inti,j;

for（i=0;i

outD=inD=0;

for（j=0;j

if（G.arcs[i][j]!

=0&&G.arcs[i][j]!

=MaxValue）

outD++;

}

for（j=0;j

if（G.arcs[j][i]!

=0&&G.arcs[j][i]!

=MaxValue）

inD++;

}

printf（"%c：

出度是%d,入度是%d\n",G.vexs[i],outD,inD）;

}

}

else

{

//计算无向图或网的度

inti,j;

intDu;

for（i=0;i

Du=0;

for（j=0;j

if（G.arcs[i][j]!

=0&&G.arcs[i][j]!

=MaxValue）

Du++;

}

printf（"%c的度是%d\n",G.vexs,Du）;

}

}

}

//************参照p265设计深度有限搜索***********

voidDFSMatrix（MGraphG,inti,intn,bool*visited）

{

cout<

visited[i]=true;

for（intj=0;j

if（G.arcs[i][j]!

=0&&G.arcs[i][j]!

=MaxValue&&!

visited[j]）

DFSMatrix（G,j,n,visited）;

}

//************参照p268设计广度有限搜索***********

voidBFSMatrix（MGraphG,inti,intn,bool*visited）

{

constintMaxSize=30;

intq[MaxSize]={0};

intfront=0,rear=0;

cout<

visited[i]=true;

q[++rear]=i;

while（front!

=rear）{

front=（front+1）%MaxSize;

intk=q[front];

for（intj=0;j

if（G.arcs[i][j]!

=0&&G.arcs[i][j]!

=MaxValue&&!

visited[j]）{

cout<

visited[j]=true;

rear=（rear+1）%MaxSize;

q[rear=j];

}

}

}

}

voidmain（）

{

MGraphG;

intk;

printf（"请选择图的种类：

0:

有向图,1:

有向网,2:

无向图,3:

无向网.请选择：

"）;

scanf（"%d",&k）;

switch（k）{//DG,DN,AG,AN

case0:

printf（"构造有向图\n"）;

CreateGraph（G,DG）;//采用数组邻接矩阵表示法，构造有向图

break;

case1:

printf（"构造有向网\n"）;

CreateGraph（G,DN）;//采用数组邻接矩阵表示法，构造有向网AGG

break;

case2:

printf（"构造无向图\n"）;

CreateGraph（G,AG）;//采用数组邻接矩阵表示法，构造无向图AGG

break;

case3:

printf（"构造无向网\n"）;

CreateGraph（G,AN）;//采用数组邻接矩阵表示法，构造无向网AGG

break;

}

PrintMGraph（G）;//打印图的邻接矩阵

bool*visited=newbool[G.vexnum];

inti;

cout<<"按图的邻接矩阵得到的深度优先遍历序列"<

for（i=0;i

DFSMatrix（G,0,G.vexnum,visited）;

cout<<"按图的邻接矩阵得到的广度优先遍历序列"<

for（i=0;i

BFSMatrix（G,0,G.vexnum,visited）;

cout<<"度：

"<

countdig（G）;

}

258:

//p-258图的存储结构以邻接表表示,构造图的算法。

//已完成若干函数，对尚未完成的请补全

//请注意输入格式，按以下方式构建一个图

/*

请选择图的种类：

0:

有向图,1:

有向网,2:

无向图,3:

无向网.请选择：

0

构造有向图

输入要构造的有向图的顶点数和弧数：

4,5

依次输入图的顶点名称ABCD...等等：

abcd

按照：

尾顶点名->头顶点名输入数据:

如A->B

a->b

a->c

a->d

c->b

d->c

*/

#include

#include

#include

#include

typedefcharVertexType;//顶点的名称为字符

constintMaxVertexNum=10;//图的最大顶点数

constintMaxEdgeNum=100;//边数的最大值

typedefintWeightType;//权值的类型

constWeightTypeMaxValue=32767;//权值的无穷大表示

typedefVertexTypeVexlist[MaxVertexNum];//顶点信息，定点名称

//邻接矩阵

typedefenum{DG,DN,AG,AN}GraphKind;//有向图,有向网,无向图,无向网

structEdgeNode{//链表边结点，表示弧

intadjvex;//存放与头结点顶点有关的另一个顶点在邻接表（数组）中的下标。

EdgeNode*next;//指向链表下一个结点

WeightTypeinfo;//权重值，或为该弧相关信息

};

typedefstructVNode{//邻接表，表示顶点

VertexTypedata;//顶点数据，顶点名称

EdgeNode*firstarc;//指向边结点链表第一个结点

}VNode,AdjList[MaxVertexNum];

typedefstruct{

AdjListvertices;

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

GraphKindkind;//图的种类标志

}ALGraph;

voidCreateGraph_DG（ALGraph&G）{//构造有向图G

EdgeNode*p;

inti,j,k;

charv,w;

G.kind=DG;//图的种类

printf（"输入要构造的有向图的顶点数和弧数：

\n"）;

scanf（"%d,%d",&G.vexnum,&G.arcnum）;

getchar（）;//过滤回车

printf（"依次输入图的顶点名称ABCD...等等：

\n"）;

for（i=0;i

scanf（"%c",&G.vertices[i].data）;//构造顶点数据

G.vertices[i].firstarc=NULL;//初始化指向链表指针

}

getchar（）;//过滤回车

printf（"按照：

尾顶点名->头顶点名输入数据:

如A->B\n"）;

for（k=0;k

scanf（"%c->%c",&v,&w）;

getchar（）;

for（i=0;i

if（G.vertices[i].data==v）break;//查找出v在vertices[]中的位置i

if（i==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）;}

for（j=0;j

if（G.vertices[j].data==w）break;//查找出w在vertices[]中的位置i

if（j==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）;}

p=（EdgeNode*）malloc（sizeof（EdgeNode））;//申请弧结点

p->adjvex=j;//置入弧尾顶点号

p->info=MaxValue;//图的权值默认为无穷大

p->next=G.vertices[i].firstarc;//插入链表

G.vertices[i].firstarc=p;

}

}

////////////////////////////////////////////////////////////////////////////////////////////////

voidCreateGraph_DN（ALGraph&G）//构造有向网G

{

EdgeNode*p;

inti,j,k;

charv,w;

WeightTypeq;

G.kind=DN;//图的种类

printf（"输入要构造的有向网的顶点数和弧数：

\n"）;

scanf（"%d,%d",&G.vexnum,&G.arcnum）;

getchar（）;//过滤回车

printf（"依次输入图的顶点名称ABCD...等等：

\n"）;

for（i=0;i

scanf（"%c",&G.vertices[i].data）;//构造顶点数据

G.vertices[i].firstarc=NULL;//初始化指向链表指针

}

getchar（）;//过滤回车

printf（"按照：

尾顶点名->头顶点名,权值输入数据:

如A->B,8\n"）;

for（k=0;k

scanf（"%c->%c,%d",&v,&w,&q）;

getchar（）;

for（i=0;i

if（G.vertices[i].data==v）break;//查找出v在vertices[]中的位置i

if（i==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）;}

for（j=0;j

if（G.vertices[j].data==w）break;//查找出w在vertices[]中的位置i

if（j==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）;}

p=（EdgeNode*）malloc（sizeof（EdgeNode））;//申请弧结点

p->adjvex=j;//置入弧尾顶点号

p->info=q;//图的权值默认为无穷大

p->next=G.vertices[i].firstarc;//插入链表

G.vertices[i].firstarc=p;

}

}

voidCreateGraph_AG（ALGraph&G）//构造无向图G

{

EdgeNode*p;

inti,j,k;

charv,w;

G.kind=AG;//图的种类

printf（"输入要构造的有向图的顶点数和弧数：

\n"）;

scanf（"%d,%d",&G.vexnum,&G.arcnum）;

getchar（）;//过滤回车

printf（"依次输入图的顶点名称ABCD...等等：

\n"）;

for（i=0;i

scanf（"%c",&G.vertices[i].data）;//构造顶点数据

G.vertices[i].firstarc=NULL;//初始化指向链表指针

}

getchar（）;//过滤回车

printf（"按照：

尾顶点名->头顶点名输入数据:

如A->B\n"）;

for（k=0;k

scanf（"%c->%c",&v,&w）;

getchar（）;

for（i=0;i

if（G.vertices[i].data==v）break;//查找出v在vertices[]中的位置i

if（i==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）;}

for（j=0;j

if（G.vertices[j].data==w）break;//查找出w在vertices[]中的位置i

if（j==G.vexnum）{cerr<<"vertexERROR!

";exit

（1）