数据结构有向网络实验报告.doc

数　据　结　构　实 验 报 告 成绩_____ 学号 1007402078 姓名 贾俊杨 授课教师 黄　欣 专业 数学科学学院基地 实验报告递交日期 2012/12/10 实验题目 设有向网络用邻接表存储，编制求广度优先生成树的算法。 一． 需求分析 1,实验要求 输入图的边集，建立邻接表； 遍历图，生成树的孩儿链表； 遍历孩儿链表，输出生成树的边集； 删除。 2，数据输入 从键盘输入n个整型数据，来表示图的顶点，再从键盘输入e组有序数对来表示图的e条边，与此同时，输入相应边的权值，权值定义为浮点型，数据间都以逗号间隔，以回车作为结束符。本程序中定义图的顶点数为7，边数为10。 3，数据输出 从键盘输入数据后，由BFSL函数对图进行广度优先有哪些信誉好的足球投注网站遍历，再由preorder函数输出生成树的边集，输出结果都是整型数据。 二. 主要算法的算法思想. 1，邻接表建立函数creatgraph （1）确定有向网络的顶点个数和边的个数，本程序中令顶点数位6，边为8 （2）输入顶点信息存储在顶点表中并初始化该顶点的边表； （3）依次输入边的信息并存储在边表中： a．输入边的顶点序号； b．生成邻接点序号为j的边表结点； c．将结点s插入到第j个边表的表头。 2，广度优先遍历图，生成树的孩儿链表BFSL 队列初始化，孩儿链表初始化； 访问v的所有邻接点v（ij）； 访问v（ij）的所有未访问的邻接点； 将图的邻接表用树的孩儿链表表示。 3，孩儿链表的遍历 用递归算法前序遍历孩儿链表。 三. 设计： 1,数据的存储结构，类型定义 邻接表存储结构：顺序存储与链式存储相结合 类型定义： typedef struct node { int adjvex;/*邻接点域*/ adjtype weight; struct node *next;/*链域*/ }edgenode;/*边表结点*/　　　 typedef struct { vextype vertex;/*顶点信息*/ edgenode *link;/*边表头指针*/ } vexnode;/*顶点表结点*/ 队列存储结构：顺序队列 类型定义： typedef struct { datatype data[maxsize]; int front,rear; }sequeue; 孩儿链表存储结构：顺序存储与链式存储相结合 类型定义： typedef struct cnode { int child; struct cnode *next; }link; typedef struct { datatype data; link *headptr; }ctree; ctree T[maxnode]; 2、参数表 参数名 数据传递方式 数据内容 传递 所属函数 maxnode 符号常量 孩儿链表数组空间大小 值100 BFSL函数preorder函数 maxsize 符号常量 队列空间大小 值100 BFSL函数ENQUEUE函数 NULL 符号常量 代表空 值0 所有函数 n 符号常量 顶点数 值7 Creatgraph函数BFSL函数 m 符号常量 边数 值10 creatgraph ga[n] 全局变量 邻接表的顶点信息 整形数据 BFSL函数preorder函数 T[maxnode] 全局变量 孩儿链的顶点信息 整型数据 BFSL函数preorder函数 3，函数调用关系图 4，具体分析 函数声明：void creatgraph(vexnode ga[]) 函数作用：建立有向网络的邻接表 函数值：无 形参内容与形式：s 边表节点 主要算法的实现步骤： for(i=0;in;i++) //建立顶点表 { ga[i].vertex=getchar(); //读入顶点信息 ga[i].link=NULL;//边表置为空表 } for(k=0;ke;k++) //建立边表 { scanf(%d%d%f,i,j,w);//读入边(vi，vj)的顶点对序号及相应边的权值 s=(edgenode *)malloc(sizeof(edgenode)); //生成边表结点 s-adjvex=j; //邻接点序号为j s-next=ga[i].link; s-weight=w; ga[i].link=s; //将新结点*s插入顶点vi的边表头部 } （2）函数声明：void BFSL(int k) 函数作用：广度优先遍历图，生成树的孩儿链表 函数值：广度优先遍历序列 形参内容与