数据结构-查找（1）

一、查找的核心目标

1. 存在性检查：判断目标元素是否存在于数据集合中。

2. 位置定位：若存在，确定其存储位置（如数组索引、内存地址）。

3. 信息获取：返回与目标元素关联的数据（如键值对中的值）

二、查找算法的关键指标

1. 时间复杂度：衡量算法执行时间与数据规模的关系。

2. 空间复杂度：算法执行所需的额外内存空间。

3. 稳定性：是否总能找到目标（如哈希表可能因冲突漏查）。

4. 适用性：是否依赖数据结构的特性（如有序性）。

三、静态查找方法

1. 适用场景

• 数据集合初始化后不再修改。

• 需要高效的单次或批量查找操作。

• 示例：历史数据查询、离线数据分析。

2. 常用方法

a. 顺序查找（线性查找）

• 原理：逐个遍历元素，直到找到目标。

• 时间复杂度：𝑂(𝑛)O(n)。

• 代码示例：

• #include <stdio.h>
  #include <stdlib.h> // 用于动态内存分配
  
  // 顺序查找函数
  int sequential_search(int arr[], int size, int target) {
      for (int i = 0; i < size; i++) {
          if (arr[i] == target) {
              return i; // 找到目标，返回索引位置
          }
      }
      return -1; // 未找到目标
  }
  
  int main() {
      int n, target, result;
  
      // 输入数组大小
      printf("请输入数组的大小：");
      scanf("%d", &n);
  
      // 动态分配数组内存
      int *arr = (int *)malloc(n * sizeof(int));
      if (arr == NULL) {
          printf("内存分配失败！\n");
          return 1;
      }
  
      // 输入数组元素
      printf("请输入%d个整数：\n", n);
      for (int i = 0; i < n; i++) {
          scanf("%d", &arr[i]);
      }
  
      // 输入要查找的目标值
      printf("请输入要查找的目标值：");
      scanf("%d", &target);
  
      // 执行顺序查找
      result = sequential_search(arr, n, target);
  
      // 输出结果
      if (result != -1) {
          printf("目标值 %d 在数组中的位置是第 %d 个元素（下标：%d）\n", target, result + 1, result);
      } else {
          printf("目标值 %d 未在数组中找到。\n", target);
      }
  
      // 释放动态分配的内存
      free(arr);
  
      return 0;
  }

  

b. 二分查找（折半查找）

• 原理：要求数据有序，每次比较中间元素缩小范围。

• 时间复杂度：𝑂(log⁡𝑛)O(logn)。

• 代码示例：

• #include <stdio.h>
  #include <stdlib.h> // 用于动态内存分配和qsort
  
  // 二分查找函数（迭代实现）
  int binary_search(int arr[], int size, int target) {
      int low = 0;
      int high = size - 1;
  
      while (low <= high) {
          int mid = low + (high - low) / 2; // 避免整数溢出
          
          if (arr[mid] == target) {
              return mid;           // 找到目标值
          } else if (arr[mid] < target) {
              low = mid + 1;        // 目标在右半区
          } else {
              high = mid - 1;       // 目标在左半区
          }
      }
      return -1; // 未找到目标值
  }
  
  // 检查数组是否升序排列
  int is_sorted(int arr[], int size) {
      for (int i = 0; i < size-1; i++) {
          if (arr[i] > arr[i+1]) {
              return 0; // 发现逆序对
          }
      }
      return 1; // 数组已排序
  }
  
  int main() {
      int n, target, result;
  
      // 输入数组大小
      printf("请输入升序数组的大小：");
      scanf("%d", &n);
  
      // 动态分配数组内存
      int *arr = (int *)malloc(n * sizeof(int));
      if (arr == NULL) {
          printf("内存分配失败！\n");
          return 1;
      }
  
      // 输入数组元素
      printf("请依次输入%d个升序整数：\n", n);
      for (int i = 0; i < n; i++) {
          scanf("%d", &arr[i]);
      }
  
      // 验证数组有序性
      if (!is_sorted(arr, n)) {
          printf("错误：数组不是升序排列！\n");
          free(arr);
          return 1;
      }
  
      // 输入要查找的目标值
      printf("请输入要查找的目标值：");
      scanf("%d", &target);
  
      // 执行二分查找
      result = binary_search(arr, n, target);
  
      // 输出结果
      if (result != -1) {
          printf("目标值 %d 在数组中的位置是第 %d 个元素（下标：%d）\n", 
                 target, result + 1, result);
      } else {
          printf("目标值 %d 未在数组中找到。\n", target);
      }
  
      // 释放动态分配的内存
      free(arr);
  
      return 0;
  }

