数据结构试验报告07

计算机科学与工程学院计算机科学与工程学院《算法与数据结构》实验报告 《算法与数据结构》实验报告 计算机科学与工程学院《算法与数据结构》实验报告（七）专业班级2017级实验地点503机房学生学号1710050108指导教师姚峰学生姓名刘政林实验时间20XX-XX-XX实验项目图的应用一实验类别基础性（）设计性（Q综合性（）其它（）实验（1）熟练掌握图的基本存储方法；目（2）熟练掌握图的深度优先和广度优先搜索方法。的及要求成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律按要求完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分说明：评阅教师： 姚峰日期：Z0—年 月 日实验内容实验内容：图的两种遍历方法及对应的生成树。自己编写源程序，把图的深度优先遍历、广度优先遍历改为输出深度优先生成树、广度优先生成树。实验说明：(1)读懂教师给定的程序或课本的程序；(2)输入图；(3)把显示遍历序列改为显示深度优先、广度优先生成树。#include<stdio.h>#include<malloc.h>#defineMAXV100#defineINF1024typedefintInfotype;typedefstruct{intno;Infotypeinfo;}Vertextype;typedefstruct{intedges[MAXV][MAXV];intn,e;Vertextypevexs[MAXV];}Mgraph;typedefstructAnode{intadjvex;structAnode*nextarc;Infotypeinfo;}Arcnode;typedefintVertex;typedefstructVNode{Vertexdata;Arcnode*firstarc;}Vnode;typedefVnodeAdjlist[MAXV];typedefstruct{Adjlistadjlist;intn,e;}Algraph;voidMattolist(Mgraphg,Algraph*&G){inti,j;Arcnode*p;G=(Algraph*)malloc(sizeof(Algraph));for(i=0;i<g.n;i++)G->adjlist[i].firstarc=NULL;for(i=0;i<g.n;i++)for(j=g.n-1;j>=0;j--)if(g.edges[i][j]!=0){p=(Arcnode*)malloc(sizeof(Arcnode));p->adjvex=j;p->nextarc=G->adjlist[i].firstarc;G->adjlist[i].firstarc=p;}G->n=g.n;G—>e=g.e;}voidDispadj(Algraph*G){inti;Arcnode*p;for(i=0;i<G->n;i++){p=G->adjlist[i].firstarc;printf("%3d:",i);while(p!=NULL){printf("%3d",p->adjvex);p=p->nextarc;}printf("\n");}}intvisited[MAXV];voidDFS(Algraph*G,intv){Arcnode*p;visited[v]=1;p=G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("<%d,%d>",v,p->adjvex);DFS(G,p->adjvex);}p=p->nextarc;}}voidBFS(Algraph*G,intv){Arcnode*p;intqueue[MAXV],front=0,rear=0;intw,i;for(i=0;i<G->n;i++)visited[i]=0;visited[v]=1;rear=(rear+1)%MAXV;queue[rear]=v;whilefront!=rear){front=(front+1)%MAXV;w=queue[front];p=G->adjlist[w].firstarc;while(p!=NULL){if(visited[p->adjvex]==0){printf("<%d,%d>",w,p->adjvex);visited[p->adjvex]=1;rear=(rear+1)%MAXV;queue[rear]=p->adjvex;}p=p->nextarc;}}printf("\n");}voidmain(){inti,j;Mgraphg;Algraph*G;intA[MAXV][n]={{0,1,1,1,0,0,0,0,0,0,0},{1,0,0,0,1,1,0,0,0,0,0},{1,0,0,1,0,1,1,0,0,0,0},{1,0,1,0,0,0,0,1,0,0,0},{0,1,0,0,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0,0},{0,0,1,0,0,0,0,1,1,1,0},{0,0,0,1,0,0,1,0,0,0,1},{0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,0,1,0,0,0}};g.n=11;g.e=13;for(i=0;i<g.n;i++)for(j=0;j<g,n;j++)g.edges[i][j]=A[i][j];G=(Algraph*)malloc(sizeof(Algraph));Mattolist(g,G);printf("图G的邻接表:\n");Dispadj(G);

printf("\n");for(i=0;i<g.n;i++)visited[i]=0;printf("深度优先生成树:")；DFS(G,0);printf("\n");for(i=0;i<g.n;i++)visited[i]=0;printf("广度优先生成树:")；BFS(G,0);printf("\n");}图G的邻接表;0：61：0452；36103：0274：15:126：27897：03568：1239：610：7：<0,6><6,2><2,3><3