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