实验3 图型数据结构实验.docx

实验3 图型数据结构实验.docx

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

实验3图型数据结构实验

淮海工学院计算机工程学院

实验报告书

课程名：

《数据结构》

题目：

实验3图形数据结构实验

班级：

学号：

姓名：

实验3图形数据结构实验

实验目的和要求

1．熟悉图的两种常用的存储结构，邻接矩阵和邻接表。

2．在这两种存储结构上的两种遍历图的方法，即深度优先遍历和广度优先遍历。

3．熟练掌握拓扑排序算法；理解求有向无环图的关键路径算法。

4．进一步掌握递归算法的设计方法。

实验环境

TurboC或VC++

实验学时

4学时，必做实验

实验内容和步骤

一、要求画图并对所画的图进行DFS和BFS遍历。

如：

实验步骤

实验步骤：

1.输入图的顶点数目和边数.

2.建立图的邻接表.

3.按深度优先和广度优先遍历图.

4.给出遍历序列.

源程序

t#defineN10

#defineINFINITY32768

#defineTrue1

#defineFalse0

#defineError-1

#defineOk1

#include"stdlib.h"

#include"stdio.h"

typedefenum{DG,DN,UDG,UDN}GraphKind;

typedefcharVertexData;

/*..............................*/

typedefstructArcNode2

{

intadjvex;

structArcNode2*nextarc;

}ArcNode2;

typedefstructVertexNode

{

VertexDatadata;

ArcNode2*firstarc;

}VertexNode;

typedefstruct

{

VertexNodevertex[N];

intvexnum2,arcnum2;

GraphKindkind2;

}AdjList;

/*.............................*/

typedefstructNode

{

intdata;

structNode*next;

}LinkQueueNode;

typedefstruct

{

LinkQueueNode*front;

LinkQueueNode*rear;

}LinkQueue;

intInitQueue（LinkQueue*Q）

{

Q->front=（LinkQueueNode*）malloc（sizeof（LinkQueueNode））;

if（Q->front!

=NULL）

{

Q->rear=Q->front;

Q->front->next=NULL;

return（True）;

}

else

return（False）;

}

intEnterQueue（LinkQueue*Q,intx）

{

LinkQueueNode*NewNode;

NewNode=（LinkQueueNode*）malloc（sizeof（LinkQueueNode））;

if（NewNode!

=NULL）

{

NewNode->data=x;

NewNode->next=NULL;

Q->rear->next=NewNode;

Q->rear=NewNode;

return（True）;

}

else

return（False）;

}

intDeleteQueue（LinkQueue*Q,int*x）

{

LinkQueueNode*p;

if（Q->front==Q->rear）

return（False）;

p=Q->front->next;

Q->front->next=p->next;

if（Q->rear==p）

Q->rear=Q->front;

*x=p->data;

free（p）;

return（True）;

}

intIsEmpty（LinkQueue*Q）

{

if（Q->front==Q->rear）

return（True）;

else

return（False）;

}

/*..........................*/

typedefstructnode1

{

chardata;

structnode1*next;

}Node1,*LinkList1;

typedefstructnode2

{

chardata1;

chardata2;

structnode2*next;

}Node2,*LinkList2;

inta[2];

intvisited[N];

intLocateVertex2（AdjList*G2,VertexDatav）

{

intk,j=Error;

for（k=0;kvexnum2;k++）

if（G2->vertex[k].data==v）

{

j=k;

break;

}

return（j）;

}

intCreateUDG2（AdjList*G2）