• 

c. 插值查找

• 原理：根据目标值分布预测位置，适用于均匀分布的有序数据。

• 公式：𝑚𝑖𝑑=𝑙𝑜𝑤+(𝑡𝑎𝑟𝑔𝑒𝑡−𝑎𝑟𝑟[𝑙𝑜𝑤])𝑎𝑟𝑟[ℎ𝑖𝑔ℎ]−𝑎𝑟𝑟[𝑙𝑜𝑤]×(ℎ𝑖𝑔ℎ−𝑙𝑜𝑤)mid=low+arr[high]−arr[low](target−arr[low])​×(high−low)

• 时间复杂度：平均 𝑂(log⁡log⁡𝑛)O(loglogn)，最坏 𝑂(𝑛)O(n)。

d. 斐波那契查找

• 原理：利用斐波那契数列分割有序数组。

• 时间复杂度：𝑂(log⁡𝑛)O(logn)。

• 优势：避免二分查找的乘除运算，适合计算资源受限环境。

• 示例代码：

• #include <stdio.h>
  #include <stdlib.h>
  
  // 生成斐波那契数列，直到找到第一个 >= n 的斐波那契数
  int generateFibonacci(int n, int** fib) {
      if (n <= 0) return 0;
      int k = 0;
      int a = 0, b = 1, c = 1;
      // 计算所需的斐波那契数列长度
      while (c < n) {
          a = b;
          b = c;
          c = a + b;
          k++;
      }
  
      // 动态分配内存存储斐波那契数列
      *fib = (int*)malloc((k + 3) * sizeof(int)); // 多分配一些空间防止溢出
      (*fib)[0] = 0;
      (*fib)[1] = 1;
      for (int i = 2; ; i++) {
          (*fib)[i] = (*fib)[i - 1] + (*fib)[i - 2];
          if ((*fib)[i] >= n) {
              return i; // 返回斐波那契数列的索引k
          }
      }
  }
  
  // 斐波那契查找算法
  int fibonacciSearch(int arr[], int n, int target) {
      int* fib = NULL;
      int k = generateFibonacci(n, &fib); // 生成斐波那契数列
      int low = 0, high = n - 1;
      int mid;
  
      // 扩展数组到 F(k)-1 的长度
      int extendedSize = fib[k] - 1;
      int* extendedArr = (int*)malloc(extendedSize * sizeof(int));
      for (int i = 0; i < n; i++) extendedArr[i] = arr[i];
      for (int i = n; i < extendedSize; i++) extendedArr[i] = arr[n - 1]; // 填充末尾元素
  
      // 开始查找
      while (low <= high) {
          mid = low + fib[k - 1] - 1;
  
          if (target < extendedArr[mid]) {
              high = mid - 1;
              k -= 1; // 左半部分长度为 F(k-1)
          }
          else if (target > extendedArr[mid]) {
              low = mid + 1;
              k -= 2; // 右半部分长度为 F(k-2)
          }
          else {
              // 返回原始数组的索引（避免返回填充的位置）
              free(fib);
              free(extendedArr);
              return (mid < n) ? mid : n - 1;
          }
      }
  
      // 未找到
      free(fib);
      free(extendedArr);
      return -1;
  }
  
  /********************** 示例测试 **********************/
  int main() {
      int arr[] = { 1, 3, 5, 7, 9, 11 };
      int n = sizeof(arr) / sizeof(arr[0]);
      int target = 5;
  
      int index = fibonacciSearch(arr, n, target);
      if (index != -1) {
          printf("元素 %d 在数组中的索引为: %d\n", target, index);
      }
      else {
          printf("元素 %d 未找到\n", target);
      }
      return 0;
  }

  

