数据结构第六次实验报告.docx

数据结构第六次实验报告.docx

《数据结构第六次实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构第六次实验报告.docx（19页珍藏版）》请在冰点文库上搜索。

数据结构第六次实验报告

数据结构试验报告

实验名称：

图

学生姓名：

　　王勇　

学号：

E01014367

专业：

10级网络工程一班

完成时间：

　2012年5月31日

一、实验目的

1.熟练掌握图的邻接矩阵与邻接表的存储方式。

2.实现图的一些基本运算，特别是深度遍历和广度遍历。

3.掌握以图为基础的一些常用算法，如最小生成树、拓扑排序、最短路径等。

二、实验内容与要求

1.从键盘上输入图的顶点数、边数以及边的信息，建立图的邻接矩阵。

请将使用的图画在实验报告上。

有向图（g1）和无向图（g2）各创建一个。

2.参照要求1，创建图g1，g2的邻接表。

3.在要求2完成后，对邻接表表示的图g1和g2进行深度优先遍历和广度优先遍历，并输出遍历结果。

请以不同的起始点测试遍历运行结果。

程序；

#include"stdafx.h"

#include

#include

usingnamespacestd;

#defineint_max0

#defineinf9999

#definemax20

//…………………………………………邻接矩阵定义……………………

typedefstructArcCell

{

intadj;

char*info;

}ArcCell,AdjMatrix[20][20];

typedefstruct

{

charvexs[20];

AdjMatrixarcs;

intvexnum,arcnum;

}MGraph_L;

//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

intlocalvex（MGraph_LG,charv）//返回V的位置

{

inti=0;

while（G.vexs[i]!

=v）

{

++i;

}

returni;

}

//创建无向图邻接矩阵

intcreatUDG（MGraph_L&G）

{

charv1,v2;

inti,j,w;

cout<<"…………创建无向图…………"<

（46）不包括“（）”"<

cin>>G.vexnum>>G.arcnum;

for（i=0;i!

=G.vexnum;++i）

{

cout<<"输入顶点"<

cin>>G.vexs[i];

}

for（i=0;i!

=G.vexnum;++i）

for（j=0;j!

=G.vexnum;++j）

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

for（intk=0;k!

=G.arcnum;++k）

{

cout<<"输入一条边依附的顶点和权:

（ab3）不包括“（）”"<

cin>>v1>>v2>>w;//输入一条边依附的两点及权值

i=localvex（G,v1）;//确定顶点V1和V2在图中的位置

j=localvex（G,v2）;

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

}

cout<<"图G邻接矩阵创建成功！

"<

returnG.vexnum;

}

//创建有向图邻接矩阵

intcreatDG（MGraph_L&G）

{

charv1,v2;

inti,j,w;

cout<<"…………创建有向图…………"<

（46）不包括“（）”"<

cin>>G.vexnum>>G.arcnum;

for（i=0;i!

=G.vexnum;++i）

{

cout<<"输入顶点"<

cin>>G.vexs[i];

}

for（i=0;i!

=G.vexnum;++i）

for（j=0;j!

=G.vexnum;++j）

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

for（intk=0;k!

=G.arcnum;++k）

{

cout<<"输入一条边依附的顶点和权:

（ab3）不包括“（）”"<

cin>>v1>>v2>>w;//输入一条边依附的两点及权值

i=localvex（G,v1）;//确定顶点V1和V2在图中的位置

j=localvex（G,v2）;

G.arcs[i][j].adj=w;

}

cout<<"图G邻接矩阵创建成功！

"<

returnG.vexnum;

}

//邻接矩阵输出

voidljjzprint（MGraph_LG）

{

inti,j;

for（i=0;i!

=G.vexnum;++i）

{

for（j=0;j!

=G.vexnum;++j）

cout<

cout<

}

}

intvisited[max];//访问标记

intwe;

//邻接表相关定义

typedefstructarcnode//弧结点

{

intadjvex;//该弧指向的顶点的位置

structarcnode*nextarc;//弧尾相同的下一条弧

char*info;//该弧信息

}arcnode;

typedefstructvnode//邻接链表顶点头接点

{

chardata;//结点信息

arcnode*firstarc;//指向第一条依附该结点的弧的指针

}vnode,adjlist;

typedefstruct//图的定义

{

adjlistvertices[max];

intvexnum,arcnum;

intkind;

}algraph;

//…………………………………………队列定义……………………

typedefstructqnode

{

intdata;

structqnode*next;

}qnode,*queueptr;

typedefstruct

{

queueptrfront;

queueptrrear;

}linkqueue;

typedefstructacr

{

intpre;//弧的一结点

intbak;//弧另一结点

intweight;//弧的权

}edg;

//创建无向图邻接表

intcreatadj（algraph&gra,MGraph_LG）

{

inti=0,j=0;

arcnode*arc,*tem,*p;

for（i=0;i!

=G.vexnum;++i）

{

gra.vertices[i].data=G.vexs[i];

gra.vertices[i].firstarc=NULL;

}

for（i=0;i!

=G.vexnum;++i）

{

for（j=0;j!

=G.vexnum;++j）

{

if（gra.vertices[i].firstarc==NULL）

{

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

=int_max&&j!

=G.vexnum）

{

arc=（arcnode*）malloc（sizeof（arcnode））;

arc->adjvex=j;

gra.vertices[i].firstarc=arc;

arc->nextarc=NULL;

p=arc;

++j;

while（G.arcs[i][j].adj!

=int_max&&j!

=G.vexnum）

{

tem=（arcnode*）malloc（sizeof（arcnode））;

tem->adjvex=j;

gra.vertices[i].firstarc=tem;

tem->nextarc=arc;

arc=tem;

++j;

}

--j;

}

}

else

{

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

=int_max&&j!

=G.vexnum）

{

arc=（arcnode*）malloc（sizeof（arcnode））;

arc->adjvex=j;

p->nextarc=arc;

arc->nextarc=NULL;

p=arc;

}

}

}

}

gra.vexnum=G.vexnum;

gra.arcnum=G.arcnum;

cout<<"图G邻接表创建成功！

"<

return1;

}

