数据结构实验六七八.docx

数据结构实验六七八.docx

《数据结构实验六七八.docx》由会员分享，可在线阅读，更多相关《数据结构实验六七八.docx（19页珍藏版）》请在冰点文库上搜索。

数据结构实验六七八

实验六图的遍历

一、实验目的

1、熟悉图的各种存储结构及其构造算法

2、熟练掌握图的两种搜索路径的遍历：

遍历的逻辑定义、深度优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。

3、应用图的遍历算法求解各种简单路径问题。

4、理解教科书中讨论的各种图的算法。

二、实验预备知识

本实验的重点：

深度优先搜索和广度优先搜索。

图的遍历：

和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。

它是许多图的算法的基础。

深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。

它们对无向图和有向图均适用。

图的深度优先遍历：

假设给定初始状态图G中的所有顶点均未曾访问过。

在G中任选一顶点v出发，首先访问出发点v，并将其标记为已访问过，然后依次从v出发搜索v的每个邻接点。

若该邻结点未曾访问过，则以该邻结点为新的出发点继续进行深度优先遍历，直至图中所有和点v有路径相通的顶点均已被访问为止。

若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均被访问为止。

（a）无向图G

（b）图G深度优先过程

深度优先遍历序列：

v1→v2→v4→v5→v3→v6→v7

图的广度优先遍历：

设初始状态图G中的所有顶点均未访问过。

在G中任选一顶点v，首先访问出发点v，接着依次访问v的所有邻接点，然后再依次访问与邻接的所有未曾访问过的顶点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。

依此类推，直至图中所有和点v有路径相通的顶点都已访问到。

若此时图中尚有顶点未被访问，则另选图中的一个未被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。

（c）无向图G

（d）图G广度优先搜索过程

广度悠闲遍历序列：

v1→v2→v3→v4→v5→v6→v7→v8→v9

三、实验要求

1、掌握图的遍历思想以及其特点。

2、选择程序上机进行调试找出问题、保存和打印出程序的运行结果。

3、上机学会运用图的思想解决实际问题。

4、课后尝试自己编写程序并上机运行得出结果。

深度遍历图，邻接表加递归

#include

#include

#include

#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

{

scanf（"%d",&G.adjlist[i].vexdata）;

G.adjlist[i].first=NULL;

//scanf（"%c",&temp）;

}

for（i=0;i

{

scanf（"%d",&tempi）;

while（tempi!

=100）

{

p=（LinkNode*）malloc（sizeof（LinkNode））;

p->adjvex=tempi;

q=G.adjlist[i].first;

G.adjlist[i].first=p;

p->next=q;

scanf（"%d",&tempi）;

}

}

}

voidprint（）

{

inti;

LinkNode*p;

for（i=0;i

{

printf（"%d\t",G.adjlist[i].vexdata）;

p=G.adjlist[i].first;

while（p!

=NULL）

{

printf（"%d\t",p->adjvex）;

p=p->next;

}

printf（"\n"）;

}

}

voidDFS（intu,intv,intd）

