数据结构有向网络实验报告Word格式文档下载.docx
- 文档编号:4400985
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:13
- 大小:30.53KB
数据结构有向网络实验报告Word格式文档下载.docx
《数据结构有向网络实验报告Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构有向网络实验报告Word格式文档下载.docx(13页珍藏版)》请在冰点文库上搜索。
c.将结点s插入到第j个边表的表头。
2,广度优先遍历图,生成树的孩儿链表BFSL
(1)队列初始化,孩儿链表初始化;
(2)访问v的所有邻接点v(ij);
(3)访问v(ij)的所有未访问的邻接点;
(4)将图的邻接表用树的孩儿链表表示。
3,孩儿链表的遍历
用递归算法前序遍历孩儿链表。
三.设计:
1,数据的存储结构,类型定义
邻接表存储结构:
顺序存储与链式存储相结合
类型定义:
typedefstructnode
{
intadjvex;
/*邻接点域*/
adjtypeweight;
structnode*next;
/*链域*/
}edgenode;
/*边表结点*/
typedefstruct
vextypevertex;
/*顶点信息*/
edgenode*link;
/*边表头指针*/
}vexnode;
/*顶点表结点*/
队列存储结构:
顺序队列
类型定义:
datatypedata[maxsize];
intfront,rear;
}sequeue;
孩儿链表存储结构:
typedefstructcnode
intchild;
structcnode*next;
}link;
datatypedata;
link*headptr;
}ctree;
ctreeT[maxnode];
2、参数表
参数名
数据传递方式
数据内容
传递
所属函数
maxnode
符号常量
孩儿链表数组空间大小
值100
BFSL函数preorder函数
maxsize
队列空间大小
BFSL函数ENQUEUE函数
NULL
代表空
值0
所有函数
n
顶点数
值7
Creatgraph函数BFSL函数
m
边数
值10
creatgraph
ga[n]
全局变量
邻接表的顶点信息
整形数据
T[maxnode]
孩儿链的顶点信息
整型数据
3,函数调用关系图
4,具体分析
(1)函数声明:
voidcreatgraph(vexnodega[])
函数作用:
建立有向网络的邻接表
函数值:
无
形参内容与形式:
s边表节点
主要算法的实现步骤:
for(i=0;
i<
n;
i++)//建立顶点表
{
ga[i].vertex=getchar();
//读入顶点信息
ga[i].link=NULL;
//边表置为空表
}
for(k=0;
k<
e;
k++)//建立边表
scanf("
%d%d%f"
&
i,&
j,&
w);
//读入边(vi,vj)的顶点对序号及相应边的权值
s=(edgenode*)malloc(sizeof(edgenode));
//生成边表结点
s->
adjvex=j;
//邻接点序号为j
next=ga[i].link;
s->
weight=w;
ga[i].link=s;
//将新结点*s插入顶点vi的边表头部
(2)函数声明:
voidBFSL(intk)
广度优先遍历图,生成树的孩儿链表
广度优先遍历序列
k遍历的起始点序号
SETNULL(Q);
//初始化队列
for(i=0;
i++)
{sq=(ctree*)malloc(sizeof(ctree));
//开辟新节点
T[i]=sq;
T[i].data=ga[i].vertex;
//把邻接表的顶点信息赋给孩儿链表
T[i].headptr->
child=i;
T[i]->
headptr->
next=NULL;
//孩儿链表头指针初始化
p=ga[i].link;
//取vi+1的边表头指针
while(p!
=NULL)//依次搜索v(i+1)的邻接点
if(!
visited[p->
adjvex-1])//访问v(i+1)未曾访问的邻接点
{
sp=(link*)malloc(sizeof(link));
sp->
child=p->
adjvex;
s=T[i]->
next;
T[i]->
next=sp;
next=s;
adjvex-1]=1;
ENQUEUE(Q,p->
adjvex-1);
//访问过的顶点入队
}p=p->
next;
找vi+1的下一个邻接点
voidpreorder(ctree*T)
前序遍历孩儿链表
生成树的边集
sp孩儿链表结点
while(sp)
printf("
(%d,%d)"
T->
child,&
sp->
child);
//输出生成树的边集
preorder(&
T[sp->
child]);
//递归调用
sp=sp->
函数首部:
voiddel(ctree*t)
函数的删除
形参:
t孩儿链结点
主要步骤:
{while(t)//非空
t=T[i]->
headptr;
if(t->
child)//有子链
t=t->
child;
free(t);
//释放结点
}
四.调试分析:
1,要注意不要忘记在程序的开始对如NULL,maxnode进行定义,还要对vertex等的类型进行声明。
2,时,空复杂度分析
Creatgraph函数:
T(n)=O(n+e)S(n)=O(n+e)
BFSL函数:
T(n)=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,7
1,2,11,4,21,5,3
1,6,42,3,54,3,6
5,7,73,6,87,3,9
7,6,10
输出:
(1,2)(1,4)(1,5)
(1,6)(2,3)(5,7)
七.源代码清单
#include<
stdio.h>
stdlib.h>
#definemaxnode100
#definemaxsize100
#defineNULL0
#definen7//顶点数
#definee10//边数
typedefintdatatype;
typedefintvextype;
//顶点数据类型
typedeffloatadjtype;
//权值类型
//孩子链表结点
//孩子链表头指针
vexnodega[n];
voidcreatgraph(vexnodega[])//建立有向网络的邻接表
inti,j,k;
floatw;
edgenode*s;
}
voidBFSL(intk)//从v(k+1)出发广度优先搜索图ga
{inti,m;
intvisited[n];
edgenode*p;
ctree*sq
sequeue*Q;
link*sp;
structcnode*s;
Q=(sequeue*)malloc(sizeof(sequeue));
visited[k]=1;
ENQUEUE(Q,k);
//被访问顶点入队
while(!
EMPTY(Q))//队列非空
{i=DEQUEUE(Q);
//k出队
p=ga[i].link;
}
p=p->
//找vi+1的下一个邻接点
voidSETNULL(sequeue*sq)//置空队
sq->
front=-1;
rear=-1;
intEMPTY(sequeue*sq)//判队空
if(sq->
rear==sq->
front)
return1;
elsereturn0;
intENQUEUE(sequeue*sq,intx)//进队
front==-1&
&
rear==maxsize-1)
return0;
else
{sq->
rear++;
data[sq->
rear]=x;
return1;
intDEQUEUE(sequeue*sq)//出队
if(EMPTY(sq))
return0;
front++;
voidpreorder(ctree*T)//前序遍历
sp=T->
while(sp)
main()
{inti;
ctree*sq;
creatgraph(ga);
%d"
i);
sq=BFSL(i);
preorder(sq);
del(t);
源代码共行
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 网络 实验 报告