三、动态查找方法

1. 适用场景

• 数据集合频繁插入、删除。

• 需要实时维护数据结构的平衡性。

• 示例：数据库索引、实时缓存系统。

2. 常用方法

a. 二叉搜索树（BST）

• 原理：左子树值 < 根 < 右子树值。

• 时间复杂度：平均 𝑂(log⁡𝑛)O(logn)，最坏 𝑂(𝑛)O(n)（退化为链表）。

• 代码示例：

• #include <stdio.h>
  #include <stdlib.h>
  
  // 定义二叉排序树节点结构
  typedef struct TreeNode 
  {
      int data;
      struct TreeNode* left;
      struct TreeNode* right;
  } TreeNode;
  //作用：定义二叉树的节点结构，每个节点包含：
  //data：存储整数值。
  //left 和 right：分别指向左子树和右子树的指针
  /*--------------------- 核心操作函数 ---------------------*/
  
  //
  
  // 创建新节点
  TreeNode* createNode(int value) {
      TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
      if (newNode == NULL) {
          fprintf(stderr, "内存分配失败！\n");
          exit(EXIT_FAILURE);
      }
      newNode->data = value;
      newNode->left = NULL;
      newNode->right = NULL;
      return newNode;
  }
  
  // 插入节点（递归实现）
  TreeNode* insertNode(TreeNode* root, int value) {
      if (root == NULL) {
          return createNode(value);
      }
      if (value < root->data) {
          root->left = insertNode(root->left, value);
      }
      else if (value > root->data) {
          root->right = insertNode(root->right, value);
      }
      // 如果值已存在，不做插入
      return root;
  }
  
  // 查找节点（递归实现）
  TreeNode* searchNode(TreeNode* root, int target) {
      if (root == NULL || root->data == target) {
          return root;
      }
      if (target < root->data) {
          return searchNode(root->left, target);
      }
      else {
          return searchNode(root->right, target);
      }
  }
  
  // 找到子树的最小节点（用于删除操作）
  TreeNode* findMinNode(TreeNode* node) {
      while (node->left != NULL) {
          node = node->left;
      }
      return node;
  }
  
  // 删除节点（递归实现）
  TreeNode* deleteNode(TreeNode* root, int key) {
      if (root == NULL) return root;
  
      // 定位要删除的节点
      if (key < root->data) {
          root->left = deleteNode(root->left, key);
      }
      else if (key > root->data) {
          root->right = deleteNode(root->right, key);
      }
      else {
          // 找到目标节点，处理三种情况：
          // 1. 无子节点或只有一个子节点
          if (root->left == NULL) {
              TreeNode* temp = root->right;
              free(root);
              return temp;
          }
          else if (root->right == NULL) {
              TreeNode* temp = root->left;
              free(root);
              return temp;
          }
          // 2. 有两个子节点：用右子树的最小节点替换当前节点
          TreeNode* temp = findMinNode(root->right);
          root->data = temp->data;
          root->right = deleteNode(root->right, temp->data);
      }
      return root;
  }
  
  // 中序遍历（升序输出）
  void inOrderTraversal(TreeNode* root) {
      if (root != NULL) {
          inOrderTraversal(root->left);
          printf("%d ", root->data);
          inOrderTraversal(root->right);
      }
  }
  
  // 释放二叉树内存
  void freeTree(TreeNode* root) {
      if (root == NULL) return;
      freeTree(root->left);
      freeTree(root->right);
      free(root);
  }
  
  /*--------------------- 测试用例 ---------------------*/
  int main() {
      TreeNode* root = NULL;
      int values[] = { 8, 3, 10, 1, 6, 14, 4, 7, 13 };
      int n = sizeof(values) / sizeof(values[0]);
  
      // 插入节点构建BST
      for (int i = 0; i < n; i++) {
          root = insertNode(root, values[i]);
      }
  
      // 中序遍历验证结构
      printf("中序遍历结果: ");
      inOrderTraversal(root);
      printf("\n");
  
      // 查找节点测试
      int searchKey = 6;
      TreeNode* result = searchNode(root, searchKey);
      if (result != NULL) {
          printf("找到节点 %d\n", searchKey);
      }
      else {
          printf("未找到节点 %d\n", searchKey);
      }
  
      // 删除节点测试
      printf("删除节点 6 后:\n");
      root = deleteNode(root, 6);
      inOrderTraversal(root);
      printf("\n");
  
      // 再次查找已删除节点
      result = searchNode(root, searchKey);
      if (result != NULL) {
          printf("错误: 节点 %d 未被正确删除\n", searchKey);
      }
      else {
          printf("节点 %d 已成功删除\n", searchKey);
      }
  
      // 释放内存
      freeTree(root);
      return 0;
  }

  

