算法练习-常用查找算法复现_本关任务:实现折半查找。相关知识为了完成本关任务,你需要掌握:1.静态查找表

一个不知名大学生，江湖人称菜狗
original author: jacky Li
Email : 3435673055@qq.com

Time of completion：2023.1.1
Last edited: 2023.1.1

 

目录

算法练习-常用查找算法复现（PS：1 -- 3自己写的，4、5懒得写了，直接拿的同学的）

第1关：顺序查找（算法7.1和7.2）

任务描述

相关知识

编程要求

测试说明

参考代码

第2关：折半查找（算法7.3）

任务描述

相关知识

编程要求

测试说明

参考代码

第3关：二叉排序树和查找（算法7.4-7.7）

任务描述

相关知识

编程要求

测试说明

参考代码

 第4关：B- 树的查找和插入（算法7.8和7.9）

任务描述

相关知识

编程要求

测试说明

 参考代码

第5关：散列表查找（算法7.10）

任务描述

相关知识

编程要求

测试说明

参考代码

作者有言

---

算法练习-常用查找算法复现（PS：1 -- 3自己写的，4、5懒得写了，直接拿的同学的）

第1关：顺序查找（算法7.1和7.2）

任务描述

本关任务：用顺序查找法找出关键字在列表中的位置，下标由1开始计数。

相关知识

顺序查找（Sequential Search）的查找过程为：从表的一端开始，依次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败。

数据元素类型定义

1. typedef struct{
2. KeyType key; //关键字域
3. InfoType otherinfo; //其他域
4. }ElemType;

顺序表的定义

1. typedef struct{
2. ElemType *R; //存储空间基地址
3. int length; //当前长度
4. }SSTable;

算法7.1 顺序查找

算法描述

示例如下：

1. int Search_Seq(SSTable ST,KeyType key)
2. {//在顺序表ST中顺序查找其关键字等于key的数据元素。
3. //若找到，则函数值为该元素在表中的位置，否则为0
4. for(i=ST.length;i>=1;--i)
5. if(ST.R[i].key==key) return i; //从后往前找
6. return 0;
7. }

算法7.1在查找过程中每步都要检测整个表是否查找完毕，即每步都要有循环变量是否满足条件i>=1的检测。改进这个程序，可以免去这个检测过程。改进方法是查找之前先对ST.R[0]的关键字赋值key，在此，ST.R[0]起到了监视哨的作用，如算法7.2所示。

算法7.2 设置监视哨的顺序查找

算法描述

1. int Search_Seq(SSTable ST,KeyType key)
2. {//在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
3. ST.R[0].key=key;//“哨兵”
4. for(i=ST.length;ST.R[i].key!=key;--i);//从后往前找
5. return i;
6. }

算法分析

算法7.2仅是一个程序设计技巧上的改进，即通过设置监视哨，免去查找过程中每一步都要检测整个表是否查找完毕。然而实践证明，这个改进能使顺序查找在ST.length≥1000时，进行一次查找所需的平均时间几乎减少一半。当然，监视哨也可设在高下标处。算法7.2和算法7.1的时间复杂度一样，在第2章已经做过分析，即 ASL=n1​∑i=1n​i=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

参考代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
 
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }
 
const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;
 
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
 
