图遍历数据结构实验报告.docxVIP

图遍历数据结构实验报告 　　数据结构试验报告　　实验四　　图的存储及应用　　实验题目：图的遍历问题　　专业班级：计科系1405班　　组长：张纪远　　组员：周振军　　朱新祥　　梁丽蓉　　段慧娟　　XX年6月1日　　1　　实验报告　　实验类型__综合设计__实验室_软件实验室三__　　一、实验题目　　图的存储及应用　　二、实验目的和要求　　1．掌握图的存储思想及其存储实现　　2．掌握图的深度、广度优先遍历算法思想及其程序实现　　3．掌握图的常见应用算法的思想及其程序实现　　三、需求分析　　1．问题描述　　使用菜单实现图的相关算法,如键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北，建立一个有向图或无向图的邻接表并输出该邻接表；在图的邻接表的基础上计算各顶点的度，并输出；以有向图的邻接表为基础实现输出它的拓扑排序序列；采用邻接表存储实现无向图的深度优先遍历；采用邻接表存储实现无向图的广度优先遍历；采用邻接矩阵存储实现无向图的最小生成树的PRIM算法　　2.设计分析　　调用菜单项，分别调用相应的子函数。注意顶点存储地名，使用字符数组来实现。　　3.结构类型定义　　typedefcharvextype[10];/*顶点数据类型*/　　typedefintedgetype;/*边数据类型*/　　typedefstruct{　　vextypevex[MAXSIZE];　　edgetypearc[MAXSIZE][MAXSIZE];　　intvexnum,arcnum;　　}Mgraph;　　typedefstructnode{　　intadjvex;　　structnode*next}EdgeNode;　　typedefstructnode{　　vextypevex;　　EdgeNode*firstedge;}VexNode;　　typedefstruct{　　VexNodeadjvex[MAXSIZE];　　2　　intn,e;}ALGraph;　　四、概要设计　　为了实现上述程序功能，代码如下：#include　　#include　　#include　　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;iv;i++){printf(请输入图中第%d元素：,i+1);scanf(%s,G-List[i].name);//读入顶点信息3　　}}for(k=0;ke;k++){printf(请请输入第%d条边的两顶点序号(空格隔开)：,k+1);scanf(%d%d,i,j);//读入边的顶点对序号;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,k;node*q;G=malloc(20*sizeof(vnode));printf(请输入图的顶点数和边数【空格隔开】：);scanf(%d%d,G-v,G-e);for(i=0;iv;i++){}for(k=0;ke;k++){printf(请请输入第%d边的两顶点序号【空格隔开】：,k+1);scanf(%d%d,i,j);4printf(请输入图中第%d元素：,i+1);scanf(%s,G-List[i].name);//读入顶点信息G-List[i].fnext=NULL;　　}}q-adj=j;//邻接点序号为jq-next=G-List[i].fnext;