b. 平衡二叉树（AVL树、红黑树）

• 原理：通过旋转保持树平衡，确保高度差受限。

• 时间复杂度：严格 𝑂(log⁡𝑛)O(logn)。

• 应用场景：C++ STL的std::map（红黑树实现）。

• 示例代码：

• #include <stdio.h>
  #include <stdlib.h>
  
  // AVL树节点结构
  typedef struct AVLNode {
      int key;//节点存储的键值
      struct AVLNode* left;//左子节点指针
      struct AVLNode* right;//右子节点指针
      int height; // 节点高度（用于计算平衡因子）
  } AVLNode;
  
  // 辅助函数：获取节点高度
  int height(AVLNode* node) {
      return node ? node->height : 0;
  }
  
  // 辅助函数：计算平衡因子（左子树高度 - 右子树高度）
  //bf>1 左子树过高，需右旋
  //bf<1 右子树过高，需左旋
  int balanceFactor(AVLNode* node) 
  {
      return node ? height(node->left) - height(node->right) : 0;
  }
  
  // 辅助函数：更新节点高度
  //节点高度 = 左右子树中较高的高度 + 1
  //调用时机：插入、删除或旋转后需更新高度
  void updateHeight(AVLNode* node) 
  {
      if (node) {
          int leftHeight = height(node->left);
          int rightHeight = height(node->right);
          node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
      }
  }
  
  // 右旋操作（处理左左失衡）
  AVLNode* rightRotate(AVLNode* y) 
  {
      AVLNode* x = y->left;
      AVLNode* T2 = x->right;
  
      // 执行旋转
      x->right = y;
      y->left = T2;
  
      // 更新高度
      updateHeight(y);
      updateHeight(x);
  
      return x;
  }
  
  // 左旋操作（处理右右失衡）
  AVLNode* leftRotate(AVLNode* x) {
      AVLNode* y = x->right;
      AVLNode* T2 = y->left;
  
      // 执行旋转
      y->left = x;
      x->right = T2;
  
      // 更新高度
      updateHeight(x);
      updateHeight(y);
  
      return y;
  }
  
  // 平衡节点（四种失衡情况处理）
  AVLNode* balanceNode(AVLNode* node) {
      if (!node) return NULL;
  
      // 更新高度
      updateHeight(node);
  
      // 检查平衡因子
      int bf = balanceFactor(node);
  
      // 左左失衡
      if (bf > 1 && balanceFactor(node->left) >= 0)
          return rightRotate(node);
  
      // 右右失衡
      if (bf < -1 && balanceFactor(node->right) <= 0)
          return leftRotate(node);
  
      // 左右失衡
      if (bf > 1 && balanceFactor(node->left) < 0) {
          node->left = leftRotate(node->left);
          return rightRotate(node);
      }
  
      // 右左失衡
      if (bf < -1 && balanceFactor(node->right) > 0) {
          node->right = rightRotate(node->right);
          return leftRotate(node);
      }
  
      return node;
  }
  
  // 插入节点
  AVLNode* insert(AVLNode* node, int key) {
      // 执行标准BST插入
      if (!node) {
          AVLNode* newNode = (AVLNode*)malloc(sizeof(AVLNode));
          newNode->key = key;
          newNode->left = newNode->right = NULL;
          newNode->height = 1;
          return newNode;
      }
  
      if (key < node->key)
          node->left = insert(node->left, key);
      else if (key > node->key)
          node->right = insert(node->right, key);
      else
          return node; // 不允许重复键
  
      // 平衡当前节点
      return balanceNode(node);
  }
  
  // 找到最小值节点（用于删除操作）
  AVLNode* minValueNode(AVLNode* node) {
      while (node->left)
          node = node->left;
      return node;
  }
  
  // 删除节点
  AVLNode* deleteNode(AVLNode* root, int key) {
      if (!root) return root;
  
      // 执行标准BST删除
      if (key < root->key)//无左子节点，用右子节点替换
          root->left = deleteNode(root->left, key);
      else if (key > root->key)//无右子节点，用左子节点替换
          root->right = deleteNode(root->right, key);
      else //两个子节点，用右子树的最小节点替换当前值，再递归删除该最小节点
      {
          if (!root->left || !root->right) 
          {
              AVLNode* temp = root->left ? root->left : root->right;
              if (!temp) 
              {
                  temp = root;
                  root = NULL;
              }
              else
                  *root = *temp; // 复制内容
              free(temp);
          }
          else 
          {
              AVLNode* temp = minValueNode(root->right);
              root->key = temp->key;
              root->right = deleteNode(root->right, temp->key);
          }
      }
  
      if (!root) return root;
  
      // 平衡当前节点
      return balanceNode(root);
  }
  
  // 中序遍历
  void inOrder(AVLNode* root) 
  {
      if (root) {
          inOrder(root->left);
          printf("%d ", root->key);
          inOrder(root->right);
      }
  }
  
  // 释放内存
  void freeTree(AVLNode* root) {
      if (root) {
          freeTree(root->left);
          freeTree(root->right);
          free(root);
      }
  }
  
  // 测试用例
  int main() {
      AVLNode* root = NULL;
  
      // 测试插入
      root = insert(root, 10);
      root = insert(root, 20);
      root = insert(root, 30);  // 触发左旋
      root = insert(root, 40);
      root = insert(root, 50);
      root = insert(root, 25);  // 触发右左旋
  
      printf("中序遍历结果: ");
      inOrder(root);  // 输出: 10 20 25 30 40 50
      printf("\n");
  
      // 测试删除
      root = deleteNode(root, 30);
      printf("删除30后遍历: ");
      inOrder(root);  // 输出: 10 20 25 40 50
      printf("\n");
  
      freeTree(root);
      return 0;
  }

  