{

inti,temp;

LinkNode*p;

pre[u]=1;

d++;

path[d]=u;

p=G.adjlist[u].first;

if（u==v）

{

for（i=0;i<=d;i++）

printf（"%d\t",path[i]）;

printf（"\n"）;

}

while（p!

=NULL）

{

temp=p->adjvex;

if（pre[temp]==0）

{

DFS（temp,v,d）;

}

p=p->next;

}

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）中的有向边，，…，组成。

路径长度：

路径长度定义为该路径上边的数目。

子图：

设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

#include

#include

#include

#defineMAX100

typedefstructdege

{

intvex1;

intvex2;

intweight;

}Edge;

typedefstructlinknode

{

intvex;

intweight;

structlinknode*next;

}LINKNODE;

typedefstructnode

{

intdata;

structlinknode*first;

}NODE;

typedefstructcd

{

intadjvex;

intlowcost;

}CD;

NODEG[MAX];

EdgeE[MAX];

CDclosedge[MAX];

intGRAPH[MAX][MAX];

intvisited[MAX];

intgraphcount;

voidprintgraph（）;

voidconvert（）;

voidprim（intu）;

intmain（）

{

inti;

inttempcount,temp;

LINKNODE*p;

freopen（"in.txt","r",stdin）;

//freopen（"out.txt","w",stdout）;

scanf（"%d",&tempcount）;

while（tempcount!

=0）

{

graphcount=tempcount;

for（i=0;i

{

G[i].data=i;

G[i].first=NULL;

}

for（i=0;i

{

scanf（"%d",&temp）;

while（temp!

=100）

{

p=（LINKNODE*）malloc（sizeof（LINKNODE））;

p->vex=temp;

scanf（"%d",&temp）;

p->weight=temp;

p->next=G[i].first;

G[i].first=p;

scanf（"%d",&temp）;

}

}

scanf（"%d",&tempcount）;

}

printgraph（）;

convert（）;

prim（0）;

return0;

}

voidprintgraph（）

{

inti;

LINKNODE*p;

for（i=0;i

{

printf（"data=%d",G[i].data）;

p=G[i].first;

while（p!

=NULL）

{

printf（"<%d,%d>",p->vex,p->weight）;

p=p->next;

}

printf（"\n"）;

}

}

voidprim（intu）

{

inti,j,min,p;

for（j=0;j

{

if（j!

=u）

{

closedge[j].adjvex=u;

closedge[j].lowcost=GRAPH[j][u];

}

}

closedge[u].lowcost=0;

for（i=0;i

{

p=1;

min=MAX;

for（j=0;j

if（closedge[j].lowcost!

=0&&closedge[j].lowcost

{

min=closedge[j].lowcost;

p=j;

}

printf（"<%d,%d>->%d\n",closedge[p].adjvex,p,min）;

closedge[p].lowcost=0;

for（j=0;j

if（GRAPH[p][j]

{

closedge[j].lowcost=GRAPH[p][j];

closedge[j].adjvex=p;

}

}

}

voidconvert（）

{

inti,j;

LINKNODE*p;

for（i=0;i

{

for（j=0;j

GRAPH[i][j]=MAX;

}

for（i=0;i

{

GRAPH[i][i]=0;

p=G[i].first;

while（p!

=NULL）

{

GRAPH[i][p->vex]=p->weight;

p=p->next;

}

}

for（i=0;i

{

for（j=0;j

printf（"%d\t",GRAPH[i][j]）;

printf（"\n"）;

}

}

最小生成树：

kruskal；

#include

#include

#include

#defineMAX100

typedefstructedge

{

intu;

intv;

intweight;

}Edge;

EdgeE[MAX];

intEcount;

voidkruskal（）;

intmain（）

{

inti;

freopen（"in.txt","r",stdin）;

freopen（"out.txt","w",stdout）;

scanf（"%d",&Ecount）;

for（i=0;i

{

scanf（"%d",&E[i].u）;

scanf（"%d",&E[i].v）;

scanf（"%d",&E[i].weight）;

}

kruskal（）;

return0;

}

voidkruskal（）

{

intvset[MAX];

inti,j,k,tempu,tempv,s1,s2;

for（i=0;i

vset[i]=i;

k=1;

j=0;

while（k

{

tempu=E[j].u;

tempv=E[j].v;

s1=vset[tempu];

s2=vset[tempv];

if（s1!

=s2）

{

printf（"u=%d,v=%d,weight=%d\n",tempu,tempv,E[j].weight）;

k++;

for（i=0;i

if（vset[i]==s2）

vset[i]=s1;

}

j++;

}

if（j==Ecount&&k!

=Ecount-1）

printf（"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

{

scanf（"%d",&x）;

s=（bonde*）malloc（sizeof（bonde））;

s->data=x;

s->left=NULL;

s->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（xdata）return（search（b->left））;

elsereturn（search（b->right））;

}

}

四、实验要求

1、根据以上给出算法写出二叉排序树的生成程序。

2、根据以上给出算法写出二叉排序树的查找程序。

3、写出调试运行的分析和体会。

4、写出输出结果和实验报告。

五、强化与提高

思考题：

编写一个从有m个结点其数据域值为r[I]的二叉树中删除结点x的算法。