{

inti,j,k;

ArcNode2*p,*r;

VertexDatav1,v2;

printf（"\ninputG->vexnum,G->arcnum\n"）;

scanf（"%d,%d",&（G2->vexnum2）,&（G2->arcnum2））;

getchar（）;

printf（"inputG->vexs\n"）;

for（i=0;ivexnum2;i++）

{

scanf（"%c",&（G2->vertex[i].data））;

G2->vertex[i].firstarc=NULL;

}

getchar（）;

printf（"inputGv1,v2\n"）;

for（k=0;karcnum2;k++）

{

scanf（"%c",&v1）;

scanf（"%c",&v2）;

getchar（）;

i=LocateVertex2（G2,v1）;

j=LocateVertex2（G2,v2）;

if（G2->vertex[i].firstarc==NULL）

{

p=（ArcNode2*）malloc（sizeof（ArcNode2））;

if（p==NULL）

return（False）;

G2->vertex[i].firstarc=p;

p->adjvex=j;

p->nextarc=NULL;

}

else

{

r=G2->vertex[i].firstarc;

while（r->nextarc!

=NULL）

r=r->nextarc;

p=（ArcNode2*）malloc（sizeof（ArcNode2））;

if（p==NULL）

return（False）;

r->nextarc=p;

p->adjvex=j;

p->nextarc=NULL;

}

if（G2->vertex[j].firstarc==NULL）

{

p=（ArcNode2*）malloc（sizeof（ArcNode2））;

if（p==NULL）

return（False）;

G2->vertex[j].firstarc=p;

p->adjvex=i;

p->nextarc=NULL;

}

else

{

r=G2->vertex[j].firstarc;

while（r->nextarc!

=NULL）

r=r->nextarc;

p=（ArcNode2*）malloc（sizeof（ArcNode2））;

if（p==NULL）

return（False）;

r->nextarc=p;

p->adjvex=i;

p->nextarc=NULL;

}

}

return（Ok）;

}

voidBreadth2（AdjListg2,intvo）

{

ArcNode2*p;

intvi;

LinkQueueQ;

InitQueue（&Q）;

visited[vo]=True;

EnterQueue（&Q,vo）;

while（!

IsEmpty（&Q））

{

DeleteQueue（&Q,&vi）;

printf（"%c",g2.vertex[vi].data）;

p=g2.vertex[vi].firstarc;

while（p!

=NULL）

{

if（!

visited[p->adjvex]）

{

visited[p->adjvex]=True;

EnterQueue（&Q,p->adjvex）;

}

p=p->nextarc;

}

}

}

voidDepth2（AdjListg2,intvo）

{

ArcNode2*p;

printf（"%c",g2.vertex[vo].data）;

visited[vo]=True;

p=g2.vertex[vo].firstarc;

while（p!

=NULL）

{

if（!

visited[p->adjvex]）

Depth2（g2,p->adjvex）;

p=p->nextarc;

}

}

voidTraverse2（AdjListg2）

{

intvi;

for（vi=0;vi

visited[vi]=False;

printf（"\nTheorderofG2Depth\n"）;

for（vi=0;vi

{

if（!

visited[vi]）

{

Depth2（g2,vi）;

printf（"\n"）;

}

}

for（vi=0;vi

visited[vi]=False;

printf（"\nTheorderofG2Breadth\n"）;

for（vi=0;vi

{

if（!

visited[vi]）

{

Breadth2（g2,vi）;

printf（"\n"）;

}

}

}

intmain（）

{

AdjListg2;

CreateUDG2（&g2）;

Traverse2（g2）;

return0;

}

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

实验体会

二、图的应用实验——计算AOE网的关键路径

内容：

按照图的“邻接表”存储结构表示AOE网，实现求其关键路径的算法，并验证如下图1所示AOE网的关键路径。

实验步骤

实验步骤：

1.输入图的顶点数目.

2.按偏序顺序输入各边顶点及权值.

3.输入（0,0）结束

4.程序会自动计算出关键路径

源程序

#include

#include

#definemax_vertex_num50

#definemaxvalue32760

#defineNULL0

typedefstructedgenode{

intadjvex;

structedgenode*next;

intweight;}edgenode,*pedgenode;

typedefstructvnode{

intdata;

structedgenode*firstarc;

}vnode,adjlist[max_vertex_num],*pvnode;

voidcreatgraphadlist（pvnode&pn,intn）

