图形数据结构实验.docx
《图形数据结构实验.docx》由会员分享，可在线阅读，更多相关《图形数据结构实验.docx（20页珍藏版）》请在冰点文库上搜索。
图形数据结构实验
淮海工学院计算机科学系
实验报告书
课程名：
《数据结构》
题目：
图形数据结构实验
班级：
学号：
姓名：
图形数据结构实验报告要求
1目的与要求:
1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；
2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；
3）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；
4）认真书写实验报告,并按时提交（第12周周三提交）。
2实验内容或题目
题目：
一、图形数据结构实验——图的建立与遍历。
内容：
1）使用邻接矩阵和邻接表储表示分别实现如下给定的图1和图2所示图的物理存储结构。
2）在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。
3实验步骤与源程序
邻接矩阵：
#include"stdlib.h"
#include"stdio.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）*/
typedefstructnode
{
intdata;
structnode*next;
structnode*first;
structnode*last;
}LinkQueue;
intInitQueue（LinkQueue*s）
{
s->first=（LinkQueue*）malloc（sizeof（LinkQueue））;
s->last=s->first;
s->first->next=NULL;
returnTrue;
}
intEnterQueue（LinkQueue*s,intx）
{
LinkQueue*temp;
temp=（LinkQueue*）malloc（sizeof（LinkQueue））;
if（temp!
=NULL）
{
temp->data=x;
temp->next=NULL;
s->last->next=temp;
s->last=temp;
returnTrue;
}
returnFalse;
}
intIsEmpty（LinkQueue*s）
{
if（s->first==s->last）
returnTrue;
else
returnFalse;
}
intDeleteQueue（LinkQueue*s,int*v）
{
LinkQueue*temp;
if（s->last==s->first）
returnFalse;
temp=（LinkQueue*）malloc（sizeof（LinkQueue））;
temp->first=s->first->next;
s->first->next=temp->first->next;
if（s->last==temp->first）
s->last=s->first;
*v=temp->first->data;
free（temp）;
returnTrue;
}
intLocateVertex（AdjMatrix*G,VertexDatav）/*求顶点位置函数*/
{
intj=Error,k;
for（k=0;kvexnum;k++）
if（G->vexs[k]==v）
{
j=k;
break;
}
return（j）;
}
intvisited[50];
intCreateDN（AdjMatrix*G）/*创建一个有向网*/
{
inti,j,k,weight;
VertexDatav1,v2;
printf（"输入图的弧数和顶点数\n"）;
fflush（stdin）;
scanf（"%d,%d",&G->arcnum,&G->vexnum）;/*输入图的顶点数和弧数*/
for（i=0;ivexnum;i++）/*初始化邻接矩阵*/
for（j=0;jvexnum;j++）
G->arcs[i][j].adj=INFINITY;
for（i=0;ivexnum;i++）//输入顶点字符循环
{
printf（"输入图的顶点\n"）;
fflush（stdin）;
scanf（"%c",&G->vexs[i]）;/*输入图的顶点*/
}
for（k=0;karcnum;k++）
{
printf（"输入一条弧的两个顶点及权值\n"）;
fflush（stdin）;
scanf（"%c,%c,%d",&v1,&v2,&weight）;/*输入一条弧的两个顶点及权值*/
i=LocateVertex（G,v1）;
j=LocateVertex（G,v2）;
G->arcs[i][j].adj=1;/*建立弧*/
}
return（Ok）;
}
intCreateUDN（AdjMatrix*G）/*创建一个有向网*/
{
inti,j,k,weight;
VertexDatav1,v2;
printf（"输入图的弧数和顶点数\n"）;
fflush（stdin）;
scanf（"%d,%d",&G->arcnum,&G->vexnum）;/*输入图的顶点数和弧数*/
for（i=0;ivexnum;i++）/*初始化邻接矩阵*/
for（j=0;jvexnum;j++）
G->arcs[i][j].adj=INFINITY;
for（i=0;ivexnum;i++）//输入顶点字符循环
{
printf（"输入图的顶点\n"）;
fflush（stdin）;
scanf（"%c",&G->vexs[i]）;/*输入图的顶点*/
}
for（k=0;karcnum;k++）
{
printf（"输入一条弧的两个顶点及权值\n"）;
fflush（stdin）;
scanf（"%c,%c,%d",&v1,&v2,&weight）;/*输入一条弧的两个顶点及权值*/
i=LocateVertex（G,v1）;
j=LocateVertex（G,v2）;
G->arcs[i][j].adj=1;/*建立弧*/
G->arcs[j][i].adj=G->arcs[i][j].adj;
}
return（Ok）;
}
voidDepth1（AdjMatrixg1,intvo）
{
intvj;
printf（"%c",g1.vexs[vo]）;
visited[vo]=True;
for（vj=0;vjif（（!
visited[vj]）&&（g1.arcs[vo][vj].adj==1））
Depth1（g1,vj）;
}
voidBreadth1（AdjMatrixg1,intvo）
{
intvi,vj;
LinkQueueQ;
InitQueue（&Q）;
visited[vo]=True;
EnterQueue（&Q,vo）;
while（!
IsEmpty（&Q））
{
DeleteQueue（&Q,&vi）;
printf（"%c",g1.vexs[vi]）;
for（vj=0;vjif（（!
visited[vj]）&&（g1.arcs[vi][vj].adj==1））
{
visited[vj]=True;
EnterQueue（&Q,vj）;
}
}
}
voidTraverse1（AdjMatrixg1）//邻接矩阵存储结构的深度和广度优先搜索遍历
{
intvi;
for（vi=0;vivisited[vi]=False;
printf（"\n图的深度遍历序列\n"）;
for（vi=0;vi{
if（!
visited[vi]）
{
Depth1（g1,vi）;
printf（"\n"）;
}
}
for（vi=0;vivisited[vi]=False;
printf（"\n图的广度遍历序列\n"）;
for（vi=0;vi{
if（!
visited[vi]）
{
Breadth1（g1,vi）;
printf（"\n"）;
}
}
}
voidmain（）
{
printf（"有向图\n"）;
AdjMatrixG;
CreateDN（&G）;
Traverse1（G）;
printf（"无向图\n"）;
CreateUDN（&G）;
Traverse1（G）;
}
邻接表：
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"math.h"
#defineMAX_INT1000
#defineMAX_VERTEX_NUM20
#defineMAX_QUEUE_NUMBER20
#defineTRUE1
#defineFALSE0
#defineQueueElementTypeint
typedefstructArcNode
{
intadjvex;
doubleadj;
structArcNode*nextarc;
}ArcNode;
typedefstructVexNode
{
charszName[40];
ArcNode*firstarc;
}VexNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
{
AdjListvexs;
intvexnum,arcnum;
}Net;
//定义队列
typedefstruct{
int*elem;
intfront,rear;
}Queue;
voidInitQueue（Queue&Q）
{
Q.elem=newint[MAX_QUEUE_NUMBER];
Q.front=Q.rear=0;
}
intEmptyQueue（QueueQ）
{
if（Q.front==Q.rear）
return0;
else
return1;
}
voidDestroyQueue（Queue&Q）{
delete[]Q.elem;
Q.front=Q.rear=0;
}
voidEnterQueue（Queue&Q,inte）
{
if（（Q.rear+1）%MAX_QUEUE_NUMBER!
=Q.front）
Q.elem[Q.rear]=e;
else
printf（"队列满!
\n"）;
Q.rear=（Q.rear+1）%MAX_QUEUE_NUMBER;
}
voidLeaveQueue（Queue&Q,int&e）
{
if（Q.rear!
=Q.front）
e=Q.elem[Q.front];
else
printf（"队列空!
\n"）;
Q.front=（Q.front+1）%MAX_QUEUE_NUMBER;
}
intLocateVex（Netga,char*name）
{
inti;
for（i=0;iif（strcmp（name,ga.vexs[i].szName）==0）
returni;
return-1;
}
voidcrt_net（Net&ga）
{
ArcNode*p;
charname1[40],name2[40];
inti,j,k;
doublew;
printf（"请输入顶点数和弧数：
"）;
scanf（"%d%d",&ga.vexnum,&ga.arcnum）;
printf（"请依次输入顶点名：
\n"）;
for（i=0;i{
scanf（"%s",ga.vexs[i].szName）;
ga.vexs[i].firstarc=NULL;
}
for（k=0;k{
printf（"请输入相邻的两个定点和权值：
"）;
scanf（"%s%s%lf",name1,name2,&w）;
i=LocateVex（ga,name1）;
j=LocateVex（ga,name2）;
p=newArcNode;
p->adjvex=j;
p->adj=w;
p->nextarc=ga.vexs[i].firstarc;
ga.vexs[i].firstarc=p;
}
}
voidDFS（Netga,char*name,int*visited）
{
intv,w;
ArcNode*p;
v=LocateVex（ga,name）;
visited[v]=1;
printf（"%s",ga.vexs[v].szName）;
p=ga.vexs[v].firstarc;
while（p!
=NULL）
{
w=p->adjvex;
if（visited[w]==0）
DFS（ga,ga.vexs[w].szName,visited）;
p=p->nextarc;
}
}
voidDFSTravel（Netga,char*name）
{
intv,k=0;
intvisited[20];
for（v=0;vvisited[v]=0;
for（v=LocateVex（ga,name）;k!
=2;v=（v+1）%（ga.vexnum-1））
{
if（v+1==LocateVex（ga,name））
k++;
if（visited[v]==0）
DFS（ga,ga.vexs[v].szName,visited）;
}
}
voidBFSTravel（Netga,char*name）
{
ArcNode*p;
intv,w,u,k=0;
QueueQ;
intvisited[20];
for（v=0;vvisited[v]=0;
InitQueue（Q）;
for（v=LocateVex（ga,name）;k!
=2;v=（v+1）%（ga.vexnum-1））
{
if（v+1==LocateVex（ga,name））
k++;
if（visited[v]==0）
{
visited[v]=1;
printf（"%s",ga.vexs[v].szName）;
EnterQueue（Q,v）;
while（EmptyQueue（Q）!
=0）
{
LeaveQueue（Q,u）;
p=ga.vexs[u].firstarc;
while（p!
=NULL）
{
w=p->adjvex;
if（visited[w]==0）
{
printf（"%s",ga.vexs[w].szName）;
visited[w]=1;
EnterQueue（Q,w）;
}
p=p->nextarc;
}
}
}
}
}
voidmain（）
{
Netga;
crt_net（ga）;
printf（"深度优先遍历：
"）;
DFSTravel（ga,ga.vexs[1].szName）;
printf（"\n"）;
printf（"广度优先遍历：
"）;
BFSTravel（ga,ga.vexs[1].szName）;
printf（"\n"）;
}
4测试数据与实验结果（可以抓图粘贴）
5结果分析与实验体会
个人觉得这次的实验很难，很多的地方都不知道要怎么写，比如怎么输出邻接矩阵，邻接表的也不知道要怎么处理，自己改了很久，但是不对，最后是请同学帮忙完成的。
升级会员 