




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
实验名称:数据结构实验五
实验内容: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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年新材料科学与工程考试试卷及答案
- 外科术后引流管的护理
- 2025年社会心理学基础知识考试试卷及答案
- 2025年旅游策划与管理专业考试试题及答案
- 2025年计算机等级考试综合能力试卷及答案
- 2025年海洋科学与技术基础知识测试试题及答案
- 2025年机器人技术与应用能力测试试题及答案
- 2025年中医药学基础知识与实践考试试题及答案
- 2025年电子信息工程专业毕业设计答辩试题及答案
- 农产品溯源升级2025年农产品质量安全追溯体系建设实施方案标准制定研究
- 肝硬化门静脉高压症食管、胃底静脉曲张破裂出血诊治专家共识2025解读
- 公司挂名法人免责协议书
- 2025年南通市通大全过程工程咨询有限公司招聘笔试参考题库附带答案详解
- 玉石国际贸易买卖合同8篇
- GB 45549-2025石墨和萤石单位产品能源消耗限额
- SL631水利水电工程单元工程施工质量验收标准第4部分:堤防与河道整治工程
- 2025年山东省淄博市高新区中考一模历史试题(原卷版+解析版)
- 机场航站楼行李输送带维护
- 2024年1月四川省普通高中学业水平合格性考试物理试题(含答案)
- 银行保安笔试题及答案
- 早期食管癌的内镜下治疗主题课件
评论
0/150
提交评论