数据结构 图.docx
《数据结构 图.docx》由会员分享，可在线阅读，更多相关《数据结构 图.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构图
淮海工学院计算机科学系
实验报告书
课程名：
《数据结构》
题目：
图形数据结构实验
班级：
学号：
姓名：
图形数据结构实验报告要求
1目的与要求:
1）掌握图的邻接矩阵、邻接表、十字链表、邻接多重链表存储结构表示及其创建算法的c语言实现；
2）掌握图的深度优先搜索遍历算法和图的广度优先搜索遍历算法及C语言实现；
3）掌握AOV-网普里姆构造最小生成树算法的数据结构和算法实现；
4）掌握AOE-网关路经的生成算法和实现；
5）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；
6）认真书写实验报告,并按时提交（第12周周一提交）。
2实验内容或题目
题目：
一、图形数据结构实验——图的建立与遍历。
内容：
1）使用邻接矩阵和邻接表储表示分别实现如下给定的图1和或图2所示图的物理存储结构。
2）在1）所建立的图形存储结构上分别实现深度优先搜索遍历和广度优先搜索遍历，并给出遍历结果（序列）。
题目：
二、连通网的最小生成树及其应用实验（选做）
内容：
对下图所示通信连通网，按照普里姆算法实现其最小生成树。
3实验步骤与源程序
邻接矩阵存储图进行深度广度遍历
#include
#include
#defineINFINITY32767
#defineMAX_VEX20//最大顶点个数
#defineQUEUE_SIZE（MAX_VEX+1）//队列长度
usingnamespacestd;
bool*visited;//访问标志数组
//图的邻接矩阵存储结构
typedefstruct{
char*vexs;//顶点向量
intarcs[MAX_VEX][MAX_VEX];//邻接矩阵
intvexnum,arcnum;//图的当前顶点数和弧数
}Graph;
//队列类
classQueue{
public:
voidInitQueue（）{
base=（int*）malloc（QUEUE_SIZE*sizeof（int））;
front=rear=0;
}
voidEnQueue（inte）{
base[rear]=e;
rear=（rear+1）%QUEUE_SIZE;
}
voidDeQueue（int&e）{
e=base[front];
front=（front+1）%QUEUE_SIZE;
}
public:
int*base;
intfront;
intrear;
};
//图G中查找元素c的位置
intLocate（GraphG,charc）{
for（inti=0;iif（G.vexs[i]==c）returni;
return-1;
}
//创建无向网
voidCreateUDN（Graph&G）{
inti,j,w,s1,s2;
chara,b,temp;
printf（"输入顶点数和弧数:
"）;
scanf（"%d%d",&G.vexnum,&G.arcnum）;
temp=getchar（）;//接收回车
G.vexs=（char*）malloc（G.vexnum*sizeof（char））;//分配顶点数目
printf（"输入%d个顶点.\n",G.vexnum）;
for（i=0;iprintf（"输入顶点%d:
",i）;
scanf（"%c",&G.vexs[i]）;
temp=getchar（）;//接收回车
}
for（i=0;ifor（j=0;jG.arcs[i][j]=INFINITY;
printf（"输入%d条弧.\n",G.arcnum）;
for（i=0;iprintf（"输入弧%d:
",i）;
scanf（"%c%c1",&a,&b,&w）;//输入一条边依附的顶点和权值
temp=getchar（）;//接收回车
s1=Locate（G,a）;
s2=Locate（G,b）;
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//图G中顶点k的第一个邻接顶点
intFirstVex（GraphG,intk）{
if（k>=0&&kfor（inti=0;iif（G.arcs[k][i]!
=INFINITY）returni;
}
return-1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
intNextVex（GraphG,inti,intj）{
if（i>=0&&i=0&&jfor（intk=j+1;kif（G.arcs[i][k]!
=INFINITY）returnk;
}
return-1;
}
//深度优先遍历
voidDFS（GraphG,intk）{
inti;
if（k==-1）{//第一次执行DFS时,k为-1
for（i=0;iif（!
visited[i]）DFS（G,i）;//对尚未访问的顶点调用DFS
}
else{
visited[k]=true;
printf（"%c",G.vexs[k]）;//访问第k个顶点
for（i=FirstVex（G,k）;i>=0;i=NextVex（G,k,i））
if（!
visited[i]）DFS（G,i）;//对k的尚未访问的邻接顶点i递归调用DFS
}
}
//广度优先遍历
voidBFS（GraphG）{
intk;
QueueQ;//辅助队列Q
Q.InitQueue（）;
for（inti=0;iif（!
visited[i]）{//i尚未访问
visited[i]=true;
printf（"%c",G.vexs[i]）;
Q.EnQueue（i）;//i入列
while（Q.front!
=Q.rear）{
Q.DeQueue（k）;//队头元素出列并置为k
for（intw=FirstVex（G,k）;w>=0;w=NextVex（G,k,w））
if（!
visited[w]）{//w为k的尚未访问的邻接顶点
visited[w]=true;
printf（"%c",G.vexs[w]）;
Q.EnQueue（w）;
}
}
}
}
//主函数
voidmain（）{
inti;
GraphG;
CreateUDN（G）;
visited=（bool*）malloc（G.vexnum*sizeof（bool））;
printf（"\n深度优先遍历:
"）;
for（i=0;ivisited[i]=false;
DFS（G,-1）;
printf（"\n广度优先遍历:
"）;
for（i=0;ivisited[i]=false;
BFS（G）;
//printf（"12346578\n"）;
printf（"\n程序结束.\n"）;
}
//要输入权值1
邻接表深度广度遍历
#include
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineNULL0
#defineMAX20
typedefintStatus;
typedefstructNode
{intelem;
structNode*next;
}Node,*QNode;
typedefstruct
{QNodefront;
QNoderear;
}Queue;
typedefstructArcNode/*头节点*/
{intadjvex;/*该边所指向的顶点的位置*/
structArcNode*nextarc;/*指向下一条边*/
}ArcNode;
typedefstructVNode/*表节点*/
{intdata;/*顶点信息*/
ArcNode*firstarc;/*指向第一条依附该节点的边的指针*/
}VNode,AdjList[MAX];
typedefstruct
{AdjListvertices;/*表节点*/
intvexnum;/*节点的个数*/
intarcnum;/*边的条数*/
}Graph;
StatusInitQueue（Queue*Q）
{Q->front=Q->rear=（QNode）malloc（sizeof（Node））;
if（!
Q->front）exit（OVERFLOW）;
Q->front->next=NULL;
returnOK;
}
StatusEnQueue（Queue*Q,inte）
{QNodep=（QNode）malloc（sizeof（Node））;
if（!
p）exit（OVERFLOW）;
p->elem=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
returnOK;
}
StatusDeQueue（Queue*Q,int*e）
{QNodep;
p=Q->front->next;
Q->front->next=p->next;
if（Q->rear==p）
Q->rear=Q->front;
*e=p->elem;
free（p）;
returnOK;
}
StatusQueueEmpty（QueueQ）
{if（Q.rear==Q.front）returnTRUE;
elsereturnFALSE;
}
intLocateVex（Graph*G,intv）/*返回节点v在图中的位置*/
{inti;
for（i=0;ivexnum;++i）
if（G->vertices[i].data==v）break;
elsecontinue;
if（ivexnum）returni;
elsereturn-1;
}
StatusCreateGraph（Graph*G）/*以邻接表形式创建无向连通图G*/
{intm,n,i,j,k,v1,v2,flag=0;
ArcNode*p1,*q1,*p,*q;
printf（"输入顶点数:
"）;
scanf（"%d",&m）;
printf（"输入弧数:
"）;
scanf（"%d",&n）;
G->vexnum=m;/*顶点数目*/
G->arcnum=n;/*边的数目*/
for（i=0;ivexnum;++i）
{G->vertices[i].data=i+1;/*顶点信息*/
G->vertices[i].firstarc=NULL;
}
printf（"输出顶点信息:
\n"）;
for（i=0;ivexnum;++i）
printf（"v%d\n",G->vertices[i].data）;
for（k=0;karcnum;++k）
{printf（"请输入第%d对边:
",k+1）;
scanf（"%d%d",&v1,&v2）;
i=LocateVex（G,v1）;
j=LocateVex（G,v2）;
if（i>=0&&j>=0）
{++flag;
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->adjvex=j;
p->nextarc=NULL;
if（!
G->vertices[i].firstarc）G->vertices[i].firstarc=p;
else{for（p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc）;
p1->nextarc=p;
}
q=（ArcNode*）malloc（sizeof（ArcNode））;
q->adjvex=i;
q->nextarc=NULL;
if（!
G->vertices[j].firstarc）G->vertices[j].firstarc=q;
else{for（q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc）;
q1->nextarc=q;
}
}
else{printf（"没有这条边!
\n"）;
k=flag;
}
}
printf（"邻接表:
\n"）;/*输出邻接表*/
for（i=0;ivexnum;++i）
{printf（"\t%dv%d->",i,G->vertices[i].data）;
p=G->vertices[i].firstarc;
while（p->nextarc）
{printf（"%d->",p->adjvex）;
p=p->nextarc;
}
printf（"%d\n",p->adjvex）;
}
returnOK;
}
intFirstAdjVex（GraphG,intv）/*返回v的第一个邻接顶点*/
{if（G.vertices[v].firstarc）
returnG.vertices[v].firstarc->adjvex;
else
return-1;
}/*FirstAdjVex*/
intNextAdjVex（GraphG,intv,intw）/*返回v中相对于w的下一个邻接顶点*/
{intflag=0;
ArcNode*p;
p=G.vertices[v].firstarc;
while（p）
{
if（p->adjvex==w）
{
flag=1;
break;
}
p=p->nextarc;
}
if（flag&&p->nextarc）
returnp->nextarc->adjvex;
else
return-1;
}/*NextAdjVex*/
intVisited[MAX];
voidDFS（GraphG,intv）/*深度优先遍历*/
{intw;
Visited[v]=TRUE;
printf（"v%d",G.vertices[v].data）;
for（w=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））
if（!
Visited[w]）DFS（G,w）;
}
voidDFSTraverse（GraphG）
{intv;
for（v=0;vVisited[v]=FALSE;
for（v=0;vif（!
Visited[v]）DFS（G,v）;
}
voidBFSTraverse（GraphG）/*广度优先遍历*/
{intv,v1,w;
Queueq;
for（v=0;vVisited[v]=FALSE;
InitQueue（&q）;
for（v=0;vif（!
Visited[v]）
{Visited[v]=TRUE;
printf（"v%d",G.vertices[v].data）;
EnQueue（&q,v）;/*第一个顶点入队*/
while（!
QueueEmpty（q））
{DeQueue（&q,&v1）;/*第一个顶点出对*/
for（w=FirstAdjVex（G,v1）;w>=0;w=NextAdjVex（G,v1,w））
if（!
Visited[w]）{Visited[w]=TRUE;
printf（"v%d",G.vertices[w].data）;
EnQueue（&q,w）;
}/*if*/
}
}
}
main（）
{GraphG;
charch;
system（"cls"）;
CreateGraph（&G）;
while
（1）
{printf（"深度遍历
（1）广度遍历
（2）放弃（0）?
\n"）;
scanf（"%d",&ch）;
switch（ch）
{case1:
printf（"DepthFirstSearch:
\n"）;
DFSTraverse（G）;
break;
case2:
printf（"\nBreadthFirstSearch:
\n"）;
BFSTraverse（G）;
break;
case0:
exit（0）;
}
}
getch（）;
}
4测试数据与实验结果（可以抓图粘贴）
邻接表进行深度广度遍历
邻接表存储
5结果分析与实验体会
通过本次图的实验，我熟悉掌握了图的邻接矩阵和邻接表的存储的算法，了解了图的多种存储方法，以及邻接矩阵、邻接表的深度及广度遍历的算法，对图又有一进一步的了解。
升级会员 