数据结构图的遍历实验报告.doc

上传人:小** 文档编号:3013345 上传时间:2020-06-21 格式:DOC 页数:23 大小:491.95KB
返回 下载 相关 举报
数据结构图的遍历实验报告.doc_第1页
第1页 / 共23页
数据结构图的遍历实验报告.doc_第2页
第2页 / 共23页
点击查看更多>>
资源描述

《数据结构图的遍历实验报告.doc》由会员分享,可在线阅读,更多相关《数据结构图的遍历实验报告.doc(23页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、.-题目:图的遍历的实现 完成日期:2011.12.221、 需求分析1. 本演示程序中,输入的数据类型均为整型数据,不允许输入字符等其他数据类型,且需要按照提示内容进行输入,成对的关系数据必须在所建立的图中已经存在对应的结点。2. 演示程序以用户和计算机的对话方式执行,在计算机终端上显示的提示信息的说明下,按照要求输入数据,运算结果在其后显示。3. 本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图,有、无向网的建立和遍历。遍历分DFS和BFS两种算法,并分别以递归和非递归形式实现。4. 测试数据:(1) 无向图 结点数 4 弧数 3 结点:1 2 3 4 结点关系:1 2;1 3;2

2、4(2) 有向图 结点数 6 弧数 6 结点:1 2 3 4 5 6 结点关系:1 2;1 3;2 4;3 5;3 6;2 52、 概要设计为实现上述程序功能,图的存储结构分为邻接矩阵和邻接表两种。遍历过程中借助了栈和队列的存储结构。1. 邻接矩阵存储结构的图定义:ADT mgraph数据对象V:V是具有相同特性的的数据元素的集合,成为顶点集。数据关系 R: R=VRVR= | v,w V且P(v,w),表示从v到w的弧,谓词P(v,w)定义了弧的意义或信息 基本操作 P:locatevex(G, mes);初始条件:图G存在,mes和G中顶点有相同的特征。操作结果:若G中存在顶点u,则返回该

3、顶点在图中位置;否则返回其他信息。createudn( & G);初始条件:图G 存在。操作结果:创建无向图。createdn( & G);初始条件:图G 存在。操作结果:创建有向图。createudg( & G);初始条件:图G 存在。操作结果:创建无向网。createdg(& G);初始条件:图G 存在。操作结果:创建有向网。DFS(G,v);初始条件:图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果:深度优先搜索遍历图G,访问顶点时使用函数visit.BFS(G,v);初始条件:图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果:广度优先搜索遍历图G,访问顶点时使用函数

4、visit.visit( a);初始条件:a为图中的某个顶点值。操作结果:访问顶点a,本程序中作用结果为输出顶点值。ADT mgraph2. 邻接表存储结构的图定义:ADT algraph数据对象V:V是具有相同特性的的数据元素的集合,成为顶点集。数据关系 R: R=VRVR= | v,w V且P(v,w),表示从v到w的弧,谓词P(v,w)定义了弧的意义或信息 基本操作 P:locatevex(G, mes);初始条件:图G存在,mes和G中顶点有相同的特征。操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回其他信息。createudn( & G);初始条件:图G 存在。操作结果:

5、创建无向图。createdn( & G);初始条件:图G 存在。操作结果:创建有向图。createudg( & G);初始条件:图G 存在。操作结果:创建无向网。createdg(& G);初始条件:图G 存在。操作结果:创建有向网。DFS(G,v);初始条件:图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果:深度优先搜索遍历图G,访问顶点时使用函数visit.BFS(G,v);初始条件:图G已经存在并被赋值,v是图中某个顶点的位置坐标。操作结果:广度优先搜索遍历图G,访问顶点时使用函数visit.visit( a);初始条件:a为图中的某个顶点值。操作结果:访问顶点a,本程序中作用

6、结果为输出顶点值。ADT algraph3. 主程序流程: 定义并创建图status creatgraph(mgraph & G) cout请选择构造的图的类型:( 1:有向图,2:有向网,3:无向图,4:无向网) endl; int kind; scanf(%d,& kind); switch (kind)/通过选择确定创建哪一种图; case 1: return createdg(G); case 2: return createdn(G); case 3:return createudg(G); case 4: return createudn(G); default: return e

7、rror; 然后采用DFS或BFS进行遍历(访问结果为输出顶点值)。4.函数的调用关系图: main creatgraph DFS (BFS) createdg createdn createudg createudnvisit initstack push destroystack locatevex pop gettop visit locatevex linkqueue enqueue gethead dequeue destroyqueue其中,当DFS使用递归算法时相关的栈操作不使用,当BFS使用递归算法时相关的队列操作仍有部分使用。4、 调试分析1. 采用邻接表结构创建图时,由于没

8、有正确进行弧元素的跟进插入,导致图创建不成功。2. 没有采用多文件结构,导致在快要完成时发现函数定义的位置不尽合理,后续添加功能时难度增大。3. 本程序主要为实现遍历算法思想,对实用性考虑偏少,但考虑到了多种数据类型情况下的分别实现,函数拆分较详细,算法可靠性强。4. 算法的时空分析1) 由于对顶点元素的存储均采用了线性结构,所以在创建图和遍历时多依赖于该线性存储的大小。当结点个数为n,弧条数为e时, createdg createdn createudg createudn的算法时间复杂度都为O(n+e*n),其中对邻接矩阵的初始化耗费了O(n)的时间。2) 当用二维数组表示邻接矩阵作为图的