#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.length ++, L.R[L.length].key = n;
	return OK;
	/*********************** 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。 。

【算法描述】

1. int Search_Bin(SSTable ST,KeyType key)
2. {//在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为该元素在表中的位置，否则为0
3. low=1;high=ST.length; //置查找区间初值
4. while(low<=high)
5. {
6. mid=(low+high)/2;
7. if(key==ST.R[mid].key) return mid; //找到待查元素
8. else if(key<ST.R[mid].key) high=mid-1; //继续在前一子表进行查找
9. else low=mid+1; //继续在后一子表进行查找
10. } //while
11. return 0; //表中不存在待查元素
12. }

本算法很容易理解，唯一需要注意的是，循环执行的条件是low<=high，而不是low<high，因为low=high时，查找区间还有最后一个结点，还要进一步比较。 折半查找算法7.3的平均查找长度为 ASL=nn+1​log2​(n+1)−1 当n较大时，时间复杂度有近似结果O(log2​n)。

编程要求

根据提示，在右侧编辑器Begin和End间补充代码，完成折半查找之任务。

测试说明

平台会对你编写的代码进行测试：

测试输入（共两行，第一行为待查找的关键字，第二行为以空格分隔的顺序表各元素：

4

0 1 2 3 4 5

预期输出：

找到4位置为5

测试输入：

7

0 1 2 3 4 5

预期输出：

未找到7

参考代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
 
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }
 
const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;
 
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
 
#define ERROR 0
#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.length ++, L.R[L.length].key = n;
	return OK;
/*********************** 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) >> 1;
		if(ST.R[mid].key == key) return mid;
		else if(key > ST.R[mid].key) low = mid + 1;
		else high = mid - 1;
	}  
	return ERROR;
/*********************** 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行为单个字符，是需要从二叉排序树中删除的字符):

参考代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
 
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl;
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define NO cout << "NO" << endl;
//#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }
 
const int N = 5e5+10, mod = 1e9+7, M = 1e7+5, K = 1e5+10, Z = 2e5+7;
 
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
 
#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循环从根开始查找关键字等于key的结点*p-------------*/
  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);
}

 第4关：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-树主要用做文件的索引，因此它的查找涉及外存的存取，在此略去外存的读写，只做示意性的描述。假设结点类型定义如下：

1. #define m 3 // B-树的阶，暂设为3
2. typedef struct BTNode
3. {
4. int keynum;//结点中关键字的个数，即结点的大小
5. struct BTNode *parent; //指向双亲结点
6. KeyType K[m+1];//关键字向量，0号单元未用
7. struct BTNode *ptr[m+1];//子树指针向量
8. Record *recptr[m+1]; //记录指针向量，0号单元未用
9. }BTNode,*BTree; //B-树结点和B-树的类型
10. typedef struct
11. {
12. BTNode *pt; //指向找到的结点
13. int i; //1..m，在结点中的关键字序号
14. int tag; //1：查找成功，0：查找失败
15. }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互称为同义词。 构造散列函数的常用方法包括数字分析法、平方取中法、折叠法及除留余数法。 处理冲突的手段主要有开放地址法和链地址法两类。 下面以开放地址法为例，给出散列表的存储表示。

1. //- - - - -开放地址法散列表的存储表示- - - - -
2. #define m 20 //散列表的表长
3. typedef struct{
4. KeyType key; //关键字项
5. InfoType otherinfo; //其他数据项
6. }HashTable[m];

算法步骤

在散列表上进行查找的过程和创建散列表的过程基本一致。算法7.10描述了开放地址法（线性探测法）处理冲突的散列表的查找过程。

算法7.10 散列表的查找

① 给定待查找的关键字key，根据造表时设定的散列函数计算H0=H(key)。 ② 若单元H0为空，则所查元素不存在。 ③ 若单元H0中元素的关键字为key，则查找成功。 ④ 否则重复下述解决冲突的过程： ·按处理冲突的方法，计算下一个散列地址Hi； ·若单元Hi为空，则所查元素不存在； ·若单元Hi中元素的关键字为key，则查找成功。

算法描述

示例如下：

1. #define NULLKEY 0 //单元为空的标记
2. int SearchHash(HashTable HT,KeyType key)
3. {//在散列表HT中查找关键字为key的元素，若查找成功，返回散列表的单元标号，否则返回-1
4. H0=H(key);
5. //根据散列函数H（key）计算散列地址
6. if(HT[H0].key==NULLKEY) return -1; //若单元H0为空，则所查元素不存在
7. else if(HT[H0].key==key) return H0; //若单元H0中元素的关键字为key，则查找成功
8. else
9. {
10. for(i=1;i<m;++i){
11. Hi=(H0+i)%m; //按照线性探测法计算下一个散列地址Hi
12. if(HT[Hi].key==NULLKEY) return -1; //若单元Hi为空，则所查元素不存在
13. else if(HT[Hi].key==key) return Hi; //若单元Hi中元素的关键字为key，则查找成功
14. } //for
15. return -1;
16. } //else
17. }

算法分析

从散列表的查找过程可见： （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;
	}
}

作者有言

如果感觉博主讲的对您有用，请点个关注支持一下吧，将会对此类问题持续更新……