2023年数据结构邻接矩阵邻接表图实验报告_第1页
2023年数据结构邻接矩阵邻接表图实验报告_第2页
2023年数据结构邻接矩阵邻接表图实验报告_第3页
2023年数据结构邻接矩阵邻接表图实验报告_第4页
2023年数据结构邻接矩阵邻接表图实验报告_第5页
已阅读5页,还剩16页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

实验名称:数据结构实验五

实验内容:1.使用邻接矩阵速立一个图,深度遍历。2.使

用邻接表建立一个图,广度遍历。3.建立一个图,存储结构自

己拟定,并进行拓扑排序。

实验代码:

1.#inc1ude"stdio.h”

#defineInfinity100

#defineMaxVertexNum20

typedefenum{DGDN,UDG,UDN}GraphKind;

typedefintVRType;

typedefcharVertexType;

boolVisit[MaxVertexNum];

typedefstructArcCell

(

VRTypeadj;

}ArcCe11,AdjMatrix[MaxVertexNum][MaxVertexNum];

typedefstruct

(

VertexTypevexs[MaxVertexNum];

AdjMatrixares;//邻接矩阵

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

。GraphKindkind;

)MGraph;

intLocateVex(MGraphG,VertexTypev)

for(inti=0;i<G.vexnum;++i)

wif(v==G.vexsEi])

0returni;

)

if(i=Gvexnum)

oprintf("输入的顶点不合法\n”);

return0;

)

VertexTypevl,v2;

VRTypew;

voidCreateUDG(MGraph&G)

(

ointi,j,k;

printf("请输入顶点数:\n");

scanf("%d”,&G.vexnum);

叩rintf("请输入弧数:\n”);

scanf("%d",&G.arcnum);

。i=0;

owhile(i<Gvexnum)

printf("请输入第%d个顶点\n",i);

getchar();

scanf(n%cn,&Gvexs[i]);

。++i;

。}

©for(i=0;i<G.vexnum;++i)

for(j=0:j<G.vexnum;++j)

®®Garcs[i][j].adj=0;

0)

ofor(k=0;k<G.arcnum;++k)

°{

“printf("请输入一条边依附的顶点及权值(vlv2w)\n");

egetchar();

oscanf("%c%c%d",&vl,&v2,&w);

Qi=LocateVex(G,v1);

何=LocateVex(G,v2);

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

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

°)

6return;

)

voidDFSTraverse(MGraph&Qinti)