9、存储结构时,查找每个顶点的邻接点所需时间为O(n),而以邻接表为存储结构时为O(e)。以邻接表为存储结构时,深度优先搜索遍历图(DFS)的时间复杂度为O(n+e)。3) 广度优先搜索遍历图(BFS)的时间复杂度和深度优先搜索遍历(DFS)相同。5.对链表的操作需要很重要的一个量来定位链表和定位操作的位置,指针的作用不可替代。多种数据结构的联合使用在程序中非常重要,多种存储结构的程序实现原理上相同,但具体的操作技巧有很大差别。5、 用户使用说明1. 本程序运行环境建议为window xp.2. 打开程序工程,并运行其中可执行文件,终端对话框会出现文字提示,请严格按照文字提示进行输入操作。3. 数

10、据之间的分隔可用空格或回车键执行。4. 如下图是某无向图的创建并进行DFS的结果:结果随后出现按照文字提示进行输入数据分隔使用空格或回车6、 测试结果DFS:7、 附录邻接矩阵结构创建图:#include #include #includetypedef int vertextype;typedef int infotype;typedef int status;typedef int selemtype;#define error 0#define ok 1#define INFINTY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /最大定点个数#define

11、 FALSE 0#define TRUE 1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define overflow -2using namespace std;/弧定义typedef struct arccellint adj; / infotype *info;arccell,adjmatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/图定义typedef struct vertextype vexsMAX_VERTEX_NUM;/顶点 adjmatrix arcs;/ 弧矩阵 int vexnum,arcn

12、um;mgraph;int locatevex(mgraph G,vertextype mes) for(int i=0;iG.vexnum;+i) if(mes=G.vexsi) return i; return 0;/定位函数/创建无向网status createudn(mgraph & G) cout请输入无向网的顶点数,弧数:endl;/可添加info选项。 scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0

13、;iG.vexnum;+i) for(int j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值以及其权值:(形如:11 22 1)endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; int w; scanf(%d%d%d, &v1,&v2,&w); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcsij.adj=w; G.arcsji=G.arcsij; return ok;/创建有向网status createdn(mgraph & G) c

14、out请输入有向网的顶点数,弧数:endl;/可添加info选项。 scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0;iG.vexnum;+i) for(int j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值以及其权值:(形如:11 22 1)endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; int w; sca

15、nf(%d%d%d, &v1,&v2,&w); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcsij.adj=w; return ok;/创建无向图status createudg(mgraph & G) cout请输入无向图的顶点数,弧数:endl;/可添加info选项。 scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0;iG.vexnum;+i) for(i

16、nt j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值:(形如:11 22 )endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2); int i=locatevex(G,v1);int j=locatevex(G,v2); G.arcsij.adj=1; G.arcsji=G.arcsij; return ok;/创建有向图status createdg(mgraph & G) cout请输入有向图的顶点数,弧数:endl;/可添加info选项。 scan