• 示例代码：C++ STL的std::map（红黑树实现）

• #include <iostream>
  #include <map>
  #include <string>
  
  using namespace std;
  
  int main() {
      // 创建一个空的map，键类型为int，值类型为string
      map<int, string> studentMap;
  
      // 插入元素的三种方式
      // 1. 使用insert和pair
      studentMap.insert(pair<int, string>(101, "Alice"));
      
      // 2. 使用insert和make_pair
      studentMap.insert(make_pair(102, "Bob"));
      
      // 3. 使用emplace（C++11+更高效的方式）
      studentMap.emplace(103, "Charlie");
      studentMap.emplace(105, "Eva");
      studentMap.emplace(104, "David");
  
      // 遍历map（自动按键升序排列）
      cout << "学生列表（学号顺序）：" << endl;
      for (const auto& pair : studentMap) {
          cout << "学号：" << pair.first 
               << "\t姓名：" << pair.second << endl;
      }
      /* 输出：
          学号：101    姓名：Alice
          学号：102    姓名：Bob
          学号：103    姓名：Charlie
          学号：104    姓名：David
          学号：105    姓名：Eva
      */
  
      // 查找元素
      int searchId = 103;
      auto it = studentMap.find(searchId);
      if (it != studentMap.end()) {
          cout << "\n找到学生：" << endl
               << "学号：" << it->first 
               << "\t姓名：" << it->second << endl;
      } else {
          cout << "\n未找到学号：" << searchId << endl;
      }
  
      // 删除元素
      int deleteId = 102;
      if (studentMap.erase(deleteId)) {
          cout << "\n已删除学号：" << deleteId << endl;
      } else {
          cout << "\n删除失败，学号不存在：" << deleteId << endl;
      }
  
      // 修改元素
      studentMap[104] = "Daniel";  // 通过键直接访问
      studentMap.at(101) = "Alex"; // 安全访问方式（会检查键是否存在）
  
      // 检查元素存在性
      cout << "\n104号学生存在性：" 
           << (studentMap.count(104) ? "存在" : "不存在") << endl;
  
      // 显示修改后的map
      cout << "\n更新后的学生列表：" << endl;
      for (auto iter = studentMap.begin(); iter != studentMap.end(); ++iter) {
          cout << "学号：" << iter->first 
               << "\t姓名：" << iter->second << endl;
      }
      /* 输出：
          学号：101    姓名：Alex
          学号：103    姓名：Charlie
          学号：104    姓名：Daniel
          学号：105    姓名：Eva
      */
  
      // 获取map信息
      cout << "\nMap大小：" << studentMap.size() << endl;
      cout << "最大容量：" << studentMap.max_size() << endl;
      cout << "是否为空：" << (studentMap.empty() ? "是" : "否") << endl;
  
      return 0;
  }

  