printf(*'%cn,G.vexs[i]);

Visit[i]=true;

for(intj=0;j<Gvexnum;j++)

°{

时f(Garcs[i][j].adj==l&&!Visit[jl)

(

DFSTraverse(G,j);

00}

")

)

voidDFS(MGraph&G)

(

•inti;

for(i=0;i<G.vexnum;i++)Visil[i]=faIse;

»for(i=0;i<G.vexnum;i++)

(

。if(!Visit[i])

0(

。DFSTraverse(G,i);

)

voidmain()

<>MGraphgraph;

*>CreateUDG(graph);

中rintf("顶点集合为::");

fbr(inti=0;i<graph.vexnum;++i)

«>printf(n%c",graph.vexsLi]);

printf("\n深度遍历结果是:");

eDFS(graph);

叩rintf(”\n”);

^return;

)

2.

#include"stdio.h1'

#include"stdlib.h"

#defineMaxVertexNum20

typedefintInfbType;

typedefcharVertexType;

typedefVertexTypeQElemType;

boo1visited[MaxVertexNum];

typedefstructArcNode

(

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

^structArcNode*nextarc;//指向下一条弧的指针

InfoType*info;

}ArcNode;

typedefstructVNode

aVertexTypedata;//顶点信息

ArcNode*firstare;//指向第一条依附该顶点的弧的指针

}VNode,AdjList[MaxVertexNumJ;

typedefstruct

!

AdjListvertices;

“ntvexnum,arenum;//图的当前顶点数和弧数

)ALGraph;

typedefstructQNode

(

QElemTypedata;

®structQNode*next;

}QNode,*Queueptr;

typedefstruet

(

Queueptrfront;

Queueptrrear;

}LinkQueue;

voidInitQueue(LinkQueue&Q)

(

Q.front=Q.rear=(Queueptr)ma1loc(sizeof(QNode));

if(!Q.front)return;

Q.front—>nextNULL;

©return;

voidEnQueue(LinkQueue&Q,QElemTypee)

(

oQueueptrp=NULL;

p=(Queueptr)malloc(sizeof(QNode));

if(!p)return;

®p->data=e;

p->next=NULL;

Q.rear—>next=p;

Q.rear=p;

return;

)

QE1emTypeDeQueue(LinkQueue&Q,QElemType&e)

(

Queueptrp;

“f(Q.front==Q.rear)return'’;

p=Q.front->next;

笛=p->data;

oQ.front—>next=p->next;

“f(Q.rear==p)

Q.rear=Q.front;

ofree(p);

oreturne;

)

intQueueEmpty(LinkQueueQ)

if(Q.front==Q.rear)

return1;

oelse

。return0;

)

intLocate(ALGraphG,VertexTypev)

(

ofor(intk=0;k<G.vexnum;++k)

°(

if(v==Gvertices[k].data)

returnk;

)

if(k=Gvexnum)

Printf("输入的顶点不合法\n");

6return0;

)

voidCreateALGraph(ALGraph&G)

(

VertexTypevl,v2;

°inti,j,k;

®ArcNode*p,*r;

printf("请输入顶点数和弧数(以空格分开):”);

scanf("%d%(!",&G,vexnum,&G.arcnum);

ofor(i=0;i<G.vexnum;++i)

(

getchar();

pr血f(”请输入第%d个结点:”,i);

。scanf(H%cn,&G,verticesLi],data);

oG.vertices[i].firstarc=NULL;

。}

©for(i=0;i<G.arcnum;++i)

(

。printf(”请输入第%d条弧(格式:顶点顶点(以空格隔开)):口);

ogetchar();

。scanf("%c%c",&vl,&v2);

8k=Locale(G,vl);

。。j=Locate(G,v2);

op=(ArcNode)malloc(sizeof(ArcNode));

。。「二(AreNode*)ma11oc(sizeof(ArcNode));

p->adjvex=j;

。叩・>info=NULL;

r->adjvex=k;

or—>info=NULL;

p->nextarc=G.vertices[k].firstarc;

Gvertices[k].firstarc=p;

or->nextarc=G.vertices[j].firstarc;

G.vertices[j].firstarc=r;

return;

)

voidBFSTraverse(ALGraphG,QElemTypex)

(

Anti,v;

oArcNode*p;

oQElemTypev1;

for(v=0;v<G.vexnum;++v)

visited[v]=false;

®LinkQueueQ;

nitQueue(Q);

aEnQueue(Q,x);

A=Loeate(G,x);

^visited[i]=true;

for(v=0;v<G.vexnum;++v)

°{

while(!QueueEmpty(Q))

oooDeQueue(Q,v1);

。。printf(M%c”,vl);

gi=Locate(G,vl);

8P=G.vertices[i].firstarc;

。while(p!=NULL)

000if(!visited[p—>adjvex])

00

00visited[p—>adjvex]=tru

oEnQueue(Q,G.vertices[p->adjvex].data);

000}

。。p=p->nextarc;

000j0

0)

«if(!visited[v])

(

gvisited[v]=true;

“oEnQueue(Q,G.vertices[v].data);

voidmain()

(

ocharf1agl;

ALGraphgraph2;

oQElemTypex;

aCreateALGraph(graph2);

flag1='¥*;

while(flag1=='YIIflagl=='y,)

°{

printf(”请输入遍历的起点:”);

ggetchar();

scanf(u%cn,&x);

gprintf("广度遍历结果是:\n");

“BFSTraverse(graph2,x);

sprintf(n\n继续遍历(Y/N):");

^getchar();

oscanf("%c'\&flagl);

0)

©return;

)

3.

#include”stdio.hu

#include"stdlib.h"

#defineStackInitSize20

#defineStackincrement5

#defineMaxVertexNum20

typedefintInfoType;

typedefcharVertexType;

typedefVertexTypeSE1emType;

typedefstruct

(

oSElemType*base;

SE1emType*top;

intstacksize;

}SqStack;

typedefstructArcNode

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

struetArcNode*nextarc;//指向下一条弧的指针

InfoType*info;

}ArcNode;

typedefstructVNode

(

©intindegree;

WertexTypedata;〃顶点信息

ArcNode*firstare;//指向第一条依附该顶点的弧的指针

}VNode,AdjList[MaxVertexNum];

typedefstruct

(

AdjListvertices;

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

}ALGraph;

boo1InitStack(SqStack&s)

(

s.base=(SElemType*)ma1loc(StacklnitSize*sizeof(SEIemType));

if(Js.base)returnfalse;

as.top=s.base;

os.stacksize=StackInitSize;

returntrue;

)

boo1Pop(SqStack&s,int&e)

(

if(s.top==s.base)

sreturnfalse;

e=*-s.top;

oreturntrue;

)

boolPush(SqStack&s,inte)

(

oif(s.top-s.base>=s.stacksize)

°(

s.base=(SE1emType*)rea11oc(s.base,(s.stacksize+Stackinere

men。*sizeof(SElemType));

if(!s.base)

«»returnfalse;

»s.top=s.base+s.stacksize;

8s.stacksize+=StackIncrement;

°)

*s.top++=e;

oreturntrue;

)

boolStackEmpty(SqStacks)

if(s.top==s,base)

8returntrue;

else

。returnfalse;

)

intLocate(ALGraphG,VertexTypev)

(

ofor(intk=0;k<G.vexnum;++k)

(

if(v==G.vertices[k].data)

。。returnk;

。if(k=G.vexnum)

。printf("输入的顶点不合法\n”);

return0;

)

voidCreateALGraph(ALGraph&G)//邻接表存储

(

VertexTypev1,v2;

“nti,j,k;

AreNode*p;

叩rintf(”请输入顶点数和弧数(以空格分开):”);

seanf("%d%d",&G.vexnum,&Garcnum);

for(i=0;i<G.vexnum;++i)

°(

。getchar();

-printf("请输入第%d个结点:”,i);

。scanf("%c”,&G.vertices[i].data);

。G.vertices[i].firstare=NULL;

oG.vertices[i].indegree=0;

)

ofor(i=0;i<G.arcnum;++i)

°{

printf("请输入第%d条有向弧弧(格式:顶点顶点(以空格隔开)):\i);

。getchar();

scanf("%c%c",&v1,&v2);

k=Locate(G,v1);

j=Locate(G,v2);

p=(ArcNode*)malloc(sizeof(ArcNode));

。叩->adjvex=j;

p->info=NULL;

®p->nextarc=G.vertices[k].firstarc;

G.vertices[k].firstarc=p;

°}

return;

)

voidFindInDegree(ALGraphG,inta[MaxVertexNum])

inti,k:

ArcNode*p;

ofor(i=0;i<G.vexnum;++i)

(

。for(p=G.verticesLi].firstarc;p;p=p->nextarc)

00|

oak=p->adjvex;

。a[k]=++G,vertices[k].indegree;

00}

return;

)

voidTopologicalSort(ALGraphG)//拓扑排序算法

(

inti,j,count;

oArcNode*p;

SqStacks;

intindegree[MaxVertexNum];

6for(i=0;i<MaxVertexNum;++i)

®indegree[i]=0;

FindinDegree(G,indegree);

InitStack(s);

for(i=0;i<G.vexnum;++i)

°(

eif(!indegree[i])

®Push(s,i);

)

count=0;

®whi1e(!StackEmpty(s))

(

Pop(s,i);

3Printf("%cM,G.vertices[i].data);

叶+count;

for(p=G.vertices[i].firstarc;p;p=p->nextarc)

00I

。j=p->adjvex;

°®if(!(-indegree[j]))Push(s,j);

00I

°}

oif(count<Gvexnum)

。printf("错误!该有向图有回路!\nn);

eelsereturn;

)

voidmain()

(

ALGraphgraph3;

CreateALGraph(graph3);

叩rintf("拓扑排序的结果是:\n”);

TopologicalSort(graph3);

printf(H\nn);

®return;

3■D:\VC++6.旭天中文精简黑色版(D\VC6\MyProjects\Graph\Debug\Graph.exe*1

___________________—一——一,1

请输入顶点数:

8

请输入弧数:

:青输入第。个顶点

,输入第1个顶点

福输入第2个顶点

:青输入第3个顶点

;青输入第4个顶点

:青输入第5个顶点

:青输入第6个顶点

箱输入第7个顶点

请输入一条边依附的顶点及权值(viv2w)

请输入一条边依附的顶点及权值(""2w)

ac1

睛输入一条边依附的顶点及权值目

3"D:\VC++6.0创天中文精简景&®l)\VC6\MyProjects\Graph\Debug\Graph.exe'

请输入一条边依附的顶点及权值(以

bd1

请输入一条边依附的顶点及权值(UW)

be1

请输入一条边依附的顶点及权值(皿«)

eh1

请输入一条边依附的顶点及权值(以W)

Idh1

情输入一条边依附的顶点及权值(MW)

lcf1

请输入一条边依附的顶点及权值(”M)

pg1

请输入一条边依附的顶点及权值(U1«)

fg1

顶点集合为::abcdefgh

深度遍历结果是:abdhecfg

Pressanykeytocontinue.

I

-,・D:\VC++6.0s|天中文精简螟色版⑴\VC6\MyProjects\Graph3\Debug\Gr叩h3.exe,

明1215

0点A

1点B

2点C

结D

3点

第E

4结

第5F

第6G

第7H

点I

第8

点J

第9

:』K

第1

卜n

第1L

一R

鬲开

第0_n

鬲开

第1f

_.空

向\

有.

鬲开

第2_f.

向x

有.

鬲开

第3_f.)

向\.

/占

鬲开

第4_l.)

南\.

有i

鬲开

第5_Z.)

响N(.

6鬲开

第_.)

响.

7鬲开

第_

向z.)

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论