17、f(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.vexsi); /构造顶点 for(int i=0;iG.vexnum;+i) for(int j=0;jG.vexnum;+j) G.arcsij.adj=0; cout请输入成对的关系顶点数值:(形如:11 22 )endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2); int i=locatevex(G,v1);int j=loca

18、tevex(G,v2); G.arcsij.adj=1; return ok;邻接矩阵的DFS非递归算法:void visit(vertextype a)printf(-%d-,a);void DFS(mgraph G,int v) int visitpMAX_VERTEX_NUM; sqstack S; if(initstack(S)=1); for(int i=0;iG.vexnum;i+) visitpi=FALSE; /首先访问第一个顶点 visit(G.vexsv); visitpv=TRUE; push(S, G.vexsv); while (S.top!=S.base)/若栈不为

19、空,则继续从栈顶元素进行遍历 int k=0,m=0,num=0,j=0 ,temp=0; gettop(S,k); m=locatevex(G,k); /得到栈顶元素,并在图中定位 for(j=0;jG.vexnum;j+) if(G.arcsmj.adj)!=0 & visitpj=FALSE) num+=1; if(num=0) /如果与栈顶元素相关联的顶点都被访问过,则删除栈顶元素 pop(S,temp); /如果与栈顶元素相关联的顶点还有未被访问的, /则将与其相关联的顶点全部访问 else for(int w=0;wG.vexnum;w+) if(G.arcsmw.adj !=0

20、& visitpw=FALSE) visit(G.vexsw);/执行visit操作 visitpw=TRUE;/访问标志置真 push(S,G.vexsw);/刚访问的顶点入栈 break; destroystack(S);邻接矩阵的DFS递归算法:int visitpMAX_VERTEX_NUM;/全局变量,/注意在main函数中都赋初值FALSEvoid visit(vertextype a)printf(-%d-,a);void DFS(mgraph G,int v) visit(G.vexsv); visitpv=TRUE; for(int j=0;jG.vexnum;j+) if(

21、G.arcsvj.adj)!=0 & visitpj=FALSE) DFS(G,j);邻接矩阵存储结构的BFS非递归算法:void visit(vertextype a)printf(-%d-,a);void BFS(mgraph G,int v) int visitpMAX_VERTEX_NUM; linkqueue Q; if(initqueue(Q)=1) for(int i=0;iG.vexnum;i+) visitpi=FALSE; else exit(1); /首先访问第一个顶点 visit(G.vexsv); visitpv=TRUE; enqueue(Q,G.vexsv); w

22、hile (Q.front!=Q.rear) int k=0,m=0,num=0,temp=0,j=0; gethead(Q,k); m=locatevex(G,k);/得到队首元素并定位 for(j=0;jG.vexnum;j+) if(G.arcsmj.adj)!=0 & visitpj=FALSE) num+=1; if(num=0) dequeue(Q,temp);/如果此顶点的后继均访问过,则从队列中删除 else for(int w=0;wG.vexnum;w+) if(G.arcsmw.adj !=0 & visitpw=FALSE) visit(G.vexsw);/执行visi

23、t操作 visitpw=TRUE;/访问标志置真 enqueue(Q,G.vexsw); destroyqueue(Q);邻接矩阵存储结构的BFS递归算法:void BFS(mgraph G,int v) linkqueue Q; initqueue(Q); if(visitpv=FALSE) visit(G.vexsv); visitpv=TRUE; int j; int e; int address; for(j=0;jG.vexnum;j+) if(G.arcsvj.adj)!=0 & visitpj=FALSE) visit(G.vexsj); visitpj=TRUE; enqueu

24、e(Q,G.vexsj); while (Q.front!=Q.rear) dequeue(Q,e); address=locatevex(G,e); BFS(G,address); destroyqueue(Q);int main() mgraph G; creatgraph(G); int i; for(i=0;iG.vexnum;i+) visitpi=FALSE; BFS(G,0); return 0;邻接表存储结构的图的创建:#include #include #include typedef int vertextype;typedef int infotype;typedef i

25、nt status;typedef int selemtype;#define FALSE 0#define TRUE 1#define error 0#define ok 1#define MAX_VERTEX_NUM 20 /最大顶点个数#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define overflow -2using namespace std;typedef struct arcnodeint adjvex; /弧指向的顶点的位置int adj;/权值struct arcnode *nextrarc; /指向下一条弧

