查找 实验报告_折半查找实验报告
查找 实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“折半查找实验报告”。
实验六
查找
实验目的：
掌握几种查找的思想及算法 问题分析：
（一）顺序查找 1.查找思想
从表的一端开始逐个将记录的关键字和给定K值进行比较，若某个记录的关键字和给定K值相等，查找成功；否则，若扫描完整个表，仍然没有找到相应的记录，则查找失败。2.算法实现
int Seq_Search(SSTable ST,int key){
int p;
} ST.data[0].key=key;/* 设置监视哨兵,失败返回0 */ for(p=ST.length;ST.data[p].key!=key;p--);return(p);
3.算法分析
设查找每个记录成功的概率相等，即Pi=1/n；查找第i个元素成功的比较次数Ci=n-i+1 ； ◆ 查找成功时的平均查找长度ASL：
◆
包含查找不成功时：查找失败的比较次数为n+1，若成功与不成功的概率相等，对每个记录的查找概率为Pi=1/(2n)，则平均查找长度ASL：
（二）折半查找
前提条件：查找表中的所有记录是按关键字有序(升序或降序)。
查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，直到找到或找不到记录为止。1.查找思想
用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。
⑴
取中间位置Mid：Mid=(Low+High)/2 ；
⑵
比较中间位置记录的关键字与给定的K值： ①
相等： 查找成功；
②
大于：待查记录在区间的前半段，修改上界指针： High=Mid-1，转⑴ ； ③
小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ； 直到越界(Low>High)，查找失败。2.算法实现
int Bin_Search(SSTable ST , KeyType k){
int low=1，high=ST.length, mid;
while(low
mid=(low+high)/2;
if(EQ(ST.data[mid].key, k))
return(mid);
else if(LT(ST.dat[mid].key, k))
low=mid+1;
else high=mid-1;
}
return(0);
/*
查找失败
*/ } 3.算法分析
①
查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示： ◆
根结点就是第一次进行比较的中间位置的记录； ◆ 排在中间位置前面的作为左子树的结点； ◆ 排在中间位置后面的作为右子树的结点；
对各子树来说都是相同的。这样所得到的二叉树称为判定树(Decision Tree)。②
将二叉判定树的第㏒2n+1层上的结点补齐就成为一棵满二叉树，深度不变，h= ㏒2(n+1)。4.算法分析
①
查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示： ◆
根结点就是第一次进行比较的中间位置的记录； ◆ 排在中间位置前面的作为左子树的结点； ◆ 排在中间位置后面的作为右子树的结点；
对各子树来说都是相同的。这样所得到的二叉树称为判定树(Decision Tree)。②
将二叉判定树的第㏒2n+1层上的结点补齐就成为一棵满二叉树，深度不变，h= ㏒2(n+1)。
③
由满二叉树性质知，第i 层上的结点数为2i-1(i≤h)，设表中每个记录的查找概率相等，即Pi=1/n，查找成功时的平均查找长度ASL：
当n很大(n>50)时，ASL≈ ㏒2(n+1)-1。
（三）BST树 1.BST树的插入（1）插入思想
在BST树中插入一个新结点x时，若BST树为空，则令新结点x为插入后BST树的根结点；否则，将结点x的关键字与根结点T的关键字进行比较：
① 若相等： 不需要插入；
②
若x.keykey：结点x插入到T的左子树中； ③
若x.key>T->key：结点x插入到T的右子树中。（2）算法实现
递归算法
void Insert_BST(BSTree T , KeyType key){ BSTNode *s;s=(BSTNode *)malloc(sizeof(BSTNode));s->key=key;s->Lchild=s->Rchild=NULL;if(T==NULL)T=s;else { if(EQ(T->key, s->key))return;/* 已有结点
*/ else if(LT(s->key, T->key))Insert_BST(T->Lchild, key);else Insert_BST(T->Rchild, key);
} 非递归算法
void Insert_BST(BSTree T , KeyType key){ BSTNode *s, *p , *f;s=(BSTNode *)malloc(sizeof(BSTNode));s->key=key;s->Lchild=s->Rchild=NULL;if(T==NULL)T=s;else { p=T;
while(p!=NULL)
{
if(EQ(p->key, s->key))return;
f=p;
/*q作为p的父结点
*/
if(LT(s->key, p->key))p=p->Lchild;
else p=p->Rchild;
}
if(LT(s->key, f->key))f->Lchild=s;else f->Rchild=s;} }
利用BST树的插入操作，可以从空树开始逐个插入每个结点，从而建立一棵BST树，算法如下：
#define ENDKEY 65535 BSTree create_BST(){
KeyType key;BSTree T=NULL;scanf(“%d”, &key);while(key!=ENDKEY){
Insert_BST(T, key);scanf(“%d”, &key);} return(T);}
2.BST树的查找
（1）查找思想
首先将给定的K值与二叉排序树的根结点的关键字进行比较：若相等： 则查找成功； ① 给定的K值小于BST的根结点的关键字：继续在该结点的左子树上进行查找； ②
给定的K值大于BST的根结点的关键字：继续在该结点的右子树上进行查找。（2）算法实现
递归算法
BSTNode *BST_Serach(BSTree T , KeyType key)
{
if(T==NULL)return(NULL);else
{ if(EQ(T->key, key))return(T);else if(LT(key, T->key))
return(BST_Serach(T->Lchild, key));
else
return(BST_Serach(T->Rchild, key));} } 非递归算法
BSTNode *BST_Serach(BSTree T , KeyType key){ BSTNode * p=T;while(p!=NULL&&!EQ(p->key, key)){ if(LT(key, p->key))p=p->Lchild;else p=p->Rchild;} if(EQ(p->key, key))return(p);else return(NULL);} 在随机情况下，二叉排序树的平均查找长度ASL和㏒(n)(树的深度)是等数量级的。3.BST树的删除
（1）
删除操作过程分析
从BST树上删除一个结点，仍然要保证删除后满足BST的性质。设被删除结点为p，其父结点为f，删除情况如下： ①
若p是叶子结点： 直接删除p
②
若p只有一棵子树(左子树或右子树)：直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。即原来p是f 的左子树，则p的子树成为f 的左子树；原来p是f 的右子树，则p的子树成为f的右子树
③ 若p既有左子树又有右子树 ：处理方法有以下两种，可以任选其中一种。◆
用p的直接前驱结点代替p。即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的左子树中的最右边的结点且没有右子树，对s的删除同②
◆ 用p的直接后继结点代替p。即从p的右子树中选择值最小的结点s放在p的位置(用结点s的内容替换结点p内容)，然后删除结点s。s是p的右子树中的最左边的结点且没有左子树，对s的删除同②（2）算法实现
void Delete_BST(BSTree T , KeyType key)
// 在以T为根结点的BST树中删除关键字为key的结点
{ BSTNode *p=T , *f=NULL , *q , *s;while(p!=NULL&&!EQ(p->key, key)){ f=p;//f 指向p的父结点
if(LT(key, p->key))p=p->Lchild;//搜索左子树
else p=p->Rchild;// 搜索右子树
} if(p==NULL)return;
// 没有要删除的结点 s=p;
// 找到了要删除的结点为p
if(p->Lchild!=NULL&& p->Rchild!=NULL)
{ f=p;s=p->Lchild;
// 从左子树开始找
while(s->Rchild!=NULL)
{
f=s;s=s->Rchild;
} // 左、右子树都不空，找左子树中最右边的结点
p->key=s->key;p->otherinfo=s->otherinfo;
// 用结点s的内容替换结点p内容
}
// 将第3种情况转换为第2种情况
if(s->Lchild!=NULL)
// 若s有左子树，右子树为空
q=s->Lchild;else q=s->Rchild;if(f==NULL)T=q;else if(f->Lchild==s)f->Lchild=q;
else f->Rchild=q;free(s);}
（四）哈希查找
1.基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。2.哈希函数 除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key
MOD p
(pm)3.冲突处理
★链地址法（拉链法）
方法：将所有关键字为同义词(散列地址相同)的记录存储在一个单链表中，并用一维数组存放链表的头指针。
设散列表长为m，定义一个一维指针数组： RecNode *linkhash[m]，其中RecNode是结点类型，每个分量的初值为空。凡散列地址为k的记录都插入到以linkhash[k]为头指针的链表中，插入位置可以在表头或表尾或按关键字排序插入。（1）链地址法查找
int Hash_Insert2(HTNode *T[ ], HTNode *s, int m)
{ HTNode *p=Hash_Search(T,s->key,m);
if(p!=NULL)
return 0;
//表中已有该结点
else {
d=h(s->key);
s->next=T[d];
T[d]=s;
return 1;
//插入成功
}
}
（2）链地址法插入
typedef struct node { KeyType key;struct node *next;}HTNode;
HTNode *hash_search2(HTNode *T[ ], KeyType k){ HTNode *p;
int i;p=T[h(k)];while(p!=NULL&&p->key!=k)
p=p->next;return p;} /*用链地址法解决冲突
*/
源程序清单：
#include #include typedef struct RecType{
int key;char info;}RecType;#define MAX_SIZE 100 typedef struct SSTable{
// 顺序表结构
RecType data[MAX_SIZE];
int length;}SSTable;
typedef struct Node{
//二叉树结构
int key;char info;struct Node *Lchild,*Rchild;}BSTNode;
typedef BSTNode * BSTree;
int Seq_Search(SSTable ST,int key){
//顺序查找
int p;
ST.data[0].key=key;for(p=ST.length;ST.data[p].key!=key;p--);return(p);}
void Bin_Search(SSTable ST,int key){ //折半查找
int low=1,high=ST.length,mid;int i,j,k;
} for(i=1;i
if(ST.data[j].key
k=j;} if(k!=i){
ST.data[0].key=ST.data[i].key;
ST.data[i].key=ST.data[k].key;
ST.data[k].key=ST.data[0].key;
ST.data[0].info=ST.data[i].info;
ST.data[i].info=ST.data[k].info;
ST.data[k].info=ST.data[0].info;} } while(lowhigh)printf(“Error!”);else printf(“%d,%cn”,ST.data[mid].key,ST.data[mid].info);BSTree Insert_BST(BSTree T,int key,char info){
//BST树的插入
BSTNode *s,*p,*f;s=(BSTNode *)malloc(sizeof(BSTNode));s->key=key;s->Lchild=s->Rchild=NULL;s->info=info;if(T==NULL)T=s;else{
p=T;
while(p!=NULL){
if(p->key==s->key)break;
f=p;
if(s->key
key)p=p->Lchild;
else p=p->Rchild;
}
if(s->keykey)f->Lchild=s;
else f->Rchild=s;} return T;}
void InorderTraverse(BSTree T){ if(T!=NULL){
InorderTraverse(T->Lchild);
printf(“%d,%ct”,T->key,T->info);
InorderTraverse(T->Rchild);} }
#define ENDKEY 65535 BSTree create_BST(SSTable ST){
//BST树的建立
BSTree T=NULL;int i,key,info;for(i=1;i
key=ST.data[i].key;
info=ST.data[i].info;
T=Insert_BST(T,key,info);} return T;} BSTNode *BST_Serach(BSTree T,int key){
if(T==NULL)return(NULL);else{
if(T->key==key)return(T);
else if(keykey)
return(BST_Serach(T->Lchild,key));
else
return(BST_Serach(T->Rchild,key));} }
BSTree Delete_BST(BSTree T, int key){
//BST树的删除
BSTNode *p=T,*f=NULL,*q,*s;while(p!=NULL&&(p->key!=key)){
f=p;
if(key
key)p=p->Lchild;
else p=p->Rchild;} if(p==NULL)return T;else s=p;if(p->Lchild!=NULL&&p->Rchild!=NULL){
f=p;s=p->Lchild;
while(s->Rchild!=NULL){
f=s;s=s->Rchild;
}
p->key=s->key;p->info=s->info;} if(s->Lchild!=NULL)q=s->Lchild;else q=s->Rchild;if(f==NULL)T=q;else if(f->Lchild==s)f->Lchild=q;else f->Rchild=q;free(s);return T;}
typedef struct node2{ int key;char info;struct node2 *next;}HTNode;HTNode *Hash_Search(HTNode *T[],int key,int m){
//链地址查找
HTNode *p;p=T[key%m];while(p!=NULL&&p->key!=key)p=p->next;return p;} HTNode *Hash_Insert(HTNode *T[],int key,char info,int m){
//链地址插入，建立哈希表
HTNode *s=(HTNode *)malloc(sizeof(HTNode));s->key=key;s->info=info;s->next=NULL;HTNode *p=Hash_Search(T,s->key,m);int d;if(p!=NULL)return *T;else{
d=s->key%m;
s->next=T[d];
T[d]=s;
} return *T;}
void main(){ int a,key,p,i,m;char info;SSTable ST;BSTree T=NULL;BSTNode *s;HTNode *HT[20];HTNode *ht;printf(“1.输入数据n2.顺序查找n3.折半查找n4.BST树的查找n5.BST树的插入n6.BST树的删除n7.链地址法查找n8.链地址法插入n0.退出n”);while(1){
printf(“n请选择：”);scanf(“%d”,&a);getchar();switch(a){ case 1: printf(“请输入记录数量n：”);scanf(“%d”,&ST.length);
printf(“请输入除数：”);scanf(“%d”,&m);
for(i=0;i
printf(“请输入关键字码与数据：”);scanf(“%d,%c”,&ST.data[i].key,&ST.data[i].info);*HT=Hash_Insert(HT,ST.data[i].key,ST.data[i].info,m);}
T=create_BST(ST);printf(“已建立！”);break;case 2:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);p=Seq_Search(ST,key);printf(“%d,%cn”,ST.data[p].key,ST.data[p].info);break;case 3:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);Bin_Search(ST,key);break;case 4:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);s=BST_Serach(T,key);printf(“%d,%cn”,s->key,s->info);break;case 5:printf(“请输入要添加的关键字码及数据：”);scanf(“%d,%c”,&key,&info);T=Insert_BST(T,key,info);printf(“添加后的结果：”);InorderTraverse(T);printf(“n”);
}
} break;case 6:printf(“请输入要删除的关键字码：”);scanf(“%d”,&key);T=Delete_BST(T,key);
printf(“删除后的结果：”);InorderTraverse(T);printf(“n”);break;case 7:printf(“请输入要查找的关键字码：”);scanf(“%d”,&key);ht=Hash_Search(HT,key,m);printf(“%d,%cn”,ht->key,ht->info);break;case 8:printf(“请输入要添加的关键字码及数据：”);scanf(“%d,%c”,&key,&info);*HT=Hash_Insert(HT,key,info,m);for(i=0;i
ht=HT[i];
while(ht!=NULL){
printf(“%d,%ct”,ht->key,ht->info);
ht=ht->next;
} } break;case 0: exit(0);} 运行结果：