c. B树/B+树

• 原理：多路平衡树，减少磁盘I/O。

• B树特点：内部节点存储数据，适合文件系统。

• B+树特点：数据仅存于叶子节点，叶子形成链表，适合数据库索引。

• 示例代码：

• #include <stdio.h>
  #include <stdlib.h>
  #include <stdbool.h>
  
  #define MAX_ORDER 3  
  #define MIN_KEYS (MAX_ORDER/2)
  
  typedef struct BPlusTreeNode Node;
  
  struct BPlusTreeNode {
      int is_leaf;        
      int num_keys;       
      int keys[MAX_ORDER];
      union {
          Node **children; // 内部节点子节点指针（数组）
          void *values[MAX_ORDER]; // 叶子节点值指针（数组，修正此处）
      };
      Node *next; 
  };
  
  typedef struct {
      Node *root;
  } BPlusTree;
  
  Node* create_node(int is_leaf) {
      Node *node = (Node*)malloc(sizeof(Node));
      node->is_leaf = is_leaf;
      node->num_keys = 0;
      node->next = NULL;
      
      if (!is_leaf) { // 内部节点初始化子节点数组
          node->children = (Node**)malloc((MAX_ORDER + 1) * sizeof(Node*));
          for (int i = 0; i < MAX_ORDER + 1; i++) {
              node->children[i] = NULL;
          }
      }
      // 叶子节点的values数组无需手动初始化，malloc已分配内存
      return node;
  }
  
  Node* find_leaf(Node *root, int key) {
      // 无需修改
      if (!root) return NULL;
      Node *current = root;
      while (!current->is_leaf) {
          int i = 0;
          while (i < current->num_keys && key >= current->keys[i]) i++;
          current = current->children[i];
      }
      return current;
  }
  
  void insert_into_leaf(Node *leaf, int key, void *value) {
      int pos = 0;
      while (pos < leaf->num_keys && leaf->keys[pos] < key) pos++;
  
      // 移动键和值（修正为操作数组）
      for (int i = leaf->num_keys; i > pos; i--) {
          leaf->keys[i] = leaf->keys[i-1];
          leaf->values[i] = leaf->values[i-1]; // 操作数组元素
      }
  
      leaf->keys[pos] = key;
      leaf->values[pos] = value; // 存入数组对应位置
      leaf->num_keys++;
  }
  
  Node* split_leaf(Node *leaf) {
      Node *new_leaf = create_node(true);
      int split_pos = leaf->num_keys / 2;
  
      // 复制后半部分键和值到新节点（修正为数组操作）
      for (int i = split_pos; i < leaf->num_keys; i++) {
          new_leaf->keys[i - split_pos] = leaf->keys[i];
          new_leaf->values[i - split_pos] = leaf->values[i]; // 复制数组元素
      }
      
      new_leaf->num_keys = leaf->num_keys - split_pos;
      leaf->num_keys = split_pos;
      new_leaf->next = leaf->next;
      leaf->next = new_leaf;
      return new_leaf;
  }
  
  void insert(BPlusTree *tree, int key, void *value) {
      // 逻辑无需修改，但需确保values是数组
      if (!tree->root) {
          tree->root = create_node(true);
          insert_into_leaf(tree->root, key, value);
          return;
      }
  
      Node *leaf = find_leaf(tree->root, key);
      insert_into_leaf(leaf, key, value);
  
      if (leaf->num_keys == MAX_ORDER) {
          Node *new_leaf = split_leaf(leaf);
          int new_key = new_leaf->keys[0];
          
          Node *new_root = create_node(false);
          new_root->keys[0] = new_key;
          new_root->children[0] = leaf;
          new_root->children[1] = new_leaf;
          new_root->num_keys = 1;
          tree->root = new_root;
      }
  }
  
  void* search(BPlusTree *tree, int key) {
      if (!tree->root) return NULL;
      Node *leaf = find_leaf(tree->root, key);
      for (int i = 0; i < leaf->num_keys; i++) {
          if (leaf->keys[i] == key) {
              return leaf->values[i]; // 返回数组元素
          }
      }
      return NULL;
  }
  
  void print_tree(Node *node, int level) {
      // 无需修改
      if (!node) return;
      printf("Level %d: ", level);
      for (int i = 0; i < node->num_keys; i++) {
          printf("%d ", node->keys[i]);
      }
      printf("\n");
      if (!node->is_leaf) {
          for (int i = 0; i <= node->num_keys; i++) {
              print_tree(node->children[i], level + 1);
          }
      }
  }
  
  int main() {
      BPlusTree tree = {0};
      // 插入时仍需强制转换（C语言字符串字面量为const char*）
      insert(&tree, 5, (void*)"Apple");
      insert(&tree, 8, (void*)"Banana");
      insert(&tree, 3, (void*)"Cherry");
      insert(&tree, 7, (void*)"Date");
      insert(&tree, 12, (void*)"Fig");
      insert(&tree, 6, (void*)"Grape");
  
      printf("B+树结构：\n");
      print_tree(tree.root, 0);
  
      int keys[] = {5, 7, 10};
      for (int i = 0; i < 3; i++) {
          void *result = search(&tree, keys[i]);
          if (result) {
              printf("键 %d 找到值：%s\n", keys[i], (char*)result);
          } else {
              printf("键 %d 未找到\n", keys[i]);
          }
      }
      return 0;
  }

  

