图的基本操作-数据实验报告书(共11页).doc
精选优质文档-倾情为你奉上数据结构实验报告书实验内容：图的基本操作* 计科111* 前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容问题描述对给定图，实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。三、 算法设计1、 程序所需头文件已经预处理宏定义和结构体定义如下#include<iostream.h>#define MaxVerNum 100struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;2、 队列的定义及相关函数的实现 struct QueueNodeint nData;QueueNode* next;struct QueueList QueueNode* front;QueueNode* rear;void EnQueue(QueueList* Q,int e)QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q=NULL)return;if(Q->rear=NULL)Q->front=Q->rear=q;elseQ->rear->next=q;Q->rear=Q->rear->next;void DeQueue(QueueList* Q,int* e)if (Q=NULL)return;if (Q->front=Q->rear)*e=Q->front->nData;Q->front=Q->rear=NULL;else*e=Q->front->nData;Q->front=Q->front->next;3、 创建无向图void CreatAdjList(Graph* G)int i,j,k;edgenode* p1;edgenode* p2;cout<<"请输入顶点数和边数:"<<endl;cin>>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<<endl;for (i=0;i<G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<<"开始输入边表信息:"<<endl;for (k=0;k<G->arcnum;k+)cout<<"请输入边<Vi,Vj>对应的顶点:"cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因为是无向图，所以有两次建立边表的过程4、 深度优先遍历void DFS(Graph *G,int i,int visit)cout<<G->adjlistsi.vertex<<" "visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->endver,visit);void DFStraversal(Graph *G,char c)/深度优先遍历cout<<"该图的深度优先遍历结果为:"<<endl;int visitMaxVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化为0，即未访问状态int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根据字符查找序号m=i;DFS(G,i,visit);break;/继续访问未被访问的结点for(i=0;i<G->vexnum;i+)if(visiti=0)DFS(G,i,visit);cout<<endl;5、 广度优先遍历void BFS(Graph* G,int v,int visit)QueueList *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL)int e=0;DeQueue(Q,&e);cout<<G->adjlistse.vertex<<" "visite=1;edgenode* p=new edgenode;p=G->adjlistse.edgelink;if(p)int m=p->endver;if(m=0)EnQueue(Q,m);while(visitm=0)p=p->edgenext;if(p=NULL)break;m=p->endver;EnQueue(Q,m);void BFStraversal(Graph *G,char c)cout<<"该图的广度优先遍历结果为:"<<endl;int visitedMaxVerNum;for (int i=0;i<G->vexnum;i+)visitedi=0;int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)m=i;BFS(G,i,visited);break;/继续访问未被访问的结点for(i=0;i<G->vexnum;i+)if(visitedi=0)BFS(G,i,visited);cout<<endl;四、 调试与测试 我们开始测试数据，如图： 由图可知，我们得出了结果。五、总结通过做这次实验，发现自己在数据结构这门课中还有很多不足有很多知识还没掌握，所以在写程序的时候出现了很多的错误，及还有很多的知识不以灵活运用。因为以前C语言没有掌握好，所以这次做本次实验还是有点吃力，刚开始完全没有思，后来经过查找资料，在自己的努力下和同学的帮助下，终于完了本次实验。还要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。此次实验发现的自己的不足，我相信在以后的学习中，我会更加的努力。六、源代码#include<iostream.h>#define MaxVerNum 100struct edgenodeint endver;int inform;edgenode* edgenext; ;struct vexnode char vertex;edgenode* edgelink;struct Graph vexnode adjlistsMaxVerNum;int vexnum;int arcnum;/队列的定义及相关函数的实现struct QueueNodeint nData;QueueNode* next;struct QueueList QueueNode* front;QueueNode* rear;void EnQueue(QueueList* Q,int e)QueueNode *q=new QueueNode;q->nData=e;q->next=NULL;if(Q=NULL)return;if(Q->rear=NULL)Q->front=Q->rear=q;elseQ->rear->next=q;Q->rear=Q->rear->next;void DeQueue(QueueList* Q,int* e)if (Q=NULL)return;if (Q->front=Q->rear)*e=Q->front->nData;Q->front=Q->rear=NULL;else*e=Q->front->nData;Q->front=Q->front->next;/创建图void CreatAdjList(Graph* G)int i,j,k;edgenode* p1;edgenode* p2;cout<<"请输入顶点数和边数:"<<endl;cin>>G->vexnum>>G->arcnum;cout<<"开始输入顶点表:"<<endl;for (i=0;i<G->vexnum;i+)cin>>G->adjlistsi.vertex;G->adjlistsi.edgelink=NULL;cout<<"开始输入边表信息:"<<endl;for (k=0;k<G->arcnum;k+)cout<<"请输入边<Vi,Vj>对应的顶点:"cin>>i>>j;p1=new edgenode;p1->endver=j;p1->edgenext=G->adjlistsi.edgelink;G->adjlistsi.edgelink=p1;p2=new edgenode;p2->endver=i;p2->edgenext=G->adjlistsj.edgelink;G->adjlistsj.edgelink=p2;/因为是无向图，所以有两次建立边表的过程/深度优先遍历void DFS(Graph *G,int i,int visit)cout<<G->adjlistsi.vertex<<" "visiti=1;edgenode *p=new edgenode;p=G->adjlistsi.edgelink;if(G->adjlistsi.edgelink&&!visitp->endver)DFS(G,p->endver,visit);void DFStraversal(Graph *G,char c)/深度优先遍历cout<<"该图的深度优先遍历结果为:"<<endl;int visitMaxVerNum;for(int i=0;i<G->vexnum;i+)visiti=0;/全部初始化为0，即未访问状态int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)/根据字符查找序号m=i;DFS(G,i,visit);break;/继续访问未被访问的结点for(i=0;i<G->vexnum;i+)if(visiti=0)DFS(G,i,visit);cout<<endl;/广度优先遍历void BFS(Graph* G,int v,int visit)QueueList *Q=new QueueList;Q->front=Q->rear=NULL;EnQueue(Q,v);while(Q->rear!=NULL)int e=0;DeQueue(Q,&e);cout<<G->adjlistse.vertex<<" "visite=1;edgenode* p=new edgenode;p=G->adjlistse.edgelink;if(p)int m=p->endver;if(m=0)EnQueue(Q,m);while(visitm=0)p=p->edgenext;if(p=NULL)break;m=p->endver;EnQueue(Q,m);void BFStraversal(Graph *G,char c)cout<<"该图的广度优先遍历结果为:"<<endl;int visitedMaxVerNum;for (int i=0;i<G->vexnum;i+)visitedi=0;int m;for (i=0;i<G->vexnum;i+)if (G->adjlistsi.vertex=c)m=i;BFS(G,i,visited);break;/继续访问未被访问的结点for(i=0;i<G->vexnum;i+)if(visitedi=0)BFS(G,i,visited);cout<<endl;void main()Graph * G=new Graph;CreatAdjList(G);char ch;cout<<"请输入开始遍历的顶点:"cin>>ch;DFStraversal(G,ch);BFStraversal(G,ch);专心-专注-专业
