数据结构实验六七八Word格式文档下载.docx
- 文档编号:8595560
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:19
- 大小:105.28KB
数据结构实验六七八Word格式文档下载.docx
《数据结构实验六七八Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构实验六七八Word格式文档下载.docx(19页珍藏版)》请在冰点文库上搜索。
stdio.h>
string.h>
stdlib.h>
#defineMAX100
typedefstructLinknode
{
intadjvex;
//intinfo;
structLinknode*next;
}LinkNode;
typedefstructVexnode
intvexdata;
LinkNode*first;
}VexNode;
typedefstruct{
intvexnum;
VexNodeadjlist[100];
}ALGraph;
ALGraphG;
intpre[MAX],path[MAX];
voidcreate();
voidprint();
voidDFS(intu,intv,intd);
voidmain()
create();
//print();
DFS(2,2,-1);
}
voidcreate()
inti,tempi;
LinkNode*p,*q;
freopen("
in.txt"
"
r"
stdin);
//freopen("
out.txt"
w"
stdout);
scanf("
%d"
&
G.vexnum);
//scanf("
%c"
temp);
for(i=0;
i<
G.vexnum;
i++)
{
scanf("
G.adjlist[i].vexdata);
G.adjlist[i].first=NULL;
//scanf("
}
tempi);
while(tempi!
=100)
{
p=(LinkNode*)malloc(sizeof(LinkNode));
p->
adjvex=tempi;
q=G.adjlist[i].first;
G.adjlist[i].first=p;
next=q;
scanf("
}
voidprint()
inti;
LinkNode*p;
printf("
%d\t"
G.adjlist[i].vexdata);
p=G.adjlist[i].first;
while(p!
=NULL)
printf("
p->
adjvex);
p=p->
next;
\n"
);
voidDFS(intu,intv,intd)
inti,temp;
pre[u]=1;
d++;
path[d]=u;
p=G.adjlist[u].first;
if(u==v)
for(i=0;
=d;
printf("
path[i]);
while(p!
temp=p->
adjvex;
if(pre[temp]==0)
{
DFS(temp,v,d);
p=p->
pre[u]=0;
d--;
voidprint_path(intpre[],intv)
if(pre[v]!
=v)
print_path(pre,pre[v]);
printf("
%d"
v);
实验七最小生成树
1、图的邻接矩阵、邻接表和边集数组表示。
2、掌握建立图的邻接矩阵的算法,由邻接矩阵转换为邻接表和边集数组的算法。
3、熟悉最小生成树的构造。
4、熟悉并掌握求图的最小生成树的普里姆算法克鲁斯卡尔算法。
掌握图的概念、图的邻接矩阵表示法和邻接表表示法、图的深度和广度优先遍历、生成树和最小生成树、树的最短路径、拓扑排序。
有向图:
若图G中的每条边都是有方向的,则称G为有向图。
无向图:
若图G中的每条边都是没有方向的,则称G为无向图。
完全图:
有1/2条边的图无向图称为完全图。
恰有n(n-1)条边的有向图称为有向完全图,恰有n(n-1)/2条边的无向图称无向完全图。
连通图:
图中G中任意两个顶点Vi、Vj∈V、Vi和Vj连通的,则G称为连通图。
度:
顶点V的度是和V相关联的边的数目。
强连通图:
在有向图G中,如果对于每一对Vi,Vj∈V、Vi、Vj,从Vi到Vj和从Vj到Vi都存在路径,则G是强连通图。
无向图的路径:
在无向图G中,若存在一个顶点序列vp,vi1,vi2,…,vim,vq,使得(vp,vi1),(vi1,vi2),…,(vim,vq)均属于E(G),则称顶点vp到vq存在一条路径。
有向图的路径:
在有向图G中,路径也是有向的,它由E(G)中的有向边<
vp,vi1>
,<
vi1,vi2>
,…,<
vim,vq>
组成。
路径长度:
路径长度定义为该路径上边的数目。
子图:
设G=(V,E)是一个图,若V'
是V的子集,E'
是E的子集,且E'
中的边所关联的顶点均在V'
中,则G'
=(V'
,E'
)也是一个图,并称其为G的子图。
生成树:
如果连通图G的一个子图是一棵包含G的所有顶点的树,则该子图称为G的生成树。
最小生成树:
权最小的生成树称为G的最小生成树。
图中(b)、(c)、(d)都是生成树,权分别是:
21、13、9。
可以证明(d)为一棵最小生成树。
(a)带权图(b
)生成树
(c)生成树(d)最小生成树
1、认真阅读和掌握本实验的内容。
2、从实验本上选择一个程序上机调试。
3、得出正确的程序后,运行程序输入一个图形,保存和打印出程序运行的结果,并进行程序的性能分析。
4、请重新编写一个程序并上机进行调试,得出结果后总结出程序的特点。
prim
typedefstructdege
intvex1;
intvex2;
intweight;
}Edge;
typedefstructlinknode
intvex;
structlinknode*next;
}LINKNODE;
typedefstructnode
intdata;
structlinknode*first;
}NODE;
typedefstructcd
intlowcost;
}CD;
NODEG[MAX];
EdgeE[MAX];
CDclosedge[MAX];
intGRAPH[MAX][MAX];
intvisited[MAX];
intgraphcount;
voidprintgraph();
voidconvert();
voidprim(intu);
intmain()
{
inttempcount,temp;
LINKNODE*p;
tempcount);
while(tempcount!
=0)
graphcount=tempcount;
graphcount;
G[i].data=i;
G[i].first=NULL;
while(temp!
{
p=(LINKNODE*)malloc(sizeof(LINKNODE));
p->
vex=temp;
scanf("
weight=temp;
next=G[i].first;
G[i].first=p;
}
printgraph();
convert();
prim(0);
return0;
voidprintgraph()
data=%d"
G[i].data);
p=G[i].first;
<
%d,%d>
"
vex,p->
weight);
voidprim(intu)
inti,j,min,p;
for(j=0;
j<
j++)
if(j!
=u)
closedge[j].adjvex=u;
closedge[j].lowcost=GRAPH[j][u];
closedge[u].lowcost=0;
graphcount-1;
p=1;
min=MAX;
for(j=0;
if(closedge[j].lowcost!
=0&
&
closedge[j].lowcost<
min)
min=closedge[j].lowcost;
p=j;
->
%d\n"
closedge[p].adjvex,p,min);
closedge[p].lowcost=0;
if(GRAPH[p][j]<
closedge[j].lowcost)
closedge[j].lowcost=GRAPH[p][j];
closedge[j].adjvex=p;
voidconvert()
inti,j;
for(j=0;
GRAPH[i][j]=MAX;
GRAPH[i][i]=0;
GRAPH[i][p->
vex]=p->
weight;
GRAPH[i][j]);
kruskal;
typedefstructedge
intu;
intv;
intEcount;
voidkruskal();
Ecount);
Ecount;
E[i].u);
E[i].v);
E[i].weight);
kruskal();
voidkruskal()
intvset[MAX];
inti,j,k,tempu,tempv,s1,s2;
vset[i]=i;
k=1;
j=0;
while(k<
Ecount&
j<
Ecount)
tempu=E[j].u;
tempv=E[j].v;
s1=vset[tempu];
s2=vset[tempv];
if(s1!
=s2)
u=%d,v=%d,weight=%d\n"
tempu,tempv,E[j].weight);
k++;
for(i=0;
if(vset[i]==s2)
vset[i]=s1;
j++;
if(j==Ecount&
k!
=Ecount-1)
NOthesmallesttree"
实验八二叉排序树
1、掌握二叉排序树的生成、查找和删除的基本概念
2、熟练运用二叉排序树进行排序和查找。
二、预备知识
(1)二叉排序树又称二叉查找树。
指的是一棵空的二叉树或者是一棵具有以下特性的非空二叉树:
1、若它的左子树非空,则右子树上所有结点的值均小于根结点的值;
2、若它的右子树非空,则右子树上所有节点的值均大于根结点的值;
3、左,右子树本身有各是一棵二叉排序树。
(2)二叉排序树的特点:
1、二叉排序树中任一结点x,其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
2、二叉排序树中,各结点关键字是惟一的。
注意:
实际应用中,不能保证被查找的数据集中各元素的关键字互不相同,所以可将二叉排序树定义中BST性质
(1)里的"
小于"
改为"
大于等于"
,或将BST性质
(2)里的"
大于"
小于等于"
,甚至可同时修改这两个性质。
3、序遍历该树所得到的中序序列是一个递增有序序列。
例
下图所示的两棵树均是二叉排序树,它们的中序序列均为有序序列:
2,3,4,5,7,8。
高度为3高度为5
二叉排序树示例
三、实验内容
本实验主要掌握二叉排序树的生成、插入、删除。
重点掌握利用二叉排序树对数据进行查找,以及对查找进行分析。
实验基本思想:
首先建立一个二叉查找树,
其过程为:
先建立一个空树b,,然后向该空树中插入一个个结点实现,因此,根据用户输入的一系列正数(以-1标志结束)生成一棵二叉排序树的算法如下:
voidcreat(btree*b)
Elemtypex;
tree*s
b=NULL;
do
x);
s=(bonde*)malloc(sizeof(bonde));
s->
data=x;
left=NULL;
right=NULL;
insert(b,s);
}while(x!
=1);
在二叉排序树b中查找x的过程为:
(1)若b是空树,则搜索失败,否则
(2)
(2)若x等于b的根结点的数据域之值,则查找成功;
否则(3)
(3)若x小于b的根结点的数据域之值,则搜索左子树;
否则(4)
(4)查找右子树。
实验源程序算法如下:
btree*search(btree*b;
ElemTyprx)
if(b==NULL)return(NULL);
else
if(b->
data==x)return(b);
if(x<
b->
data)return(search(b->
left));
elsereturn(search(b->
right));
四、实验要求
1、根据以上给出算法写出二叉排序树的生成程序。
2、根据以上给出算法写出二叉排序树的查找程序。
3、写出调试运行的分析和体会。
4、写出输出结果和实验报告。
五、强化与提高
思考题:
编写一个从有m个结点其数据域值为r[I]的二叉树中删除结点x的算法。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 六七
![提示](https://static.bingdoc.com/images/bang_tan.gif)