班级        学号            姓名        实验组别            

试验日期          室温              报告日期           成绩               

报告内容：（目的和要求、原理、步骤、数据、计算、小结等）

实验名称：查找算法的实现

实验目的：

1.  掌握顺序表上查找的实现及监视哨的作用。

2.  掌握折半查找所需的条件，折半查找的过程和实现方法。

3.  掌握二叉顺序树的创建过程，掌握二叉顺序树查找过程的实现。

4.  掌握哈希表的基本概念，熟悉哈希函数的选择方法，掌握使用线性探测法和链地址法进行冲突解决的方法

实验环境（硬/软件要求）：

Windows 2000, Visual C++ 6.0

实验内容：

通过具体算法程序，进一步加深对各种查找方法的掌握，以及对实际应用中问题解决方法的掌握。

各查找算法的输入序列为：26 5 37 1 61  11 59 15 48 19.

输出要求：查找关键字37，给出查找结果。

实验要求

1.顺序查找

首先从键盘输入一个数据序列生成一个顺序表，然后从键盘上任意输入一个值，在顺序表中进行查找。

【C语言源程序】

#include<stdio.h>

#define MAX 100

typedef int keytype;

typedef struct

{  keytype key;

}elemtype;

typedef struct

{  elemtype elem[MAX+1];

   int length;

}SStable;

void create_seq(SStable *list);

int seq_search(SStable *list,keytype k);

void main()                //主函数

{  SStable *list,table;

   keytype key;

   int i;

   list=&table;

   printf("请输入顺序表的长度:");

   scanf("%d",&list->length);

   create_seq(list);

   printf("创建的顺序表内容:\n");

   for(i=0;i<list->length;i++)

            printf("list.elem[%d].key=%d\n",i+1,list->elem[i].key);

   printf("输入查找关键字:");

   scanf("%d",&key);

   seq_search(list,key);

}

void create_seq(SStable *list)         //创建顺序表list的函数

{  int i;

   printf("请输入顺序表的内容:\n");

   for(i=0;i<list->length;i++)

   {  printf("list.elem[%d].key=",i+1);

      scanf("%d",&list->elem[i].key);

   }

}

int seq_search(SStable *list,keytype k)      //在顺序表中查找给定的k值

{  int i=0,flag=0;

   while(i<list->length)

  {  if(list->elem[i].key==k)

   {  printf("查找成功.\n");

      flag=1;

           printf("list.elem[%d].key=%d\n",i+1,k);

   }

   i++;

  }

if(flag==0)

   printf("没有找到数据%d!\n",k);

return(flag);

}

2.折半查找

任意输入一组数据作为个数据元素的键值，首先将此序列进行排序，然后在该有序表上进行折半查找算法进行对给定值key的查找。

【C语言源程序】

#include<stdio.h>

#define MAX 100

typedef struct

{  int elem[MAX+1];

   int length;

}Stable;

void creat_seq(Stable *list);

int sort_seq(Stable *list);

int bin_search(Stable *list,int k,int low,int high);

void main()

{  Stable *list,table;

   int i,key;

   list=&table;

   printf("请输入线性表的长度:");

   scanf("%d",&list->length);

   creat_seq(list);

   sort_seq(list);

   printf("排序后的数据\n");

   for(i=1;i<=list->length;i++)

            printf("list.elem[%d].key=%d\n",i,list->elem[i]);

   printf("\n请输入查找的值:");

   scanf("%d",&key);

   bin_search(list,key,1,list->length);

}

void creat_seq(Stable *list)

{  int i;

   printf("请输入顺序表的内容:\n");

   for(i=1;i<=list->length;i++)

   {  printf("list.elem[%d].key=",i);

      scanf("%d",&list->elem[i]);

   }

}

int sort_seq(Stable *list)       //冒泡法排序

{  int i,j,flag;

   for(i=1;i<list->length;i++)

   {  flag=0;

      for(j=1;j<list->length-i+1;j++)

                     if(list->elem[j]>list->elem[j+1])

                     {  list->elem[0]=list->elem[j+1];

             list->elem[j+1]=list->elem[j];

             list->elem[j]=list->elem[0];

                             flag=1;

                     }

                     if(flag==0)return 1;

   }

}

int bin_search(Stable *list,int k,int low,int high)    //折半查找法的递归函数

