程序设计类课程实验报告.docx
《程序设计类课程实验报告.docx》由会员分享，可在线阅读，更多相关《程序设计类课程实验报告.docx（15页珍藏版）》请在冰点文库上搜索。
程序设计类课程实验报告
国脉信息学院
（程序设计类课程）实验报告
课程名称：
算法与数据结构
姓名：
系：
张三
计算机科学与技术
专业:
年级:
学号:
指导教师：
李小林
职称：
副教授
2012年11月日
实验项目列表
序号
实验项目名称
成绩
指导教师
1
第七章检索及基本算法
2
3
4
5
6
7
8
9
10
11
12
福建农林大学计算机与信息学院实验报告
系：
计算机科学与技术专业：
年级：
姓名：
张三学号：
实验室号计算机号93
实验时间：
201261指导教师签字：
成绩：
实验七检索
一、实验目的和要求
1）掌握检索的不同方法，并能用高级语言实现检索算法。
2）熟练掌握顺序表和有序表的检索方法，以及静态检索树的构造方法和检索算法，理解静态检索树的折半检索方法。
3）熟练掌握二叉排序树的构造和检索方法。
4）熟悉各种存储结构的特征以及如何应用树结构解决具体问题。
二、实验内容和原理
实验内容：
1）编程实现在二叉检索树中删除一个结点的算法。
2）编程实现Fibonacci检索算法。
实验原理：
1）构造排序树，每输入一个数就进行排序，选择插入的结点，删除结点，没删除一个节点就返回到构造排序树的方法。
》2）o由此得
2）Fibonacci数的定义为fO=O,f1=1,fi二f（i-1）+f（i-2）（i
Fibonacci数列为0,1,1,2,3,5,8,13,21,34,55,89,144,
设数组F中元素按关键字值从小到大顺序排列，并假定元素个数n比某个
Fibonacci树fi小
1,即卩n二fi-1。
第一次用待查关键字k与F[f（i-1）],
Key比较，其算法描述
如下:
①若k=F[f（i-1）],Key
，贝叶佥索成功，F[f（i-1）]为k所在记录。
②若k则下一次的检索范围为下标1到f（i-1）,序列长度为
f（i-1）o
③若k>F[f（i-1）],Key
则下一次的检索范围为下标f（i+1）+1到fi-1，序列
长度为（fi-1）-（f（i-1）+1）+1=fi-f（i-1）-1=f（i-2）-1
设F是顺序存储的线性表且满足F[1],keykey,k
是已知的关键字值，在F中检索关键字值为k的记录。
若找到返回其下标值，
否则返回0.
三、实验环境
WindowsXP系统
visualC++6.0
四、算法描述及实验步骤
实验习题一：
#include"stdio.h"
#include"malloc.h"
structBTnode
{
intdata;structBTnode*lchild,*rchild;
}*root;
typedefstructBTnodeNode,*Nodep;voidcreatetree（intdata）{
Node*node,*p,*q;
node=（Nodep）malloc（sizeof（Node））;node->data=data;
node->lchild=0;
node->rchild=0;
if（root==0）
{
root=node;return;
}
else
{p=root;
while（p!
=0）
{
if（datadata）
{
q=p;p=p->lchild;if（p==0）q->lchild=node;
}elseif（data>p->data）
{
q=p;p=p->rchild;
if（p==0）
q->rchild=node;
}
else
break;
}
}
}
voidshowtree（structBTnode*proot,structBTnode*m,intspace）{
inti;
charb;
if（proot!
=0）
{
for（i=1;i<=space-3;i++）
printf（""）;
if（space-3>=0）
printf（"---->"）;
if（proot==root）
printf（"%d\n",proot->data）;
else
{
if（m->data>proot->data）
b='L';
else
b='R';
printf（"%d（%c）",proot->data,b）;
printf（"\n"）;
}
m=proot;
showtree（proot->lchild,m,space+6）;showtree（proot->rchild,m,space+6）;
}
}
Nodepdeletep（Node*p）
{
Node*q,*t;
t=p;
if（p->lchild!
=0）
{
p=p->lchild;
q=p;
while（p->rchild!
=0）
{
q=p;
p=p->rchild;
if（p==q）
p->rchild=t->rchild;
free（t）;return（p）;
}
if（p->lchild!
=O）q->rchild=p->lchild;
else
q->rchild=O;p->lchild=t->lchild;
p->rchild=t->rchild;free（t）;
return（p）;
}
else
if（p->rchild!
=O）
{
p=p->rchild;
q=p;
while（p->lchild!
=O）
{
q=p;p=p->lchild;
}
if（p==q）
{p->lchild=t->lchild;free（t）;return（p）;
}
if（p->rchild!
=0）q->lchild=p->rchild;else
q->lchild=0;p->rchild=t->rchild;
p->lchild=t->lchild;free（t）;
return（p）;
}
else
{
free（p）;
return（0）;
NodepdeleteBTnode（intx）
{
Node*p=root,*q;
while（p!
=0）
{
q=p；
if（p->data>x）
if（p->lchild）
p=p->lchild;
else
break;
else
if（p->dataif（p->rchild）
p=p->rchild;
else
break;
if（p->data==x）
break;
}
if（（p==root）&&（p->data==x））
root=deletep（p）;
else
if（（p==q->lchild）&&（p->data==x））
q->lchild=deletep（p）;
else
if（（p==q->rchild）&&（p->data==x））
q->rchild=deletep（p）;
else
if（p->data!
=x）
{printf（"cannotfoundthedatayouwanttodelete,pleasecheckit!
\n"）;
return0;
}
returnroot;
}
intmain（）
{charch;
intdata;
printf（"Enter'c'createtree,Enter'd'deleteanode:
"）;
scanf（"%c",&ch）;
getchar（）;
root=0;
while（ch=='c'||ch=='d'）
{if（ch=='c'）
{printf（"pleaseinputthekey:
"）;
seanf（"%d",&data）;getchar（）;
createtree（data）;showtree（root,0,0）;
}
else
{printf（"pleaseinputthekeyofthenodeyouwantdel:
"）;
seanf（"%d",&data）;
getchar（）;
if（deleteBTnode（data））
showtree（root,0,0）;
}
printf（"Enter'c'createtree,Enter'd'deleteanode:
"）;
seanf（"%c",&ch）;
}
return0;
}
实验习题二：
#include"stdio.h"
typedef
int
keytype;
typedef
int
datatype;
typedef
structnode
{
int
key;
}rectype;
intfibonacci（intn）
{
if（n==0）return0;else
if（n==1）return1;
else
returnfibonacci（n-1）+fibonacci（n-2）;}
voidprintData（rectypeR[],intn）
{
inti;
for（i=1;i<=n;i++）
{
printf（"%5d",R[i].key）;
if（i%8==0）printf（"\n"）;}
printf（"\n"）;
}
intfibsearch（rectypeR[],keytypeK,intn）
{
intm,i,p,q,t;
for（m=0;fibonacci（m）<=（n+1）;m++）{}
m--;
i=fibonacci（m-1）;
p=fibonacci（m-2）;
q=fibonacci（m-3）;
while（i>=0&&i<=n）
{
if（K==R[i].key）
{
returni;}
elseif（K{
i=i-q;
t=p;
p=q;
q=t-q;}elseif（K>R[i].key）
{i=i+q;p=p-q;q=q-p;
}
}
return0;
}
voidmain（）
{
intm,i,k,n;
rectypeR[20];
printf（"Enterknum:
"）;
scanf（"%d",&k）;
printf（"enterR[20]:
"）;
for（i=1;i<=20;i++）
{
scanf（"%d",&R[i].key）;
}
printData（R,20）;
m=fibsearch（R,k,20）;
if（m==0）
{
printf（"Notfound!
\n"）;
}
m）;
else
printf（"TheKeyhasbeenfoundatR[%d]\n"getchar（）;
}
五、调试过程
1）
构建二叉排序树：
删除二叉树的节点:
2）
LA
'—已启动生成：
项昌：
埶揺结枸试验,，裁食:
DibngTirdE
1闿成倉动时间対2011/6/916：
22.34o
L/'Iijitiali口s；
!
■》正在创逢叮弗口於数揭结构试验.zwucuewMHHmiU"，因拘己指定AlwaysCreataM
LXJ12
L>l>c：
1>
L>
l>c：
L>
L>c；
1>
*
L>
1>吐a
cumpile:
數摇皓枸试验.=pp
3理負蚯皿业询1埶据结构诫轻埶搦结构i或验哦H絃构试验嘶〔⑴：
*rrwC203Q：
L,ckty":
不昱"rutW的成员
0lx比八hplhMkMiA埶据结构诫翳A加据结构试验I加攥结构试憾.比P15）卷风*f“直列的声明
血I仏血P啾据结构试瞪嵋据结构试验谶松结构试验好dC2V：
errwcmg：
-key":
不是f皿”的成员
匚:
\u5erAhpWeSktOpm据结枸试验I数据结构试验'数攜结梅试验.cppCS）:
蜃见丽旅"的芮明_
皿ersgld■旳ktojA埶据结构试验、数据结翰试验哦拥结构试验c叩⑶）；errorC^039:
i-key":
不是"iw"的成员
u；也sktojA敎拥结槪睡\数松结构试矗谶攝结构试验SP㈤；転见“册朗'*］声明
\usart\lipUa5ktop\^据结构试洛遢拥结松试甕数拥结构试监注抵）：
叱叶C如的；"k歹：
不是‘5"的咸员
cVusers\hpUesktcp\数苗絃构试矗'数据绪构i磁'数霭貓构试瞪■cppW.参见"tw血"俞声明
\u5ars\lip\.AesktopVS据结构试热教塘结柯试验I竅壇姑柯试热叼曲盯《rrorC20轴叫电不是％皿”的咸员
XkplJe士昂讥數据结构：
擞\數据结构i腸'救堀结构试唸，"⑸）：
筆见竹磔朕待的肓明
Vile吐匸
c.Vusers
冃时间00:
00:
0109
=====牛应：
fsfiiho4半时1金*尿新0金，跚Po个
在创建结构体时未定义key.
六、实验结果
1）成功实现删除二叉检索树上删除结点的算法
成功创建二叉检索树：
删除结点成功：
删除结点失败：
2）
在Fibonacci数列没有找到关键字的情况：
在Fibonacci数列找到关键字的情况：
七、总结
1）掌握了二叉排序树的构造和检索方法。
2）删除二叉检索树的结点时，必须保证删除后的二叉树仍是一棵二叉检索树。
3）二叉检索树很方便查找数据，因为它的排列是有一定顺序的，即左子树＜根＜
右子树。
4）除此之外，还进一步了解了其他的检索方法。
升级会员 