班级学号姓名实验组别试验日期室温报告日期成绩报告内容：（目的和要求、原理、步骤、数据、计算、小结等）实验名称：查找算法的实现实验目的：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 100typedef 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 100typedef 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);}elseif(list->elem[mid]<k)return(bin_search(list,k,mid+1,high));elsereturn(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);elseif(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;elsep->rchild=q;}}void bit_search(bnode *p,int k){if(p->key>k&&p->lchild)bit_search(p->lchild,k);elseif(p->key<k&&p->rchild)bit_search(p->rchild,k);elseif(p->key==k)printf("查找成功！\n");elseprintf("%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 11void 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");}。