UDataStructures

一个使用 C++ 实现的数据结构学习项目，用于记录常见数据结构的基本操作、教材课后习题、测试用例和学习笔记。

项目以“实现基础接口 → 完成章节习题 → 编写测试验证”为主线。代码尽量保持简单直接，便于回顾数据结构本身，而不是隐藏在复杂的工程框架中。

当前进度

模块	基本实现	测试	课后习题
顺序表	已完成	已完成	持续补充
单链表	已完成	已完成	待补充
双链表	计划中	计划中	计划中
栈与队列	计划中	计划中	计划中
串	计划中	计划中	计划中
树	计划中	计划中	计划中
图	计划中	计划中	计划中
查找与排序	计划中	计划中	计划中

目前已经实现：

• 顺序表的初始化、查找、插入、删除、遍历、判空和销毁。
• 带头结点单链表的初始化、查找、插入、删除、头插建表、尾插建表、遍历、判空和销毁。
• 线性表章节的部分课后习题。
• 顺序表和单链表的基本操作、边界条件测试。

环境要求

• 支持 C++17 的编译器，例如 GCC、Clang 或 MSVC。
• CMake 3.20 或更高版本。
• 可选：Ninja，用于更快、更简洁地执行构建。

构建项目

在项目根目录执行：

cmake -S . -B build
cmake --build build

如果使用 Ninja：

cmake -S . -B build -G Ninja
cmake --build build

CMake 会构建数据结构核心库 ds_core、已启用的课后习题以及测试程序。

运行测试

项目使用 CTest 管理测试，不依赖第三方测试框架：

cmake -S . -B build -DBUILD_TESTING=ON
cmake --build build
ctest --test-dir build --output-on-failure

也可以直接运行单个测试程序：

./build/tests/test_seq_list
./build/tests/test_singly_linked_list

在使用多配置生成器（例如 Visual Studio）时，需要在构建和测试命令中指定配置：

cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

运行课后习题

每道习题都是一个独立的可执行程序。完成构建后，可以直接运行对应目标。例如：

./build/exercises/ch02_linear_list/ch02_sub02_q01_delete_min

不同平台或 CMake 生成器可能会将可执行文件放在不同位置。如果无法确定路径，可以使用下面的命令先构建指定习题：

cmake --build build --target ch02_sub02_q01_delete_min

项目结构

项目按照数据结构类别组织公共接口、实现、课后习题、测试和笔记。下面是项目逐步扩展时采用的整体结构：

UDataStructures/
├── CMakeLists.txt
├── README.md
│
├── cmake/
│   └── add_exercise.cmake
│
├── include/
│   └── ds/
│       ├── linear/
│       │   ├── seq_list.h
│       │   ├── singly_linked_list.h
│       │   └── doubly_linked_list.h
│       │
│       ├── stack_queue/
│       │   ├── seq_stack.h
│       │   ├── linked_stack.h
│       │   ├── seq_queue.h
│       │   └── linked_queue.h
│       │
│       ├── string/
│       │   └── string.h
│       │
│       ├── tree/
│       │   ├── binary_tree.h
│       │   └── threaded_tree.h
│       │
│       ├── graph/
│       │   ├── adjacency_matrix.h
│       │   └── adjacency_list.h
│       │
│       └── search_sort/
│           ├── search.h
│           └── sort.h
│
├── src/
│   ├── linear/
│   │   ├── seq_list.cc
│   │   ├── singly_linked_list.cc
│   │   └── doubly_linked_list.cc
│   │
│   ├── stack_queue/
│   ├── string/
│   ├── tree/
│   ├── graph/
│   └── search_sort/
│
├── exercises/
│   ├── CMakeLists.txt
│   │
│   ├── ch02_linear_list/
│   │   ├── CMakeLists.txt
│   │   ├── sub02_q01_delete_min.cc
│   │   ├── sub02_q02_reverse_seq_list.cc
│   │   ├── sub02_q03_delete_value.cc
│   │   ├── sub02_q04_delete_range.cc
│   │   └── ...
│   │
│   ├── ch03_stack_queue/
│   ├── ch04_string/
│   ├── ch05_tree/
│   ├── ch06_graph/
│   ├── ch07_search/
│   └── ch08_sort/
│
├── tests/
│   ├── CMakeLists.txt
│   ├── test_seq_list.cc
│   ├── test_singly_linked_list.cc
│   └── ...
│
└── notes/
    ├── linear_list.md
    ├── stack_queue.md
    ├── tree.md
    └── mistakes.md

部分目录和文件代表后续规划，会随着学习进度逐步添加。当前课后习题文件名还会包含教材小节编号，例如 sub02_q01_delete_min.cc，用于避免不同小节之间题号重复。

代码约定

接口与实现

• 公共接口放在 include/ds/ 下。
• 对应实现放在 src/ 下。
• ds_core 静态库统一提供数据结构实现。
• 接口注释记录操作含义和时间复杂度。

位序与下标

数据结构接口中的“位序”从 1 开始，例如 GetElem(L, 1) 表示第一个元素；直接访问底层数组时，下标仍然从 0 开始。

顺序表

顺序表使用静态数组存储，当前最大容量由 MAXSIZE 定义，默认值为 100。

单链表

单链表采用带头结点的实现。调用其他操作前，应先通过 InitList 初始化；使用完成后应调用 DestroyList 释放结点。交互式头插和尾插建表以输入 -1 作为结束标记。

课后习题

每道习题尽量记录：

• 题目位置和题号。
• 解题思路。
• 时间复杂度和空间复杂度。
• 容易出错的地方。
• 一个能够直接运行的示例或断言。

习题目标名称使用“章节 + 小节 + 题号 + 简短描述”的格式，例如：

ch02_sub02_q01_delete_min

添加新的数据结构

以添加双链表为例：

1. 在 include/ds/linear/ 中添加 doubly_linked_list.h。
2. 在 src/linear/ 中添加 doubly_linked_list.cc。
3. 将实现文件加入根目录 CMakeLists.txt 中的 ds_core。
4. 在 tests/ 中添加对应测试文件。
5. 在 tests/CMakeLists.txt 中注册测试目标。

添加新的课后习题

在对应章节目录中创建源文件，然后使用 add_ds_exercise 注册目标：

add_ds_exercise(
    ch02_sub02_q04_delete_range
    sub02_q04_delete_range.cc
)

add_ds_exercise 会创建可执行程序、链接 ds_core，并启用项目统一的编译警告选项。

学习目标

这个项目主要关注：

• 理解数据结构的存储方式和基本操作。
• 熟悉操作中的边界条件和失败情况。
• 能够分析算法的时间复杂度与空间复杂度。
• 通过测试及时发现位序、指针和内存管理问题。
• 保留错题和易错点，形成可以持续复习的代码资料。

License

本项目采用 Apache License 2.0 协议开源。

你可以自由使用、修改、分发本项目，但必须：

• 保留原作者署名 (Siaospeed)
• 在引用时注明原项目来源

Copyright 2026 Siaospeed

欢迎提交 Issue 或 Pull Request。