数据结构实验四五六.docx
《数据结构实验四五六.docx》由会员分享，可在线阅读，更多相关《数据结构实验四五六.docx（29页珍藏版）》请在冰点文库上搜索。
数据结构实验四五六
数据结构实验
实验四、图遍历的演示。
【实验学时】5学时
【实验目的】
（1）掌握图的基本存储方法。
（2）熟练掌握图的两种搜索路径的遍历方法。
【问题描述】
很多涉及图上操作的算法都是以图的遍历操作为基础的。
试写一个程序，演示连通的无向图上，遍历全部结点的操作。
【基本要求】
以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。
【测试数据】
教科书图7.33。
暂时忽略里程，起点为北京。
【实现提示】
设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1，2，…，n）。
通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。
注意，生成树的边是有向边，端点顺序不能颠倒。
【选作内容】
（1）借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。
（2）以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。
（3）正如习题7。
8提示中分析的那样，图的路径遍历要比结点遍历具有更为广泛的应用。
再写一个路径遍历算法，求出从北京到广州中途不过郑州的所有简单路径及其里程。
【源程序】
#include
#include
#include
#defineMAX_VERTEX_NUM20
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineTRUE1
#defineOK1
#defineFALSE0
#defineERROR0
#defineOVERFLOW-2
typedefenum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向网}
boolvisited[MAX_VERTEX_NUM];
typedefstructArcNode
{
intadjvex;//该弧所指向的顶点在数组中的下标
structArcNode*nextarc;
int*info;//该弧相关信息的指针
}ArcNode;
typedefstructVNode
{
intdata;//顶点信息
ArcNode*firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct
{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
intkind;//图的种类标志
}ALGraph;
typedefstruct
{
int*base;
int*top;
intstacksize;
}SqStack;
typedefstructQNode
{
intdata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
intLocateVex（ALGraphG,intv）
{//返回数组下标值
inti;
for（i=0;iif（G.vertices[i].data==v）returni;
return-1;
}
voidCreateDN（ALGraph&G）
{//采用邻接表存储表示,构造有向图G（G.kind=DN）
inti,j,k;ArcNode*p;intv1,v2;
G.kind=DN;
printf（"输入顶点数:
"）;
scanf（"%d",&G.vexnum）;
printf（"输入弧数:
"）;
scanf（"%d",&G.arcnum）;
printf（"输入顶点:
\n"）;
for（i=0;i{//构造表头向量
scanf（"%d",&G.vertices[i].data）;
G.vertices[i].firstarc=NULL;//初始化指针
}
for（k=0;k{
printf（"第%d条弧:
",k+1）;
scanf（"%d",&v1）;
scanf（"%d",&v2）;//输入一条弧的始点和终点
i=LocateVex（G,v1）;j=LocateVex（G,v2）;//确定v1和v2在G中位置
p=（ArcNode*）malloc（sizeof（ArcNode））;//假定有足够空间
p->adjvex=j;p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
scanf（"%d",&p->info）;
}//for
}
intPush（SqStack&S,inte）
{//插入元素e为新的栈顶元素
if（S.top-S.base>=S.stacksize）
{//栈满，追加存储空间
S.base=（int*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（int））;
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
intInitStack（SqStack&S）//栈的初始化
{
S.base=（int*）malloc（STACK_INIT_SIZE*sizeof（int））;
if（!
S.base）exit（OVERFLOW）;//存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
intPop（SqStack&S,int&e）//删除栈顶元素
{//若栈不空，则删除S的栈顶元素，用e返回其值
if（S.top==S.base）
returnERROR;
e=*--S.top;
returnOK;
}
intGetTop（SqStackS,int&e）//取栈顶元素
{//若栈不空，则用e返回S的栈顶元素
if（S.top==S.base）
returnERROR;
e=*（S.top-1）;
returnOK;
}
intStackEmpty（SqStackS）//栈空
{
if（S.top==S.base）
returnTRUE;
else
returnFALSE;
}
intInitQueue（LinkQueue&Q）//队列初始化
{
Q.front=Q.rear=（QueuePtr）malloc（sizeof（QNode））;
if（!
Q.front）exit（OVERFLOW）;
Q.front->next=NULL;
returnOK;
}
intEnQueue（LinkQueue&Q,inte）//插入
{//插入元素e为Q的新的队尾元素
QueuePtrp=（QueuePtr）malloc（sizeof（QNode））;
if（!
p）exit（OVERFLOW）;
p->data=e;p->next=NULL;
Q.rear->next=p;
Q.rear=p;
returnOK;
}
intDeQueue（LinkQueue&Q,int&e）
{//若队列不空，则删除Q的队头元素，用e返回其值
if（Q.front==Q.rear）
returnERROR;
QueuePtrp=Q.front->next;
e=p->data;
Q.front->next=p->next;
if（Q.rear==p）Q.rear=Q.front;
free（p）;
returnOK;
}
intQueueEmpty（LinkQueueQ）//队列空
{
if（Q.front==Q.rear）
returnTRUE;
else
returnFALSE;
}
intFirstAdjVex（ALGraphG,intu）
{
if（!
G.vertices[u].firstarc）
return-1;
returnLocateVex（G,G.vertices[u].firstarc->adjvex）;
}
intNextAdjVex（ALGraphG,intu,intw）
{
ArcNode*p=G.vertices[u].firstarc;
while（p&&LocateVex（G,p->adjvex）!
=w）
p=p->nextarc;
if（!
p）
returnFirstAdjVex（G,u）;
p=p->nextarc;
if（!
p）
return-1;
returnLocateVex（G,p->adjvex）;
}
voidVisit（ALGraphG,intv）
{
printf（"%2d",G.vertices[v].data）;
}
voidDFSTraverse（ALGraphG）
{//按深度优先非递归遍历图G,使用辅助栈S和访问标志数组visited
intv,w;SqStackS;
for（v=0;vvisited[v]=FALSE;
InitStack（S）;
for（v=0;vif（!
visited[v]）
{//v尚未被访问
visited[v]=TRUE;
Visit（G,v）;
Push（S,v）;//v进栈
while（!
StackEmpty（S））
{
for（w=FirstAdjVex（G,v）;w>=0;w=NextAdjVex（G,v,w））
{
if（!
visited[w]）
{
Visit（G,w）;
visited[w]=TRUE;
Push（S,w）;
GetTop（S,v）;
}//if
}//for
Pop（S,v）;
GetTop（S,v）;
}//while
}//if
printf（"\n"）;
}
voidBFSTraverse（ALGraphG）
{//按广度优先非递归遍历图G,使用辅助队列Q和访问标志数组visited
intv,u,w;LinkQueueQ;
for（v=0;vvisited[v]=FALSE;
InitQueue（Q）;
for（v=0;vif（!
visited[v]）
{//v尚未被访问
visited[v]=TRUE;
Visit（G,v）;
EnQueue（Q,v）;//v入队列
while（!
QueueEmpty（Q））
{
DeQueue（Q,u）;//队头元素出队并置为u
for（w=FirstAdjVex（G,u）;w>=0;w=NextAdjVex（G,u,w））
if（!
visited[w]）
{//w为u的尚未访问的邻接顶点
visited[w]=TRUE;Visit（G,w）;
EnQueue（Q,w）;
}//if
}//while
}//if
printf（"\n"）;
}
voidPrintDN（ALGraphG）//图的显示
{
inti;ArcNode*p;
printf（"顶点:
\n"）;
for（i=0;iprintf（"%2d",G.vertices[i].data）;
printf（"\n弧:
\n"）;
for（i=0;i{
p=G.vertices[i].firstarc;
if（p）
{
while（p）
{
printf（"%d→%d（%d）\t",i,p->adjvex,p->info）;
p=p->nextarc;
}
printf（"\n"）;
}//if
}//for
}
voidmain（）
{
ALGraphG;
printf（"************题目：
图的遍历***************\n\n"）;
CreateDN（G）;
PrintDN（G）;
printf（"深度优先遍历:
"）;
DFSTraverse（G）;
printf（"\n广度优先遍历:
"）;
BFSTraverse（G）;
}
【运行结果】
实验五查找算法实现
【实验学时】5学时
【实验目的】
熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。
【问题描述】
查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。
【基本要求】
（1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。
（2）根据给定的数据建立平衡二叉树。
（3）比较二叉排序树和平衡二叉树的平均查找长度。
【测试数据】
随机生成。
【实现提示】
（1）初始，二叉排序树和平衡二叉树都为空树，操作界面给出查找、插入和删除三种操作供选择。
每种操作均要提示输入关键字。
每次插入或删除一个结点后，应更新平衡二叉树或二叉排序树的显示。
（2）平衡二叉树或二叉排序树的显示可以采用凹入表形式，也可以采用图形界面画出树形。
【源程序】
#include
#include
#include
#defineEQ（a,b）（（a）==（b））
#defineLT（a,b）（（a）<（b））
#defineLQ（a,b）（（a）>（b））
typedefintKeytype;
typedefstruct
{Keytypekey;
}ElemType;
typedefstructBSTnode
{ElemTypedata;
intbf;
structBSTnode*lchild,*rchild;
}BSTnode,*BSTree;
voidInitBSTree（BSTree&T）
{T=NULL;
}
voidR_Rotate（BSTree&p）
{BSTnode*lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;
p=lc;
}
voidL_Rotate（BSTree&p）
{BSTnode*rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
}
voidLeftbalance（BSTree&T）
{BSTnode*lc,*rd;
lc=T->lchild;
switch（lc->bf）
{
case+1:
T->bf=lc->bf=0;
R_Rotate（T）;
break;
case-1:
rd=lc->rchild;
switch（rd->bf）
{case1:
T->bf=-1;
lc->bf=0;
break;
case0:
T->bf=lc->bf=0;
break;
case-1:
T->bf=0;
lc->bf=1;
break;
}
rd->bf=0;
L_Rotate（T->lchild）;
R_Rotate（T）;
}
}
voidRbalance（BSTree&T）
{BSTnode*lc,*ld;
lc=T->rchild;
switch（lc->bf）
{case1:
ld=lc->lchild;
switch（ld->bf）
{case1:
T->bf=0;
lc->bf=-1;
break;
case0:
T->bf=lc->bf=0;
break;
case-1:
T->bf=1;
lc->bf=0;
break;
}
ld->bf=0;
R_Rotate（T->rchild）;
L_Rotate（T）;
case-1:
T->bf=lc->bf=0;
L_Rotate（T）;
break;
}
}
intInsertAVL（BSTree&T,ElemTypee,bool&taller）
{if（!
T）
{T=（BSTree）malloc（sizeof（BSTnode））;
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=0;
taller=true;
}
else
{if（EQ（e.key,T->data.key））
{taller=false;
cout<<"结点"<"<return0;
}
if（LT（e.key,T->data.key））
{if（!
InsertAVL（T->lchild,e,taller））
{return0;
}
if（taller）
switch（T->bf）
{case1:
Leftbalance（T）;
taller=false;
break;
case0:
T->bf=+1;
taller=true;
break;
case-1:
T->bf=0;
taller=false;
break;
}
}
else
{if（!
InsertAVL（T->rchild,e,taller））
{return0;
}
if（taller）
switch（T->bf）
{case1:
T->bf=0;
taller=false;
break;
case0:
T->bf=-1;
taller=true;
break;
case-1:
Rbalance（T）;
taller=false;
break;
}
}
}
return1;
}
boolSearchBST（BSTreeT,ElemTypekey,BSTreef,BSTree&p）
{if（!
T）
{p=f;
cout<<"结点不存在。
"<returnfalse;
}
elseif（EQ（key.key,T->data.key））
{p=T;
cout<<"查找成功，存在结点";
cout<data.key<returntrue;
}
elseif（LT（key.key,T->data.key））
returnSearchBST（T->lchild,key,T,p）;
else
returnSearchBST（T->rchild,key,T,p）;
}
voidLeftbalance_div（BSTree&p,int&shorter）
{BSTreep1,p2;
if（p->bf==+1）//p结点的左子树高，删除结点后p的bf减1,树变矮
{p->bf=0;
shorter=1;
}
elseif（p->bf==0）//p结点左、右子树等高，删除结点后p的bf减1,树高不变
{p->bf=-1;
shorter=0;
}
else
{p1=p->rchild;//p1指向p的右子树
if（p1->bf==0）//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变
{L_Rotate（p）;
p1->bf=1;
p->bf=-1;
shorter=0;
}
elseif（p1->bf==-1）//p1的右子树高，左旋处理后，树变矮
{L_Rotate（p）;
p1->bf=p->bf=0;
shorter=1;
}
else
{p2=p1->lchild;
p1->lchild=p2->rchild;
p2->rchild=p1;
p->rchild=p2->lchild;
p2->lchild=p;
if（p2->bf==0）
{p->bf=0;
p1->bf=0;
}
elseif（p2->bf==-1）
{p->bf=+1;
p1->bf=0;
}
else
{p->bf=0;
p1->bf=-1;
}
p2->bf=0;
p=p2;
shorter=1;
}
}
}
voidRbalance_div（BSTree&p,int&shorter）
{BSTreep1,p2;
if（p->bf==-1）
{p->bf=0;
shorter=1;
}
elseif（p->bf==0）
{p->bf=+1;
shorter=0;
}
else
{p1=p->lchild;
if（p1->bf==0）
{R_Rotate（p）;
p1->bf=-1;
p->bf=+1;
shorter=0;
}
elseif（p1->bf==+1）
{R_Rotate（p）;
p1->bf=p->bf=0;
shorter=1;
}
else
{p2=p1->rchild;
p1->rchild=p2->lchild;
p2->lchild=p1;
p->lchild=p2->rchild;
p2->rchild=p;
if（p2->bf==0）
{p->bf=0;
p1->bf=0;
}
elseif（p2->bf==1）
{p->bf=-1;
p1->bf=0;
}
else
{p->bf=0;
p1->bf=1;
}
p2->bf=0;
升级会员 