《数据结构有向网络实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构有向网络实验报告.doc（9页珍藏版）》请在三一文库上搜索。
1、 数据结构实 验 报 告 成绩_学号1007402078姓名贾俊杨授课教师黄欣专业数学科学学院基地实验报告递交日期2012/12/10实验题目设有向网络用邻接表存储，编制求广度优先生成树的算法。一 需求分析1,实验要求（1） 输入图的边集，建立邻接表；（2） 遍历图，生成树的孩儿链表；（3） 遍历孩儿链表，输出生成树的边集；（4） 删除。2，数据输入 从键盘输入n个整型数据，来表示图的顶点，再从键盘输入e组有序数对来表示图的e条边，与此同时，输入相应边的权值，权值定义为浮点型，数据间都以逗号间隔，以回车作为结束符。本程序中定义图的顶点数为7，边数为10。3，数据输出 从键盘输入数据后，由BFS
2、L函数对图进行广度优先搜索遍历，再由preorder函数输出生成树的边集，输出结果都是整型数据。二. 主要算法的算法思想.1，邻接表建立函数creatgraph （1）确定有向网络的顶点个数和边的个数，本程序中令顶点数位6，边为8（2）输入顶点信息存储在顶点表中并初始化该顶点的边表；（3）依次输入边的信息并存储在边表中： a输入边的顶点序号； b生成邻接点序号为j的边表结点； c将结点s插入到第j个边表的表头。2，广度优先遍历图，生成树的孩儿链表BFSL（1） 队列初始化，孩儿链表初始化；（2） 访问v的所有邻接点v（ij）；（3） 访问v（ij）的所有未访问的邻接点；（4） 将图的邻接表用树
3、的孩儿链表表示。3，孩儿链表的遍历 用递归算法前序遍历孩儿链表。三. 设计：1,数据的存储结构，类型定义 邻接表存储结构：顺序存储与链式存储相结合 类型定义：typedef struct nodeint adjvex;/*邻接点域*/ adjtype weight; struct node *next;/*链域*/edgenode;/*边表结点*/ typedef struct vextype vertex;/*顶点信息*/ edgenode *link;/*边表头指针*/ vexnode;/*顶点表结点*/队列存储结构：顺序队列类型定义：typedef structdatatype data
4、maxsize; int front,rear;sequeue;孩儿链表存储结构：顺序存储与链式存储相结合类型定义：typedef struct cnodeint child; struct cnode *next;link;typedef structdatatype data; link *headptr;ctree;ctree Tmaxnode;2、参数表参数名数据传递方式数据内容传递所属函数maxnode符号常量孩儿链表数组空间大小值100BFSL函数preorder函数maxsize符号常量队列空间大小值100BFSL函数ENQUEUE函数NULL符号常量代表空值0所有函数n符号常量
5、顶点数值7Creatgraph函数BFSL函数m符号常量边数值10creatgraphgan全局变量邻接表的顶点信息整形数据BFSL函数preorder函数Tmaxnode全局变量孩儿链的顶点信息整型数据BFSL函数preorder函数3，函数调用关系图4，具体分析（1） 函数声明：void creatgraph(vexnode ga)函数作用：建立有向网络的邻接表函数值：无形参内容与形式：s 边表节点主要算法的实现步骤：for(i=0;in;i+) /建立顶点表 gai.vertex=getchar(); /读入顶点信息 gai.link=NULL;/边表置为空表 for(k=0;kadjv
6、ex=j; /邻接点序号为j s-next=gai.link; s-weight=w; gai.link=s; /将新结点*s插入顶点vi的边表头部 （2）函数声明：void BFSL(int k)函数作用：广度优先遍历图，生成树的孩儿链表函数值：广度优先遍历序列形参内容与形式：k 遍历的起始点序号 SETNULL(Q);/初始化队列 for(i=0;ichild=i; Ti-headptr-next=NULL;/孩儿链表头指针初始化 p=gai.link;/取vi+1的边表头指针 while(p!=NULL)/依次搜索v（i+1)的邻接点if (! visitedp-adjvex-1)/访问
7、v（i+1)未曾访问的邻接点 sp=(link*)malloc(sizeof(link); sp-child=p-adjvex; s=Ti-headptr-next; Ti-headptr-next=sp; sp-next=s; visitedp-adjvex-1=1; ENQUEUE(Q,p-adjvex-1);/访问过的顶点入队 p=p-next；找vi+1的下一个邻接点（2）函数声明：void preorder(ctree *T)函数作用：前序遍历孩儿链表函数值：生成树的边集形参内容与形式：sp 孩儿链表结点while(sp)printf(%d,%d),&T-headptr-child,
8、&sp-child);/输出生成树的边集preorder(&Tsp-child);/递归调用sp=sp-next;函数首部：void del(ctree *t) 函数作用：函数的删除形参：t 孩儿链结点主要步骤：while(t)/非空t=Ti-headptr;if(t-child)/有子链t=t-child;free(t);/释放结点t=t-next;四. 调试分析： 1，要注意不要忘记在程序的开始对如NULL，maxnode进行定义，还要对vertex等的类型进行声明。 2，时，空复杂度分析Creatgraph函数：T（n）=O（n+e） S（n）=O（n+e）BFSL函数: T (n) =
9、O (n+e) S（n）=O（n） Preorder函数： T（n）=O（n） S（n）=O（n）五. 使用说明：如何使用你编制的程序、操作步骤. 从键盘输入n个整型数表示图的顶点，然后再输入e组有序数对为图的边，及对应的权，运行可得生成树的边集（vi，vj）。六. 测试结果：输入： 1,2,3,4,5,6，71,2,1 1,4,2 1,5,3 1,6,4 2,3,5 4,3,65,7,7 3,6,8 7,3,9 7,6,10输出：（1,2）（1,4）（1,5）（1,6）（2,3）（5,7）七源代码清单#include #include #define maxnode 100#define m
10、axsize 100#define NULL 0#define n 7/顶点数#define e 10/边数typedef int datatype;typedef int vextype;/顶点数据类型typedef float adjtype;/权值类型typedef struct nodeint adjvex;/*邻接点域*/ adjtype weight; struct node *next;/*链域*/edgenode;/*边表结点*/ typedef struct vextype vertex;/*顶点信息*/ edgenode *link;/*边表头指针*/ vexnode;/*
11、顶点表结点*/typedef structdatatype datamaxsize; int front,rear;sequeue;typedef struct cnodeint child; struct cnode *next;link;/孩子链表结点typedef structdatatype data; link *headptr;/孩子链表头指针ctree;ctree Tmaxnode;vexnode gan;void creatgraph(vexnode ga) /建立有向网络的邻接表 int i,j,k; float w; edgenode *s; for(i=0;in;i+)
12、/建立顶点表 gai.vertex=getchar(); /读入顶点信息 gai.link=NULL;/边表置为空表 for(k=0;kadjvex=j; /邻接点序号为j s-next=gai.link;s-weight=w; gai.link=s; /将新结点*s插入顶点vi的边表头部 void BFSL(int k)/从v（k+1)出发广度优先搜索图ga int i,m; int visitedn; edgenode *p; ctree *sq sequeue *Q; link *sp; struct cnode *s; Q=(sequeue*)malloc(sizeof(sequeue
13、); SETNULL(Q);/初始化队列 for(i=0;ichild=i; Ti.headptr-next=NULL; visitedk=1; ENQUEUE(Q,k);/被访问顶点入队 while(! EMPTY(Q)/队列非空 i=DEQUEUE(Q);/k出队 p=gai.link;/取vi+1的边表头指针 while(p!=NULL)/依次搜索v（i+1)的邻接点if (! visitedp-adjvex-1)/访问v（i+1)未曾访问的邻接点 sp=(link*)malloc(sizeof(link); sp-child=p-adjvex; s=Ti-headptr-next; T
14、i-headptr-next=sp; sp-next=s; visitedp-adjvex-1=1; ENQUEUE(Q,p-adjvex-1);/访问过的顶点入队p=p-next;/找vi+1的下一个邻接点 void SETNULL(sequeue *sq)/置空队sq-front=-1;sq-rear=-1;int EMPTY(sequeue *sq)/判队空if(sq-rear=sq-front)return 1;else return 0;int ENQUEUE(sequeue *sq,int x)/进队if(sq-front=-1 & sq-rear=maxsize-1)return
15、 0;elsesq-rear+; sq-datasq-rear=x; return 1;int DEQUEUE(sequeue *sq)/出队if(EMPTY(sq)return 0;elsesq-front+; return 1;void preorder(ctree *T)/前序遍历link *sp;sp=T-headptr;while(sp)printf(%d,%d),&T-headptr-child,&sp-child);preorder(&Tsp-child);sp=sp-next;main()int i; ctree *sq; creatgraph(ga); scanf(%d,&i
16、); sq=BFSL(i); preorder(sq); del（t）； return 1; 源代码共 行their own conditions to develop the correct road, the maximum to avoid investment risk, gain profit.(three) vigorously promote the brand. To establish brand awareness, awareness of the use of brand, brand value, brand acquisition performance, enha
17、nce the competitive strength. Concentrated manpower, careful planning, packaging and publicity of a number of unique, market influence and coverage of the brand, the implementation of key breakthroughs, to enhance the competitive strength, walking business road the competition of alienation and char
18、acteristics, the pursuit of stability and development of the market.(four) to promote the integration of resources. To further broaden their horizons, effective integration of resources within the group, the city resources, other industries and regional resources, mutual trust, mutual benefit, seeki
19、ng win-win principle, in the framework of national policies and regulations, strict inspection and argumentation, legal consultation, examination and approval procedures, strict regulation of economic activities, attract injection the social investment to the industry group, to achieve leveraging th
20、e development, ensure that the value of state-owned assets.(five) to strengthen the construction management personnel. Strengthen the management of education and training of cadres and workers of the existing business, firmly establish the concept of the market, enhance the sense of crisis to adapt
21、to market competition, the sense of urgency, improve the ability to respond to market competition, improve management and operation of the market. At the same time, according to the need of industrial development, vigorously the introduction of high-quality management management personnel, and striv
22、e to build a high-quality professional management team, hard work, and promote the entire workforce knowledge structure, age structure, structure optimization and upgrading ability, enhance core competitiveness, adapt to the need of market competition.(six) seriously study the policy for policy. Ser
23、ious research about social support the development of cultural undertakings in the country and the XX policy, especially the policy of industrial development, financial investment policy, financial policy and tax policy, and actively seek policy, projects and funds, enterprise and industry group mission to promote leapfrog development.1007402078 贾俊杨数据结构实验报告第9页共9页