d. 哈希表

• 原理：通过哈希函数直接定位存储位置。

• 时间复杂度：平均 𝑂(1)O(1)，最坏 𝑂(𝑛)O(n)（冲突严重时）。

• 代码示例（开放寻址法）：

  #define HASH_SIZE 10007
  
  int hash(int key) { return key % HASH_SIZE; }
  
  int hash_search(int* table, int key) {
      int index = hash(key);
      while (table[index] != -1) { // -1表示空槽
          if (table[index] == key) return index;
          index = (index + 1) % HASH_SIZE; // 线性探测
      }
      return -1;
  }

四、方法选择策略

五、性能对比

六、实际应用案例

1. 数据库索引

   • B+树：MySQL的InnoDB引擎使用B+树索引，支持范围查询和高效磁盘访问。

   • 哈希索引：Memcached通过哈希表实现键值快速存取。

2. 文件系统

   • B树：NTFS文件系统用B树管理文件元数据，加速目录查找。

3. 编程语言标准库

   • 红黑树：C++的std::map、Java的TreeMap基于红黑树实现有序键值对。

   • 哈希表：Python的字典（dict）采用哈希表，支持平均 𝑂(1)O(1) 的查找。

七、总结

• 静态查找：适用于数据固定的场景，以预处理（如排序）换取高效查询，典型方法为二分查找。

• 动态查找：适用于数据频繁变动的场景，通过动态平衡结构（如AVL树、B+树）维护操作效率。

选择原则：根据数据变动频率、查询模式（精确/范围）、内存/磁盘访问特点综合选择。例如，数据库系统常组合使用B+树（范围查询）和哈希索引（精确匹配）以满足不同需求。