{  int mid;

   if(low>high)

   {  printf("没有找到要查找的值\n");

      return(0);

   }

   mid=(low+high)/2;

   if(list->elem[mid]==k)

   {  printf("查找成功\n");

      printf("list[%d]=%d\n",mid,k);

           return(mid);

   }

   else

            if(list->elem[mid]<k)

                      return(bin_search(list,k,mid+1,high));

            else

           return(bin_search(list,k,low,mid-1));

3.二叉树查找

任意输入一组数据作为二叉排序树中结点的键值，首先创建一颗二叉排序树，然后在此二叉排序树上实现对给定值K的查找过程。

【C语言源程序】

#include<stdio.h>

#include <stdlib.h>

typedef struct bitnode

{

    int key;

         struct bitnode *lchild;

         struct bitnode *rchild;

} bnode;

void ins_bitree(bnode *p,int k)

{

     bnode *q;

          if(p->key>k&&p->lchild)

                    ins_bitree(p->lchild,k);

          else

         if(p->key<=k&&p->rchild)

                   ins_bitree(p->rchild,k);

         else

         {

            q=(bnode*)malloc(sizeof(bnode));

            q->key=k;

            q->lchild=NULL;

            q->rchild=NULL;

            if(p->key>k)

                      p->lchild=q;

            else

                      p->rchild=q;

         }

}

    void bit_search(bnode *p,int k)

         {

           if(p->key>k&&p->lchild)

                     bit_search(p->lchild,k);

           else

                    if(p->key<k&&p->rchild)

                             bit_search(p->rchild,k);

                    else

                             if(p->key==k)

                                      printf("查找成功！\n");

                             else

                                      printf("%d不存在\n",k);

         }

void inorder(bnode *p)

{

   if(p)

           {

            inorder(p->lchild);

            printf("%4d",p->key);

            inorder(p->rchild);}

}

void main()

{

  int k;

  bnode *p;

  p=NULL;

  printf("请输入二叉树节点的值，输入0结束：\n");

  scanf("%d",&k);

  p=(bnode*)malloc(sizeof(bnode));

  p->key=k;

  p->lchild=NULL;

  p->rchild=NULL;

  scanf("%d",&k);

  while(k>0)

  {

    ins_bitree(p,k);

         scanf("%d",&k);}

         printf("\n");

         printf("二叉树排序结果\n");

         inorder(p);

         printf("\n请直接输入查找的值\n");

         scanf("%d",&k);

         bit_search(p,k);

 

}

4.哈夫曼查找

任意输入一组数据作为各元素的键值，哈希函数为Hash(key)=key%11,用线性探测再散列法解决冲突问题。

【C语言源程序】

#include<stdio.h>

#define MAX 11

void ins_hash(int hash[],int key)

{

         int k,k1,k2;

         k=key%MAX;

         if(hash[k]==0)

         {

                   hash[k]=key;

                   return;

         }

         else

         {

                   k1=k+1;

                   while(k1<MAX&&hash[k1]!=0)

                            k1++;

                   if(k1<MAX)

                   {

                            hash[k1]=key;

                            return;

                   }

                   k2=0;

                   while(k2<k&&hash[k2]!=0)

                            k2++;

                   if(k2<k)

                   {

                            hash[k2]=key;

                            return;

                   }

         }

}

void out_hash(int hash[])

{

         int i;

         for(i=0;i<MAX;i++)

                   if(hash[i])

                            printf("hash[%d]=%d\n",i,hash[i]);

}

void hash_search(int hash[],int key)

{

         int k,k1,k2,flag=0;

         k=key%MAX;

         if(hash[k]==key)

         {

                   printf("hash[%d]=%d",k,key);

                   flag=1;

         }

         else

         {

                   k1=k+1;

                   while(k1<MAX&&hash[k1]!=key)

                            k1++;

                   if(k1<MAX)

                   {

                            printf("hash[%d]=%d",k1,key);

                            flag=1;

                   }

                   k2=0;

                   if(!flag)

                   {

                            while(k2<k&&hash[k2]!=key)

                                     k2++;

                            if(k2<k)

                            {

                                     printf("hash[%d]=%d",k2,key);

                                     flag=1;

                            }

                   }

                   if(flag)

                   {

                            printf("查找成功!\n");

                            return;

                   }

                   else

                   {

                            printf("查找失败!\n");

                            return;

                   }

         }

}

void main()

{

         int i,key,k,sum=0;

         int hash[MAX];

         for(i=0;i<MAX;i++)

                   hash[i]=0;

         printf("请输入数据，以0结束:\n");

         scanf("%d",&key);

         sum++;

         while(key&&sum<MAX)

         {

                   ins_hash(hash,key);

                   scanf("%d",&key);

                   sum++;

         }

         printf("\n");

         out_hash(hash);

         printf("\n");

         printf("请输入查找的值:");

         scanf("%d",&k);

         hash_search(hash,k);

         printf("\n");

}

 

第二篇：实验报告——实验1：处理机调度算法的实现

 

天津理工大学

计算机与通信工程学院

实验报告

20##  至  2011  学年  第   二  学期

附录（可包括源程序清单或其它说明）