基于二叉搜索树的C语言简易数据库代码问题求助

核心问题排查方向 #

大规模测试失败的共性原因通常集中在以下几点：

• 唯一性判断逻辑漏洞：存储/查找/删除时，未同时校验year/month/day/name四个字段，仅比较部分字段导致重复或误判
• 内存操作错误：哈希表扩容时的野指针、内存泄漏，或BST节点删除后指针未正确清理，导致大规模操作后内存状态混乱
• 哈希表设计缺陷：哈希函数未覆盖所有字段，或冲突处理（如线性探测）在数据量大时出现堆积，引发效率暴跌甚至死循环
• BST退化问题：普通二叉搜索树在有序输入下退化成链表，导致大规模操作时间复杂度飙升，触发超时或逻辑错误
• 输入处理失效：scanf格式匹配错误，未校验返回值，大规模输入时出现指令解析混乱

替代实现方案（禁用链表） #

1. 有序数组+二分查找 #

实现简单、无复杂指针操作，适合大规模数据场景：

• 定义条目结构体：

  typedef struct {
      int year;
      int month;
      int day;
      char name[64]; // 根据需求调整长度
  } Entry;
  

• 全局维护动态数组及元素计数：

  Entry *db = NULL;
  size_t db_size = 0;
  

• 实现条目比较函数（用于二分查找和排序）：

  int compare_entries(const void *a, const void *b) {
      const Entry *ea = (const Entry *)a;
      const Entry *eb = (const Entry *)b;
      if (ea->year != eb->year) return ea->year - eb->year;
      if (ea->month != eb->month) return ea->month - eb->month;
      if (ea->day != eb->day) return ea->day - eb->day;
      return strcmp(ea->name, eb->name);
  }
  

• 核心操作逻辑：
  • 存储：用bsearch查找是否存在，不存在则realloc扩容数组，移动元素后插入；存在则输出Already stored
  • 查找：bsearch定位，找到输出Found，否则Not found
  • 删除：找到位置后，将后续元素向前移动覆盖，可选缩小数组容量

2. 改进版哈希表 #

修复原哈希表的设计缺陷：

• 覆盖全字段的哈希函数：

  #define TABLE_SIZE 100003 // 选用质数作为表长
  unsigned int hash_entry(const Entry *e) {
      unsigned int hash = e->year;
      hash = hash * 31 + e->month;
      hash = hash * 31 + e->day;
      for (const char *p = e->name; *p; p++) {
          hash = hash * 31 + (unsigned char)*p;
      }
      return hash % TABLE_SIZE;
  }
  

• 双重哈希解决冲突（避免线性探测的堆积问题）：

  unsigned int hash2(const Entry *e) {
      return (e->day + 1) % (TABLE_SIZE - 1) + 1; // 保证与TABLE_SIZE互质
  }
  

• 负载因子控制：当元素数量超过表长70%时，扩容为原表长的2倍（仍取质数）并重新哈希

3. AVL平衡二叉搜索树 #

解决普通BST的退化问题，保证O(logn)操作时间：

• 节点结构增加高度字段：

  typedef struct AVLNode {
      Entry data;
      int height;
      struct AVLNode *left;
      struct AVLNode *right;
  } AVLNode;
  

• 实现核心辅助函数：
  • get_height：获取节点高度
  • update_height：更新节点高度
  • get_balance：计算平衡因子
  • 左旋、右旋操作：维护树的平衡

关键细节检查 #

无论选用哪种方案，必须确保：

• 所有操作的唯一性判断严格同时校验四个字段
• 输入读取时校验scanf返回值，处理无效输入：

  char op;
  int y, m, d;
  char name[64];
  if (scanf("%c: %d %d %d %s", &op, &y, &m, &d, name) != 5) {
      while(getchar() != '\n'); // 跳过无效行
      continue;
  }
  

• 动态内存操作时，检查realloc/malloc返回值，避免空指针操作

调试建议 #

• 加入日志输出：记录大规模测试中的每步操作及中间状态，快速定位错误点
• 边界用例测试：覆盖最大/最小年份、日期边界值、连续重复存储/删除等场景
• 内存检测：用valgrind排查内存泄漏、野指针等问题

内容的提问来源于stack exchange，提问作者123