Data Structures and Algorithms in C++

这是一个基于 C++ 模板类实现的通用数据结构与算法库，涵盖了计算机科学中常用的基础组件。项目旨在通过简洁的 C++ 实现，展示数据结构的核心原理及其效率优化。

🚀 核心内容

1. 线性结构 (Linear Structures)

• Vector: 动态数组实现，支持自动扩容（push_back）、随机访问（operator[]）及迭代器。
• List: 单链表实现，支持头插、尾插及指定节点后的插入。
• String (KMP): 实现了高效的子串搜索算法（KMP 算法），包含 lps (部分匹配表) 的计算。

2. 树形结构 (Tree Structures)

• BinTree: 二叉树基础实现，包含前/中/后序遍历、计算最大直径（maxDistance）以及根据先序和中序序列重建二叉树。
• ThreadTree: 线索二叉树，实现了中序线索化，支持高效的中序遍历（前驱/后继查找）。
• BinSearchTree: 二叉搜索树（BST），支持基础的插入、删除和递归查找。
• AVLTree: 高度平衡的二叉搜索树，通过四种旋转（L, R, LR, RL）在插入和删除时保持树的平衡。
• GenList: 广义表实现，支持原子项和子表的复合结构，包含从字符串解析（conv）和等价性判断（equal）。

3. 图与并查集 (Graph & Disjoint Set)

• Graph: 基于邻接表实现的图结构。

• 支持 Dijkstra 算法的两种实现：普通 O(V²) 版本和基于 priority_queue 的 O(E log V) 优化版本。

• Disjoint Set: 并查集实现，包含路径压缩（Path Compression）优化。

4. 堆与排序 (Heap & Sorting)

• Heap: 最小堆（Min-Heap）实现，支持 siftup 和 siftdown 操作。
• Sorts: 包含多种排序算法的对比分析：
• 基础排序：冒泡排序、插入排序、选择排序。
• 高效排序：希尔排序（标准及 Knuth 序列）、快速排序、堆排序、归并排序。
• 内置工具：提供了 benchmark 函数，用于测量不同算法在不同规模数据下的耗时。

🛠 代码特点

• 泛型设计: 大部分数据结构使用 template <typename T> 实现，支持存储任意类型。
• 内存管理: 各类中均实现了析构函数以递归释放动态分配的内存，防止内存泄漏。
• 标准兼容: 提供了类似 STL 的接口（如 begin(), end(), push_back()），方便上手使用。

📈 性能测试

在 sorts.h 中内置了基准测试工具，可以直观地观察到 算法与 算法在处理大规模数据时的性能差异。

---

事实上，对于大部分的数据结构，应当禁止默认的拷贝构造函数和拷贝函数。