数据结构图的操作.docx

上传人:王** 文档编号:941990 上传时间:2024-03-01 格式:DOCX 页数:16 大小:96.10KB
下载 相关 举报
数据结构图的操作.docx_第1页
第1页 / 共16页
数据结构图的操作.docx_第2页
第2页 / 共16页
数据结构图的操作.docx_第3页
第3页 / 共16页
数据结构图的操作.docx_第4页
第4页 / 共16页
数据结构图的操作.docx_第5页
第5页 / 共16页
数据结构图的操作.docx_第6页
第6页 / 共16页
数据结构图的操作.docx_第7页
第7页 / 共16页
数据结构图的操作.docx_第8页
第8页 / 共16页
数据结构图的操作.docx_第9页
第9页 / 共16页
数据结构图的操作.docx_第10页
第10页 / 共16页
亲,该文档总共16页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构图的操作.docx》由会员分享,可在线阅读,更多相关《数据结构图的操作.docx(16页珍藏版)》请在优知文库上搜索。

1、实验7:图的操作算法一、实验目的1 .熟悉各种图的存储结构。2 .掌握图的各种搜索路径的遍历方法。二、实验内容1.设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。算法:#include#include#include#include#defineMAXV10#defineINF980708usingnamespacestd;typedefintInfoType;邻接矩阵typedefstruct(intno;InfoTypeinfo;JVertexType;顶点类型typedefstruct(intedgesMAXVMAX

2、V;intnze;VertexTypevesMAXV;MatGraph;完整的图邻接矩阵类型邻接表typedefstructANode(intadjve;structANode*nextarc;intweight;ArCNOde;边结点类型typedefstructVnodeInfoTypeinfo;ArcNode*firstarc;VNode;邻接表的头结点类型typedefstruct(VNodeadjlistMAXV;intn,e;AdjGraph;完整的图邻接表类型typedefstruct(InfoTypedataMAXV;intfront,rear;SqQueue;队列初始化队列v

3、oidInitQUeUe(SqQUeUe*&q)(q=(SqQueue*)malloc(sizeof(SqQueue);q-front=q-rear=-l;)判断队列是否为空boolQueueEmptyfSqQueue*q)(return(q-front=q-rear);)进队列booleQueue(SqQueue*&q,InfoTypee)(if(q-rear=MAXV)returnfalse;q-rear+;q-dataq-rear=e;returntrue;)出队列booldeQueue(SqQueue*&q,InfoType&e)(if(q-front=q-rear)returnfal

4、se;q-front=(q-front+l)%MAXV;e=q-dataq-front;returntrue;)创建邻接表voidCreateAdj(AdjGraph*&GJntAMAXVMAXVJntnjnte)(intij;ArcNode*p;G=(AdjGraph*)malloc(sizeof(AdjGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;i=OJ-)if(Aij!=O&Ai0!=INF)p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=j;p-nextarc=G-adjIisti.firstar

5、c;G-adjlisti.firstarc=p;)G-n=n;G-e=e;)输出邻接表voidDispAdj(AdjGraph*G)(COUt“邻接表存储:endl;inti;ArcNode*p;for(i=0;in;i+)(p=G-adjlisti.firstarc;printf(%3dzi);printf(%3d-,J);while(p!=NULL)(printf(%3d-,p-adjvex);p=p-nextarc;)coutAendl;)/DFS深度优先遍历intvisitedMAXV=0;voidDFSfAdjGraph*G,intv)(ArcNode*p;visitedv=l;co

6、utadjlistv.firstarc;while(p!=NULL)(if(visitedp-adjvex=O)DFS(G,p-adjvex);p=p-nextarc;)/BFS广度优先遍历voidBFS(AdjGraph*GJntv)(intWjjArcNode*p;SqQueue*qu;InitQueue(qu);intvisitedlMAXV;for(inti=0;in;i+)visitedli=O;printf(%2d,v);visitedlv=l;enQueue(qu,v);while(!QueueEmpty(qu)(deQueue(quzw);p=G-adjlistw.firsta

7、rc;while(p!=NULL)(if(visitedlp-adjvex=O)(printf(%2d,p-adjvex);visitedlp-adjvex=l;eQueue(qu,p-adjvex);p=p-nextarc;)coutendl;)销毁邻接表voidDestroyAdj(AdjGraph*&G)(inti;ArcNode*pre,*p;for(i=0;in;i+)(pre=G-adjlisti.firstarc;if(pre!=NULL)(p=pre-nextarc;while(p!=NULL)(free(pre);pre=p;p=p-nextarc;free(pre);)fr

8、ee(G);)创建邻接矩阵voidCreatMat(MatGraph*&GJntnjnte)(intijljjlznuml,num2;G=(MatGraph*)malloc(sizeof(MatGraph);邻接矩阵初始化for(i=0;in;i+)(for(j=0;jedgesij=O;)顶点信息COUt请输入顶点编号endl;for(i=0;iG-vexsi.no;边信息for(i=0;ie;i+)(COUt”请输入起始端点编号和终止端点编号*iljl;for(j=0;jvexsj.no=il)numl=j;if(G-vexsj.no=jl)num2=j;)G-edgesnumlnum2=

9、l;)G-n=n;G-e=e;)输出邻接矩阵voidDispMat(MatGraph*G)(cout”邻接矩阵存储:endl;couttt;for(inti=0;in;i+)coutvexsi.not;coutendl;for(inti=0;in;i+)(couttvexsi.not;for(intj=O;jn;j+)coutedgesijt;coutendl;)intmain()(intnze,vl;MatGraph*G;AdjGraph*p;COUt请输入顶点个数n;COUt请输入边的个数e;CreatMat(G,nze);DispMat(G);CreateAdj(p,G-edges,nz

10、e);DispAdj(p);COUtv;DFS(pzv);coutendl;COUtvl;BFS(p,vl);COUt销毁图IE -2-3-1: 13运行结果:请输入顶点个数3输入边的个数1输入顶点编号12345请输入起始端点编号和终止端点编号13请输入起始端点编号和终止端点编号14请输入起始端点编号和终止端点编号12请输入起始端点编号和终止端点编号43请输入起始端点编号和终止端点编号2 4请输入起始端点编号和终止端点编号3 5请输入起始端点编号和终止端点编号5 2邻接矩阵存储:2-3-请输入初始点:1请输入初始点:1,-STJTJ-IJnJTJLLLLL1342Itt:-S/(mlIi-J深

11、1o1234S接O.1:2:3:4:F4存在问题:无2.求两点之间最短路径。算法设计:求两点之间最短路径。#include#include#include#include#defineINF32767#defineMAXV100usingnamespacestd;typedefcharInfoType;以下定义邻接矩阵类型typedefstructintno;顶点编号InfoTypeinfo;顶点其他信息VertexType;typedefstruct顶点类型intedgesMAXVMAXV;邻接矩阵数组intnze;顶点数,边数VertexTypevexsMAXV;存放顶点信息MatGraph;完整的图邻接矩阵类型voidCreateMat(MatGraph&g,intAMAXVMAXVJntnjnte)仓IJ建图的邻接矩阵inti,j;g.n=n;g.e=e;for(i=0;ig,n;i+)for(j=O;jg.n;j+)g.edgesij=Aij;voidDispMat(MatGraphg)输出邻接矩阵ginti,j;for(i=0;ig,n;i+)for(j=O;jg,n;j+)if(g.edgesij!=INF)printf(%4d,g.edge

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!