《数据结构（C语言版）第二版》第七章-查找（7.3.3-7.4）

【B-树、B+树：适用于 文件很大且存放于计算机外存的查找】

⭐7.3.3 B-树（平衡多叉树，属于动态查找树，适用于动态查找表）【一种在外存文件系统中常用的动态索引技术】

▲课本算法实现/▲09 查找/08 B-Tree/B-Tree.c —— kangjianwei

【仅包括 查找、插入、分裂、创建、中序遍历打印，不包括删除】

#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define m  3
#define TRUE 1
#define FALSE 0typedef int KeyType;
typedef char Record;  //假设位置存储类型是char型的typedef struct BTNode
{int keynum;struct BTNode* parent;KeyType key[m + 1];struct BTNode* ptr[m + 2];Record* recptr[m + 1];
}BTNode, * BTree;typedef struct
{BTNode* pt;int i;int tag;
}Result;void CreateBTree(BTree& T);
int InsertBTree(BTree& T, KeyType K, BTree q, int i);
void  split(BTree& q, int s, BTree& ap);
void NewRoot(BTree& T, int x, BTree& ap);
void Insert(BTree& q, int i, KeyType x, BTree ap);
Result SearchBTree(BTree T, KeyType key);
int Search(BTree T, KeyType key);
void PrintBTree(BTree T);int main()
{BTree T = NULL;CreateBTree(T);printf("\n该B-树的中序序列为：");PrintBTree(T);return 0;
}//B-树的创建（通过B-树的插入实现）
void CreateBTree(BTree& T)
{T = NULL;Result r = { NULL,0,0 };int j = 0;int N = 0;KeyType KEY = 0;printf("请输入关键字总个数：");scanf_s(" %d", &N);for (j = 1; j <= N; j++){printf("请输入第%d个关键字：", j);scanf_s(" %d", &KEY);r = SearchBTree(T, KEY); //在B-树整棵树上查找key是否存在if (r.tag == 0){InsertBTree(T, KEY, r.pt, r.i);}else{printf("该关键字已存在，无法插入，请重新输入。\n");j--;}}
}//算法7.9 B-树的插入【BTree q, int i 这两个参数来自于SearchBTree函数r.tag为0时的r.pt和r.i】
int InsertBTree(BTree& T, KeyType K, BTree q, int i)
{KeyType x = K;BTree ap = NULL;bool finished = FALSE;int s = 0;while (q && !finished){Insert(q, i, x, ap);if (q->keynum < m){finished = TRUE;}else  //if(q->keynum == m){s = (int)ceil((double)m / 2);//C 标准库 <math.h>函数 double ceil(double x) 返回大于或等于 x 的最小的整数值。//B树结点中关键字个数必须>=ceil(m/2)-1split(q, s, ap);x = q->key[s];q = q->parent;if (q){i = Search(q, x);}}}if (!finished)  //q的初始值为空，即整棵树T是空树{NewRoot(T,x,ap);  //书上是NewRoot(T,q,x,ap)，但q为NULL，在NewRoot函数中无用}return 1;
}void  split(BTree& q, int s, BTree& ap)
{int i = 0;ap = (BTree)malloc(sizeof(BTNode));//将q->key[s+1,..,m]保存到ap->key[1,..,m-s]中for (i = 1; i <= m-s; i++){ap->key[i] = q->key[s+i];q->key[s + i] = 0;}//将q->ptr[s,..,m]保存到ap->ptr[0,..,m-s]中for (i= 0; i <= m-s; i++){ap->ptr[i] = q->ptr[s+i];if (ap->ptr[i]){ap->ptr[i]->parent = ap;}q->ptr[s + i] = NULL;}ap->keynum = m - s;q->keynum = s-1;ap->parent = q->parent;
}//生成含信息（T, x, ap）的新的根结点*T，原T和ap为子树指针
void NewRoot(BTree& T, int x, BTree& ap)
{BTree newT = (BTree)malloc(sizeof(BTNode));newT->key[1] = x;newT->ptr[0] = T;  //必须等于T，而不能等于q，q指向NULLnewT->ptr[1] = ap;newT->keynum = 1;newT->parent = NULL;//第一次创建节点时，即树的根结点，该结点/树中只有一个关键字，且该关键字的左右子树都是空的，还无法指定其父节点为其本身。if (newT->ptr[0]){newT->ptr[0]->parent = newT;}if (newT->ptr[1]){newT->ptr[1]->parent = newT;}T = newT;
}//将x和ap分别插入到q->key[i + l]和q->ptr[i+1]
void Insert(BTree &q, int i, KeyType x, BTree ap)
{int a = 0;int b = 0;//将q->key中K(i+1)个到K(keynum)整体往后移动一个单位for (a = q->keynum + 1; a >= i + 2; a--){q->key[a] = q->key[a - 1];}//将q->ptr中的P(i+1)到第P(keynum)整体往后移动一个单位for (b = q->keynum + 1; b >= i + 2; b--){q->ptr[b] = q->ptr[b - 1];}q->key[i + 1] = x;q->ptr[i + 1] = ap;q->keynum++;
}//算法7.8 B-树的查找
//在磁盘上（外存）进行的：在B-树整棵树上查找结点
Result SearchBTree(BTree T, KeyType key)
{BTree p = T;BTree q = NULL;bool found = FALSE;int i = 0;Result r = { NULL,0,0 };while (p && !found){i = Search(p, key);/* 在内存中的Search函数中找到p中目标关键字的位置i之后，在外存磁盘上是不能将p->key[i]直接拿来使用的。在外存上，要先从Record指针类型的一维数组中，读取到该BTNode结点指针p中存储第i个关键字Ki的物理（实际）存放位置recptr[i]，也就是说是p->key[i]的索引项，才能在外存上使用关键字p->key[i]. 书上没有体现。 */if (i > 0 && p->key[i] == key){found = TRUE;}else             //if( p->key[i] != key ){q = p;p = p->ptr[i];}}//找到了或者p指向了叶子结点，跳出while循环if (found){r.pt = p;r.i = i;r.tag = 1;}else{r.pt = q;r.i = i;r.tag = 0;//可以在此处由q指向结点的第i个和第i+1个关键字之间，插入关键字key}return r;
}int Search(BTree p, KeyType K)
{int i = 0; int j = 1;for (i = 0, j = 1; j <= p->keynum; j++){if (p->key[j] <= K)i = j;elsebreak;}return i;
}/*
//在内存上进行的：在结点T中找关键字key
int Search(BTree T, KeyType key)
{BTree p = T;int i = 0;int endnum = 0;if (p)  //结点不为空时{endnum = p->keynum;  //获得节点包含的关键字个数}else{return 0;}if(key >= p->key[endnum])   //节点不为空，但当前值比最大的key还大,返回当前关键字的下标{i = endnum;return i; }else if (key <= p->key[1])  //节点不为空，但当前值比最小的key还小,返回当前关键字的下标{return i;  //i==0}else   //key < p->key[endnum] && key > p->key[1]{for (i = 1; i < endnum; i++)  {if (p->key[i] <= key && key < p->key[i + 1]){return i;}}}
}
*///中序遍历打印B-数
void PrintBTree(BTree T)
{int i = 0;if (T){for (i = 0; i <= T->keynum; i++){PrintBTree(T->ptr[i]);if (i < T->keynum)  /* 因为关键字的下标最大值为T->keynum，若打印关键字i最大只能取到T->keynum-1（打印时下标为i+1）若打印子树指针指向的树，那么i可取到T->keynum  */{printf("%d  ", T->key[i + 1]);}}}
}

⭐7.3.4 B+ 树（属于动态查找树，适用于动态查找表） 【B-树的变形，严格来说已不符合树的定义。更适合做文件系统的索引。】

▲课本算法实现/▲09 查找/09 B+Tree/B+Tree.c —— kangjianwei
【不包含删除代码】

B+ 树 ——OI Wiki

数据结构之B+树删除详解 —— 每天都要进步一点点

判断一个数是否为质数（素数）的4种方法 —— 是杰夫呀

7.4 ⭐散列表的创建与查找

【仅含：使用除留余数法构造散列函数，同时使用 线性探测法 、二次探测法、链地址法处理冲突的代码。

不包含：（1）使用数字分析法、平方取中法、折叠法构造散列函数，
（2）使用“伪随机探测法” 处理冲突的代码。】

7.4.4 除留余数法构造散列函数

7.4.4.1 使用线性探测法处理冲突

#include  <stdio.h>
#include  <stdlib.h>
#include <math.h>#define m 16  //表长,能容纳的最多的元素个数
#define NULLKEY 0typedef int KeyType;
typedef char OtherInfo;typedef struct elem
{KeyType key;OtherInfo otherinfo;
}elem;/*  elem HashTable[m];HashTable是一个一维数组名称，里面包含m个元素，每个元素类型为一个结构体elem。HashTable 也是指向该数基地址/第一个元素地址的指针  */void CreateHash(elem HT[]);
void Insert(elem HT[], KeyType key);
int SearchHash(elem HT[], KeyType key);
int H(KeyType key);
int maxPrimeNumber(int n);
int checkPrimeNumber(int n);
void printHashTable(elem HT[]);int main()
{elem HT[m] = { 0 };CreateHash(HT);printHashTable(HT);return 0;
}//散列表的创建
void CreateHash(elem HT[])
{int i = 0;int j = 0;int KEY = 0;int flag = 0;/*HT = (elem*)malloc(sizeof(elem) * m); //HT已经被定义为一个具有固定大小的数组。  */for (i = 0; i < m; i++){HT[i].key = NULLKEY;   //将所有位置置为空}for (i = 1; i <= m; i++){printf("请输入第%d个关键字（结束时输入-1）：", i);scanf_s(" %d", &KEY);if (KEY != -1){flag = SearchHash(HT, KEY);if (flag == -1){Insert(HT, KEY);}else{printf("该元素已存在，无法插入，请重新输入。\n");i--;}}else{break;}}if (i > m){printf("散列表已满。");return;}
}//将查找不存在的元素，插入哈希表中
void Insert(elem HT[],KeyType key)
{int	H0 = 0;int Hi = 0;int i = 0;H0 = H(key);if (HT[H0].key == NULLKEY){HT[H0].key = key;}else{for (i = 1; i < m; i++){Hi = (H0 + i) % m;if (HT[Hi].key == NULLKEY){HT[Hi].key = key;break;}//如果HT[Hi].key是其它元素,那么继续计算下一个散列值}}
}//算法7.10 散列表的查找
int SearchHash(elem HT[], KeyType key)
{int i = 0;int	H0 = H(key);int Hi = 0;if (HT[H0].key == NULLKEY){return -1;}else if(HT[H0].key == key){return H0;}else   //HT[H0].key是其它元素{for (i = 1; i < m; i++){Hi = (H0 + i) % m;if (HT[Hi].key == NULLKEY){return -1;}else if (HT[Hi].key == key){return Hi;}else  {; //如果HT[Hi].key是其它元素,那么继续计算下一个散列值}}return -1;}
}//散列函数
/* 采用除留余数法构造散列函数，选择p为小于表长m的最大质数 */
int H(KeyType key)
{int p = maxPrimeNumber(m);return key % p;
}//确定[0,n]范围内的最大质数
int maxPrimeNumber(int n)
{int i = 0;int status = checkPrimeNumber(0);int max = 0;for (i = 0; i <= n; i++){status = checkPrimeNumber(i);if (status){max = i;}}return max;
}//判断一个数是否是素数（是的话返回1，不是返回0）
int checkPrimeNumber(int n)
{int i = 0;int sq = floor(sqrt(n)); //不大于√n的最大整数/*floor向下取整，ceil向上取整 */if (n <= 1) {return 0; //负数、0 、1均不是素数}if(n == 2){return 1; //2是素数}	/* 如果 i 是简单类型（int ， char)，在使用层面，i+=2 与 i=i+2 做的事是一样的，都是将 i 的值加了2，但生成的可执行代码不一样，且i+=2 与 i=i+2 运行的效率不同，i+=2 肯定更快。 *///只需判断一个数能否被不超过sq 的奇数整除for (i = 3; i <= sq; i+=2){if (n % 2 == 0 || n % i == 0)  //n%2==0，说明n是偶数，而（除2之外）质数一定不是偶数{return 0;}}return 1;
}void printHashTable(elem HT[])
{int i = 0;printf("\n散列表中的元素为：");for (i = 0; i < m ; i++){if (HT[i].key != NULLKEY){printf("\n HT[%d].key = %d",i, HT[i].key);}//空槽不输出，但是其它的元素还是要输出}
}

7.4.4.2 使用二次探测法处理冲突

#include  <stdio.h>
#include  <stdlib.h>
#include <math.h>#define m 10  //表长,能容纳的最多的元素个数
#define NULLKEY 0typedef int KeyType;
typedef char OtherInfo;typedef struct elem
{KeyType key;OtherInfo otherinfo;
}elem;/*  elem HashTable[m];HashTable是一个一维数组名称，里面包含m个元素，每个元素类型为一个结构体elem。HashTable 也是指向该数基地址/第一个元素地址的指针  */void CreateHash(elem HT[]);
void Insert(elem HT[], KeyType key);
int SearchHash(elem HT[], KeyType key);
int H(KeyType key);
int maxPrimeNumber(int n);
int checkPrimeNumber(int n);
void printHashTable(elem HT[]);int main()
{elem HT[m] = { 0 };CreateHash(HT);printHashTable(HT);return 0;
}//散列表的创建
void CreateHash(elem HT[])
{int i = 0;int j = 0;int KEY = 0;int flag = 0;/*HT = (elem*)malloc(sizeof(elem) * m);//HT已经被定义为一个具有固定大小的数组。  */for (i = 0; i < m; i++){HT[i].key = NULLKEY;   //将所有位置置为空}for (i = 1; i <= m; i++){printf("请输入第%d个关键字（结束时输入-1）：", i);scanf_s(" %d", &KEY);if (KEY != -1){flag = SearchHash(HT, KEY);if (flag == -1){Insert(HT, KEY);}else{printf("该元素已存在，无法插入，请重新输入。\n");i--;}}else{break;}}if (i > m){printf("散列表已满。");return;}
}//将查找不存在的元素，插入哈希表中（二次探测法处理冲突）
void Insert(elem HT[], KeyType key)
{int	H0 = 0;int Hi = 0;int i = 0;int flag = 0;H0 = H(key);if (HT[H0].key == NULLKEY){HT[H0].key = key;}else{for (i = 1; i < m; ){if (flag == 0){Hi = (H0 + i * i) % m;flag = 1;}else  //if (flag == 1){Hi = (H0 - i * i) % m;i++;flag = 0;}if (HT[Hi].key == NULLKEY){HT[Hi].key = key;break;}//如果HT[Hi].key是其它元素,那么继续计算下一个散列值}}
}//算法7.10 散列表的查找（二次探测法处理冲突）
int SearchHash(elem HT[], KeyType key)
{int i = 0;int	H0 = H(key);int Hi = 0;int flag = 0;if (HT[H0].key == NULLKEY){return -1;}else if (HT[H0].key == key){return H0;}else   //HT[H0].key是其它元素{for (i = 1; i < m;){if (flag == 0){Hi = (H0 + i * i) % m;flag = 1;}else  //if (flag == 1){Hi = (H0 - i * i) % m;i++;flag = 0;}if (HT[Hi].key == NULLKEY){return -1;}else if (HT[Hi].key == key){return Hi;}else{; //如果HT[Hi].key是其它元素,那么继续计算下一个散列值}}return -1;}
}//散列函数
/* 采用除留余数法构造散列函数，选择p为小于表长m的最大质数 */
int H(KeyType key)
{int p = maxPrimeNumber(m);return key % p;
}//确定[0,n]范围内的最大质数
int maxPrimeNumber(int n)
{int i = 0;int status = checkPrimeNumber(0);int max = 0;for (i = 0; i <= n; i++){status = checkPrimeNumber(i);if (status){max = i;}}return max;
}//判断一个数是否是素数（是的话返回1，不是返回0）
int checkPrimeNumber(int n)
{int i = 0;int sq = floor(sqrt(n)); //不大于√n的最大整数/*floor向下取整，ceil向上取整 */if (n <= 1){return 0; //负数、0 、1均不是素数}if (n == 2){return 1; //2是素数}/* 如果 i 是简单类型（int ， char)，在使用层面，i+=2 与 i=i+2 做的事是一样的，都是将 i 的值加了2，但生成的可执行代码不一样，且i+=2 与 i=i+2 运行的效率不同，i+=2 肯定更快。 *///只需判断一个数能否被不超过sq 的奇数整除for (i = 3; i <= sq; i+=2){if (n % 2 == 0 || n % i == 0)//n%2==0，说明n是偶数，而（除2之外）质数一定不是偶数{return 0;}}return 1;
}void printHashTable(elem HT[])
{int i = 0;printf("\n散列表中的元素为：");for (i = 0; i < m; i++){if (HT[i].key != NULLKEY){printf("\n HT[%d].key = %d", i, HT[i].key);}//空槽不输出，但是其它的元素还是要输出}
}

7.4.4.3 使用链地址法处理冲突

//除留余数法构造散列函数，“链地址法”处理冲突#include <stdio.h>
#include <stdlib.h>
#include <math.h>#define m 13
#define NULLKEY 0typedef int KeyType;
typedef char InfoType;typedef struct KeyNode
{KeyType Key;InfoType OtherInfo;struct KeyNode* next;
}KeyNode;void CreateHash(KeyNode HT[]);
void Insert(KeyNode HT[], KeyType key);
int SearchHash(KeyNode HT[], KeyType key);
int H(KeyType key);
int maxPrimeNumber(int n);
int checkPrimeNumber(int n);
void Delete(KeyNode HT[], KeyType key);
void printHashTable(KeyNode HT[]);int main()
{KeyNode HT[m] = { 0 };KeyType k1 = 0;KeyType k2 = 0;char choice = '\0';CreateHash(HT);printHashTable(HT);while (1){printf("\n\n请输入要插入的数值：");scanf_s(" %d", &k1);Insert(HT, k1);printHashTable(HT);printf("\n\n请输入要删除的数值：");scanf_s(" %d", &k2);Delete(HT, k2);printHashTable(HT);printf("\n\n是否继续？（y/Y）");scanf_s(" %c", &choice);if (choice != 'y' && choice != 'Y'){break;}}return 0;
}//创建散列表
void CreateHash(KeyNode HT[])
{int i = 0;int KEY = 0;int flag = 0;for (i = 0; i < m; i++){HT[i].Key = NULLKEY;HT[i].next = NULL;}for (i = 1; i <= m; i++){printf("请输入第%d个关键字（结束时输入-1）：", i);scanf_s(" %d", &KEY);  //记录个数可以小于表长度if (KEY != -1){flag = SearchHash(HT, KEY);if (flag == -1){Insert(HT, KEY);}else{printf("该元素已存在，无法插入，请重新输入。\n");i--;}}else{break;}}if (i > m){printf("散列表已满。");return;}
}//散列表的查找
int SearchHash(KeyNode HT[], KeyType key)
{int	H0 = H(key);KeyNode* p = HT[H0].next;while (p != NULL){if (p->Key == key){return H0; //找见了}p = p->next;}return -1; //没找见
}//散列表的插入（链地址法处理冲突）
void Insert(KeyNode HT[], KeyType key)
{int H0 = H(key);KeyNode* p = HT[H0].next;while (p != NULL){if (p->Key == key){printf("该元素已存在，无法插入。\n");}p = p->next;}KeyNode* r = (KeyNode*)malloc(sizeof(KeyNode));r->Key = key;r->next = HT[H0].next;HT[H0].next = r;
}//散列函数
/* 采用除留余数法构造散列函数，选择p为小于表长m的最大质数 */
int H(KeyType key)
{int p = maxPrimeNumber(m);return key % p;
}//确定[0,n]范围内的最大质数
int maxPrimeNumber(int n)
{int i = 0;int status = checkPrimeNumber(0);int max = 0;for (i = 0; i <= n; i++){status = checkPrimeNumber(i);if (status){max = i;}}return max;
}//判断一个数是否是质数
int checkPrimeNumber(int n)
{int i = 0;int sq = floor(sqrt(n));if (n <= 1){return 0;}if (n == 2 || n == 3){return 1;}//只有6x-1和6x+1的数才有可能是质数（但不一定就是，如n=35，还需要继续判断）if (n % 6 != 1 && n % 6 != 5)   //n=4和n=6时，n%6满足该if条件，返回false，正好符合情况{return false;}/* 如果 i 是简单类型（int ，char)，在使用层面，i+=6 与 i=i+6 做的事是一样的，都是将 i 的值加了6，但生成的可执行代码不一样，且i+=6 与 i=i+6 运行的效率不同，i+=6 肯定更快。 *///只判断 该与6的倍数相邻的数n 能否被 其它不超过sq 且 也与6的倍数相邻的数i和i+2 整除// 同样因为“只有与6的倍数相邻的数才可能是质数”，所以用i和i+2来判断（i=5\11\17\23\29\35...  i+2=7\13\19\25\31\37...）。// 定理：如果一个数n不能整除 比它小的任何素数（比n小的全部素数一定都包含在i和i+2中），那么这个数n就是素数。for (i = 5; i <= sq; i+= 6){if (n % i == 0 || n % (i + 2) == 0)  {return 0;}}//此处for循环中，仍然找的是整数n的因数，所以仍然可以使用定理：如果一个数m不是质数，那么它必定有一个因子≤√m，另一个≥√m。所以i仍然判断到sq就可以。//真命题“如果数n存在一个大于√n的整数因数，那么它必定存在一个小于√n的整数因数。”的逆否命题也是真命题。// 即如果一个数n没有小于√n的整数因数，那么它也一定不会有大于√n的整数因数（除了它自己）。//n = 5 和 n=7 时，不会进入if判断语句，也不会进入for循环，而是直接返回true，此时也判断正确return true;
}void printHashTable(KeyNode HT[])
{int i = 0;KeyNode* p = NULL;printf("\n散列表中的元素为：");for (i = 0; i < m; i++){if (HT[i].next != NULL){printf("\n在%d个位置处，保存的关键字有：", i+1);for (p = HT[i].next; p; p = p->next){printf("%d ", p->Key);}}//空槽（链表不为空的）不输出，但是其它的元素还是要输出//链地址法中，散列表每个位置的HT[i].key成员并不存储任何数据，通常设置为 NULLKEY或者不使用}
}//散列表的删除
void Delete(KeyNode HT[],KeyType key)
{int	H0 = H(key);KeyNode* p = HT[H0].next;KeyNode* q = NULL;while (p != NULL){if (p->Key == key){break;}q = p;p = p->next;}if (!q){HT[H0].next = p->next;}else{q->next = p->next;}if (!p){printf("%d查找失败，无法删除。\n", key);}free(p);p = NULL;}