查找 实验报告

实验目的： 掌握几种查找的思想及算法 问题分析：

（一）顺序查找 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<=high){ 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 (pm) 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;iwhile(low<=high){ mid=(low+high)/2; if(ST.data[mid].key==key) break; else if(ST.data[mid].keyif(low>high) printf(\"Error!\");

else printf(\"%d,%c\\n\

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->keykey) 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,%c\\ InorderTraverse(T->Rchild) ; } }

#define ENDKEY 65535

BSTree create_BST(SSTable ST){ //BST树的建立 BSTree T=NULL; int i,key,info; for(i=1;i<=ST.length;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(keykey) 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\switch(a) {

case 1: printf(\"请输入记录数量n：\"); scanf(\"%d\ printf(\"请输入除数：\"); scanf(\"%d\ for(i=0;i<20;i++) HT[i]=NULL; for(i=1;i<=ST.length;i++) {

printf(\"请输入关键字码与数据：\"); scanf(\"%d,%c\ *HT=Hash_Insert(HT,ST.data[i].key,ST.data[i].info,m); }

T=create_BST(ST); printf(\"已建立！\"); break;

case 2:printf(\"请输入要查找的关键字码：\"); scanf(\"%d\ p=Seq_Search(ST,key); printf(\"%d,%c\\n\ break;

case 3:printf(\"请输入要查找的关键字码：\"); scanf(\"%d\ Bin_Search(ST,key); break;

case 4:printf(\"请输入要查找的关键字码：\"); scanf(\"%d\ s=BST_Serach(T,key); printf(\"%d,%c\\n\ break;

case 5:printf(\"请输入要添加的关键字码及数据：\"); scanf(\"%d,%c\ T=Insert_BST(T,key,info); printf(\"添加后的结果：\"); InorderTraverse(T); printf(\"\\n\");

}

}

break;

case 6:printf(\"请输入要删除的关键字码：\"); scanf(\"%d\ T=Delete_BST(T,key);

printf(\"删除后的结果：\"); InorderTraverse(T); printf(\"\\n\"); break;

case 7:printf(\"请输入要查找的关键字码：\"); scanf(\"%d\ ht=Hash_Search(HT,key,m); printf(\"%d,%c\\n\ break; case 8:printf(\"请输入要添加的关键字码及数据：\"); scanf(\"%d,%c\ *HT=Hash_Insert(HT,key,info,m); for(i=0;inext; } } break; case 0: exit(0); }

运行结果：