26、的指针infotype *info;arcnode;/顶点结点定义typedef struct vnodevertextype data; /顶点数据arcnode *firsttarc;/指向第一条依附该顶点的弧的指针vnode,adjlistMAX_VERTEX_NUM;/图定义typedef structadjlist vertices;/顶点数组int vexnum,arcnum;/顶点数目,弧数目int kind; /图的种类标志,以数字代表algraph;int locatevex(algraph G,vertextype mes) for(int i=0;iG.vexnum;+i

27、) if(mes=G.verticesi.data) return i; return -1;/创建无向网status createudn(algraph &G) cout请输入无向网的顶点数,弧数:endl; scanf(%d%d,&G.vexnum,&G.arcnum);/输入顶点数和弧数 cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data); /输入并构造顶点 for(int i=0;iG.vexnum;+i) G.verticesi.firsttarc=NULL;/初始化指针firsttarc

28、cout请输入成对的关系顶点数值以及其权值:(形如:11 22 1)endl; for(int k=0;knextrarc=G.verticesi.firsttarc-nextrarc; G.verticesi.firsttarc=a; /处理另一条对称的顶点j if(G.verticesj.firsttarc=NULL) G.verticesj.firsttarc=a;/当此弧是顶点j的第一条弧时 else/当此弧不是顶点j的第一条弧时 a-nextrarc=G.verticesj.firsttarc-nextrarc; G.verticesj.firsttarc=a; return ok;

29、/有向网status createdn(algraph &G) cout请输入有向网的顶点数,弧数:endl; scanf(%d%d,&G.vexnum,&G.arcnum); cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data); /构造顶点 for(int i=0;iG.vexnum;+i) G.verticesi.firsttarc=NULL;/初始化指针firsttarc cout请输入成对的关系顶点数值以及其权值:(形如:11 22 1)endl; for(int k=0;knextrarc=

30、G.verticesi.firsttarc-nextrarc; G.verticesi.firsttarc=a; return ok;/无向图status createudg(algraph &G) cout请输入无向图的顶点数,弧数:endl; scanf(%d %d,&G.vexnum,&G.arcnum);getchar(); cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data);/顶点赋值 getchar(); for(int i=0;iG.vexnum;+i) G.verticesi.firs

31、ttarc=NULL;/初始化指针firsttarc cout请输入成对的关系顶点数值:(形如:11 22 )endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2);getchar(); int i=locatevex(G,v1); int j=locatevex(G,v2); arcnode * a; a=(arcnode *)malloc(sizeof (arcnode);/为加入的弧结点申请空间 if (a=NULL) exit(1); ( * a).adjvex=j;(* a).adj=1; (* a

32、).nextrarc=NULL; (* a).info=NULL; if(G.verticesi.firsttarc=NULL)/当此弧是顶点i的第一条弧时 G.verticesi.firsttarc=a;/coutattach to firsttarcnextrarc=G.verticesi.firsttarc; G.verticesi.firsttarc=a; /coutattach successfully!endl; /处理对称的另一个顶点 if(G.verticesj.firsttarc=NULL)/当此弧是顶点j的第一条弧时 G.verticesj.firsttarc=a;/cou

33、tattach to firsttarcnextrarc=G.verticesj.firsttarc; G.verticesj.firsttarc=a; /coutattach successfully!endl; return ok;status createdg(algraph &G) cout请输入无向图的顶点数,弧数:endl; scanf(%d %d,&G.vexnum,&G.arcnum);getchar(); cout请输入各顶点的值:endl; for(int i=0;iG.vexnum;+i) scanf(%d,&G.verticesi.data);/顶点赋值 getchar(); for(int i=0;iG.vexnum;+i) G.verticesi.firsttarc=NULL;/初始化指针firsttarc cout请输入成对的关系顶点数值:(形如:11 22 )endl; for(int k=0;kG.arcnum;+k) vertextype v1,v2; scanf(%d%d, &v1,&v2);getchar(); int i=locatevex(G,v1); int j=locatevex(G,v2); arcnode * a; a=(arcnode *)malloc(sizeof (arcno

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 技术资料 > 其他杂项

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

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