概述

Data Structs and Algorithms(DSA)

版本号：14.2.0，与 CMakeLists.txt 同步

• 第一位：架构
• 第二位：api
• 第三位：小版本号

我自己实现的各种数据结构和算法的模板，采用 C++20 语言标准，统一在 DSA 命名空间中，支持跨平台

使用说明

环境要求

通用

1. Asan（DEBUG 模式需要）
2. 容器元素必须支持operator<<（DEBUG 模式需要）

Linux

1. 编译器：gcc version 14.2.0 (Ubuntu 14.2.0-4ubuntu2~24.04)
2. 调试器：GNU gdb (Ubuntu 15.0.50.20240403-0ubuntu1) 15.0.50.20240403-git
3. CMake：cmake version 3.31.1
4. Graphviz（DEBUG 模式需要）

Windows

1. 编译器：Visual Studio 2022 (v143)

构建步骤

以 Linux 平台为例，Windows 打开DSA.sln用 Visual Studio 2022 Build 即可：

• 按照 C++ 开发的一般规范，声明以及模板卸载头文件即 .h 文件中，实现代码写在 .cpp 源文件中
• 增加源文件需要在src/CMakeLists.txt文件中的“添加库源文件”中添加
• 如果增加了头文件目录，需要在src/CMakeLists.txt文件中的“安装头文件”中添加
• 执行tool/build_debug.sh进行构建调试版（VSCode task: Build debug），会启用 AddressSanitizer(asan) 有助于内存分析
• 执行tool/build_release.sh进行构建发布版（VSCode task: Build release）
• 构建好的头文件、库文件和文档都在目标目录dist目录下
• 执行tool/clean.sh可以对项目进行 clean（VSCode task: Clean）

单元测试

• 在test目录下编写单元测试代码，命名规范为：test_xxx.cpp
• 在项目构建好后，执行tool/run_test.sh脚本（Linux）即可运行单元测试（VSCode task: Run test）
• 可以运行 Python3 脚本进行测试，执行tool/run_python_test.sh脚本（Windows 下为tool/run_python_test.bat）即可（VSCode task: Run python test，与 Asan 不太兼容，故只支持 RELEASE 模式构建的），Python 脚本的执行入口为test/python/main.py
• Windows 下用 VS 打开项目解决方案DSA.sln后将 test 项目设置为启动项目

性能分析

• Vtune：使用 Vtune 工具进行性能分析（推荐）
• gperftools：（与 Asan 不太兼容，故只支持 RELEASE 模式构建的）对于 Linux 环境下，安装 gperftools，运行tool/run_test_with_gperftools.sh会生成性能分析报告dsa-test.prof及dsa-test.pdf（VSCode task：Run test on Linux with gperftools）

内容

通用算法（模板）

1. 字典序比较操作符

2. 区间内最大值与最小值的查找算法

3. 交换算法

4. 查找算法

   • 顺序查找

   • 二分查找

   • 斐波那契查找

5. 排序算法

   • 选择排序

   • 插入排序

   • 冒泡排序

   • 归并排序

   • 快速排序

   • 堆排序

   • 希尔排序

6. 匹配算法

   • 括号匹配

   • 串匹配算法

     • 蛮力算法

     • KMP 算法

7. 找中位数算法

   • 两个有序序列合并后的中位数

8. 逆置算法

9. Remove 算法

10. 整数幂算法

11. TopK 算法

12. Shuffle 算法

13. 素数判断算法

容器（模板）类

1. 向量

2. 位域

3. 链表

4. 双向队列

5. 堆栈

6. 队列

7. 树

   • 二叉树

     • 普通二叉树

     • 二叉搜索树

       • AVL 树

       • 伸展树

       • 红黑树

   • B 树

   • B+ 树

   • 前缀树

8. 算术表达式

9. 字符串

10. 并查集

11. Map

    • TreeMap

    • 键值对 KVPair

    • HashMap

12. 堆

    • 普通堆

    • 左式堆

13. 素数表

14. 集合

    • FlatHashSet

    • HashSet

    • TreeSet

15. 图

    • 邻接表

    • 邻接矩阵

    • 图算法

      • 深度优先搜索 dfs

      • 广度优先搜索 bfs

      • 最短路径

        • Dijkstra（包括堆优化与普通）

        • Floyd

      • 连通集个数

      • 回路判断

        • 欧拉回路

        • 半欧拉回路

      • 最小生成树

        • Prim

        • Kruskal

      • 拓扑排序

16. 树状数组

特殊工具

1. 智能指针

   • Shared_ptr

   • Weak_ptr

2. 迭代器

   • 单向迭代器

   • 双向迭代器

   • 随机访问迭代器

3. 单元测试模板

4. 内存分配器

5. Asset 宏

6. Python3 调用接口

参考资料

1. 《数据结构》3rd-邓俊辉
2. http://en.cppreference.com/w/
3. 《C++ Primer》5th-Stanley B. Lippman, Josée Lajoie, Barbara E. Moo
4. 《Effective C++》3rd-Scott Meyers
5. 《数据结构》2nd-陈越
6. 《2019年数据结构考研复习指导》-王道论坛组编
7. 《Database System Concepts》6th-Abraham Silberschatz, Henry F. Korth, S. Sudarshan
8. 《STL 源码剖析》-侯捷
9. 《C++ 内存管理》-侯捷 10.《Computer Systems A Programmer's Perspective》3e-Randal E.Bryant, David R. O'Hallaron

TODO

• 实现稀疏集
• 整理一下编译规则，在 Windows 下也使用 CMake，参考 SCGF 项目
• 将其用在 SCGF 项目中
• 实现树状数组（区间）
• 实现 KD 树
• 优化树的打印方法
• 哈希表容器元素用指针（桶）而不是原始元素
• 全组合算法（参考 《Lua 程序设计》4th-p6.6）