{

//依次输入顶点偶对，建立无向图邻接表

edgenode*p;

inti,j,k,wei;

i=j=1;

pn=（pvnode）malloc（（n+1）*sizeof（vnode））;

for（k=1;k<=n;k++）

pn[k].firstarc=NULL;//初始化每个链表为空

for（intf=1;!

（i==0&&j==0）;）

{

cout<<"请输入第-"<

";

cin>>i>>j;

if（i>0&&i<=n&&j>0&&j<=n）

{

p=（edgenode*）malloc（sizeof（edgenode））;//生成一个节点

p->adjvex=j;//为节点j的序号附值为j

p->next=pn[i].firstarc;//将该p节点作为第i个链表的第一个节点插入pn[i]之后

pn[i].firstarc=p;//将接点j作为第一个接点插入连表i的后面

cout<<"请输入该边的权值（即时间）：

";

cin>>wei;p->weight=wei;

f++;

}

elseif（i==0&&j==0）

;//什么也不做

elsecout<<"你输入的序号不符合要求，请重新输入.\n";

}//for

cout<<"---------------------------------------------------------\n";

}

voidfindindegree（pvnodepn,intn,int*deg）

{

for（inti=1;i<=n;i++）//第0个元素不用

deg[i]=0;//对数组进行初始化，全部置0

pedgenodepk;

for（i=1;i<=n;i++）//对邻接表进行遍历

{

pk=pn[i].firstarc;

for（;pk;pk=pk->next）

deg[pk->adjvex]++;//数组相应元素自增

}

}

intve[max_vertex_num];//存放各点发生的最早时刻（全局变量）

intst[max_vertex_num];//存放拓扑序列各顶点的栈（全局变量）

inttop2;//（全局变量）

voidtopologicalorder（pvnodepn,intn,int*tt）

{

intindegree[max_vertex_num];//该数组存放各顶点的入度

intss[max_vertex_num];//设计栈ss，用以存放入度为0的顶点的信息

int*deg;intj;

deg=indegree;

findindegree（pn,n,deg）;

for（inti=1;i<=n;i++）//ve[0]不用

ve[i]=0;//初始化

inttop1;

top1=top2=0;//top1和top2为栈顶指针，分别指向栈ss和tt，初始值均为0（即栈为空）

for（i=1;i<=n;i++）

if（!

indegree[i]）//若顶点i入度为0，则进栈

ss[++top1]=i;

intcount=0;//对输出顶点计数

cout<<"该图的拓扑排序为：

\n";

while（top1）//若ss非空，进入循环

{

j=ss[top1--];//i出栈

cout<

tt[++top2]=j;//将i进入tt栈

count++;//计数

for（pedgenodep=pn[j].firstarc;p;p=p->next）

{

intk=p->adjvex;

indegree[k]--;//对每一个以i为弧尾的顶点，将他们的入度减1

if（!

indegree[k]）

ss[++top1]=k;//如果减为0，则入栈。

因为若入度为x,必然要自减x次才能如栈，所以可以避免重复进栈

if（（ve[j]+p->weight）>ve[k]）

ve[k]=ve[j]+p->weight;//显然此时j是k的前驱，且ve[j]是j发生的最早时间，若

}

}

if（count

{

cout<<"\n该图存在环——错误!

\n";

return;

}

cout<<"\n---------------------------------------------------------"<

cout<<"各顶点发生的最早时间如下"<

for（i=1;i<=n;i++）

cout<<"顶点（"<

"<

cout<<"\n---------------------------------------------------------"<

}

voidcriticalpath（pvnodepn,intn,int*tt）

{

intj,k,dut,ee,el,tag,f=1;

pedgenodep;

intvl[max_vertex_num];//存放各点发生的最迟时刻

for（inti=1;i<=n;i++）

vl[i]=ve[n];//用顶点n的最早时间初始化各顶点的最迟时间*/

while（top2）

{

j=tt[top2--];//出栈

for（p=pn[j].firstarc;p;p=p->next）

{

k=p->adjvex;

dut=p->weight;

if（（vl[k]-dut）

}

}

cout<<"经计算该图的关键路径如下：

\n";

for（j=1;j<=n;j++）

for（p=pn[j].firstarc;p;p=p->next）

{

k=p->adjvex;

dut=p->weight;

ee=ve[j];el=vl[k]-dut;

if（ee==el）//ee==el,说明是关键活动

cout<<"第"<

"<

}

}

intmain（）

{

intn,*tt;

pvnodepn;

tt=st;

cout<<"请输入图的顶点个数：

";

cin>>n;

cout<<"---------------------------------------------------------"<

creatgraphadlist（pn,n）;

topologicalorder（pn,n,tt）;

criticalpath（pn,n,tt）;

return0;

}

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

实验体会