一个不知名大学生，江湖人称菜狗
original author: Jacky Li
Email : 3435673055@qq.comTime of completion：2024.03.24
Last edited: 2024.03.24
目录
算法练习-常用查找算法复现
第1关：顺序查找（算法7.1和7.2）
任务描述
相关知识
数据元素类型定义
顺序表的定义
算法7.1 顺序查找
算法描述
算法7.2 设置监视哨的顺序查找
算法描述
算法分析
编程要求
测试说明
代码如下：
第2关：折半查找（算法7.3）
任务描述
相关知识
算法7.3 折半查找
【算法步骤】
【算法描述】
编程要求
测试说明
代码如下：
第3关：二叉排序树和查找（算法7.4-7.7）
任务描述
相关知识
编程要求
测试说明
代码如下：
B- 树的查找和插入（算法7.8和7.9）
任务描述
相关知识
B-树的查找
算法7.8 B-树的查找
B-树的插入
算法7.9 B-树的插入
编程要求
测试说明
第5关：散列表查找（算法7.10）
任务描述
相关知识
算法步骤
算法7.10 散列表的查找
算法描述
算法分析
编程要求
测试说明
作者有言
算法练习-常用查找算法复现
第1关：顺序查找（算法7.1和7.2）
任务描述
本关任务：用顺序查找法找出关键字在列表中的位置，下标由1开始计数。
相关知识
顺序查找（Sequential Search）的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。
数据元素类型定义
typedef struct{KeyType key; //关键字域InfoType otherinfo; //其他域}ElemType;
顺序表的定义
typedef struct{ElemType *R; //存储空间基地址int length; //当前长度}SSTable;
算法7.1 顺序查找
算法描述
示例如下：
int Search_Seq(SSTable ST,KeyType key){//在顺序表ST中顺序查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0for(i=ST.length;i>=1;--i)if(ST.R[i].key==key) return i; //从后往前找return 0;}
算法7.1在查找过程中每步都要检测整个表是否查找完毕，即每步都要有循环变量是否满足条件i>=1的检测。改进这个程序，可以免去这个检测过程。改进方法是查找之前先对ST.R[0]的关键字赋值key，在此，ST.R[0]起到了监视哨的作用，如算法7.2所示。
算法7.2 设置监视哨的顺序查找
算法描述
int Search_Seq(SSTable ST,KeyType key){//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0ST.R[0].key=key;//“哨兵”for(i=ST.length;ST.R[i].key!=key;--i);//从后往前找return i;}
算法分析
算法7.2仅是一个程序设计技巧上的改进，即通过设置监视哨，免去查找过程中每一步都要检测整个表是否查找完毕。然而实践证明，这个改进能使顺序查找在ST.length≥1000时，进行一次查找所需的平均时间几乎减少一半。当然，监视哨也可设在高下标处。算法7.2和算法7.1的时间复杂度一样，在第2章已经做过分析，即 ASL=n1∑i=1ni=2n+1 算法7.2的时间复杂度为O(n)。
编程要求
根据提示，在右侧编辑器Begin和End间补充代码，完成顺序查找之任务。
测试说明
平台会对你编写的代码进行测试：
测试输入（共两行，第一行为待查找的关键字，第二行为以空格分隔的顺序表各元素： 4 0 1 2 3 4 5 预期输出： 找到4位置为5
测试输入： 7 0 1 2 3 4 5 预期输出： 未找到7
开始你的任务吧，祝你成功！
代码如下：
//算法7.1 顺序查找
#include<iostream>
#include<stdio.h>
#include <fstream>
using namespace std;
#define MAXSIZE 10000
#define OK 1;
typedef struct{
int key;//关键字域
}ElemType;
typedef struct{
ElemType *R;
int length;
}SSTable;
int InitList_SSTable(SSTable &L)
{
L.R=new ElemType[MAXSIZE];
if (!L.R)
{
cout<<"初始化错误";
return 0;
}
L.length=0;
return OK;
}
int Insert_SSTable(SSTable &L) //将所有关键字输入顺序表备查
{
/***********************Begin**********************/
int n;
while(scanf("%d", &n) != EOF)
{
L.R[++ L.length].key = n;
}
/*********************** End **********************/
}
int Search_Seq(SSTable ST, int key){
//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为
//该元素在表中的位置，否则为0
/***********************Begin**********************/
for(int i = 1; i <= ST.length; i ++)
{
if(ST.R[i].key == key) return i;
}
return 0;
/*********************** End **********************/
}// Search_Seq
void Show_End(int result,int testkey)
{
if(result==0)
cout<<"未找到"<<testkey<<endl;
else
cout<<"找到"<<testkey<<"位置为"<<result<<endl;
return;
}
int main()
{
int testkey1;
scanf("%d",&testkey1);
SSTable ST;
InitList_SSTable(ST);
Insert_SSTable(ST);
int result;
result=Search_Seq(ST, testkey1);
Show_End(result,testkey1);
}
第2关：折半查找（算法7.3）
任务描述
本关任务：用折半查找算法查找关键字在有序列表中的位置，下标从1开始计数。
相关知识
折半查找（Binary Search）也称二分查找，它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。在下面及后续的讨论中，均假设有序表是递增有序的。 折半查找的查找过程为：从表的中间记录开始，如果给定值和中间记录的关键字相等，则查找成功；如果给定值大于或者小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败。 折半查找每一次查找比较都使查找范围缩小一半，与顺序查找相比，很显然会提高查找效率。为了标记查找过程中每一次的查找区间，下面分别用low和high来表示当前查找区间的下界和上界，mid为区间的中间位置。
算法7.3 折半查找
【算法步骤】
① 置查找区间初值，low为1，high为表长。 ② 当low小于等于high时，循环执行以下操作： ·mid取值为low和high的中间值； ·将给定值key与中间位置记录的关键字进行比较，若相等则查找成功，返回中间位置mid； ·若不相等则利用中间位置记录将表对分成前、后两个子表。如果key比中间位置记录的关键字小，则high取为mid-1，否则low取为mid+1。 ③ 循环结束，说明查找区间为空，则查找失败，返回0。 。
【算法描述】
int Search_Bin(SSTable ST,KeyType key){//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0low=1;high=ST.length; //置查找区间初值while(low<=high){mid=(low+high)/2;if(key==ST.R[mid].key) return mid; //找到待查元素else if(key<ST.R[mid].key) high=mid-1; //继续在前一子表进行查找else low=mid+1; //继续在后一子表进行查找} //whilereturn 0; //表中不存在待查元素}
本算法很容易理解，唯一需要注意的是，循环执行的条件是low<=high，而不是low<high，因为low=high时，查找区间还有最后一个结点，还要进一步比较。 折半查找算法7.3的平均查找长度为 ASL=nn+1log2(n+1)−1 当n较大时，时间复杂度有近似结果O(log2n)。
编程要求
根据提示，在右侧编辑器Begin和End间补充代码，完成折半查找之任务。
测试说明
平台会对你编写的代码进行测试：
测试输入（共两行，第一行为待查找的关键字，第二行为以空格分隔的顺序表各元素： 4 0 1 2 3 4 5 预期输出： 找到4位置为5
测试输入： 7 0 1 2 3 4 5 预期输出： 未找到7
开始你的任务吧，祝你成功！
代码如下：
//算法7.3 折半查找
#include<iostream>
#include<stdio.h>
#include<fstream>
using namespace std;
#define MAXSIZE 2000
#define OK 1;
typedef struct{
int key;//关键字域
}ElemType;
typedef struct{
ElemType *R;
int length;
}SSTable;
int InitList_SSTable(SSTable &L)
{
L.R=new ElemType[MAXSIZE];
if (!L.R)
{
cout<<"初始化错误";
return 0;
}
L.length=0;
return OK;
}
int Insert_SSTable(SSTable &L) //将所有关键字输入顺序表备查
{
/***********************Begin**********************/
int n;
while(scanf("%d", &n) != EOF)
L.R[++ L.length].key = n;
/*********************** End **********************/
}
int Search_Bin(SSTable ST,int key) {
// 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为
// 该元素在表中的位置，否则为0
/***********************Begin**********************/
int low = 1, high = ST.length;
while(low <= high)
{
int mid = (low + high) / 2;
if(ST.R[mid].key == key) return mid;
else if(key > ST.R[mid].key) low = mid + 1;
else high = mid - 1;
}
return 0;
/*********************** End **********************/
}// Search_Bin
void Show_End(int result,int testkey)
{
if(result==0)
cout<<"未找到"<<testkey<<endl;
else
cout<<"找到"<<testkey<<"位置为"<<result<<endl;
return;
}
int main()
{
int testkey1;
scanf("%d",&testkey1);
SSTable ST;
InitList_SSTable(ST);
Insert_SSTable(ST);
int result;
result=Search_Bin(ST, testkey1);
Show_End(result,testkey1);
}第3关：二叉排序树和查找（算法7.4-7.7）
任务描述
本关任务：实现二叉排序树的创建、插入、查找、删除操作。
相关知识
二叉排序树（Binary Sort Tree）又称二叉查找树，它是一种对排序和查找都很有用的特殊二叉树。 1．二叉排序树的定义二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）它的左、右子树也分别为二叉排序树。 二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。
编程要求
根据提示，在右侧编辑器Begin和End间补充代码，完成折半查找之任务。
测试说明
平台会对你编写的代码进行测试，以下为两个测试用例的例子。
测试输入（共3行：第1行，为构造二叉排序树的字符序列，行末为结束符号#；第2行为单个字符，是需要在二叉排序树中查找的字符；第3行为单个字符，是需要从二叉排序树中删除的字符): ZYXWMSL# S S 预期输出(共3行)： 当前有序二叉树中序遍历结果为LMSWXYZ 找到字符S 当前有序二叉树中序遍历结果为LMWXYZ
测试输入：
AYBXWMSL# Q X
预期输出：
当前有序二叉树中序遍历结果为ABLMSWXY 未找到Q 当前有序二叉树中序遍历结果为ABLMSWY
开始你的任务吧，祝你成功！
代码如下：
//算法7.4 二叉排序树的递归查找
//算法7.5 二叉排序树的插入
//算法7.6 二叉排序树的创建
//算法 7.7 二叉排序树的删除
#include<iostream>
using namespace std;
#define ENDFLAG '#'
typedef struct ElemType{
char key;
}ElemType;
typedef struct BSTNode{
ElemType data; //结点数据域
BSTNode *lchild,*rchild; //左右孩子指针
}BSTNode,*BSTree;
//算法7.4 二叉排序树的递归查找
BSTree SearchBST(BSTree T,char key) {
//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
//若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
/***********************Begin**********************/
if(!T || key == T->data.key) return T;
else if(key < T->data.key) return SearchBST(T->lchild, key);
else return SearchBST(T->rchild, key);
/*********************** End **********************/
} // SearchBST
//算法7.5 二叉排序树的插入
void InsertBST(BSTree &T,ElemType e ) {
//当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
/***********************Begin**********************/
if(!T)
{
BSTree S = new BSTNode;
S->data = e;
S->lchild = S->rchild = NULL;
T = S;
}
else if(e.key < T->data.key) InsertBST(T->lchild, e);
else if(e.key > T->data.key) InsertBST(T->rchild, e);
/*********************** End **********************/
}// InsertBST
//算法7.6 二叉排序树的创建
void CreateBST(BSTree &T ) {
//依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
/***********************Begin**********************/
T = NULL;
ElemType e;
cin >> e.key;
while(e.key != ENDFLAG)
{
InsertBST(T, e);
cin >> e.key;
}
/*********************** End **********************/
}//CreatBST
void DeleteBST(BSTree &T,char key) {
//从二叉排序树T中删除关键字等于key的结点
/***********************Begin**********************/
BSTree p = T, f = NULL, q, s;
while(p)
{
if(p -> data.key == key) break; //找到关键字等于key的结点*p，结束循环
f = p; //*f为*p的双亲结点
if(p -> data.key > key) p = p -> lchild; //在*p的左子树中继续查找
else p = p -> rchild; //在*p的右子树中继续查找
}
if(!p) return; //找不到被删结点则返回
/*―考虑三种情况实现p所指子树内部的处理：*p左右子树均不空、无右子树、无左子树―*/
if((p -> lchild) && (p -> rchild))
{ //被删结点*p左右子树均不空
q = p, s = p->lchild;
while(s -> rchild) //在*p的左子树中继续查找其前驱结点，即最右下结点
q = s, s = s -> rchild; //向右到尽头
p -> data = s -> data; //s指向被删结点的“前驱”
if(q != p)
q -> rchild = s->lchild; //重接*q的右子树
else q -> lchild = s -> lchild; //重接*q的左子树
delete s;
}//if
else
{
if(!p->rchild) //被删结点*p无右子树，只需重接其左子树
q = p, p = p -> lchild;
else if(! p -> lchild) //被删结点*p无左子树，只需重接其右子树
q = p, p = p -> rchild;
/*――――――――――将p所指的子树挂接到其双亲结点*f相应的位置――――――――*/
if(!f) T = p; //被删结点为根结点
else if (q == f -> lchild) f -> lchild = p; //挂接到*f的左子树位置
else f -> rchild = p; //挂接到*f的右子树位置
delete q;
}
/*********************** End **********************/
}//DeleteBST
//算法 7.7 二叉排序树的删除
//中序遍历
void InOrderTraverse(BSTree &T)
{
/***********************Begin**********************/
if(T)
{
InOrderTraverse(T->lchild);
cout << T->data.key;
InOrderTraverse(T->rchild);
}
/*********************** End **********************/
}
int main()
{
BSTree T;
CreateBST(T);
cout<<"当前有序二叉树中序遍历结果为";
InOrderTraverse(T);
cout<<endl;
char key;//待查找或待删除内容
cin>>key;
BSTree result=SearchBST(T,key);
if(result)
{cout<<"找到字符"<<key<<endl;}
else
{cout<<"未找到"<<key<<endl;}
cin>>key;
DeleteBST(T,key);
cout<<"当前有序二叉树中序遍历结果为";
InOrderTraverse(T);
}
B- 树的查找和插入（算法7.8和7.9）
任务描述
本关任务：根据给定数据完成B-树的构建、查找和插入。
相关知识
前面介绍的查找方法均适用于存储在计算机内存中较小的文件，统称为内查找法。若文件很大且存放于外存进行查找时，这些查找方法就不适用了。内查找法都以结点为单位进行查找，这样需要反复地进行内、外存的交换，是很费时的。1970年，R.Bayer和E.Mccreight提出了一种适用于外查找的平衡多叉树——B-树，磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B-树这种数据结构。
B-树的查找
在B-树上进行查找的过程和二叉排序树的查找类似。例如，在下图所示的B-树上
查找关键字47的过程如下：首先从根开始，根据根结点指针t找到*a结点，因*a结点中只有一个关键字，且47>35，若查找的记录存在，则必在指针P1所指的子树内，顺指针找到*c结点，该结点有两个关键字（43和78），而43<47<78，若查找的记录存在，则必在指针P1所指的子树中。同样，顺指针找到*g结点，在该结点中顺序查找，找到关键字47，由此，查找成功。 查找不成功的过程也类似，例如，在同一棵树中查找23。从根开始，因为23<35，则顺该结点中指针P0找到*b结点，又因为*b 结点中只有一个关键字18，且23>18，所以顺结点中第二个指针P1找到*e结点。同理，因为23<27，则顺指针往下找，此时因指针所指为叶子结点，说明此棵B-树中不存在关键字23，查找因失败而告终。 由此可见，在B-树上进行查找的过程是一个顺指针查找结点，和在结点的关键字中查找交叉进行的过程。 由于B-树主要用做文件的索引，因此它的查找涉及外存的存取，在此略去外存的读写，只做示意性的描述。假设结点类型定义如下：
#define m 3 // B-树的阶，暂设为3typedef struct BTNode{int keynum;//结点中关键字的个数，即结点的大小struct BTNode *parent; //指向双亲结点KeyType K[m+1];//关键字向量，0号单元未用struct BTNode *ptr[m+1];//子树指针向量Record *recptr[m+1]; //记录指针向量，0号单元未用}BTNode,*BTree; //B-树结点和B-树的类型typedef struct{BTNode *pt; //指向找到的结点int i; //1..m，在结点中的关键字序号int tag; //1：查找成功，0：查找失败}Result; //B-树的查找结果类型
算法7.8 B-树的查找
【算法步骤】 将给定值key与根结点的各个关键字K1, K2, …, Kj（1≤j≤m−1）进行比较，由于该关键字序列是有序的，所以查找时可采用顺序查找，也可采用折半查找。查找时： ① 若key=Ki（1≤i≤j），则查找成功； ② 若key<K1，则顺着指针P0所指向的子树继续向下查找； ③ 若Ki<key<Ki+1（1≤i≤j−1），则顺着指针Pi所指向的子树继续向下查找； ④ 若key>Kj，则顺着指针Pj所指向的子树继续向下查找。 如果在自上而下的查找过程中，找到了值为key的关键字，则查找成功；如果直到叶子结点也未找到，则查找失败。
B-树的插入
B-树是动态查找树，因此其生成过程是从空树起，在查找的过程中通过逐个插入关键字而得到。但由于B-树中除根之外的所有非终端结点中的关键字个数必须大于等于⌈m/2⌉，因此，每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m−1，则插入完成，否则表明结点已满，要产生结点的“分裂”，将此结点在同一层分成两个结点。一般情况下，结点分裂方法是：以中间关键字为界把结点一分为二，成为两个结点，并把中间关键字向上插入到双亲结点上，若双亲结点已满，则采用同样的方法继续分解。最坏的情况下，一直分解到树根结点，这时B-树高度增加1。
算法7.9 B-树的插入
【算法步骤】 ① 在B-树中查找给定关键字的记录，若查找成功，则插入操作失败；否则将新记录作为空指针ap插入到查找失败的叶子结点的上一层结点（由q指向）中。 ② 若插入新记录和空指针后，q指向的结点的关键字个数未超过m−1，则插入操作成功，否则转入步骤③。 ③ 以该结点的第⌈m/2⌉个关键字K⌈m/2⌉为拆分点，将该结点分成3个部分：K⌈m/2⌉左边部分、K⌈m/2⌉、K⌈m/2⌉右边部分。K⌈m/2⌉左边部分仍然保留在原结点中；K⌈m/2⌉右边部分存放在一个新创建的结点（由ap指向）中；关键字值为K⌈m/2⌉的记录和指针ap插入到q的双亲结点中。因q的双亲结点增加一个新的记录，所以必须对q的双亲结点重复②和③的操作，依次类推，直至由q指向的结点是根结点，转入步骤④。 ④ 由于根结点无双亲，则由其分裂产生的两个结点的指针ap和q，以及关键字为[插图]的记录构成一个新的根结点。此时，B-的高度增加1。
编程要求
根据提示，在右侧编辑器补全B-树的插入函数InsertBTree和查找函数SearchBTree的代码，完成对主函数给定数组的B-树构建。
测试说明
平台会对你编写的代码进行测试：
测试输入：无； 预期输出： OK
开始你的任务吧，祝你成功！
//算法7.8 B-树的查找
//算法7.9 B-树的插入
#include<iostream>
using namespace std;
#define FALSE 0
#define TRUE 1
#define OK 1
#define m 3 //B-树的阶，暂设为3
typedef struct BTNode{
int keynum; //结点中关键字的个数，即结点的大小
BTNode *parent; //指向双亲结点
int key[m+1]; //关键字矢量，0号单元未用
BTNode *ptr[m+1]; //子树指针矢量
}BTNode,*BTree;
//- - - - - B-树的查找结果类型定义- - - - -
struct Result{
BTNode *pt; //指向找到的结点
int i; //1..m，在结点中的关键字序号
int tag; //1：查找成功，0：查找失败
};
int Search(BTree T,int key)
{
BTree p=T;
int endnum;
if(p) //树不为空时
{
endnum=p->keynum; //获得首节点包含的记录个数
}
else
{
return 0; //返回没找到
}
int i=0;
if(endnum==0)
{
return i; //树存在，但仅有一个为空根节点
}
else if(key>=p->key[endnum])//节点不为空，但当前值比最大的key还大
{
i=endnum;
return i;
}
else if(key<=p->key[1]) //节点不为空，但当前值比最小的key还小
{
return i;}
else
{
for(i=1;i<endnum;i++) //有合适的位置，即处于当前结点的最大和最小值之间，或找到了
{
if(p->key[i]<=key && key<p->key[i+1])
return i;
}
}
}
void Insert(BTree &q,int i,int x,BTree &ap)
{//将x插入q结点的i+1位置中
int j;
for(j=m-1;j>i;j--)
{
//将插入位置之后的key全部后移一位
q->key[j+1]=q->key[j];
}
for(j=m;j>i;j--)
{
//相应地也移动其后ptr的位置
q->ptr[j]=q->ptr[j-1];
}
q->key[i+1]=x;//插入x到该位置
q->ptr[i+1]=ap;
q->keynum++;
}
void split(BTree &q,int s,BTree &ap)
{ //将q->key[s+1,..,m], q->ptr[s+1,..,m]移入新结点*ap作为右结点
//原结点作为新的左侧结点
//中间值被保存在ap[0]->key中，等待找到跳转回InsertBTree（）寻找到到合适的插入位置插入
int i;
ap=new BTNode;
for(i=s+1;i<=m;i++)
{ //将q->key[s+1,..,m]保存到ap->key[0,..,m-s+1]中
//将q->ptr[s+1,..,m]保存到ap->ptr[0,..,m-s+1]中
ap->key[i-s-1]=q->key[i];
ap->ptr[i-s-1]=q->ptr[i];
}
if(ap->ptr[0])
{
//当ap有子树的时候
for(i=0;i<=1;i++)
{
//将ap的子树的父亲改为ap自己
ap->ptr[i]->parent=ap;
}
}
ap->keynum=(m-s)-1;
ap->parent=q->parent;//将ap的父亲改为q的父亲
q->keynum=q->keynum-(m-s);//修改q的记录个数
}
void NewRoot(BTree &T,BTree q,int x,BTree &ap)//生成含信息（T, x, ap）的新的根结点*T，原T和ap为子树指针
{
BTree newT=new BTNode;//新建一个结点作为新的根
newT->key[1]=x;//写入新根的key[1]
newT->ptr[0]=T;//将原来的树根作为新根的左子树
newT->ptr[1]=ap;//ap作为新根的右子树
newT->keynum=1;
newT->parent=NULL;//新根的父亲为空
ap->parent=newT;//ap的父亲为新根
T->parent=newT;//T的父亲为新根
T=newT;//树改成新根引导的
}
//算法7.9 B-树的插入
int InsertBTree(BTree &T,int K,BTree q,int i){
/***********************Begin**********************/
/*********************** End **********************/
} //InsertBTree
//算法7.8 B-树的查找
Result SearchBTree(BTree &T, int key){
/***********************Begin**********************/
/*********************** End **********************/
}//SearchBTree
void InitialBTree(BTree &T)
{
//初始化一个空的根
T->keynum=0;
T->parent=NULL;
for(int i=0;i<m+1;i++)
{
T->ptr[i]=NULL;
}
}
int main()
{
BTree T=new BTNode;
InitialBTree(T);
//先用SearchBTree()找到要插入的位置，得到一个Result结构体
//再用InsertBTree()插入数据
Result result;
int a[11]={45,24,53,90,3,12,50,61,70,100};
for(int i=0;i<10;i++)
{
result=SearchBTree(T,a[i]);
if(result.tag==0)
{
InsertBTree(T,a[i],result.pt,result.i);
}
}
cout<<"OK";
}第5关：散列表查找（算法7.10）
任务描述
本关任务：用散列表查找法找出关键字在列表中的位置，下标由1开始计数。
相关知识
前面讨论的基于线性表、树表结构的查找方法，这些查找方法都是以关键字的比较为基础的。在查找过程中只考虑各元素关键字之间的相对大小，记录在存储结构中的位置和其关键字无直接关系，其查找时间与表的长度有关，特别是当结点个数很多时，查找时要大量地与无效结点的关键字进行比较，致使查找速度很慢。如果能在元素的存储位置和其关键字之间建立某种直接关系，那么在进行查找时，就无需做比较或做很少次的比较，按照这种关系直接由关键字找到相应的记录。这就是散列查找法（Hash Search）的思想，它通过对元素的关键字值进行某种运算，直接求出元素的地址，即使用关键字到地址的直接转换方法，而不需要反复比较。因此，散列查找法又叫杂凑法或散列法。 常用的几个术语：
（1）散列函数和散列地址：在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H(key)，称这个对应关系H为散列函数，p为散列地址。
（2）散列表：一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录。通常散列表的存储空间是一个一维数组，散列地址是数组的下标。
（3）冲突和同义词：对不同的关键字可能得到同一散列地址，即key1≠key2，而H(key1)=H(key2)，这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词，key1与key2互称为同义词。 构造散列函数的常用方法包括数字分析法、平方取中法、折叠法及除留余数法。 处理冲突的手段主要有开放地址法和链地址法两类。 下面以开放地址法为例，给出散列表的存储表示。
//- - - - -开放地址法散列表的存储表示- - - - -#define m 20 //散列表的表长typedef struct{KeyType key; //关键字项InfoType otherinfo; //其他数据项}HashTable[m];
算法步骤
在散列表上进行查找的过程和创建散列表的过程基本一致。算法7.10描述了开放地址法（线性探测法）处理冲突的散列表的查找过程。
算法7.10 散列表的查找
① 给定待查找的关键字key，根据造表时设定的散列函数计算H0=H(key)。 ② 若单元H0为空，则所查元素不存在。 ③ 若单元H0中元素的关键字为key，则查找成功。 ④ 否则重复下述解决冲突的过程： ·按处理冲突的方法，计算下一个散列地址Hi； ·若单元Hi为空，则所查元素不存在； ·若单元Hi中元素的关键字为key，则查找成功。
算法描述
示例如下：
#define NULLKEY 0 //单元为空的标记int SearchHash(HashTable HT,KeyType key){//在散列表HT中查找关键字为key的元素，若查找成功，返回散列表的单元标号，否则返回-1H0=H(key);//根据散列函数H（key）计算散列地址if(HT[H0].key==NULLKEY) return -1; //若单元H0为空，则所查元素不存在else if(HT[H0].key==key) return H0; //若单元H0中元素的关键字为key，则查找成功else{for(i=1;i<m;++i){Hi=(H0+i)%m; //按照线性探测法计算下一个散列地址Hiif(HT[Hi].key==NULLKEY) return -1; //若单元Hi为空，则所查元素不存在else if(HT[Hi].key==key) return Hi; //若单元Hi中元素的关键字为key，则查找成功} //forreturn -1;} //else}
算法分析
从散列表的查找过程可见： （1）虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需以平均查找长度作为衡量散列表查找效率的量度。 （2）查找过程中需和给定值进行比较的关键字的个数取决于三个因素：散列函数、处理冲突的方法和散列表的装填因子。散列表的装填因子α定义为即 α=散列表的长度表中填入的记录数 α标志散列表的装满程度。直观地看，α越小，发生冲突的可能性就越小；反之，α越大，表中已填入的记录越多，再填记录时，发生冲突的可能性就越大，则查找时，给定值需与之进行比较的关键字的个数也就越多。 （3）散列函数的“好坏”首先影响出现冲突的频繁程度。但一般情况下认为：凡是“均匀的”散列函数，对同一组随机的关键字，产生冲突的可能性相同，假如所设定的散列函数是“均匀”的，则影响平均查找长度的因素只有两个——处理冲突的方法和装填因子α。 4）从表7.3可以看出，散列表的平均查找长度是α的函数，而不是记录个数n的函数。由此，在设计散列表时，不管n多大，总可以选择合适的α以便将平均查找长度限定在一个范围内。
编程要求
根据提示，在右侧编辑器Begin和End间补充代码，完成散列表查找之任务。
测试说明
平台会对你编写的代码进行测试：
测试输入（共两行，第一行为待查找的关键字，第二行为以空格分隔的散列表中各元素： 55 -1 14 1 68 27 55 19 20 84 79 23 11 10 -1 -1 -1
预期输出： 在第5位置找到
测试输入： 47 -1 14 1 68 27 55 19 20 84 79 23 11 10 -1 -1 -1
预期输出： 未找到
开始你的任务吧，祝你成功！
#include<iostream>
#include<stdio.h>
using namespace std;
//算法7.10 哈希表的查找
//- - - - -开放地址法哈希表的存储表示- - - - -
#define m 16 //哈希表的表长
#define NULLKEY 0 //单元为空的标记
struct HashTable{
int key; //关键字项
// InfoType otherinfo; //其他数据项
};
// 算法7.10为哈希表查找的算法，采用线性探测法处理冲突。
// 【算法实现】
int H(int key)
{
int result;
result=key%13;
return result;
}
int SearchHash(HashTable HT[],int key){
//在哈希表HT中查找关键字为key的元素，若查找成功，返回哈希表的单元标号，否则返回-1
/***********************Begin**********************/
for(int i = 1; i <= m; i ++)
{
if(HT[i].key == key) return i;
}
return -1;
/*********************** End **********************/
}//SearchHash
int main()
{
int result,i=0;
int a[m];
char end=' ';
int lookfor; //lookfor为待查找的元素
scanf("%d",&lookfor);
for(;i<m;i++)
{
scanf("%d",&a[i]);
}
HashTable HT[m];
for(i=0;i<16;i++)
{
HT[i].key=a[i];
}
result=SearchHash(HT,lookfor);
if(result!=-1)
{
cout<<"在第"<<result<<"位置找到"<<endl;
}
else
{
cout<<"未找到"<<endl;
}
}作者有言
如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……
