Appearance
查找算法综合项目
本项目包含两大核心任务，旨在帮助学习者深入理解静态查找表、动态查找树、哈希表与 Trie 等查找结构的设计思想、性能差异和工程应用。
可使用的查找结构范围：顺序查找、有序表查找、静态树表、索引顺序表、BST、AVL 树、B-树、B+ 树、Trie、哈希表。
子项目一：校园资料智能检索系统
系统面向图书、课程资料、学生信息或校园公告等数据场景，用户可以通过编号、标题、关键词、前缀、分类等条件快速查询目标记录。项目重点不是做复杂的数据库系统，而是让不同查找结构在合适的查询场景中发挥作用。
系统示例数据：
| ID | 标题 | 分类 | 关键词 | 热度 |
|---|---|---|---|---|
| 1001 | 数据结构实验指导 | 课程资料 | 数据结构, 实验, C++ | 95 |
| 1002 | 图书馆借阅规则 | 校园公告 | 图书馆, 借阅 | 60 |
| 1003 | 查找算法复习提纲 | 课程资料 | 查找, 哈希表, AVL | 88 |
用户可执行的操作：按 ID 精确查找、按标题前缀查找、按关键词查找相关资料、按分类筛选、插入/删除/修改记录、查看热门资料或查询统计信息。
查找结构的应用场景
| 查询场景 | 适配结构 | 理由 |
|---|---|---|
| 精确查找（按 ID） | 哈希表、BST、AVL 树 | O(1)~O(log n) 精确定位 |
| 有序查找与范围查询 | 有序表、AVL 树、B+ 树 | 区间查询效率高 |
| 动态维护（频繁插入删除） | BST、AVL 树、B-树 | 动态平衡结构 |
| 关键词与前缀检索 | Trie、哈希表、倒排索引 | 逐字符路径匹配 |
| 外存索引模拟 | 索引顺序表、B-树、B+ 树 | 多级索引、磁盘分块 |
项目要求
- 数据结构设计：合理设计数据结构来表示资料记录、索引、关键词集合、查找结果和系统状态。
- 功能实现：实现资料初始化、插入、删除、修改、精确查找、范围查找、前缀查找、关键词查找和查询统计等功能。
- 结构选型说明：至少选择两类以上查找结构用于不同功能，并解释为什么该结构适合对应场景。
- 用户交互：设计简单的用户界面（命令行或图形界面）与用户交互，展示查询条件、查询结果、查找路径或统计信息。
- 代码质量：编写清晰、可维护的代码，并添加适当的注释和文档。
子项目二：多类查找结构性能横向对比
对多类查找结构进行标准化性能测评，对比查找效率、构造开销、插入删除代价、空间占用和适用场景。
测评数据集设计
- 小规模：100~1000 条，观察查找路径和结构变化。
- 中等规模：1 万~10 万条，基础性能对比。
- 近乎有序：验证 BST 退化、AVL 平衡效果。
- 随机分布：一般场景平均性能测试。
- 大量重复关键字：冲突处理与重复记录管理。
- 字符串关键字：Trie、哈希表和字符串查找结构测试。
测评指标
- 查找成功平均比较次数（平均查找长度 ASL）
- 查找失败平均比较次数或探测次数
- 构造索引或建表时间
- 插入、删除、修改操作耗时
- 哈希表冲突次数、冲突率和装填因子影响
- 树结构高度、旋转次数或节点分裂次数
- 空间占用大小
- 理论复杂度与实测结果对比
输出结果要求：性能对比表格、查询路径或结构变化过程展示、不同结构优劣分析报告、面向应用场景的查找结构选择指南、复杂度总结与学习心得。
评分标准
| 维度 | 权重 | 评价要点 |
|---|---|---|
| 功能实现 | 30% | 根据项目要求设计功能，实现完整的查找、更新和结果展示流程 |
| 数据结构设计 | 30% | 合理选择并实现查找结构，能说明结构特点、适用场景和优缺点 |
| 性能分析 | 20% | 完成多场景测试，给出 ASL、构造开销、冲突率等关键指标分析 |
| 用户交互与代码质量 | 20% | 界面清晰，代码结构合理，可维护性好，包含必要注释和文档 |
注：评分标准同时基于你的报告和实际程序内容进行评估。
目录结构建议
src/：源代码data/：测试数据result/：性能测试结果report/：实验报告main.cpp：统一入口，通过菜单选择应用项目或测评项目