班级 学号 姓名 实验组别
试验日期 室温 报告日期 成绩
报告内容：（目的和要求、原理、步骤、数据、计算、小结等）
实验名称：查找算法的实现
实验目的：
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 学年 第 二 学期
附录（可包括源程序清单或其它说明）