查找

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

// 查找表的数据结构
typedef struct {
  ElemType *elem; // 元素存储空间地址
  int TableLen; // 表长度
} SSTable; //ss search seq table

// 哨兵版查找
// 注意: 成功返回数据下标，失败返回0
// 由于0号下标是哨兵，找到哨兵后则证明没有返回找到值，返回0为查找失败
int Sentinel_Search_Seq (SSTable ST, ElemType key) {
  ST.elem[0] = key; // 使哨兵 = 查找元素
  int i;
  // 下面 for 循环的写法也是正确的
  // for (i = ST.TableLen; ST.elem[i] != key; --i)
  // 为了方便理解，改写成while循环的
  i = ST.TableLen;
  while (ST.elem[i] != key) {
    i = i - 1;
  }

  return i;
}

// 普通版查找
// 成功返回数据下标，失败返回 -1
int Search_Seq (SSTable ST, ElemType key) {
  int i;
  // 下面 for 循环的写法也是正确的
  // for (i = 0; i < ST.TableLen && ST.elem[i] != key; ++i);
  // 为了方便理解，改写成while循环的
  i = 0;
  while (i < ST.TableLen) {
    if (ST.elem[i] == key) break;
    i = i + 1;
  }

  return i == ST.TableLen ? - 1 : i;
}

