数据结构图的遍历实验报告.docx
- 文档编号:13269462
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:38
- 大小:346.94KB
数据结构图的遍历实验报告.docx
《数据结构图的遍历实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构图的遍历实验报告.docx(38页珍藏版)》请在冰点文库上搜索。
数据结构图的遍历实验报告
题目:
图的遍历的实现
完成日期:
2011.12.22
一、需求分析
1.本演示程序中,输入的数据类型均为整型数据,不允许输入字符等其他数据类型,且需要按照提示内容进行输入,成对的关系数据必须在所建立的图中已经存在对应的结点.
2.演示程序以用户和计算机的对话方式执行,在计算机终端上显示的提示信息的说明下,按照要求输入数据,运算结果在其后显示。
3.本程序实现分别基于邻接矩阵和邻接表存储结构的有、无向图,有、无向网的建立和遍历.遍历分DFS和BFS两种算法,并分别以递归和非递归形式实现.
4.测试数据:
(1)无向图结点数4弧数3结点:
1234结点关系:
12;13;24
(2)有向图结点数6弧数6结点:
123456结点关系:
12;13;24;35;36;25
二、概要设计
为实现上述程序功能,图的存储结构分为邻接矩阵和邻接表两种。
遍历过程中借助了栈和队列的存储结构。
1.邻接矩阵存储结构的图定义:
ADTmgraph{
数据对象V:
V是具有相同特性的的数据元素的集合,成为顶点集。
数据关系R:
R={VR}
VR={ 基本操作P: locatevex(G,mes); 初始条件: 图G存在,mes和G中顶点有相同的特征. 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回其他信息. 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,访问顶点时使用函数visit。 visit(a); 初始条件: a为图中的某个顶点值。 操作结果: 访问顶点a,本程序中作用结果为输出顶点值。 }ADTmgraph 2.邻接表存储结构的图定义: ADTalgraph{ 数据对象V: V是具有相同特性的的数据元素的集合,成为顶点集。 数据关系R: R={VR} VR={〈v,w〉|v,wєV且P(v,w), 基本操作P: locatevex(G,mes); 初始条件: 图G存在,mes和G中顶点有相同的特征. 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回其他信息. 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,访问顶点时使用函数visit。 visit(a); 初始条件: a为图中的某个顶点值。 操作结果: 访问顶点a,本程序中作用结果为输出顶点值。 }ADTalgraph 3.主程序流程: 定义并创建图 statuscreatgraph(mgraph&G) { cout<〈"请选择构造的图的类型: (1: 有向图,2: 有向网,3: 无向图,4: 无向网)” 〈〈endl; intkind; scanf("%d”,&kind); switch(kind)//通过选择确定创建哪一种图; { case1: returncreatedg(G); case2: returncreatedn(G); case3: returncreateudg(G); case4: returncreateudn(G); default: returnerror; } } 然后采用DFS或BFS进行遍历(访问结果为输出顶点值)。 4.函数的调用关系图: main creatgraphDFS(BFS) createdgcreatedncreateudgcreateudn visitinitstackpushdestroystacklocatevexpopgettop visitlocatevexlinkqueueenqueuegetheaddequeuedestroyqueue 其中,当DFS使用递归算法时相关的栈操作不使用,当BFS使用递归算法时相关的队列操作仍有部分使用。 四、调试分析 1.采用邻接表结构创建图时,由于没有正确进行弧元素的跟进插入,导致图创建不成功。 2.没有采用多文件结构,导致在快要完成时发现函数定义的位置不尽合理,后续添加功能时难度增大。 3.本程序主要为实现遍历算法思想,对实用性考虑偏少,但考虑到了多种数据类型情况下的分别实现,函数拆分较详细,算法可靠性强. 4.算法的时空分析 1)由于对顶点元素的存储均采用了线性结构,所以在创建图和遍历时多依赖于该线性存储的大小.当结点个数为n,弧条数为e时,createdgcreatedncreateudgcreateudn的算法时间复杂度都为O(n²+e*n),其中对邻接矩阵的初始化耗费了O(n²)的时间。 2)当用二维数组表示邻接矩阵作为图的存储结构时,查找每个顶点的邻接点所需时间为O(n²),而以邻接表为存储结构时为O(e)。 以邻接表为存储结构时,深度优先搜索遍历图(DFS)的时间复杂度为O(n+e)。 3)广度优先搜索遍历图(BFS)的时间复杂度和深度优先搜索遍历(DFS)相同。 5。 对链表的操作需要很重要的一个量来定位链表和定位操作的位置,指针的作用不可替代。 多种数据结构的联合使用在程序中非常重要,多种存储结构的程序实现原理上相同,但具体的操作技巧有很大差别。 五、用户使用说明 1.本程序运行环境建议为windowxp。 2.打开程序工程,并运行其中可执行文件,终端对话框会出现文字提示,请严格按照文字提示进行输入操作。 3.数据之间的分隔可用空格或回车键执行。 4.如下图是某无向图的创建并进行DFS的结果: 5. 六、测试结果 DFS: 七、附录 邻接矩阵结构创建图: #include #include〈string.h> #include h> typedefintvertextype; typedefintinfotype; typedefintstatus; typedefintselemtype; #defineerror0 #defineok1 #defineINFINTYINT_MAX//最大值∞ #defineMAX_VERTEX_NUM20//最大定点个数 #defineFALSE0 #defineTRUE1 #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT10 #defineoverflow-2 usingnamespacestd; //弧定义 typedefstructarccell {intadj; //infotype*info; }arccell,adjmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //图定义 typedefstruct { vertextypevexs[MAX_VERTEX_NUM];//顶点 adjmatrixarcs;//弧矩阵 intvexnum,arcnum; }mgraph; intlocatevex(mgraphG,vertextypemes) { for(inti=0;i〈G.vexnum;++i) if(mes==G。 vexs[i]) returni; return0; }//定位函数 //创建无向网 statuscreateudn(mgraph&G) { cout〈〈”请输入无向网的顶点数,弧数: ”< 。 。 。 。 。 scanf(”%d%d”,&G。 vexnum,&G。 arcnum); cout<<"请输入各顶点的值: "<〈endl; for(inti=0;i〈G.vexnum;++i)scanf(”%d”,&G.vexs[i]);//构造顶点 for(inti=0;i〈G.vexnum;++i) for(intj=0;j〈G。 vexnum;++j) G。 arcs[i][j].adj=0; cout〈〈"请输入成对的关系顶点数值以及其权值: (形如: 11221)"< for(intk=0;k〈G.arcnum;++k) {vertextypev1,v2; intw; scanf(”%d%d%d”,&v1,&v2,&w); inti=locatevex(G,v1);intj=locatevex(G,v2); G。 arcs[i][j].adj=w; G。 arcs[j][i]=G。 arcs[i][j]; } returnok; } //创建有向网 statuscreatedn(mgraph&G) { cout<〈"请输入有向网的顶点数,弧数: ”<〈endl;//可添加info选项。 。 。 .。 。 。 scanf(”%d%d”,&G。 vexnum,&G。 arcnum); cout〈<”请输入各顶点的值: ”<〈endl; for(inti=0;i〈G.vexnum;++i)scanf("%d",&G.vexs[i]);//构造顶点 for(inti=0;i vexnum;++i) for(intj=0;j〈G.vexnum;++j) G。 arcs[i][j]。 adj=0; cout〈〈"请输入成对的关系顶点数值以及其权值: (形如: 11221)"〈〈endl; for(intk=0;k { vertextypev1,v2; intw; scanf(”%d%d%d",&v1,&v2,&w); inti=locatevex(G,v1);intj=locatevex(G,v2); G。 arcs[i][j]。 adj=w; } returnok; } //创建无向图 statuscreateudg(mgraph&G) { cout〈〈"请输入无向图的顶点数,弧数: "〈 。 。 。 .。 。 scanf("%d%d",&G。 vexnum,&G。 arcnum); cout〈<”请输入各顶点的值: ”<〈endl; for(inti=0;i for(inti=0;i vexnum;++i) for(intj=0;j〈G.vexnum;++j) G。 arcs[i][j]。 adj=0; cout〈〈"请输入成对的关系顶点数值: (形如: 1122)”〈 for(intk=0;k { vertextypev1,v2; scanf("%d%d”,&v1,&v2); inti=locatevex(G,v1);intj=locatevex(G,v2); G。 arcs[i][j]。 adj=1; G。 arcs[j][i]=G。 arcs[i][j]; } returnok; } //创建有向图 statuscreatedg(mgraph&G) { cout〈<”请输入有向图的顶点数,弧数: ”< 。 。 。 ... scanf(”%d%d",&G.vexnum,&G。 arcnum); cout<〈”请输入各顶点的值: "< for(inti=0;i〈G.vexnum;++i)scanf("%d",&G。 vexs[i]);//构造顶点 for(inti=0;i〈G.vexnum;++i) for(intj=0;j〈G。 vexnum;++j) G。 arcs[i][j]。 adj=0; cout<<”请输入成对的关系顶点数值: (形如: 1122)”〈 for(intk=0;k arcnum;++k) { vertextypev1,v2; scanf(”%d%d”,&v1,&v2); inti=locatevex(G,v1);intj=locatevex(G,v2); G。 arcs[i][j]。 adj=1; } returnok; } 邻接矩阵的DFS非递归算法: voidvisit(vertextypea) {printf("——%d—",a);} voidDFS(mgraphG,intv) { intvisitp[MAX_VERTEX_NUM]; sqstackS; if(initstack(S)==1); for(inti=0;i〈G.vexnum;i++) visitp[i]=FALSE; //首先访问第一个顶点 visit(G.vexs[v]); visitp[v]=TRUE; push(S,G。 vexs[v]); while(S。 top! =S.base)//若栈不为空,则继续从栈顶元素进行遍历 { intk=0,m=0,num=0,j=0,temp=0; gettop(S,k); m=locatevex(G,k); //得到栈顶元素,并在图中定位 for(j=0;j vexnum;j++) if((G。 arcs[m][j].adj)! =0&&visitp[j]==FALSE) num+=1; if(num==0)//如果与栈顶元素相关联的顶点都被访问过,则删除栈顶元素 pop(S,temp); //如果与栈顶元素相关联的顶点还有未被访问的, //则将与其相关联的顶点全部访问 else for(intw=0;w vexnum;w++) if(G。 arcs[m][w].adj! =0&&visitp[w]==FALSE) { visit(G。 vexs[w]);//执行visit操作 visitp[w]=TRUE;//访问标志置真 push(S,G。 vexs[w]);//刚访问的顶点入栈 break; } } destroystack(S); } 邻接矩阵的DFS递归算法: intvisitp[MAX_VERTEX_NUM];//全局变量, //注意在main函数中都赋初值FALSE voidvisit(vertextypea) {printf(”-—%d-",a);} voidDFS(mgraphG,intv) { visit(G.vexs[v]); visitp[v]=TRUE; for(intj=0;j〈G.vexnum;j++) if((G。 arcs[v][j]。 adj)! =0&&visitp[j]==FALSE) DFS(G,j); } 邻接矩阵存储结构的BFS非递归算法: voidvisit(vertextypea) {printf("——%d—”,a);} voidBFS(mgraphG,intv) { intvisitp[MAX_VERTEX_NUM]; linkqueueQ; if(initqueue(Q)==1) for(inti=0;i visitp[i]=FALSE; elseexit (1); //首先访问第一个顶点 visit(G.vexs[v]); visitp[v]=TRUE; enqueue(Q,G。 vexs[v]); while(Q。 front! =Q.rear) { intk=0,m=0,num=0,temp=0,j=0; gethead(Q,k); m=locatevex(G,k);//得到队首元素并定位 for(j=0;j〈G.vexnum;j++) if((G.arcs[m][j]。 adj)! =0&&visitp[j]==FALSE) num+=1; if(num==0) dequeue(Q,temp);//如果此顶点的后继均访问过,则从队列中删除 else { for(intw=0;w〈G。 vexnum;w++) if(G。 arcs[m][w]。 adj! =0&&visitp[w]==FALSE) {visit(G.vexs[w]);//执行visit操作 visitp[w]=TRUE;//访问标志置真 enqueue(Q,G.vexs[w]);} } } destroyqueue(Q); } 邻接矩阵存储结构的BFS递归算法: voidBFS(mgraphG,intv) { linkqueueQ; initqueue(Q); if(visitp[v]==FALSE) { visit(G.vexs[v]); visitp[v]=TRUE; } intj; inte; intaddress; for(j=0;j〈G.vexnum;j++) if((G.arcs[v][j]。 adj)! =0&&visitp[j]==FALSE) { visit(G.vexs[j]); visitp[j]=TRUE; enqueue(Q,G.vexs[j]); } while(Q.front! =Q。 rear) { dequeue(Q,e); address=locatevex(G,e); BFS(G,address); } destroyqueue(Q); } intmain() { mgraphG; creatgraph(G); inti; for(i=0;i visitp[i]=FALSE; BFS(G,0); return0; } 邻接表存储结构的图的创建: #include〈stdio。 h〉 #include〈iostream〉 #include typedefintvertextype; typedefintinfotype; typedefintstatus; typedefintselemtype; #defineFALSE0 #defineTRUE1 #defineerror0 #defineok1 #defineMAX_VERTEX_NUM20//最大顶点个数 #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT10 #defineoverflow-2 usingnamespacestd; typedefstructarcnode{ intadjvex;//弧指向的顶点的位置 intadj;//权值 structarcnode*nextrarc;//指向下一条弧的指针 infotype*info; }arcnode; //顶点结点定义 typedefstructvnode{ vertextypedata;//顶点数据 arcnode*firsttarc;//指向第一条依附该顶点的弧的指针 }vnode,adjlist[MAX_VERTEX_NUM]; //图定义 typedefstruct{ adjlistvertices;//顶点数组 intvexnum,arcnum;//顶点数目,弧数目 intkind;//图的种类标志,以数字代表 }algraph; intlocatevex(algraphG,vertextypemes){ for(inti=0;i〈G。 vexnum;++i) if(mes==G。 vertices[i]。 data) returni; return—1; } //创建无向网 statuscreateudn(algraph&G){ cout〈〈”请输入无向网的顶点数,弧数: "<〈endl; scanf(”%d%d”,&G。 vexnum,&G.arcnum);//输入顶点数和弧数 cout<<"请输入各顶点的值: ”〈 for(inti=0;i〈G.vexnum;++i) scanf(”%d”,&G.vertices[i].data);//输入并构造顶点 for(inti=0;i G。 vertices[i]。 firsttarc=NULL;//初始化指针firsttarc cout〈〈"请输入成对的关系顶点数值以及其权值: (形如: 11221)"〈 for(intk=0;k {vertextypev1,v2; intw;//权值 scanf("%d%d%d”,&v1,&v2,&w);getchar(); inti=locatevex(G,v1); intj=locatevex(G,v2);//定位 arcnode*a; a=(arcnode*)malloc(sizeof(arcnode));//为加入的弧结点申请空间 if(a==NULL) exit (1); (*a)。 adjvex=j;(*a).adj=w;(*a)。 nextrarc=NULL;(*a)。 info=NULL; if(G。 vertices[i].firsttarc==NULL) G。 vertices[i]。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据 结构图 遍历 实验 报告