国脉信息学院

（程序设计类课程）

实验报告

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

试验负责人：                     试验员：