int main () {
  // 待查找的值
  ElemType searchNum = 60;
  // 查找到的下标
  int searchResultIndex;

  // 带哨兵版查找
  SSTable SentinelSS;
  // 注意：带哨兵的 table 长度为有效数据长度，不包含哨兵
  SentinelSS.TableLen = 7;
  SentinelSS.elem = (ElemType *)malloc(sizeof(ElemType) * (SentinelSS.TableLen + 1)); // + 1 是哨兵位置
  // 下标0，存储哨兵
  SentinelSS.elem[0] = -1;
  SentinelSS.elem[1] = 40;
  SentinelSS.elem[2] = 20;
  SentinelSS.elem[3] = 50;
  SentinelSS.elem[4] = 10;
  SentinelSS.elem[5] = 60;
  SentinelSS.elem[6] = 80;
  SentinelSS.elem[7] = 70;
  searchResultIndex = Sentinel_Search_Seq(SentinelSS, searchNum);
  if (searchResultIndex == 0) {
    printf("哨兵版未查找到值：%d, 查找结果为：%d\n", searchNum, searchResultIndex);
  } else {
    printf("哨兵版查找值：%d, 下标为：%d\n", searchNum, searchResultIndex);
  }

  // 普通模式查找
  SSTable SS;
  SS.TableLen = 7;
  SS.elem = (ElemType *)malloc(sizeof(ElemType) * SS.TableLen);
  SS.elem[0] = 40;
  SS.elem[1] = 20;
  SS.elem[2] = 50;
  SS.elem[3] = 10;
  SS.elem[4] = 60;
  SS.elem[5] = 80;
  SS.elem[6] = 70;
  searchResultIndex = Search_Seq(SS, searchNum);
  if (searchResultIndex == -1) {
    printf("普通版未查找到值：%d, 查找结果为：%d\n", searchNum, searchResultIndex);
  } else {
    printf("普通版查找值：%d, 下标为：%d\n", searchNum, searchResultIndex);
  }

  return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

// 查找表的数据结构
typedef struct {
  ElemType *elem; // 元素存储空间地址
  int TableLen; // 表长度
} SSTable; // search seq table

// 有序表的顺序查找
// 成功返回数据下标，失败返回 -1
int Search_Seq (SSTable ST, ElemType key) {
  for (int i = 0; i < ST.TableLen; i++) {
    if (ST.elem[i] == key) return i; // 返回目标元素在有序表中的索引位置
    if (ST.elem[i] > key) return -1; // 返回-1表示未找到目标元素
  }
  return -1; // 如果遍历完整个有序表仍未找到目标元素，则返回-1
}

int main () {
  // 待查找的值
  ElemType searchNum = 60;
  // 查找到的下标
  int searchResultIndex;
  // 普通模式查找
  SSTable SS;
  SS.TableLen = 7;
  SS.elem = (ElemType *)malloc(sizeof(ElemType) * SS.TableLen);
  SS.elem[0] = 20;
  SS.elem[1] = 40;
  SS.elem[2] = 50;
  SS.elem[3] = 60;
  SS.elem[4] = 70;
  SS.elem[5] = 80;
  SS.elem[6] = 90;
  searchResultIndex = Search_Seq(SS, searchNum);
  if (searchResultIndex == -1) {
    printf("未查找到值：%d, 查找结果为：%d
", searchNum, searchResultIndex);
  } else {
    printf("查找到值：%d, 下标为：%d
", searchNum, searchResultIndex);
  }

  return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define ElemType int

// 查找表的数据结构
typedef struct {
  ElemType *elem; // 元素存储空间地址
  int TableLen; // 表长度
} SSTable; // search seq table

// 成功返回数据下标，失败返回 -1
int Binary_Search (SSTable ST, ElemType key) {
  int low = 0; // 初始化搜索范围的下界。
  int high = ST.TableLen - 1; // 初始化搜索范围的上界。
  int mid; // 声明一个变量来存储中间索引。

   // 在下界小于等于上界的情况下执行二分查找。
  while (low <= high)  {
    mid = (low + high) / 2; // 通过计算下界和上界的平均值来计算中间索引。
    if (ST.elem[mid] == key) // 将中间索引处的元素与关键字进行比较。
      return mid; // 如果元素与关键字匹配，则返回找到的索引。
    else if (ST.elem[mid] > key)
      high = mid - 1; // 如果元素大于关键字，则将上界更新为前半部分进行搜索。
    else
      low = mid + 1;  // 如果元素小于关键字，则将下界更新为后半部分进行搜索。
  }
  // 如果循环完成仍未找到关键字，则返回 -1 表示搜索失败。
  return -1;
}

int main () {
  // 待查找的值
  ElemType searchNum = 100;
  // 查找到的下标
  int searchResultIndex;
  // 普通模式查找
  SSTable SS;
  SS.TableLen = 7;
  SS.elem = (ElemType *)malloc(sizeof(ElemType) * SS.TableLen);
  SS.elem[0] = 20;
  SS.elem[1] = 40;
  SS.elem[2] = 50;
  SS.elem[3] = 60;
  SS.elem[4] = 70;
  SS.elem[5] = 80;
  SS.elem[6] = 90;
  searchResultIndex = Binary_Search(SS, searchNum);
  if (searchResultIndex == -1) {
    printf("未查找到值：%d, 查找结果为：%d
", searchNum, searchResultIndex);
  } else {
    printf("查找到值：%d, 下标为：%d
", searchNum, searchResultIndex);
  }

  return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define MAXM 10 // 定义B树的最大的阶数

const int m = 5;             // 设定B树的阶数
const int Max = m - 1;       // 结点的最大关键字数量
const int Min = (m - 1) / 2; // 结点的最小关键字数量
typedef int ElemType;        // ElemType为关键字类型

// B树和B树结点类型
typedef struct node {
  int keynum;             // 结点关键字个数
  ElemType key[MAXM];     // 关键字数组，key[0]不使用
  struct node *parent;    // 双亲结点指针
  struct node *children[MAXM]; // 孩子结点指针数组
} BTNode, *BTree;

// B树查找结果类型
typedef struct {
  BTNode *pt; // 指向找到的结点
  int i;      // 在结点中的关键字位置;
  int tag;    // 查找成功与否标志
} Result;

// 链表和链表结点类型
typedef struct LNode {
  BTree data;         // 数据域
  struct LNode *next; // 指针域
} LNode, *LinkList;

// 枚举类型（依次递增）
typedef enum status {
  TRUE,
  FALSE,
  OK,
  ERROR,
  OVERFLOW,
  EMPTY
} Status;

// 初始化B树
Status InitBTree(BTree &t) {
  t = NULL;
  return OK;
}

/**
* 在结点p中查找关键字k的插入位置i，使得p->key[i] <= k < p->key[i+1]。
* @param p - 目标结点
* @param k - 要查找的关键字
* @return int - 插入位置i，表示在结点p的第i个关键字之后插入k
*/
int SearchBTNode(BTNode *p, ElemType k) {
 int i = 0;

 // 从前向后逐个查找结点p中的关键字，找到第一个满足 p->key[i] <= k < p->key[i+1] 的位置
 for (
   i = 0;
   i < p->keynum && p->key[i + 1] <= k;
   i++
 );

 return i;
}

/**
* 在B树t上查找关键字k，返回查找结果。
* @param t - B树的根结点指针
* @param k - 要查找的关键字
* @return Result - 包含查找结果的结构体，包括指向找到的结点、关键字位置和查找成功与否标志
*/
Result SearchBTree(BTree t, ElemType k) {
 BTNode *p = t, *q = NULL; // 初始化结点p和结点q，p指向待查结点，q指向p的双亲
 int found_tag = 0;        // 设定查找成功与否标志
 int i = 0;
 Result r; // 设定返回的查找结果

 while (p != NULL && found_tag == 0) {
   i = SearchBTNode(p, k);      // 在结点p中查找关键字k，使得p->key[i] <= k < p->key[i+1]
   if (i > 0 && p->key[i] == k) // 找到待查关键字
     found_tag = 1;             // 查找成功
   else { // 查找失败
     q = p;      // 将当前结点p作为双亲结点q
     p = p->children[i]; // 移动到子结点继续查找
   }
 }

 if (found_tag == 1) { // 查找成功
   r.pt = p;   // 指向找到的结点
   r.i = i;    // 在结点中的关键字位置
   r.tag = 1;  // 查找成功标志
 } else { // 查找失败
   r.pt = q;   // 指向双亲结点q
   r.i = i;    // 在结点中的关键字位置
   r.tag = 0;  // 查找失败标志
 }

 return r; // 返回关键字k的位置(或插入位置)
}

/**
* 在结点p中插入关键字k和子树指针q，并保持关键字有序。
* @param p - 要插入关键字的目标结点
* @param i - 插入位置，表示在结点p的第i个关键字之后插入k
* @param k - 要插入的关键字
* @param q - 要插入的子树指针
*/
void InsertBTNode(BTNode *&p, int i, ElemType k, BTNode *q) {
 int j;

 // 从结点p的末尾开始，依次后移关键字和子树指针，为新关键字和子树指针腾出位置
 for (j = p->keynum; j > i; j--) {
   p->key[j + 1] = p->key[j];
   p->children[j + 1] = p->children[j];
 }

 // 插入新关键字k和子树指针q到目标位置
 p->key[i + 1] = k;
 p->children[i + 1] = q;

 if (q != NULL)
   q->parent = p; // 更新子树指针的父节点为当前结点p

 p->keynum++; // 增加结点p中的关键字数量
}

/**
* 将结点p分裂成两个结点，前一半保留，后一半移入结点q。
* @param p - 待分裂的结点
* @param q - 分裂后的新结点
*/
void SplitBTNode(BTNode *&p, BTNode *&q) {
 int i;
 int s = (m + 1) / 2; // 计算分裂位置s，即后一半移入结点q
 q = (BTNode *)malloc(sizeof(BTNode)); // 为新结点q分配空间

 // 后一半关键字和子树指针从结点p移动到结点q
 q->children[0] = p->children[s];
 for (i = s + 1; i <= m; i++) {
   q->key[i - s] = p->key[i];
   q->children[i - s] = p->children[i];
 }

 q->keynum = p->keynum - s; // 更新新结点q的关键字数量
 q->parent = p->parent;    // 更新新结点q的父节点指针

 // 更新子树指针的父节点指针为新结点q
 for (i = 0; i <= p->keynum - s; i++)
   if (q->children[i] != NULL)
     q->children[i]->parent = q;

 p->keynum = s - 1; // 更新结点p的关键字数量，前一半保留
}

/**
* 生成新的根结点t，原p和q为子树指针。
* @param t - 新的根结点指针
* @param k - 新的根结点的关键字
* @param p - 原根结点的左子树
* @param q - 原根结点的右子树
*/
void NewRoot(BTNode *&t, ElemType k, BTNode *p, BTNode *q) {
 t = (BTNode *)malloc(sizeof(BTNode)); // 分配空间
 t->keynum = 1; // 根结点的关键字数量为1
 t->children[0] = p; // 左子树指针指向原p
 t->children[1] = q; // 右子树指针指向原q
 t->key[1] = k; // 新根结点的关键字为k

 if (p != NULL) // 调整结点p和结点q的双亲指针
   p->parent = t;
 if (q != NULL)
   q->parent = t;
 t->parent = NULL; // 新根结点的双亲为空
}

/**
* 在B树t中插入关键字k，如果需要，进行结点分裂和根结点更新操作
* @param t - B树的根结点指针
* @param i - 插入位置，表示在结点t的第i个关键字之后插入k
* @param k - 要插入的关键字
* @param p - 结点t的双亲结点指针
*/
void InsertBTree(BTree &t, int i, ElemType k, BTNode *p) {
 BTNode *q; // 用于指向可能需要分裂的子节点
 int finish_tag, newroot_tag, s; // 设定需要新结点标志和插入完成标志
 ElemType x;
 if (p == NULL)               // t是空树
   NewRoot(t, k, NULL, NULL); // 生成仅含关键字k的根结点t
 else {
   x = k;           // 将变量x的值设置为待插入的关键字k
   q = NULL;        // 将指针变量q初始化为NULL，用于指向可能需要分裂的子节点
   finish_tag = 0;  // 初始化finish_tag为0，表示插入尚未完成
   newroot_tag = 0; // 初始化newroot_tag为0，表示不需要创建新的根节点
   while (finish_tag == 0 && newroot_tag == 0) {
     InsertBTNode(p, i, x, q); // 将关键字x和结点q分别插入到p->key[i+1]和p->children[i+1]
     if (p->keynum <= Max)
       finish_tag = 1; // 插入完成
     else {
       s = (m + 1) / 2;
       SplitBTNode(p, q); // 分裂结点
       x = p->key[s];
       if (p->parent) { // 查找x的插入位置
         p = p->parent;
         i = SearchBTNode(p, x);
       }
       else // 没找到x，需要新结点
         newroot_tag = 1;
     }
   }
   if (newroot_tag == 1)  // 根结点已分裂为结点p和q
     NewRoot(t, x, p, q); // 生成新根结点t,p和q为子树指针
 }
}

/**
* 从结点p中删除关键字p->key[i]和对应的孩子指针p->children[i]。
* @param p - 目标结点
* @param i - 要删除的关键字位置
*/
void Remove(BTNode *p, int i) {
 int j;

 // 使用循环将后续的关键字和孩子指针前移，覆盖要删除的关键字和孩子指针
 for (j = i + 1; j <= p->keynum; j++) {
   p->key[j - 1] = p->key[j];
   p->children[j - 1] = p->children[j];
 }

 p->keynum--; // 减少结点p的关键字数量，实现删除操作
}

/**
* 查找被删除关键字 p->key[i]（在非叶子结点中）的替代叶子结点，即右子树中值最小的关键字。
* @param p - 目标结点，非叶子结点
* @param i - 被删除关键字的位置
*/
void Substitution(BTNode *p, int i) {
 BTNode *q;

 // 从当前结点p的右子树开始，一直向左下遍历，找到右子树中的最小关键字所在的叶子结点
 for (q = p->children[i]; q->children[0] != NULL; q = q->children[0])
   ;

 p->key[i] = q->key[1]; // 将找到的最小关键字值复制到原位置，用于替代被删除的关键字
}

/**
* 将双亲结点p中的最后一个关键字移入右结点q中，
* 将左结点aq中的最后一个关键字移入双亲结点p中。
* @param p - 双亲结点
* @param i - 从p的第i个孩子开始操作
*/
void MoveRight(BTNode *p, int i) {
 int j;
 BTNode *q = p->children[i];     // 获取右兄弟q
 BTNode *aq = p->children[i - 1]; // 获取左兄弟aq

 // 将右兄弟q中的所有关键字和孩子指针向后移动一位
 for (j = q->keynum; j > 0; j--) {
   q->key[j + 1] = q->key[j];
   q->children[j + 1] = q->children[j];
 }

 q->children[1] = q->children[0]; // 从双亲结点p移动关键字到右兄弟q中
 q->key[1] = p->key[i];           // 复制双亲结点p中的关键字值
 q->keynum++;

 p->key[i] = aq->key[aq->keynum]; // 将左兄弟aq中最后一个关键字移动到双亲结点p中
 p->children[i]->children[0] = aq->children[aq->keynum]; // 更新孩子指针
 aq->keynum--; // 减少左兄弟aq的关键字数量
}

/**
* 将双亲结点p中的第一个关键字移入左结点aq中，
* 将右结点q中的第一个关键字移入双亲结点p中。
*
* @param p - 双亲结点
* @param i - 从p的第i个孩子开始操作
*/
void MoveLeft(BTNode *p, int i) {
 int j;
 BTNode *aq = p->children[i - 1]; // 获取左兄弟aq
 BTNode *q = p->children[i];     // 获取右兄弟q

 aq->keynum++;                // 将双亲结点p中的关键字移动到左兄弟aq中
 aq->key[aq->keynum] = p->key[i];          // 复制双亲结点p中的关键字值
 aq->children[aq->keynum] = p->children[i]->children[0]; // 更新孩子指针

 p->key[i] = q->key[1];  // 把右兄弟q中的关键字移动到双亲节点p中
 q->children[0] = q->children[1]; // 更新右兄弟q的孩子指针
 q->keynum--;

 // 将右兄弟q中的所有关键字和孩子指针向前移动一位
 for (j = 1; j <= aq->keynum; j++) {
   aq->key[j] = aq->key[j + 1];
   aq->children[j] = aq->children[j + 1];
 }
}

/**
* 将双亲结点p、右结点q合并入左结点aq，并调整双亲结点p中的剩余关键字的位置。
*
* @param p - 双亲结点
* @param i - 从p的第i个孩子开始合并
*/
void Combine(BTNode *p, int i) {
 int j;
 BTNode *q = p->children[i];     // 获取右兄弟结点q
 BTNode *aq = p->children[i - 1]; // 获取左兄弟结点aq

 aq->keynum++;               // 将双亲结点的关键字p->key[i]插入到左结点aq
 aq->key[aq->keynum] = p->key[i];
 aq->children[aq->keynum] = q->children[0];

 for (j = 1; j <= q->keynum; j++) { // 将右结点q中的所有关键字插入到左结点aq
   aq->keynum++;
   aq->key[aq->keynum] = q->key[j];
   aq->children[aq->keynum] = q->children[j];
 }

 for (j = i; j < p->keynum; j++) { // 将双亲结点p中的p->key[i]后的所有关键字向前移动一位
   p->key[j] = p->key[j + 1];
   p->children[j] = p->children[j + 1];
 }
 p->keynum--; // 修改双亲结点p的keynum值
 free(q);     // 释放空右结点q的空间
}

/**
* 删除结点p中的第i个关键字后，调整B树的结构。
* 如果必要，进行关键字的移动或合并操作。
* @param p - 待调整的结点
* @param i - 被删除关键字的索引
*/
void AdjustBTree(BTNode *p, int i) {
 if (i == 0) { // 删除的是最左边的关键字
   if (p->children[1]->keynum > Min) // 右结点可以借
     MoveLeft(p, 1);
   else // 右兄弟不够借，需要合并
     Combine(p, 1);
 } else if (i == p->keynum) { // 删除的是最右边的关键字
   if (p->children[i - 1]->keynum > Min) // 左结点可以借
     MoveRight(p, i);
   else // 左兄弟不够借，需要合并
     Combine(p, i);
 } else if (p->children[i - 1]->keynum > Min) { // 删除关键字在中部且左结点够借
   MoveRight(p, i);
 } else if (p->children[i + 1]->keynum > Min) { // 删除关键字在中部且右结点够借
   MoveLeft(p, i + 1);
 } else { // 删除关键字在中部且左右结点都不够借，需要合并
   Combine(p, i);
 }
}

/**
* 在结点p中查找关键字k并更新i的值以指示查找结果。
* @param p - 当前要查找的结点
* @param k - 要查找的关键字
* @param i - 输出参数，指示查找结果：
*            -1 表示未找到关键字k；
*             0 表示关键字k小于结点p中的第一个关键字；
*             1 到 keynum 表示找到关键字k的位置。
* @return - 如果找到关键字k，返回1；否则返回0。
*/
int FindBTNode(BTNode *p, ElemType k, int &i) {
 if (k < p->key[1]) { // 如果关键字k小于结点p中的第一个关键字
   i = 0;            // 查找失败，设置i为0
 } else { // 在结点p中查找
   i = p->keynum;     // 初始化i为结点p的关键字数量
   while (k < p->key[i] && i > 1) // 从后往前查找关键字k的位置
     i--;
   if (k == p->key[i]) // 找到关键字k
     return 1;        // 返回查找成功标志
 }
 return 0;            // 未找到关键字k，返回查找失败标志
}

/**
* 在结点p中查找并删除关键字k。
* @param p - 当前要查找和删除关键字的结点
* @param k - 要删除的关键字
* @return - 如果成功删除关键字k，返回1；否则返回0。
*/
int BTNodeDelete(BTNode *p, ElemType k) {
 int i;
 int found_tag; // 查找标志

 if (p == NULL)
   return 0; // 结点p为空，查找失败

 found_tag = FindBTNode(p, k, i); // 在结点p中查找关键字k，返回查找结果

 if (found_tag == 1) { // 查找成功
   if (p->children[i - 1] != NULL) { // 删除的是非叶子结点
     Substitution(p, i); // 寻找相邻关键字(右子树中最小的关键字)
     BTNodeDelete(p->children[i], p->key[i]); // 递归删除关键字k
   } else
     Remove(p, i); // 从结点p中位置i处删除关键字k
 } else
   found_tag = BTNodeDelete(p->children[i], k); // 沿孩子结点递归查找并删除关键字k

 if (p->children[i] != NULL)
   if (p->children[i]->keynum < Min) // 删除后关键字个数小于Min
     AdjustBTree(p, i); // 调整B树

 return found_tag; // 返回查找和删除结果标志
}

// 构建删除框架，执行删除操作
void BTreeDelete(BTree &t, ElemType k) {
  BTNode *p;
  int a = BTNodeDelete(t, k); // 删除关键字k
  if (a == 0)                 // 查找失败
    printf("   关键字%d不在B树中\n", k);
  else if (t->keynum == 0) { // 调整
    p = t;
    t = t->children[0];
    free(p);
  }
}

// 递归释放B树
void DestroyBTree(BTree &t) {
  int i;
  BTNode *p = t;
  if (p != NULL) { // B树不为空
    for (i = 0; i <= p->keynum; i++) { // 递归释放每一个结点
      DestroyBTree(*&p->children[i]);
    }
    free(p);
  }
  t = NULL;
}

// 初始化队列
Status InitQueue(LinkList &L) {
  L = (LNode *)malloc(sizeof(LNode)); // 分配结点空间
  if (L == NULL)                      // 分配失败
    return OVERFLOW;
  L->next = NULL;
  return OK;
}

// 新建一个结点
LNode *CreateNode(BTNode *p) {
  LNode *q;
  q = (LNode *)malloc(sizeof(LNode)); // 分配结点空间
  if (q != NULL) { // 分配成功
    q->data = p;
    q->next = NULL;
  }
  return q;
}

// 元素q入队列
Status Enqueue(LNode *p, BTNode *q) {
  if (p == NULL)
    return ERROR;
  while (p->next != NULL) // 调至队列最后
    p = p->next;
  p->next = CreateNode(q); // 生成结点让q进入队列
  return OK;
}

// 出队列，并以q返回值
Status Dequeue(LNode *p, BTNode *&q) {
  LNode *aq;
  if (p == NULL || p->next == NULL) // 删除位置不合理
    return ERROR;
  aq = p->next; // 修改被删结点aq的指针域
  p->next = aq->next;
  q = aq->data;
  free(aq); // 释放结点aq
  return OK;
}

// 队列判空
Status IfEmpty(LinkList L) {
  if (L == NULL) // 队列不存在
    return ERROR;
  if (L->next == NULL) // 队列为空
    return TRUE;
  return FALSE; // 队列非空
}

// 销毁队列
void DestroyQueue(LinkList L) {
  LinkList p;
  if (L != NULL) {
    p = L;
    L = L->next;
    free(p); // 逐一释放
    DestroyQueue(L);
  }
}

// 用队列遍历输出B树
Status Traverse(BTree t, LinkList L, int newline, int sum) {
  int i;
  BTree p;
  if (t != NULL) {
    printf("  [ ");
    Enqueue(L, t->children[0]); // 入队
    for (i = 1; i <= t->keynum; i++) {
      printf(" %d ", t->key[i]);
      Enqueue(L, t->children[i]); // 子结点入队
    }
    sum += t->keynum + 1;
    printf("]");
    if (newline == 0) { // 需要另起一行
      printf("\n");
      newline = sum - 1;
      sum = 0;
    }
    else
      newline--;
  }

  if (IfEmpty(L) == FALSE) {                               // l不为空
    Dequeue(L, p);                // 出队，以p返回
    Traverse(p, L, newline, sum); // 遍历出队结点
  }
  return OK;
}

// 输出B树
Status PrintBTree(BTree t) {
  LinkList L;
  if (t == NULL) {
    printf("  B树为空树");
    return OK;
  }
  InitQueue(L);         // 初始化队列
  Traverse(t, L, 0, 0); // 利用队列输出
  DestroyQueue(L);      // 销毁队列
  return OK;
}

int main() {
  BTNode *t = NULL;
  Result s; // 设定查找结果
  int i, n;
  ElemType k;
  ElemType a[] = {25, 38, 49, 60, 80, 90, 99, 88, 83, 87, 70, 92, 93, 94, 73, 74, 75};
  n = sizeof(a) / sizeof(ElemType);
  printf("创建一棵%d阶B树:\n", m);
  for (i = 0; i < n; i++) { // 逐一插入元素
    s = SearchBTree(t, a[i]);
    // 未查找到才插入
    if (s.tag == 0)
      InsertBTree(t, s.i, a[i], s.pt);
    printf("   第%d步,插入元素%d:\n ", i + 1, a[i]);
    PrintBTree(t);
  }

  printf("\n");
  printf("删除操作:\n");
  k=25;
  BTreeDelete(t,k);
  printf("  删除%d:\n ",k);
  printf("  删除后的B树: \n");
  PrintBTree(t);
  printf("\n");

  k=1;
  BTreeDelete(t,k);
  printf("  删除%d:\n ",k);
  printf("  删除后的B树: \n");
  PrintBTree(t);
  printf("\n");

  printf("  递归释放B树\n"); // 递归释放B树
  DestroyBTree(t);
  PrintBTree(t);
  return 0;
}

#include <stdio.h>
#include <stdlib.h>

// 哈希表大小
#define TABLE_SIZE 13

// 哈希表结点的结构
typedef struct HashNode {
  int value;
  HashNode *next;
} HashNode;

// 函数用于检查一个整数是否是质数
int isPrime(int n) {
  if (n <= 1) return 0;
  if (n <= 3) return 1;
  if (n % 2 == 0 || n % 3 == 0) return 0;

  for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
      return 0;
    }
  }
  return 1;
}

// 哈希函数
int hash(int key) {
  // 【除留余数法】
  int p = TABLE_SIZE; // 不大于m但最接近m的质数
  while (p >= 2) {
    // 是质数
    if (isPrime(p)) break;
    p--;
  }

  //【直接定址法】
  // a * key + b

  //【数字分析法】
  //【平方取中法】
  return key % p; // 使用取余运算计算哈希值
}

// 插入值到链表
void insert(HashNode* table[], int value) {
  HashNode *newNode = (HashNode *)malloc(sizeof(HashNode));

  HashNode **head = &table[hash(value)];
  newNode->value = value;
  newNode->next = *head;
  *head = newNode;
}

// 查找值是否存在于链表中
int find(HashNode* table[], int value) {
  // 开头结点
  HashNode *current = table[hash(value)];
  while (current != NULL) {
    if (current->value == value) {
      return 1; // 找到值
    }
    current = current->next;
  }
  return 0; // 没有找到值
}

// 从链表中删除值
void removeValue(HashNode* table[], int value) {
  HashNode *head = table[hash(value)];
  HashNode *current = head;
  HashNode *pre = NULL;

  while (current != NULL) {
    if (current->value == value) {
      // 仅有一个结点
      if (pre == NULL) {
        head = current->next;
      } else {
        pre->next = current->next;
      }
      free(current);
      return;
    }

    // 继续遍历
    pre = current;
    current = current->next;
  }
}

// 打印哈希表及链表内容
void printHashTable(HashNode* table[]) {
  for (int i = 0; i < TABLE_SIZE; ++i) {
    printf("Index %d:", i);
    HashNode* current = table[i];
    while (current != NULL) {
        printf(" -> %d", current->value);
        current = current->next;
    }
    printf(" -> NULL\n");
  }
}

int main () {
  HashNode* table[TABLE_SIZE];
  // 初始化哈希表
  for (int i = 0; i < TABLE_SIZE; ++i) {
    table[i] = NULL;
  }

  // 插入值
  insert(table, 19);
  insert(table, 14);
  insert(table, 23);
  insert(table, 1);
  insert(table, 68);
  insert(table, 20);
  insert(table, 84);
  insert(table, 27);
  insert(table, 55);
  insert(table, 11);
  insert(table, 10);
  insert(table, 79);

  printHashTable(table);

  // 查找值
  printf("Value 20 exists: %s\n", find(table, 20) ? "Yes" : "No");
  printf("Value 300 exists: %s\n", find(table, 300) ? "Yes" : "No");
  printf("Value 200 exists: %s\n", find(table, 200) ? "Yes" : "No");

  // 删除值
  int removedValue = 10;
  removeValue(table, removedValue);
  printf("Value %d removed\n", removedValue);

  // 查找值
  printf("Value 200 exists: %s\n", find(table, removedValue) ? "Yes" : "No");

  printHashTable(table);
  // 释放内存
  for (int i = 0; i < TABLE_SIZE; ++i) {
    HashNode* current = table[i];
    while (current != NULL) {
      HashNode* temp = current;
      current = current->next;
      free(temp);
    }
  }

  return 0;
}

#include <stdio.h>
#include <stdlib.h>

// 哈希表结点的结构
typedef struct HashMap {
  int p; // 不大于 TABLE_SIZE 但最接近 TABLE_SIZE 的质数
  int size;
  int* table;
} HashMap;

// 函数用于检查一个整数是否是质数
int isPrime(int n) {
  if (n <= 1) return 0;
  if (n <= 3) return 1;
  if (n % 2 == 0 || n % 3 == 0) return 0;

  for (int i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
      return 0;
    }
  }
  return 1;
}

// 哈希函数
int hash(int key, int size) {
  return key % size; // 使用取余运算计算哈希值
}

// 初始化哈希表
HashMap* CreateHashMap (int size) {
  HashMap* hash = (HashMap *)malloc(sizeof(HashMap));

  int p = size; // 不大于m但最接近m的质数
  while (p >= 2) {
    // 是质数
    if (isPrime(p)) break;
    p--;
  }
  hash->p = p;
  hash->size = size;
  hash->table = (int *)malloc(sizeof(int) * hash->size);

  for (int i = 0; i < size; i++) {
    hash->table[i] = NULL; // 初始化哈希表
  }
  return hash;
}

// 线性探测插入
void HashMap_Insert_Linerar (HashMap * hashMap, int value) {
  int index = hash(value, hashMap->p);
  int count = 0; // 记录是否满
  while (hashMap->table[index] != NULL) {
    if (count == hashMap->size) {
      printf("哈希表以满");
      return;
    }
    count++;
    // 线性探测，递增索引
    index = (index + 1) % hashMap->size;
  }
  hashMap->table[index] = value;
}

// 线性探测查找
int HashMap_Search_Linerar (HashMap *hashMap, int value) {
  int index = hash(value, hashMap->p);
  int count = 0; // 记录是否没有
  while (hashMap->table[index] != NULL) {
    // 查找完整个表都没有找到
    if (count == hashMap->size) return -1;
    if (hashMap->table[index] == value)
      return index;

    index = (index + 1) % hashMap->size;
  }
  return -1;
}

// 平方探测插入
void HashMap_Insert_Quadratic (HashMap * hashMap, int value) {
  int hashIndex = hash(value, hashMap->p);
  int index = hashIndex;
  int d = 1;
  int count = 0; // 记录比较次数
  // 0²，1²，-1²，2²，-2²，.....
  // hashMap->table[index] 即代表了 d = 0 的情况
  while (hashMap->table[index] != NULL) {
    if (d > hashMap->size / 2) {
      printf("增量【d > 表长/2】，退出循环。没有遍历到的位置也不会在遍历到了");
      return;
    }
    count++;
    // 根据 d 的正负，选择使用负平方偏移或正平方偏移来计算新的索引位置
    if (d < 0) {
      index = (-1 * d * d + hashIndex) % hashMap->size;
    } else {
      index = (d * d + hashIndex) % hashMap->size;
    }

    // 如果计算出的新索引为负数，将其转换为对应的正数索引，确保索引在哈希表的有效范围内
    if (index < 0) index = hashMap->size + index;

    d = -d; // 切换正负平方偏移

    if (d >= 0) {
      d++; // 正平方偏移 + 1
    }
  }
  hashMap->table[index] = value;
}

// 平方探测查找
int HashMap_Search_Quadratic (HashMap *hashMap, int value) {
  int hashIndex = hash(value, hashMap->p);
  int d = 1;
  int index = hashIndex;
  int count = 0; // 记录比较次数
  while (hashMap->table[index] != NULL) {
    // 查找完整个表都没有找到
    if (d > hashMap->size / 2) {
      printf("增量【d > 表长/2】，退出循环。没有遍历到的位置也不会在遍历到了");
      return -1;
    }

    if (hashMap->table[index] == value) {
      return index;
    }

    if (d < 0) {
      index = (-1 * d * d + hashIndex) % hashMap->size;
    } else {
      index = (d * d + hashIndex) % hashMap->size;
    }

    if (index < 0) index = hashMap->size + index;

    d = -d; // 切换正负平方偏移
    if (d >= 0) {
      d++; // 正平方偏移+1
    }
  }
  return -1; // 未找到值
}

int main () {
  HashMap* linerHashMap = CreateHashMap(11);
  linerHashMap->p = 7;

  // 线性探测
  HashMap_Insert_Linerar(linerHashMap, 87);
  HashMap_Insert_Linerar(linerHashMap, 40);
  HashMap_Insert_Linerar(linerHashMap, 30);
  HashMap_Insert_Linerar(linerHashMap, 6);
  HashMap_Insert_Linerar(linerHashMap, 11);
  HashMap_Insert_Linerar(linerHashMap, 22);
  HashMap_Insert_Linerar(linerHashMap, 98);
  HashMap_Insert_Linerar(linerHashMap, 20);

  printf("线性探测哈希表(M:%d,P:%d)：", linerHashMap->size, linerHashMap->p);
  for (int i = 0; i < linerHashMap->size; i++) {
    printf("%d、", linerHashMap->table[i]);
  }

  // 平方探测
  HashMap* QuadraticHashMap = CreateHashMap(27);
  QuadraticHashMap->p = 13;
  HashMap_Insert_Quadratic(QuadraticHashMap, 6);
  HashMap_Insert_Quadratic(QuadraticHashMap, 19);
  HashMap_Insert_Quadratic(QuadraticHashMap, 32);
  HashMap_Insert_Quadratic(QuadraticHashMap, 45);
  HashMap_Insert_Quadratic(QuadraticHashMap, 58);
  HashMap_Insert_Quadratic(QuadraticHashMap, 71);
  HashMap_Insert_Quadratic(QuadraticHashMap, 84);

  printf("\n平方探测哈希表(M:%d,P:%d)：", QuadraticHashMap->size, QuadraticHashMap->p);
  for (int i = 0; i < QuadraticHashMap->size; i++) {
    printf("%d、", QuadraticHashMap->table[i]);
  }

  printf("\n查找84的下标为：%d", HashMap_Search_Quadratic(QuadraticHashMap, 84));

  return 0;
}