国脉信息学院
（程序设计类课程）
实验报告
20##年 11月 日
实验项目列表
福建农林大学计算机与信息学院实验报告
系：计算机科学与技术 专业： 年级：
姓名：张三 学号： 091150002 实验室号___ _ 计算机号93
实验时间： 2012.6.1 指导教师签字： 成绩：
实验七检索
一、 实验目的和要求
1) 掌握检索的不同方法，并能用高级语言实现检索算法。
2) 熟练掌握顺序表和有序表的检索方法，以及静态检索树的构造方法和检索算法，理解静态检索树的折半检索方法。
3) 熟练掌握二叉排序树的构造和检索方法。
4) 熟悉各种存储结构的特征以及如何应用树结构解决具体问题。
二、 实验内容和原理
实验内容：
1) 编程实现在二叉检索树中删除一个结点的算法。
2) 编程实现Fibonacci检索算法。
实验原理：
1）构造排序树，每输入一个数就进行排序，选择插入的结点，删除结点，没删除一个节点就返回到构造排序树的方法。
2）Fibonacci数的定义为f0=0,f1=1,fi=f(i-1)+f(i-2)(i≥2)。由此得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<F[f(i-1)],Key，则下一次的检索范围为下标1到f(i-1)，序列长度为f(i-1)。
③ 若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]，key≤F[2]，key≤…≤F[n]。key,k是已知的关键字值，在F中检索关键字值为k的记录。若找到返回其下标值，否则返回0.
三、 实验环境
Windows XP系统
visual c++6.0
四、 算法描述及实验步骤
实验习题一：
#include"stdio.h"
#include"malloc.h"
struct BTnode
{
int data;
struct BTnode *lchild,*rchild;
}*root;
typedef struct BTnode Node,*Nodep;
void createtree(int data)
{
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(data<p->data)
{
q=p;
p=p->lchild;
if(p==0)
q->lchild=node;
}
else
if(data>p->data)
{
q=p;
p=p->rchild;
if(p==0)
q->rchild=node;
}
else
break;
}
}
}
void showtree(struct BTnode *proot,struct BTnode *m,int space)
{
int i;
char b;
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);
}
}
Nodep deletep(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!=0)
q->rchild=p->lchild;
else
q->rchild=0;
p->lchild=t->lchild;
p->rchild=t->rchild;
free(t);
return(p);
}
else
if(p->rchild!=0)
{
p=p->rchild;
q=p;
while(p->lchild!=0)
{
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);
}
}
Nodep deleteBTnode(int x)
{
Node *p=root,*q;
while(p!=0)
{
q=p;
if(p->data>x)
if(p->lchild)
p=p->lchild;
else
break;
else
if(p->data<x)
if(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("can not found the data you want to delete,please check it!\n");
return 0;
}
return root;
}
int main()
{char ch;
int data;
printf("Enter 'c' create tree,Enter 'd' delete a node:");
scanf("%c",&ch);
getchar();
root=0;
while(ch=='c'||ch=='d')
{if(ch=='c')
{printf("please input the key:");
scanf("%d",&data);
getchar();
createtree(data);
showtree(root,0,0);
}
else
{printf("please input the key of the node you want del:");
scanf("%d",&data);
getchar();
if(deleteBTnode(data))
showtree(root,0,0);
}
printf("Enter 'c' create tree,Enter 'd' delete a node:");
scanf("%c",&ch);
}
return 0;
}
实验习题二：
#include "stdio.h"
typedef int keytype;
typedef int datatype;
typedef struct node
{
int key;
}rectype;
int fibonacci(int n)
{
if(n==0) return 0;
else
if(n==1) return 1;
else
return fibonacci(n-1)+fibonacci(n-2); }
void printData(rectype R[],int n)
{
int i;
for(i=1; i<=n; i++)
{
printf("%5d",R[i].key);
if(i%8==0) printf("\n"); }
printf("\n");
}
int fibsearch(rectype R[],keytype K,int n)
{
int m,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)
{
return i; }
else if(K < R[i].key)
{
i = i-q;
t = p;
p = q;
q = t-q; }
else if(K > R[i].key)
{
i=i+q;
p=p-q;
q=q-p;
}
}
return 0;
}
void main()
{
int m,i,k,n;
rectype R[20];
printf("Enter k num:");
scanf("%d",&k);
printf("enter R[20]:");
for(i=1;i<=20;i++)
{
scanf("%d",&R[i].key);
}
printData(R,20);
m=fibsearch(R,k,20);
if(m == 0)
{
printf("Not found!\n");
}
else
printf("The Key has been found at R[%d]\n",m);
getchar();
}
五、 调试过程
1)
构建二叉排序树：
删除二叉树的节点：
2)
在创建结构体时未定义key.
六、 实验结果
1） 成功实现删除二叉检索树上删除结点的算法。
成功创建二叉检索树：
删除结点成功：
删除结点失败：
2)
在Fibonacci数列没有找到关键字的情况：
在Fibonacci数列找到关键字的情况：
七、 总结
1） 掌握了二叉排序树的构造和检索方法。
2） 删除二叉检索树的结点时，必须保证删除后的二叉树仍是一棵二叉检索树。
3） 二叉检索树很方便查找数据，因为它的排列是有一定顺序的，即左子树<根<右子树。
4） 除此之外，还进一步了解了其他的检索方法。
第二篇：接地装置试验报告模板
接地装置试验报告
委托单位：***变电站 设备编号： 试验类型:预防性试验 试验依据:DL/T 596-1996
试验负责人： 试验员：