数据结构(图的遍历)实验报告

实验报告第页共页实验项目名称：二叉树的定义及基本操作（所属课程：数据结构--用C语言描述）院系：计算机系专业班级：网络工程姓名：韩强学号：17实验日期：2016.12.8实验地点：A06609合作者：指导教师：孙高飞本实验项目成绩：教师签字：日期：（以下为实验报告正文）一、实验目的验证型实验，在实际运行环境中测试课本《数据结构--用C语言描述》中212-231页关于图的基本算法，以更好的学习数据结构知识。二、实验条件Windowsxp及以上系统的个人电脑，vc++6.0，《数据结构--用C语言描述》等。三、实验内容1.根据217页代码用C语言定义图的邻接矩阵表示。2.根据227页算法7.3实现深度优先遍历图g。3.根据227页算法7.4实现深度优先遍历v0所在的连通子图。4.根据228页算法7.5实现采用邻接矩阵的深度优先遍历。5.根据230页算法7.8实现广度优先遍历图g中v0所在的连通子图。四、实验步骤实验步骤：1.书写头文件以及定义链表内结点名称等基本变量。2.根据217页代码定义图的邻接矩阵表示。3.创建main函数，创建邻接矩阵g。4.根据227页算法7.3实现深度优先遍历图g。实验报告第页共页5.修改main函数，调用TraverseGraph算法，并输出。6.观察实验结果并记录。7.创建算法FirstAdjVertex，用以寻找v0结点的第一个临接点。8.创建算法NextAdjVertex，用以寻找v0结点的第二个临接点。9.根据227页算法7.4实现深度优先遍历v0所在的连通子图。10.修改main函数，调用算法DepthFirstSearch，再次输出。11.观察实验结果并记录。12.根据228页算法7.5实现采用邻接矩阵的深度优先遍历。13.修改main函数，调用算法Depth，再次输出。14.观察实验结果并记录。15.根据230页算法7.8实现广度优先遍历图g中v0所在的连通子图。16.根据99页队列的实现和表达定义链队列。17.书写头文件以及定义链表内结点名称等基本变量。18.根据99页算法3.16实现链队列的初始化。19.根据100页算法3.17实现链队列的入队列操作。20.根据100页算法3.18实现链队列的出队列操作。21.创建算法IsEmpty，实现对队列是否为空的查询。22.修改main函数，调用算法Breadth，再次输出。23.观察实验结果并记录。五、实验结果#includestdio.h#includemalloc.htypedefstruct{charvertex[20];intarcs[20][20];intvexnum,arcnum;}AdjMatrix;typedefcharQueueElementType;#defineTrue1#defineFalse0#defineError-1#defineOK1实验报告第页共页#defineNULL0#defineINFINITY65535intvisited[20];QueueElementTypek;typedefstructNode{QueueElementTypedata;structNode*next;}LinkQueueNode;typedefstruct{LinkQueueNode*front;LinkQueueNode*rear;}LinkQueue;intInitQueue(LinkQueue*Q){Q-front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(Q-front!=NULL){Q-rear=Q-front;Q-front-next=NULL;return(True);}elsereturn(False);}intEnterQueue(LinkQueue*Q,QueueElementTypex){LinkQueueNode*NewNode;NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));if(NewNode!=NULL){NewNode-data=x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;return(True);}elsereturn(False);}实验报告第页共页intDeleteQueue(LinkQueue*Q,QueueElementType*x){LinkQueueNode*p;if(Q-front==Q-rear)return(False);p=Q-front-next;Q-front-next=p-next;if(Q-rear==p)Q-rear=Q-front;*x=p-data;free(p);return(True);}intIsEmpty(LinkQueue*Q){if(Q-front=Q-rear)return(True);elsereturn(False);}voidvisit(AdjMatrixg,intvexIndex){printf(%c,g.vertex[vexIndex]);}voidDepth(AdjMatrixg,intv0){visit(g,v0);visited[v0]=True;for(intvj=0;vjg.vexnum;vj++)if(!visited[vj]&&g.arcs[v0][vj]==1)Depth(g,vj);}voidTraverseGraph(AdjMatrixg){intvi;for(vi=0;vig.vexnum;vi++)visited[vi]=False;for(vi=0;vig.vexnum;vi++)if(!visited[vi])Depth(g,vi);}intFirstAdjVertex(AdjMatrixg,intv0){实验报告第页共页if(v0=0&&v0g.vexnum){visit(g,v0);visited[v0]=True;for(inti=0;ig.vexnum;i++)if(visited[i]&&g.arcs[v0][i]==1)returni;}returnError;}intNextAdjVertex(AdjMatrixg,intv0,intj){if(v0=0&&v0g.vexnum&&j=0&&jg.vexnum){visit(g,v0);visited[v0]=True;for(intk=j+1;kg.vexnum;k++)if(visited[v0]&&g.arcs[v0][k]==1)returnk;}returnError;}voidDepthFirstSearch(AdjMatrixg,intv0){intw;visit(g,v0);visited[v0]=True;w=FirstAdjVertex(g,v0);while(w!=-1){if(!visited[w])DepthFirstSearch(g,w);w=NextAdjVertex(g,v0,w);}}voidBreadth(AdjMatrixg,intv0){intw;visit(g,v0);visited[v0]=True;LinkQueueQ;InitQueue(&Q);EnterQueue(&Q,v0);k=v0;while(!IsEmpty(&Q)){DeleteQueue(&Q,&k);w=FirstAdjVertex(g,v0);实验报告第页共页while(w!=-1){if(!visited[w]){visit(g,w);visited[w]=True;EnterQueue(&Q,w);}w=NextAdjVertex(g,v0,w);}}}voidmain(){AdjMatrixg={{'A','B','C','D','E'},{{0,1,0,1,0},{1,0,1,0,1},{0,1,0,1,1},{1,0,1,0,0},{0,1,1,0,0}},5,5};Depth(g,1);printf(\n);TraverseGraph(g);printf(\n);DepthFirstSearch(g,1);printf(\n);Breadth(g,1);}六、讨论实验中遇到的问题：1.在程序编写的过程中，未及时定义全局变量和局部变量。2.算法书写错误，头文件引用不足。七、参考文献耿国华张德全周明全等，数据结构--用C语言描述，高等教育出版社，2015年7月，99-231页