//邻接表输出

voidadjprint（algraphgra）

{

inti;

for（i=0;i!

=gra.vexnum;++i）

{

arcnode*p;

cout<

p=gra.vertices[i].firstarc;

while（p!

=NULL）

{

cout<adjvex;

p=p->nextarc;

}

cout<

}

}

intfirstadjvex（algraphgra,vnodev）//返回依附顶点V的第一个点

//即以V为尾的第一个结点

{

if（v.firstarc!

=NULL）

returnv.firstarc->adjvex;

}

intnextadjvex（algraphgra,vnodev,intw）//返回依附顶点V的相对于W的下一个顶点

{

arcnode*p;

p=v.firstarc;

while（p!

=NULL&&p->adjvex!

=w）

{

p=p->nextarc;

}

if（p->adjvex==w&&p->nextarc!

=NULL）

{

p=p->nextarc;

returnp->adjvex;

}

if（p->adjvex==w&&p->nextarc==NULL）

return-10;

}

intinitqueue（linkqueue&q）//初始化队列

{

q.rear=（queueptr）malloc（sizeof（qnode））;

q.front=q.rear;

if（!

q.front）

return0;

q.front->next=NULL;

return1;

}

intenqueue（linkqueue&q,inte）//入队

{

queueptrp;

p=（queueptr）malloc（sizeof（qnode））;

if（!

p）

return0;

p->data=e;

p->next=NULL;

q.rear->next=p;

q.rear=p;

return1;

}

intdequeue（linkqueue&q,int&e）//出队

{

queueptrp;

if（q.front==q.rear）

return0;

p=q.front->next;

e=p->data;

q.front->next=p->next;

if（q.rear==p）

q.rear=q.front;

free（p）;

return1;

}

intqueueempty（linkqueueq）//判断队为空

{

if（q.front==q.rear）

return1;

return0;

}

voidbfstra（algraphgra）//广度优先遍历

{

inti,e;

linkqueueq;

for（i=0;i!

=gra.vexnum;++i）

visited[i]=0;

initqueue（q）;

for（i=0;i!

=gra.vexnum;++i）

if（!

visited[i]）

{visited[i]=1;

cout<

enqueue（q,i）;

while（!

queueempty（q））

{

dequeue（q,e）;

//cout<<""<

for（we=firstadjvex（gra,gra.vertices[e]）;we>=0;we=nextadjvex（gra,gra.vertices[e],we））

{

if（!

visited[we]）

{

visited[we]=1;

cout<

enqueue（q,we）;

}

}

}

}

}

intdfs（algraphgra,inti）;//声明DFS

intdfstra（algraphgra）

{

inti,j;

for（i=0;i!

=gra.vexnum;++i）

{

visited[i]=0;

}

for（j=0;j!

=gra.vexnum;++j）

{

if（visited[j]==0）

dfs（gra,j）;

}

return0;

}

intdfs（algraphgra,inti）

{

visited[i]=1;

intwe1;

cout<

for（we=firstadjvex（gra,gra.vertices[i]）;we>=0;we=nextadjvex（gra,gra.vertices[i],we））

{

we1=we;

if（visited[we]==0）

dfs（gra,we）;

}

return12;

}

intbfstra_fen（algraphgra）//求连通分量

{

inti,j;

for（i=0;i!

=gra.vexnum;++i）

{

visited[i]=0;

}

for（j=0;j!

=gra.vexnum;++j）

{

if（visited[j]==0）

{

dfs（gra,j）;

cout<

}

}

return0;

}

voidmain（）

{

algraphgra;

MGraph_LG;

inti,d,g[20][20],k;

chara='a';

cout<<"构建邻接矩阵\n"<

cout<<"***************菜单**********"<

cout<<"0:

构建有向图（同时构建邻接矩阵和邻接表）1:

构建无向图（同时构建邻接矩阵和邻接表）"<

scanf（"%d",&k）;

switch（k）{

case0:

{

d=creatDG（G）;

creatadj（gra,G）;

break;}

case1:

{

d=creatUDG（G）;

creatadj（gra,G）;

break;}

default:

exit（0）;

}

vnodev;

cout<<"…………………菜单……………………"<

cout<<"0、显示该图的邻接矩阵……………………"<

cout<<"1、显示该图的邻接表……………………"<

cout<<"2、深度优先遍历…………………………"<

cout<<"3、广度优先遍历…………………………"<

ints;

chary='y';

while（y='y'）

{

cout<<"请选择菜单：

"<

cin>>s;

switch（s）

{

case0:

cout<<"邻接矩阵显示如下：

"<

ljjzprint（G）;

break;

case1:

cout<<"邻接表显示如下：

"<

adjprint（gra）;

break;

case2:

cout<<"广度优先遍历：

";

bfstra（gra）;

cout<

break;

case3:

for（i=0;i!

=gra.vexnum;++i）

{

visited[i]=0;

}

cout<<"深度优先遍历：

";

dfstra（gra）;

cout<

break;

}

cout<

y/n:

";

cin>>y;

if（y=='n'）

break;

}

}

运行结果

1调试时的问题