数据结构实验五实验报告.doc

--------------------------校验:_____________-----------------------日期:_____________数据结构实验五实验报告数据结构实验报告实验五图子系统实验题目:图的遍历问题专业班级:网络工程1002班组长:王星(2010100230)组员:郭坤铭(2010100243)张磊(2010100244)2012年5月18日实验报告实验类型__综合__实验室_软件实验室二__实验题目图的遍历问题二、实验目的和要求1、掌握图的存储思想及其存储实现2、掌握图的深度、广度优先遍历算法思想及其程序实现3、掌握图的常见应用算法的思想及其程序实现三、需求分析本演示程序用编写,完成用户用键盘输入以下结点数据:太原、成都、北京、上海、天津、大连、河北。(1)建立一个有向图或无向图(自定)的邻接表并输出该邻接表。(2)在图的邻接表的基础上计算各顶点的度,并输出。(3)以有向图的邻接表为基础实现输出它的拓扑排序序列。(4)采用邻接表存储实现无向图的深度优先遍历。(5)采用邻接表存储实现无向图的广度优先遍历。(6)采用邻接矩阵存储实现无向图的最小生成树的PRIM算法。最后,在主函数中设计一个简单的菜单,分别调试上述算法。概要设计为了实现上述程序功能,需要定义如下内容基本数据类型定义如下:typedefstructnode{//边表结点 intadj;//边表结点数据域 structnode*next;}node; typedefstructvnode//顶点表结点{charname[20]; node*fnext;}vnode,AList[20];typedefstruct{AListList;//邻接表intv,e;//顶点树和边数}*Graph;GraphCreatDG(){}//建立无向邻接表GraphCreatAG(){} //有向邻接图voidPrint(GraphG){}//输出图的邻接表voidCreateAN(AGraph*G1){}//构造邻接矩阵结构的图GvoidDu(GraphG){}//输出各顶点的度数voidDFSTravel(GraphG){}//深度优先遍历voidBFSTravel(GraphG){}//广度优先遍历详细设计typedefstructnode{//边表结点 intadj;//边表结点数据域 structnode*next;}node;typedefstructvnode{//顶点表结点 charname[20]; node*fnext;}vnode,AList[20];typedefstruct{ AListList;//邻接表 intv,e;//顶点树和边数}*Graph;//建立无向邻接表GraphCreatDG(){ GraphG; inti,j,k; node*s; G=malloc(20*sizeof(vnode)); printf("请输入图的顶点数和边数(空格隔开):"); scanf("%d%d",&G->v,&G->e);//读入顶点数和边数 for(i=0;i<G->v;i++){ printf("请输入图中第%d元素:",i+1); scanf("%s",G->List[i].name);//读入顶点信息 G->List[i].fnext=NULL;//边表置为空表 } for(k=0;k<G->e;k++){ printf("请请输入第%d条边的两顶点序号(空格隔开):",k+1); scanf("%d%d",&i,&j);//读入边(Vi,Vj)的顶点对序号; s=(node*)malloc(sizeof(node));//生成边表结点 s->adj=j; s->next=G->List[i].fnext; G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部 s=(node*)malloc(sizeof(node)); s->adj=i;//邻接点序号为i s->next=G->List[j].fnext; G->List[j].fnext=s;//将新结点*s插入顶点Vj的边表头部} returnG;}//有向邻接图GraphCreatAG(){ GraphG; inti,j,k; node*q; G=malloc(20*sizeof(vnode)); printf("请输入图的顶点数和边数【空格隔开】:"); scanf("%d%d",&G->v,&G->e); for(i=0;i<G->v;i++){ printf("请输入图中第%d元素:",i+1); scanf("%s",&G->List[i].name);//读入顶点信息 G->List[i].fnext=NULL; } for(k