数据结构与算法实现

数据结构与算法实现

1, 顺序表（SeqList）

顺序表是线性表的顺序存储结构，它是用一组地址连续的存储单元依次存储线性表中的各个元素。

特点：

• 随机访问： 可以在O(1)时间内通过下标直接访问任意元素
• 存储密度高： 数据元素之间不需要额外空间存储逻辑关系
• 插入和删除操作需要移动大量元素： 时间复杂度为O(n)
• 需要预分配内存空间： 可能存在空间浪费或溢出问题

时间复杂度分析：

• 按位查找（getElem）：O(1)
• 按值查找（locateElem）：平均O(n)
• 插入操作（insertElem）：平均O(n)，最坏O(n)
• 删除操作（deleteElem）：平均O(n)，最坏O(n)
• 追加操作（appendElem）：O(1)

顺序表扩容机制：
通常顺序表满时，会创建一个更大的数组（如原来的1.5倍或2倍），并将原数据复制到新数组中，然后释放旧数组。这是动态数组（如C++ STL vector）的核心实现机制。

应用场景：

• 需要频繁随机访问元素的场景
• 存储密度要求高的场景
• 元素数量变化不大或可以预估的场景

// 定义默认最大容量（解决MAX_SIZE未定义问题）
const int MAX_SIZE = 100;

template <typename ElemType>
class SeqList {
private:
    ElemType* elem;  // 动态数组存储元素
    int length;      // 当前表长
    int max_size;    // 最大容量

public:
    // 构造函数（默认容量/自定义容量）
    SeqList(int size = MAX_SIZE) {
        if (size <= 0) {
            throw invalid_argument("Size must be positive");
        }
        max_size = size;
        elem = new ElemType[max_size];  // 动态分配内存
        length = 0;
    }

    // 拷贝构造函数（深拷贝，避免浅拷贝问题）
    SeqList(const SeqList& other) {
        max_size = other.max_size;
        length = other.length;
        elem = new ElemType[max_size];
        // 逐元素拷贝
        for (int i = 0; i < length; i++) {
            elem[i] = other.elem[i];
        }
    }

    // 赋值运算符重载（深拷贝）
    SeqList& operator=(const SeqList& other) {
        if (this == &other) {  // 防止自赋值
            return *this;
        }

        // 释放当前对象的内存
        delete[] elem;

        // 深拷贝其他对象的内容
        max_size = other.max_size;
        length = other.length;
        elem = new ElemType[max_size];
        for (int i = 0; i < length; i++) {
            elem[i] = other.elem[i];
        }

        return *this;
    }
    
    // C++11 移动构造函数（提高性能）
    SeqList(SeqList&& other) noexcept {
        max_size = other.max_size;
        length = other.length;
        elem = other.elem;
        // 将原对象置为空状态，避免双重释放
        other.elem = nullptr;
        other.length = 0;
        other.max_size = 0;
    }
    
    // C++11 移动赋值运算符（提高性能）
    SeqList& operator=(SeqList&& other) noexcept {
        if (this != &other) {
            delete[] elem;  // 释放当前对象的资源
            
            // 接管other的资源
            max_size = other.max_size;
            length = other.length;
            elem = other.elem;
            
            // 将原对象置为空状态
            other.elem = nullptr;
            other.length = 0;
            other.max_size = 0;
        }
        return *this;
    }

    // 析构函数（释放动态内存）
    ~SeqList() {
        delete[] elem;
        elem = nullptr;  // 避免野指针
    }

    // 获取表长
    int getLength() const {
        return length;
    }

    // 按位查找（i从1开始）
    ElemType getElem(int i) const {
        if (i < 1 || i > length) {
            throw out_of_range("Index out of range (getElem)");
        }
        return elem[i - 1];
    }
    
    // 按位查找的安全版本（返回引用，支持修改）
    ElemType& operator[](int i) {
        if (i < 1 || i > length) {
            throw out_of_range("Index out of range (operator[])");
        }
        return elem[i - 1];
    }

    // 按值查找（返回位置，找不到返回0）
    int locateElem(ElemType e) const {
        for (int i = 0; i < length; i++) {
            if (elem[i] == e) {
                return i + 1;  // 位置从1开始
            }
        }
        return 0;  // 未找到
    }
    
    // 按值查找的更通用版本（支持自定义比较函数）
    template <typename Compare>
    int locateElem(ElemType e, Compare comp) const {
        for (int i = 0; i < length; i++) {
            if (comp(elem[i], e)) {
                return i + 1;
            }
        }
        return 0;
    }

    // 插入元素到第i位
    void insertElem(int i, ElemType e) {
        // 插入位置范围：1 <= i <= length+1（支持表尾插入）
        if (i < 1 || i > length + 1) {
            throw out_of_range("Index out of range (insertElem)");
        }
        // 判断表是否已满
        if (isFull()) {
            // 动态扩容（扩展为原来的1.5倍）
            resize(max_size * 3 / 2);
        }

        // 从后往前移动元素，腾出第i位的位置
        for (int j = length; j >= i; j--) {
            elem[j] = elem[j - 1];
        }
        elem[i - 1] = e;  // 插入新元素
        length++;         // 表长+1
    }
    
    // 动态扩容方法
    void resize(int new_size) {
        if (new_size <= max_size) {
            return;  // 新容量不大于原容量，不扩容
        }
        
        ElemType* new_elem = new ElemType[new_size];
        // 复制原数据
        for (int i = 0; i < length; i++) {
            new_elem[i] = elem[i];
        }
        
        // 释放旧内存，更新指针和容量
        delete[] elem;
        elem = new_elem;
        max_size = new_size;
    }

    // 追加元素到表尾
    void appendElem(ElemType e) {
        if (isFull()) {
            // 动态扩容
            resize(max_size * 3 / 2);
        }
        elem[length++] = e;
    }

    // 删除第i位元素
    void deleteElem(int i) {
        if (i < 1 || i > length) {
            throw out_of_range("Index out of range (deleteElem)");
        }

        // 从i位置开始，后续元素前移
        for (int j = i; j < length; j++) {
            elem[j - 1] = elem[j];
        }
        length--;  // 表长-1
        
        // 可以添加缩容逻辑，当元素数量远小于容量时释放多余空间
        if (length < max_size / 4 && max_size > MAX_SIZE) {
            resize(max_size / 2);
        }
    }
    
    // 清空表
    void clear() {
        length = 0;
        // 注意：这里没有释放内存，只是重置了表长
        // 如果需要完全释放内存并重置，可以调用delete和new
    }

    // 判断是否为空表
    bool isEmpty() const {
        return length == 0;
    }

    // 判断是否满表
    bool isFull() const {
        return length == max_size;
    }
    
    // 获取当前容量
    int getCapacity() const {
        return max_size;
    }

    // 遍历打印顺序表（方便测试）
    void printList() const {
        if (isEmpty()) {
            cout << "SeqList is empty" << endl;
            return;
        }
        cout << "SeqList elements: ";
        for (int i = 0; i < length; i++) {
            cout << elem[i] << " ";
        }
        cout << endl;
    }
    
    // 合并两个顺序表
    void merge(const SeqList& other) {
        // 预分配足够空间，避免多次扩容
        int new_length = length + other.length;
        if (new_length > max_size) {
            resize(max(new_length, max_size * 3 / 2));
        }
        
        // 直接追加other中的元素
        for (int i = 0; i < other.length; i++) {
            elem[length++] = other.elem[i];
        }
    }
};

2, 单链表（Linked List）

单链表是一种常见的线性表链式存储结构，它通过指针将分散存储的结点连接起来，形成一个线性序列。

单链表的特点：

• 动态存储： 不需要预分配固定大小的内存，可根据需要动态增减结点
• 非连续存储： 物理存储上不连续，数据元素之间通过指针链接
• 插入删除效率高： 在已知位置的情况下，插入和删除操作时间复杂度为O(1)
• 随机访问效率低： 访问第i个元素需要从表头开始遍历，时间复杂度为O(n)
• 存储开销大： 每个元素需要额外空间存储指针

单链表的基本结构：

• 头结点： 通常不存储数据，指向第一个数据结点，方便操作统一
• 数据结点： 包含数据域和指针域（指向下一个结点）
• 尾结点： 指向nullptr（C++）或NULL的最后一个结点

时间复杂度分析：

• 按位查找（getElem）：O(n)
• 按值查找（locateElem）：平均O(n)
• 插入操作（insertElem）：已知位置时O(1)，未知位置时O(n)
• 删除操作（deleteElem）：已知位置时O(1)，未知位置时O(n)
• 追加操作（appendElem）：O(n)

单链表vs顺序表对比：

• 空间分配： 链表动态分配，顺序表静态或动态数组
• 内存利用： 链表不连续但有额外指针开销，顺序表连续存储利用率高
• 操作效率： 链表插入删除快，顺序表随机访问快

应用场景：

• 需要频繁插入删除操作的场景（如频繁修改的链表）
• 数据量变化较大且无法预估的场景
• 不需要频繁随机访问的场景
• 实现其他数据结构（如栈、队列、图的邻接表等）

// 单链表类（带头结点，非循环）
template <typename ElemType>
class LinkList {
private:
    // 单链表结点结构体（内部嵌套）
    struct LNode {
        ElemType data;   // 数据域
        LNode* next;     // 后继指针
        // 结点构造函数（默认值更安全）
        LNode(ElemType val = ElemType(), LNode* nxt = nullptr)
                : data(val), next(nxt) {}
    };

    LNode* head;   // 头结点指针（固定指向头结点，不存储数据）
    int length;    // 表长（直接维护，避免遍历）

public:
    // 构造函数：初始化空链表（带头结点）
    LinkList() {
        head = new LNode();  // 创建头结点
        length = 0;          // 空链表长度为0
    }
    
    // 拷贝构造函数（深拷贝）
    LinkList(const LinkList& other) {
        head = new LNode();  // 创建头结点
        length = 0;
        
        // 复制链表内容
        LNode* pOther = other.head->next;
        LNode* pCurrent = head;
        
        while (pOther != nullptr) {
            pCurrent->next = new LNode(pOther->data);
            pCurrent = pCurrent->next;
            pOther = pOther->next;
            length++;
        }
    }
    
    // 赋值运算符重载（深拷贝）
    LinkList& operator=(const LinkList& other) {
        if (this == &other) {  // 防止自赋值
            return *this;
        }
        
        // 清空当前链表
        clear();
        
        // 复制链表内容
        LNode* pOther = other.head->next;
        LNode* pCurrent = head;
        
        while (pOther != nullptr) {
            pCurrent->next = new LNode(pOther->data);
            pCurrent = pCurrent->next;
            pOther = pOther->next;
            length++;
        }
        
        return *this;
    }
    
    // C++11 移动构造函数
    LinkList(LinkList&& other) noexcept {
        head = other.head;
        length = other.length;
        
        // 将原对象置为空状态
        other.head = new LNode();
        other.length = 0;
    }
    
    // C++11 移动赋值运算符
    LinkList& operator=(LinkList&& other) noexcept {
        if (this != &other) {
            // 释放当前链表资源
            clear();
            delete head;
            
            // 接管other的资源
            head = other.head;
            length = other.length;
            
            // 将原对象置为空状态
            other.head = new LNode();
            other.length = 0;
        }
        return *this;
    }

    // 析构函数：销毁所有结点（包括头结点）
    ~LinkList() {
        clear();
        delete head;
        head = nullptr;
    }

    // ========== 核心接口 ==========
    // 获取表长
    int getLength() const {
        return length;
    }

    // 按位查找（i从1开始），返回对应元素值
    // 异常：索引越界时抛出out_of_range
    ElemType getElem(int i) const {
        if (i < 1 || i > length) {
            throw out_of_range("LinkList::getElem: 索引越界，合法范围[1, " + to_string(length) + "]");
        }
        LNode* p = head->next;  // 从第一个数据结点开始
        for (int j = 1; j < i; j++) {  // 遍历到第i个结点
            p = p->next;
        }
        return p->data;
    }
    
    // 获取指向第i个元素的指针（内部使用）
    LNode* getElemNode(int i) const {
        if (i < 0 || i > length) {
            return nullptr;
        }
        
        LNode* p = head;
        for (int j = 0; j < i; j++) {
            p = p->next;
        }
        return p;
    }

    // 按值查找，返回第一个匹配元素的位置（i从1开始），未找到返回0
    int locateElem(const ElemType& e) const {
        LNode* p = head->next;
        int pos = 1;
        while (p != nullptr) {
            if (p->data == e) {
                return pos;  // 找到，返回位置
            }
            p = p->next;
            pos++;
        }
        return 0;  // 未找到
    }
    
    // 按值查找的通用版本（支持自定义比较函数）
    template <typename Compare>
    int locateElem(const ElemType& e, Compare comp) const {
        LNode* p = head->next;
        int pos = 1;
        while (p != nullptr) {
            if (comp(p->data, e)) {
                return pos;
            }
            p = p->next;
            pos++;
        }
        return 0;
    }

    // 插入元素到第i位（i从1开始，支持表尾插入）
    // 异常：索引越界时抛出out_of_range
    void insertElem(int i, const ElemType& e) {
        if (i < 1 || i > length + 1) {
            throw out_of_range("LinkList::insertElem: 插入位置越界，合法范围[1, " + to_string(length + 1) + "]");
        }
        // 找到第i-1个结点（前驱结点）
        LNode* p = getElemNode(i - 1);
        // 创建新结点，插入到p之后
        LNode* newNode = new LNode(e, p->next);
        p->next = newNode;
        length++;  // 表长+1
    }

    // 尾插法添加元素（简化接口）
    void appendElem(const ElemType& e) {
        insertElem(length + 1, e);  // 复用插入逻辑，避免重复代码
    }
    
    // 头插法添加元素
    void prependElem(const ElemType& e) {
        insertElem(1, e);
    }

    // 删除第i位元素，返回被删除的元素值
    // 异常：索引越界时抛出out_of_range
    ElemType deleteElem(int i) {
        if (i < 1 || i > length) {
            throw out_of_range("LinkList::deleteElem: 删除位置越界，合法范围[1, " + to_string(length) + "]");
        }
        // 找到第i-1个结点（前驱结点）
        LNode* p = getElemNode(i - 1);
        LNode* temp = p->next;    // 待删除结点
        ElemType deletedVal = temp->data;  // 保存被删除值
        p->next = temp->next;     // 断开链表
        delete temp;              // 释放内存
        length--;                 // 表长-1
        return deletedVal;        // 返回被删除值
    }

    // 判断链表是否为空
    bool isEmpty() const {
        return length == 0;
    }
    
    // 清空链表（保留头结点）
    void clear() {
        while (!isEmpty()) {
            deleteElem(1);
        }
    }
    
    // 合并两个有序链表（假设元素按升序排列）
    void mergeSorted(const LinkList& other) {
        if (other.isEmpty()) {
            return;  // 另一个链表为空，无需合并
        }
        
        // 创建新链表保存合并结果
        LinkList tempList;
        LNode* p1 = head->next;
        LNode* p2 = other.head->next;
        LNode* p3 = tempList.head;
        
        // 合并两个有序链表
        while (p1 != nullptr && p2 != nullptr) {
            if (p1->data <= p2->data) {
                p3->next = new LNode(p1->data);
                p1 = p1->next;
            } else {
                p3->next = new LNode(p2->data);
                p2 = p2->next;
            }
            p3 = p3->next;
            tempList.length++;
        }
        
        // 处理剩余元素
        while (p1 != nullptr) {
            p3->next = new LNode(p1->data);
            p1 = p1->next;
            p3 = p3->next;
            tempList.length++;
        }
        while (p2 != nullptr) {
            p3->next = new LNode(p2->data);
            p2 = p2->next;
            p3 = p3->next;
            tempList.length++;
        }
        
        // 将合并后的结果移到当前链表
        clear();
        head->next = tempList.head->next;
        length = tempList.length;
        tempList.head->next = nullptr;
        tempList.length = 0;
    }

    // ========== 扩展接口 ==========
    // 头插法建表（数组元素逆序插入）
    void createListHead(const ElemType arr[], int n) {
        if (n < 0) {
            throw invalid_argument("LinkList::createListHead: 数组长度不能为负数");
        }
        // 先清空原有链表（可选，根据需求）
        clear();
        for (int i = 0; i < n; i++) {
            insertElem(1, arr[i]);  // 每次插入到第1位
        }
    }

    // 尾插法建表（数组元素顺序插入）
    void createListTail(const ElemType arr[], int n) {
        if (n < 0) {
            throw invalid_argument("LinkList::createListTail: 数组长度不能为负数");
        }
        // 先清空原有链表（可选）
        clear();
        for (int i = 0; i < n; i++) {
            appendElem(arr[i]);  // 每次插入到表尾
        }
    }
    
    // 反转链表
    void reverse() {
        if (length <= 1) {
            return;  // 空表或只有一个元素，无需反转
        }
        
        LNode* prev = nullptr;
        LNode* curr = head->next;
        LNode* next = nullptr;
        
        while (curr != nullptr) {
            next = curr->next;  // 暂存下一个结点
            curr->next = prev;  // 反转指针
            prev = curr;        // 前指针后移
            curr = next;        // 当前指针后移
        }
        
        head->next = prev;  // 头结点指向新的第一个结点
    }

    // 打印链表（调试用）
    void printList() const {
        if (isEmpty()) {
            cout << "LinkList is empty" << endl;
            return;
        }
        LNode* p = head->next;
        cout << "LinkList: ";
        while (p != nullptr) {
            cout << p->data << " -> ";
            p = p->next;
        }
        cout << "nullptr (length: " << length << ")" << endl;
    }
    
    // 获取链表第i个元素的引用（便于修改操作）
    ElemType& at(int i) {
        if (i < 1 || i > length) {
            throw out_of_range("LinkList::at: 索引越界，合法范围[1, " + to_string(length) + "]");
        }
        
        LNode* p = head->next;
        for (int j = 1; j < i; j++) {
            p = p->next;
        }
        return p->data;
    }
    
    // 获取最后一个元素
    ElemType back() const {
        if (isEmpty()) {
            throw underflow_error("LinkList::back: 链表为空");
        }
        return getElem(length);
    }
    
    // 获取第一个元素
    ElemType front() const {
        if (isEmpty()) {
            throw underflow_error("LinkList::front: 链表为空");
        }
        return getElem(1);
    }
};

3, 双向循环链表类（DuLinkList）

双向循环链表是在双向链表基础上进一步发展而来的数据结构，它既允许向前遍历，也允许向后遍历，并且首尾相连形成一个环形结构。

双向循环链表的特点：

• 双向遍历能力： 每个结点同时拥有前驱指针和后继指针，可以双向遍历
• 循环连接： 尾结点的后继指向头结点，头结点的前驱指向尾结点，形成闭环
• 头结点哨兵： 使用头结点作为哨兵，简化边界条件处理
• 插入删除高效： 在已知位置的情况下，插入删除操作只需O(1)时间，且无需额外查找前驱
• 额外空间开销： 每个结点需要额外存储一个前驱指针，空间开销较大

双向循环链表的基本结构：

• 头结点： 不存储数据，是链表的入口点，head->prior指向尾结点，head->next指向第一个数据结点
• 数据结点： 包含数据域、前驱指针和后继指针
• 尾结点： 最后一个数据结点，其next指向头结点，prior指向倒数第二个结点

时间复杂度分析：

• 按位查找（getElem）：O(n)
• 按值查找（locateElem）：平均O(n)
• 插入操作（insertElem）：已知位置时O(1)，未知位置时O(n)
• 删除操作（deleteElem）：已知位置时O(1)，未知位置时O(n)
• 追加操作：O(1)（利用循环特性可以直接访问尾结点）
• 双向遍历：从任意位置可向前或向后遍历，O(n)

双向循环链表vs单链表对比：

• 遍历方向： 单链表只能单向遍历，双向链表可双向遍历
• 操作效率： 双向链表在某些操作（如逆向遍历、已知结点删除）上更高效
• 空间开销： 双向链表需要额外存储前驱指针，空间开销更大
• 复杂度： 双向链表实现逻辑稍复杂，但使用更灵活

应用场景：

• 需要频繁双向遍历的场景
• 需要在任意位置进行高效插入删除操作的场景
• 需要实现循环队列、双向队列等数据结构
• 文本编辑器中的撤销/重做操作
• 操作系统中的进程调度表

// 双向循环链表类（带头结点，循环设计）
template <typename ElemType>
class DuLinkList {
private:
    // 双向链表结点结构体
    struct DulNode {
        ElemType data;    // 数据域
        DulNode* prior;   // 前驱指针
        DulNode* next;    // 后继指针
        // 结点构造函数
        DulNode(ElemType val = ElemType(), DulNode* pre = nullptr, DulNode* nxt = nullptr)
                : data(val), prior(pre), next(nxt) {}
    };

    DulNode* head;  // 头结点指针（循环链表的固定头）
    int length;     // 表长

public:
    // 构造函数：初始化双向循环空链表
    DuLinkList() {
        head = new DulNode();        // 创建头结点
        head->prior = head;          // 前驱指向自身（循环）
        head->next = head;           // 后继指向自身（循环）
        length = 0;                  // 空链表长度为0
    }
    
    // 拷贝构造函数（深拷贝）
    DuLinkList(const DuLinkList& other) {
        head = new DulNode();        // 创建头结点
        head->prior = head;      // 初始化为空循环链表
        head->next = head;
        length = 0;
        
        // 复制其他链表的内容
        DulNode* pOther = other.head->next;
        DulNode* pCurrent = head;
        
        while (pOther != other.head) {
            pCurrent->next = new DulNode(pOther->data, pCurrent, head);
            pCurrent = pCurrent->next;
            pOther = pOther->next;
            length++;
        }
        
        // 更新头结点的前驱指针，确保循环特性
        head->prior = pCurrent;
    }
    
    // 赋值运算符重载（深拷贝）
    DuLinkList& operator=(const DuLinkList& other) {
        if (this == &other) {  // 防止自赋值
            return *this;
        }
        
        // 清空当前链表
        clear();
        
        // 复制其他链表的内容
        DulNode* pOther = other.head->next;
        DulNode* pCurrent = head;
        
        while (pOther != other.head) {
            pCurrent->next = new DulNode(pOther->data, pCurrent, head);
            pCurrent = pCurrent->next;
            pOther = pOther->next;
            length++;
        }
        
        // 更新头结点的前驱指针
        head->prior = pCurrent;
        
        return *this;
    }
    
    // C++11 移动构造函数
    DuLinkList(DuLinkList&& other) noexcept {
        head = other.head;
        length = other.length;
        
        // 将原对象置为空状态
        other.head = new DulNode();
        other.head->prior = other.head;
        other.head->next = other.head;
        other.length = 0;
    }
    
    // C++11 移动赋值运算符
    DuLinkList& operator=(DuLinkList&& other) noexcept {
        if (this != &other) {
            // 释放当前链表资源
            clear();
            delete head;
            
            // 接管other的资源
            head = other.head;
            length = other.length;
            
            // 将原对象置为空状态
            other.head = new DulNode();
            other.head->prior = other.head;
            other.head->next = other.head;
            other.length = 0;
        }
        return *this;
    }

    // 析构函数：销毁所有结点
    ~DuLinkList() {
        clear();
        delete head;
        head = nullptr;
    }
    
    // 获取指向第i个元素的指针（内部使用，支持高效操作）
    DulNode* getElemNode(int i) const {
        if (i < 0 || i > length) {
            return nullptr;
        }
        
        // 优化：根据i的位置选择从前往后或从后往前遍历
        if (i <= length / 2) {  // 前半部分，从前向后遍历
            DulNode* p = head->next;
            for (int j = 1; j < i; j++) {
                p = p->next;
            }
            return p;
        } else {  // 后半部分，从后向前遍历
            DulNode* p = head->prior;
            for (int j = length; j > i; j--) {
                p = p->prior;
            }
            return p;
        }
    }

    // ========== 核心接口 ==========
    // 获取表长
    int getLength() const {
        return length;
    }

    // 按位查找（i从1开始），返回对应元素值
    ElemType getElem(int i) const {
        if (i < 1 || i > length) {
            throw out_of_range("DuLinkList::getElem: 索引越界，合法范围[1, " + to_string(length) + "]");
        }
        
        DulNode* p = getElemNode(i);
        return p->data;
    }
    
    // 获取链表第i个元素的引用（便于修改操作）
    ElemType& at(int i) {
        if (i < 1 || i > length) {
            throw out_of_range("DuLinkList::at: 索引越界，合法范围[1, " + to_string(length) + "]");
        }
        
        DulNode* p = getElemNode(i);
        return p->data;
    }
    
    // 获取第一个元素
    ElemType front() const {
        if (isEmpty()) {
            throw underflow_error("DuLinkList::front: 链表为空");
        }
        return head->next->data;
    }
    
    // 获取最后一个元素（利用循环特性，O(1)时间）
    ElemType back() const {
        if (isEmpty()) {
            throw underflow_error("DuLinkList::back: 链表为空");
        }
        return head->prior->data;
    }
    
    // 按值查找，返回第一个匹配元素的位置，未找到返回0
    int locateElem(const ElemType& e) const {
        if (isEmpty()) return 0;
        DulNode* p = head->next;
        int pos = 1;
        while (p != head) {          // 遍历到循环头结束
            if (p->data == e) {
                return pos;
            }
            p = p->next;
            pos++;
        }
        return 0;
    }
    
    // 按值查找的通用版本（支持自定义比较函数）
    template <typename Compare>
    int locateElem(const ElemType& e, Compare comp) const {
        if (isEmpty()) return 0;
        DulNode* p = head->next;
        int pos = 1;
        while (p != head) {
            if (comp(p->data, e)) {
                return pos;
            }
            p = p->next;
            pos++;
        }
        return 0;
    }

    // 插入元素到第i位（i从1开始）
    void insertElem(int i, const ElemType& e) {
        if (i < 1 || i > length + 1) {
            throw out_of_range("DuLinkList::insertElem: 插入位置越界，合法范围[1, " + to_string(length + 1) + "]");
        }
        
        // 找到第i-1个结点（前驱结点）
        DulNode* p = (i == 1) ? head : getElemNode(i - 1);
        
        // 创建新结点，调整前驱后继指针
        DulNode* newNode = new DulNode(e, p, p->next);
        p->next->prior = newNode;    // 原后继的前驱指向新结点
        p->next = newNode;           // 前驱的后继指向新结点
        length++;                    // 表长+1
    }
    
    // 尾插法添加元素（O(1)时间）
    void appendElem(const ElemType& e) {
        // 利用循环特性，直接在尾结点后插入
        DulNode* tail = head->prior;
        DulNode* newNode = new DulNode(e, tail, head);
        tail->next = newNode;
        head->prior = newNode;
        length++;
    }
    
    // 头插法添加元素
    void prependElem(const ElemType& e) {
        insertElem(1, e);
    }

    // 删除第i位元素，返回被删除的元素值
    ElemType deleteElem(int i) {
        if (i < 1 || i > length) {
            throw out_of_range("DuLinkList::deleteElem: 删除位置越界，合法范围[1, " + to_string(length) + "]");
        }
        
        // 找到第i个结点
        DulNode* p = getElemNode(i);
        ElemType deletedVal = p->data;  // 保存被删除值
        
        // 调整前驱后继指针
        p->prior->next = p->next;
        p->next->prior = p->prior;
        delete p;                       // 释放内存
        length--;                       // 表长-1
        return deletedVal;              // 返回被删除值
    }
    
    // 清空链表（保留头结点）
    void clear() {
        while (!isEmpty()) {
            deleteElem(1);
        }
    }
    
    // 反转链表
    void reverse() {
        if (length <= 1) {
            return;  // 空表或只有一个元素，无需反转
        }
        
        // 交换每个结点的prior和next指针
        DulNode* p = head;
        do {
            // 交换prior和next指针
            DulNode* temp = p->next;
            p->next = p->prior;
            p->prior = temp;
            
            // 移动到下一个原前驱（反转后的后继）
            p = p->next;
        } while (p != head);
    }

    // 判断链表是否为空
    bool isEmpty() const {
        return length == 0;
    }

    // 打印链表（调试用）
    void printList() const {
        if (isEmpty()) {
            cout << "DuLinkList is empty" << endl;
            return;
        }
        DulNode* p = head->next;
        cout << "DuLinkList: ";
        while (p != head) {
            cout << p->data << " <-> ";
            p = p->next;
        }
        cout << "head (length: " << length << ")" << endl;
    }
    
    // 逆向打印链表（从尾到头）
    void printListReverse() const {
        if (isEmpty()) {
            cout << "DuLinkList is empty" << endl;
            return;
        }
        DulNode* p = head->prior;  // 从尾结点开始
        cout << "DuLinkList (reversed): ";
        while (p != head) {
            cout << p->data << " <-> ";
            p = p->prior;
        }
        cout << "head (length: " << length << ")" << endl;
    }
    
    // 从数组创建双向循环链表
    void createFromArray(const ElemType arr[], int n) {
        if (n < 0) {
            throw invalid_argument("DuLinkList::createFromArray: 数组长度不能为负数");
        }
        
        clear();  // 清空原有内容
        for (int i = 0; i < n; i++) {
            appendElem(arr[i]);  // 使用O(1)的尾插法
        }
    }
};

4, 栈的实现（顺序存储和链式存储）

栈（Stack）是一种遵循**后进先出（LIFO, Last In First Out）**原则的线性数据结构，它只允许在一端（称为栈顶）进行插入和删除操作。

栈的基本特点：

• 操作受限： 只允许在栈顶进行插入（入栈/压栈）和删除（出栈/弹栈）操作
• LIFO特性： 最后进入栈的元素最先被取出
• 线性结构： 元素之间存在一对一的线性关系
• 抽象数据类型： 定义了一组操作接口，与具体实现无关

栈的主要操作：

• 初始化（InitStack）： 创建一个空栈
• 入栈（Push）： 在栈顶插入新元素
• 出栈（Pop）： 移除并返回栈顶元素
• 取栈顶元素（GetTop/Peek）： 返回栈顶元素但不移除
• 判空（IsEmpty）： 判断栈是否为空
• 判满（IsFull）： 判断顺序栈是否已满
• 获取长度（GetLength）： 获取栈中元素个数

栈的应用场景：

• 函数调用的管理
• 表达式求值
• 括号匹配验证
• 算法的回溯实现
• 内存管理
• 浏览器的前进/后退功能

顺序栈（SeqStack）：

顺序栈是使用数组实现的栈，具有以下特点：

• 优点： 实现简单，存储密度高，入栈出栈操作时间复杂度为O(1)
• 缺点： 静态空间有限，可能发生栈溢出；动态扩容时需要额外时间开销
• 适用场景： 预先知道栈最大容量，且操作频繁的场景

顺序栈的基本结构：

• 数组：用于存储栈元素
• 栈顶指针：指示当前栈顶位置，初始值为-1表示空栈
• 最大容量：栈的最大存储元素数量

顺序栈的时间复杂度：

• 入栈（push）：O(1)
• 出栈（pop）：O(1)
• 取栈顶元素（getTop）：O(1)
• 判空/判满（isEmpty/isFull）：O(1)
• 获取长度（getLength）：O(1)

链栈（LinkStack）：

链栈是使用单链表实现的栈，具有以下特点：

• 优点： 动态分配空间，不存在栈满问题；不需要预先确定大小
• 缺点： 每个元素需要额外空间存储指针，存储密度较低；操作时需要动态内存管理
• 适用场景： 无法预估栈大小，需要灵活扩展的场景

链栈的基本结构：

• 单链表节点：包含数据域和指针域
• 栈顶指针：指向链表头节点，作为栈的唯一访问点
• 链表长度：维护栈中元素数量

链栈的时间复杂度：

• 入栈（push）：O(1)
• 出栈（pop）：O(1)
• 取栈顶元素（getTop）：O(1)
• 判空（isEmpty）：O(1)
• 获取长度（getLength）：O(1)

顺序栈与链栈对比：

• 空间效率： 顺序栈存储密度高，链栈每个元素需要额外指针空间
• 时间效率： 两者基本操作均为O(1)时间复杂度，但链栈需要动态内存分配和释放
• 实现复杂度： 顺序栈实现简单，链栈稍复杂
• 空间限制： 顺序栈有容量限制，链栈无此限制
• 内存管理： 顺序栈内存连续，链栈内存分散

template <typename ElemType>
class SeqStack {
private:
    static const int MAX_STACK_SIZE = 100;  // 栈的最大容量
    ElemType stack_array[MAX_STACK_SIZE];  // 存储栈元素的数组
    int top;                               // 栈顶指针（top=-1 表示空栈）

public:
    // 构造函数（初始化空栈）
    SeqStack() : top(-1) {}
    
    // 拷贝构造函数
    SeqStack(const SeqStack& other) : top(other.top) {
        // 复制数组内容
        for (int i = 0; i <= top; i++) {
            stack_array[i] = other.stack_array[i];
        }
    }
    
    // 赋值运算符重载
    SeqStack& operator=(const SeqStack& other) {
        if (this != &other) {
            // 清空当前栈并复制内容
            top = other.top;
            for (int i = 0; i <= top; i++) {
                stack_array[i] = other.stack_array[i];
            }
        }
        return *this;
    }
    
    // C++11 移动构造函数
    SeqStack(SeqStack&& other) noexcept : top(other.top) {
        // 直接复制数组内容（对于栈这种静态数组实现，移动和复制区别不大）
        for (int i = 0; i <= top; i++) {
            stack_array[i] = std::move(other.stack_array[i]);
        }
        // 重置原栈
        other.top = -1;
    }
    
    // C++11 移动赋值运算符
    SeqStack& operator=(SeqStack&& other) noexcept {
        if (this != &other) {
            top = other.top;
            for (int i = 0; i <= top; i++) {
                stack_array[i] = std::move(other.stack_array[i]);
            }
            other.top = -1;
        }
        return *this;
    }

    // 核心接口
    bool isEmpty() const {
        return top == -1;
    }                  // 判断栈是否为空
    bool isFull() const {
        return top == MAX_STACK_SIZE - 1;
    }                  // 判断栈是否满
    void push(ElemType e) {
        if (isFull()) {
            throw overflow_error("SeqStack::push: 栈已满，无法压栈");
        }
        stack_array[++top] = e;
    }                 // 入栈（压栈）
    ElemType pop() {
        if (isEmpty()) {
            throw underflow_error("SeqStack::pop: 栈为空，无法弹栈");
        }
        return stack_array[top--];
    }                 // 出栈（弹栈）
    ElemType getTop() const {
        if (isEmpty()) {
            throw underflow_error("SeqStack::getTop: 栈为空，无法获取栈顶元素");
        }
        return stack_array[top];
    }                 // 获取栈顶元素（不弹出）
    int getLength() const {
        return top + 1;
    }                 // 获取栈中元素个数
    
    // 清空栈
    void clear() {
        top = -1;  // 简单地将栈顶指针重置为-1
    }
    
    // 打印栈内容（调试用）
    void printStack() const {
        if (isEmpty()) {
            cout << "SeqStack is empty" << endl;
            return;
        }
        cout << "SeqStack: [";
        for (int i = 0; i <= top; i++) {
            cout << stack_array[i];
            if (i < top) {
                cout << ", ";
            }
        }
        cout << "] (top: " << stack_array[top] << ")" << endl;
    }
};

template <typename ElemType>
class LinkStack {
private:
    // 链栈结点（内部嵌套类）
    struct StackNode {
        ElemType data;
        StackNode* next;
        // 结点构造函数
        StackNode(ElemType val = 0, StackNode* nxt = nullptr)
                : data(val), next(nxt) {}
    };

    StackNode* top;  // 栈顶指针（兼作头指针，无额外头结点）
    int length;      // 栈长（直接维护，避免遍历）

public:
    // 构造函数（初始化空栈）
    LinkStack() : top(nullptr), length(0) {}
    
    // 拷贝构造函数（深拷贝）
    LinkStack(const LinkStack& other) : top(nullptr), length(0) {
        if (!other.isEmpty()) {
            // 创建新链表，采用尾插法（避免栈顺序颠倒）
            StackNode* pOther = other.top;
            StackNode* tempStack = nullptr;  // 临时栈，用于反转节点顺序
            
            // 先将原栈内容复制到临时栈（会反转顺序）
            while (pOther != nullptr) {
                tempStack = new StackNode(pOther->data, tempStack);
                pOther = pOther->next;
            }
            
            // 再从临时栈复制回目标栈（恢复原顺序）
            StackNode* pTemp = tempStack;
            StackNode** pDest = &top;  // 使用二级指针简化头插法实现
            
            while (pTemp != nullptr) {
                *pDest = new StackNode(pTemp->data);
                pDest = &((*pDest)->next);
                pTemp = pTemp->next;
                length++;
            }
            
            // 清理临时栈
            while (tempStack != nullptr) {
                StackNode* temp = tempStack;
                tempStack = tempStack->next;
                delete temp;
            }
        }
    }
    
    // 赋值运算符重载
    LinkStack& operator=(const LinkStack& other) {
        if (this != &other) {
            // 清空当前栈
            while (top != nullptr) {
                StackNode* temp = top;
                top = top->next;
                delete temp;
            }
            length = 0;
            
            // 复制其他栈的内容
            if (!other.isEmpty()) {
                StackNode* pOther = other.top;
                StackNode* tempStack = nullptr;
                
                // 先复制到临时栈
                while (pOther != nullptr) {
                    tempStack = new StackNode(pOther->data, tempStack);
                    pOther = pOther->next;
                }
                
                // 再复制回目标栈
                StackNode* pTemp = tempStack;
                StackNode** pDest = &top;
                
                while (pTemp != nullptr) {
                    *pDest = new StackNode(pTemp->data);
                    pDest = &((*pDest)->next);
                    pTemp = pTemp->next;
                    length++;
                }
                
                // 清理临时栈
                while (tempStack != nullptr) {
                    StackNode* temp = tempStack;
                    tempStack = tempStack->next;
                    delete temp;
                }
            }
        }
        return *this;
    }
    
    // C++11 移动构造函数
    LinkStack(LinkStack&& other) noexcept : top(other.top), length(other.length) {
        // 转移资源所有权
        other.top = nullptr;
        other.length = 0;
    }
    
    // C++11 移动赋值运算符
    LinkStack& operator=(LinkStack&& other) noexcept {
        if (this != &other) {
            // 释放当前资源
            while (top != nullptr) {
                StackNode* temp = top;
                top = top->next;
                delete temp;
            }
            
            // 转移资源所有权
            top = other.top;
            length = other.length;
            
            // 重置原对象
            other.top = nullptr;
            other.length = 0;
        }
        return *this;
    }

    // 析构函数（释放所有结点）
    ~LinkStack() {
        while (top != nullptr) {
            StackNode* temp = top;
            top = top->next;
            delete temp;
        }
    }

    // 核心接口
    bool isEmpty() const {
        return top == nullptr;
    }                  // 判断栈是否为空
    void push(ElemType e) {
        top = new StackNode(e, top);
        length++;
    }                  // 入栈
    ElemType pop() {
        if (isEmpty()) {
            throw underflow_error("LinkStack::pop: 栈为空，无法弹栈");
        }
        ElemType poppedVal = top->data;
        StackNode* temp = top;
        top = top->next;
        delete temp;
        length--;
        return poppedVal;
    }                 // 出栈
    ElemType getTop() const {
        if (isEmpty()) {
            throw underflow_error("LinkStack::getTop: 栈为空，无法获取栈顶元素");
        }
        return top->data;
    }                 // 获取栈顶元素（不弹出）
    int getLength() const {
        return length;
    }                 // 获取栈长
    
    // 清空栈
    void clear() {
        while (top != nullptr) {
            StackNode* temp = top;
            top = top->next;
            delete temp;
        }
        length = 0;
    }
    
    // 打印栈内容（调试用）
    void printStack() const {
        if (isEmpty()) {
            cout << "LinkStack is empty" << endl;
            return;
        }
        cout << "LinkStack: [";
        StackNode* p = top;
        // 使用临时数组存储，以便按正确顺序显示
        vector<ElemType> elements;
        while (p != nullptr) {
            elements.push_back(p->data);
            p = p->next;
        }
        // 逆序输出，以匹配栈的逻辑顺序
        for (auto it = elements.rbegin(); it != elements.rend(); ++it) {
            cout << *it;
            if (next(it) != elements.rend()) {
                cout << ", ";
            }
        }
        cout << "] (top: " << top->data << ")" << endl;
    }
};

5, 队列的实现（顺序存储和链式存储）

链式队列（LinkQueue）

链式队列是队列的链式存储实现，通过单链表结构存储队列元素，避免了顺序队列的容量限制问题。

工作原理：

• 使用带头结点的单链表实现
• 队首指针（front）指向头结点
• 队尾指针（rear）指向队尾元素
• 入队操作：在队尾（rear）后添加新结点
• 出队操作：删除队首（front->next）结点
• 队列为空的判断条件：front == rear

时间复杂度分析：

• 入队（enQueue）：O(1)
• 出队（deQueue）：O(1)
• 获取队首元素（getHead）：O(1)
• 判断队列空（isEmpty）：O(1)
• 获取队列长度（getLength）：O(1)

优缺点：

• 优点：动态分配空间，不需要预先确定容量，不会出现假溢出问题
• 缺点：每个元素需要额外的空间存储指针，空间利用率相对较低

应用场景：

• 元素数量不确定的队列应用
• 频繁进行入队出队操作的场景
• 需要避免空间浪费的场合

使用示例：

template <typename ElemType>
class CircularQueue {
private:
    static const int MAX_QUEUE_SIZE = 100;  // 队列的最大容量
    ElemType queue_array[MAX_QUEUE_SIZE];  // 存储队列元素的数组
    int front;                             // 队首指针（指向队首元素前一个位置）
    int rear;                              // 队尾指针（指向队尾元素）

public:
    // 构造函数（初始化空队列）
    CircularQueue() : front(0), rear(0) {}

    // 核心接口
    bool isEmpty() const {
        return front == rear;
    }                  // 判断队列是否为空（front == rear）
    bool isFull() const {
        return (rear + 1) % MAX_QUEUE_SIZE == front;
    }                  // 判断队列是否满（(rear+1)%MAX_QUEUE_SIZE == front）
    void enQueue(ElemType e) {
        if (isFull()) {
            throw overflow_error("CircularQueue::enQueue: 队列已满，无法入队");
        }
        rear = (rear + 1) % MAX_QUEUE_SIZE;
        queue_array[rear] = e;
    }               // 入队（队尾插入）
    ElemType deQueue() {
        if (isEmpty()) {
            throw underflow_error("CircularQueue::deQueue: 队列为空，无法出队");
        }
        ElemType dequeuedVal = queue_array[(front + 1)%MAX_QUEUE_SIZE];
        front = (front + 1) % MAX_QUEUE_SIZE;
        return dequeuedVal;
    }              // 出队（队首删除）
    ElemType getHead() const {
        if (isEmpty()) {
            throw underflow_error("CircularQueue::getHead: 队列为空，无法获取队首元素");
        }
        // 修正：直接返回，无需临时变量e
        return queue_array[(front + 1) % MAX_QUEUE_SIZE];
    }       // 获取队首元素（不删除）
    int getLength() const {
        return (rear - front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    }                 // 获取队列长度
};

template <typename ElemType>
class LinkQueue {
private:
    // 链队列结点（内部嵌套类）
    struct QNode {
        ElemType data;
        QNode* next;
        // 结点构造函数
        QNode(ElemType val = 0, QNode* nxt = nullptr)
                : data(val), next(nxt) {}
    };

    QNode* front;  // 队首指针（指向头结点）
    QNode* rear;   // 队尾指针（指向队尾元素）
    int length;    // 队列长度

public:
    // 构造函数（初始化空队列，创建头结点）
    LinkQueue() {
        front = rear = new QNode();
        front->next = nullptr;
        length = 0;
    }

    // 析构函数（释放所有结点）
    ~LinkQueue() {
        while (front != nullptr) {
            QNode* temp = front;
            front = front->next;
            delete temp;
        }
    }

    // 核心接口
    bool isEmpty() const {
        return front == rear;
    }                 // 判断队列是否为空
    void enQueue(ElemType e) {
        rear->next = new QNode(e);
        rear = rear->next;
        length++;
    }               // 入队
    ElemType deQueue() {
        if (isEmpty()) {
            throw underflow_error("LinkQueue::deQueue: 队列为空，无法出队");
        }
        ElemType dequeuedVal = front->next->data;
        QNode* temp = front->next;
        front->next = temp->next;
        if (rear == temp) {
            rear = front;
        }
        delete temp;
        length--;
        return dequeuedVal;
    }             // 出队
    ElemType getHead() const {
        if (isEmpty()) {
            throw underflow_error("LinkQueue::getHead: 队列为空，无法获取队首元素");
        }
        return front->next->data;
    }        // 获取队首元素
    int getLength() const {
        return length;
    }                 // 获取队列长度
};

6, 字符串类（String）

1. 定长字符串（FixedString）核心理论

（1）数据结构本质

采用静态字符数组作为底层存储载体，属于顺序存储结构的典型实现，串的字符元素在内存中连续存放，物理地址与逻辑顺序完全一致。

（2）核心特性

• 存储容量编译期固定，由预设的最大串长常量限制，运行过程中无法扩容；
• 实际串长与底层数组空间相互独立，通过成员变量单独记录有效字符长度，避免遍历数组判断长度的性能损耗；
• 内存分配在栈区完成，生命周期由作用域控制，无需手动管理内存，访问效率高但空间灵活性差。

（3）核心操作理论支撑

1. 赋值操作：需严格校验源字符串长度，避免超出数组最大容量导致内存越界，本质是字符数组的逐字符拷贝；
2. 串连接操作：核心约束为「原串长度 + 待拼接串长度 ≤ 最大串长」，本质是在原串有效字符末尾追加新字符，同步更新实际长度；
3. 子串提取：核心是区间合法性校验（起始位置非负、长度非负、区间不超原串边界），本质是从指定起始地址开始的定长字符拷贝，需手动补充字符串结束符保证语法合规；
4. BF 模式匹配：属于暴力匹配算法，核心思想是主串从起始位置开始，与模式串逐字符比对，匹配失败则主串回溯、模式串复位，最坏时间复杂度 O(n \times m)（n 为主串长度，m 为模式串长度），优点是逻辑简单、实现成本低，缺点是存在大量无效回溯，效率较低。

2. 堆字符串（HeapString）核心理论

（1）数据结构本质

采用动态字符指针作为底层存储载体，仍属于顺序存储结构，字符元素连续存放，区别在于存储载体的内存分配方式不同。

（2）核心特性

• 存储容量运行期动态调整，可根据串的实际长度按需分配内存，完全适配数据规模，无空间浪费；
• 内存分配在堆区完成，生命周期由程序员通过构造/析构函数控制，需手动完成内存申请与释放，空间灵活性极强，访问效率与定长串一致；
• 存在内存泄漏风险，必须通过析构函数释放堆区内存，同时遵循「赋值/拼接操作先释放旧内存、再分配新内存」的原则，避免内存碎片。

（3）核心操作理论支撑

1. 赋值操作：核心是动态内存重分配，先释放当前指针指向的旧堆内存，再根据源字符串长度申请新内存，最后完成字符拷贝，保证内存空间与有效字符完全匹配；
2. 串连接操作：本质是「扩容 + 拼接」两步走，申请「原串长度 + 待拼接串长度 + 1」的新内存（预留结束符空间），先拷贝原串、再追加拼接串，释放旧内存后完成指针重定向，同步更新实际长度；
3. 子串提取：与定长串逻辑一致，区别在于子串的底层内存为堆区动态分配，需单独管理子串对象的内存生命周期；
4. KMP 模式匹配：核心是消除主串回溯，通过预处理模式串生成 next 数组，匹配失败时仅复位模式串、主串持续向后遍历，时间复杂度优化至 O(n + m)（最优/最坏复杂度一致），效率远高于 BF 算法；
5. next 数组核心原理：next[i] 表示模式串第 i 个位置之前的子串中，最长相等前后缀的长度，其作用是匹配失败时，指导模式串快速回退至最优比对位置，避免无效的字符重复比对。

（4）定长串与堆串核心对比

• 空间维度：定长串空间固定、易浪费/溢出，堆串按需分配、空间利用率100%；
• 内存维度：定长串栈区存储、无需手动管理，堆串堆区存储、需严格把控内存释放；
• 适用场景：定长串适用于字符长度已知且固定的场景，堆串适用于字符长度不确定、需动态扩容的场景。

3. 字符串通用核心理论（两类串共性）

1. 串的逻辑定义：由零个或多个字符组成的有限序列，空串的有效长度为0，需通过结束符标识边界；
2. 串与字符数组的区别：字符数组是存储字符的容器，串是基于字符数组的数据抽象，包含「存储载体 + 有效长度 + 操作接口」三层内涵；
3. 串操作的核心约束：所有操作均需保证下标合法、长度合法，避免越界访问与无效数据操作。

const int MAX_STRLEN = 100;  // 定义最大串长（可根据需要调整）
class FixedString {
private:
    char str[MAX_STRLEN];  // 存储串的字符数组
    int length;                // 串的实际长度（不含结束符）

public:
    // 构造函数（初始化空串）
    FixedString() : length(0) { str[0] = '\0'; }

    // 核心接口
    bool isEmpty() const {
        return length == 0;
    }                                  // 判断串是否为空
    int getLength() const {
        return length;
    }                                 // 获取串长
    int strAssign(const char* chars) {
        if (strlen(chars) >= MAX_STRLEN) {
            throw invalid_argument("FixedString::strAssign: 输入字符串长度超过最大限制");
        }
        strcpy(str, chars);
        length = strlen(chars);
        return length;
    }                        // 赋值（chars为字符串常量）
    void strConcat(const FixedString& s) {
        if (length + s.getLength() >= MAX_STRLEN) {
            throw overflow_error("FixedString::strConcat: 连接后字符串长度超过最大限制");
        }
        strcat(str, s.str);
        length += s.getLength();
    }                   // 串连接（将s连接到当前串末尾）
    FixedString subString(int pos, int len) const {
        if (pos < 0 || pos >= length || len < 0 || pos + len > length) {
            throw invalid_argument("FixedString::subString: 子串位置或长度无效");
        }
        FixedString sub;
        strncpy(sub.str, str + pos, len);
        sub.length = len;
        sub.str[len] = '\0';
        return sub;
    } // 求子串（从pos位置取len个字符）
    int index(const FixedString& pattern) const {
        if (pattern.isEmpty()) {
            throw invalid_argument("FixedString::index: 模式串为空");
        }
        for (int i = 0; i <= length - pattern.length; ++i) {
            if (strncmp(str + i, pattern.str, pattern.length) == 0) {
                return i;
            }
        }
        return -1;
    }           // 模式匹配（朴素BF算法）
    void clear() {
        length = 0;
        str[0] = '\0';
    }                                          // 清空串
};

class HeapString {
private:
    char* ch;  // 动态分配的字符数组指针
    int length;    // 串的实际长度

public:
    // 构造函数（初始化空串）
    HeapString() : ch(nullptr), length(0) {}

    // 析构函数（释放动态内存）
    ~HeapString() {
        if (ch != nullptr) {
            delete[] ch;
            ch = nullptr;
        }
    }

    // 核心接口
    bool isEmpty() const {
        return length == 0;
    }                                  // 判断串是否为空
    int getLength() const {
        return length;
    }

    char* getCh() const { return ch; }  // 获取字符数组指针

// 获取串长
    void strAssign(const char* chars) {
        if (ch != nullptr) {
            delete[] ch;
        }
        length = strlen(chars);
        ch = new char[length + 1];
        strcpy(ch, chars);
    }                  // 赋值（动态分配内存）
    void strConcat(const HeapString& s) {
        if (ch == nullptr) {
            ch = new char[length + 1];
            strcpy(ch, s.getCh());
        } else {
            char* temp = new char[length + s.length + 1];
            strcpy(temp, ch);
            strcat(temp, s.getCh());
            delete[] ch;
            ch = temp;
        }
        length += s.length;
    }                   // 串连接
    HeapString subString(int pos, int len) const {
        if (pos < 0 || pos >= length || len < 0 || pos + len > length) {
            throw invalid_argument("HeapString::subString: 子串位置或长度无效");
        }
        HeapString sub;
        sub.ch = new char[len + 1]; // 分配len+1空间（含结束符）
        strncpy(sub.ch, ch + pos, len);
        sub.ch[len] = '\0'; // 手动添加结束符
        sub.length = len;
        return sub;
    } // 求子串
    int indexKMP(const HeapString& pattern) const {
        vector<int> next(pattern.getLength(),0);
        char *p = pattern.getCh();
        int j=0;
        for (int i=1;i<pattern.getLength();++i) {
            while (j>0 && p[i]!=p[j]) {
                j=next[j-1];
            }
            if (p[i]==p[j]) {
                ++j;
            }
            next[i]=j;
        }

        for (int i=0,j=0;i<length;++i) {
            while (j>0 && ch[i]!=p[j]) {
                j=next[j-1];
            }
            if (ch[i]==p[j]) {
                ++j;
            }
            if (j==pattern.getLength()) {
                return i-j+1;
            }
        }
        return -1;
    }         // 模式匹配（KMP算法）
    void makeNext(const HeapString& pattern, int* next) const {
        if (next == nullptr) return;
        char* p = pattern.getCh();
        int j = 0;
        next[0] = 0; // 第一个位置next值固定为0
        for (int i = 1; i < pattern.getLength(); ++i) {
            while (j > 0 && p[i] != p[j]) {
                j = next[j - 1];
            }
            if (p[i] == p[j]) {
                ++j;
            }
            next[i] = j;
        }
    }// 生成KMP算法的next数组
};

7, 二维数组类（TwoDArray）

1. 二维数组的存储本质（核心理论）

二维数组的物理存储形态唯一：计算机底层不存在真正的「二维内存空间」，所有二维数组最终都需映射为一维连续内存存储，本类的核心就是实现「二维逻辑结构 → 一维物理结构」的映射转换，属于顺序存储结构在多维数据中的扩展应用。

2. 两种核心存储映射规则（数组寻址理论）

（1）行优先存储（Row-Major Order）

核心规则

按行序为主、列序为辅的顺序存放元素，即先完整存放第 0 行的所有列元素，再存放第 1 行的所有列元素，以此类推，是最常用的存储方式（C/C++、Java 等语言默认采用）。

寻址公式（核心）

对于 rows 行 cols 列的二维数组，逻辑下标 (i,j) 映射到一维数组的物理下标为
物理下标 = i * cols + j

理论特点

• 同一行的元素在一维数组中连续存放，行内元素访问的局部性好，缓存命中率高；
• 行索引 i 决定元素所在的「行块起始位置」，列索引 j 决定行块内的偏移量。

（2）列优先存储（Column-Major Order）

核心规则

按列序为主、行序为辅的顺序存放元素，即先完整存放第 0 列的所有行元素，再存放第 1 列的所有行元素，以此类推（Fortran 语言默认采用）。

寻址公式（核心）

对于 rows 行 cols 列的二维数组，逻辑下标 (i,j) 映射到一维数组的物理下标为
物理下标 = j * rows + i

理论特点

• 同一列的元素在一维数组中连续存放，适合以列为单位的批量数据操作；
• 列索引 j 决定元素所在的「列块起始位置」，行索引 i 决定列块内的偏移量。

3. 模板化二维数组核心特性

（1）数据类型无关性

基于模板编程思想实现，底层存储与数据元素类型解耦，可适配任意基础类型（int、float、char）与自定义类型，满足通用化数据存储需求，遵循「一次定义、多类型复用」原则。

（2）内存管理理论

• 底层通过一维动态数组实现，堆区内存分配大小为 rows \times cols \times \text{单个元素字节数}，内存连续且可按需调整行列规模；
• 析构函数统一释放堆区内存，避免内存泄漏，内存生命周期由对象实例控制，支持运行期动态指定行列数。

4. 核心操作理论约束

1. 元素访问（取值/赋值）：核心前提是下标合法性校验，行索引 i 需满足 0 ≤ i < rows，列索引 j 需满足 0 ≤ j < cols，否则触发越界错误，本质是通过寻址公式完成「二维逻辑下标 → 一维物理下标」的转换，再执行内存读写；
2. 存储顺序不可变性：行优先/列优先的存储规则在对象构造时确定，运行过程中不可修改，保证数组存储结构的一致性；
3. 空间效率特性：无冗余存储，底层一维数组的空间大小与二维数组的元素总数完全匹配，空间利用率为 100%。

5. 二维数组顺序存储的通用优缺点

优点

1. 元素物理连续，支持随机访问，通过寻址公式可在 O(1) 时间内定位任意位置元素；
2. 内存管理简单，仅需维护一个一维动态数组的指针，无额外空间开销；
3. 缓存友好性强，连续的内存访问可充分利用 CPU 缓存，提升数据读写效率。

缺点

1. 行列规模确定后，动态扩容成本较高（需重新分配更大内存并完成元素拷贝）；
2. 仅适用于规整的二维数据，对稀疏矩阵等非规整多维数据，存在大量空间浪费。

template <typename ElemType>
class TwoDArray {
private:
    ElemType* data;  // 动态分配的一维数组（模拟二维数组）
    int rows;        // 数组行数
    int cols;        // 数组列数
    bool rowMajor;   // 存储顺序：true=行优先，false=列优先

public:
    // 构造函数（初始化rows行cols列的二维数组）
    TwoDArray(int r, int c, bool rowMajor = true) {
        data = new ElemType[r * c];
        rows = r;
        cols = c;
        this->rowMajor = rowMajor;
    }

    // 析构函数（释放动态内存）
    ~TwoDArray() { delete[] data; }

    // 核心接口
    ElemType getElem(int i, int j) const {
        if (i < 0 || i >= rows || j < 0 || j >= cols) {
            throw invalid_argument("TwoDArray::getElem: 索引超出范围");
        }
        ElemType e;
        if (rowMajor) {
            e = data[i * cols + j];
        } else {
            e = data[j * rows + i];
        }
        return e;
    }  // 获取(i,j)位置的元素
    void setElem(int i, int j, ElemType e) {
        if (i < 0 || i >= rows || j < 0 || j >= cols) {
            throw invalid_argument("TwoDArray::setElem: 索引超出范围");
        }
        if (rowMajor) {
            data[i * cols + j] = e;
        } else {
            data[j * rows + i] = e;
        }
    }         // 设置(i,j)位置的元素
    int getRows() const { return rows; }                            // 获取行数
    int getCols() const { return cols; }                            // 获取列数
};

8, 稀疏矩阵类（SparseMatrix）

（1）存储结构

• 三元组数组：存储非零元素的行、列、值三元组，按行优先顺序排序，支持快速随机访问。
• 行/列指针数组：记录每一行/列的第一个非零元素在三元组数组中的索引，支持快速定位行/列的非零元素范围。

（2）核心操作

• 插入/更新非零元素：根据三元组数组中的排序规则，插入或更新指定位置的元素，保持三元组数组的有序性。
• 矩阵转置：通过行/列指针数组和三元组数组，实现稀疏矩阵的转置操作，时间复杂度为 O(tu)。
• 矩阵乘法：通过行/列指针数组和三元组数组，实现稀疏矩阵与另一个稀疏矩阵的乘法操作，时间复杂度为 O(tu * v)。

（3）适用场景

• 稀疏矩阵：适用于存储和操作稀疏矩阵，如科学计算、图像处理等领域。
• 矩阵运算：适用于矩阵乘法、矩阵转置等矩阵运算操作。

#define MAX_TRIPLE 1000

template <typename ElemType>
class SparseMatrix {
private:
    // 三元组结构体（存储非零元素：行、列、值）
    struct Triple {
        int i;          // 行号（从1开始）
        int j;          // 列号（从1开始）
        ElemType e;     // 非零元素值

        // 重载比较运算符，方便排序（按行优先，行相同按列）
        bool operator<(const Triple& other) const {
            return (i < other.i) || (i == other.i && j < other.j);
        }
    };

    Triple data[MAX_TRIPLE];  // 存储非零元素的三元组数组
    int mu;                   // 矩阵行数
    int nu;                   // 矩阵列数
    int tu;                   // 非零元素个数

    // 私有：对三元组数组按行优先排序（提取为函数，避免重复代码）
    void sortTriples() {
        if (tu <= 0) return;  // 空矩阵无需排序
        // 数组排序：data[0] 到 data[tu-1]
        std::sort(data, data + tu, [](const Triple& a, const Triple& b) {
            return a < b;  // 复用重载的<运算符
        });
    }

public:
    // 构造函数（初始化空稀疏矩阵）
    SparseMatrix() : mu(0), nu(0), tu(0) {}

    // 初始化矩阵规模（m行n列）
    void initMatrix(int m, int n) {
        if (m <= 0 || n <= 0) {
            std::cerr << "矩阵行列数必须为正！" << std::endl;
            return;
        }
        mu = m;
        nu = n;
        tu = 0;  // 重置非零元素个数
    }

    // 插入/更新非零元素（i,j位置，行/列从1开始）
    void insertElem(int i, int j, ElemType e) {
        // 1. 边界检查
        if (i < 1 || i > mu || j < 1 || j > nu) {
            std::cerr << "行/列越界！i=" << i << ", j=" << j << " (max: " << mu << "," << nu << ")" << std::endl;
            return;
        }

        // 2. 查找元素位置
        int k = find(i, j);

        // 3. 存在则更新，不存在则插入（需检查是否超出最大容量）
        if (k != -1) {
            data[k].e = e;
        } else {
            if (tu >= MAX_TRIPLE) {
                std::cerr << "非零元素个数超出最大容量！" << std::endl;
                return;
            }
            data[tu].i = i;
            data[tu].j = j;
            data[tu].e = e;
            tu++;  // 非零数+1
            sortTriples();  // 插入后保持有序（保证二分查找有效）
        }
    }

    // 普通转置（时间复杂度O(tu*log(tu))，主要耗时在排序）
    void transpose(SparseMatrix& res) {
        // 初始化结果矩阵的规模
        res.initMatrix(nu, mu);  // 原列数→行数，原行数→列数
        res.tu = tu;             // 非零元素个数不变

        // 复制并交换行列
        for (int i = 0; i < tu; ++i) {
            res.data[i].i = data[i].j;
            res.data[i].j = data[i].i;
            res.data[i].e = data[i].e;
        }

        // 转置后重新排序（保证行优先）
        res.sortTriples();
    }

    // 快速转置（时间复杂度O(nu + tu)，无排序，效率更高）
    void fastTranspose(SparseMatrix& res) {
        if (tu == 0 || mu == 0 || nu == 0) {
            res.initMatrix(nu, mu);
            res.tu = 0;
            return;
        }

        // 初始化结果矩阵
        res.initMatrix(nu, mu);
        res.tu = tu;

        // 1. 统计原矩阵每一列的非零元素个数
        std::vector<int> num(nu + 1, 0);  // num[col] = 原矩阵col列的非零数
        for (int i = 0; i < tu; ++i) {
            int col = data[i].j;
            num[col]++;
        }

        // 2. 计算原矩阵每一列第一个非零元素在结果矩阵中的起始位置
        std::vector<int> cpot(nu + 1, 0);  // cpot[col] = 原col列第一个元素在res中的位置
        for (int j = 1; j <= nu; ++j) {
            cpot[j] = cpot[j - 1] + num[j - 1];
        }

        // 3. 填充结果矩阵（无需排序，直接按位置填充）
        for (int i = 0; i < tu; ++i) {
            int col = data[i].j;          // 原矩阵的列 → 结果矩阵的行
            int pos = cpot[col];          // 该元素在res中的位置
            res.data[pos].i = data[i].j;  // 行列交换
            res.data[pos].j = data[i].i;
            res.data[pos].e = data[i].e;
            cpot[col]++;                  // 下一个同列元素的位置+1
        }
    }

    // 获取(i,j)位置的元素值（行/列从1开始）
    ElemType getElem(int i, int j) const {
        // 边界检查
        if (i < 1 || i > mu || j < 1 || j > nu) {
            std::cerr << "行/列越界！" << std::endl;
            return ElemType();  // 返回类型默认构造值
        }

        // 查找并返回
        int k = find(i, j);
        return (k == -1) ? ElemType() : data[k].e;
    }

    // 打印矩阵（直观展示，按行列展开）
    void printMatrix() const {
        std::cout << "稀疏矩阵(" << mu << "行×" << nu << "列，非零元素数：" << tu << "):" << std::endl;
        for (int i = 1; i <= mu; ++i) {
            for (int j = 1; j <= nu; ++j) {
                ElemType val = getElem(i, j);
                std::cout << val << "\t";
            }
            std::cout << std::endl;
        }
    }

    // 打印三元组数组（调试用）
    void printTriples() const {
        std::cout << "三元组列表（行, 列, 值）：" << std::endl;
        for (int i = 0; i < tu; ++i) {
            std::cout << "(" << data[i].i << ", " << data[i].j << ", " << data[i].e << ")" << std::endl;
        }
    }

private:
    // 二分查找(i,j)位置的元素在三元组数组中的索引（返回-1表示未找到）
    int find(int i, int j) const {
        int low = 0, high = tu - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (data[mid].i == i && data[mid].j == j) {
                return mid;  // 找到
            } else if (data[mid].i < i || (data[mid].i == i && data[mid].j < j)) {
                low = mid + 1;  // 目标在右半区
            } else {
                high = mid - 1; // 目标在左半区
            }
        }
        return -1;  // 未找到
    }
};

9, 广义表（Generalized List）

(1), 广义表定义

广义表是一种递归定义的数据结构，用于表示层次结构的数据。它由一个表头和一个表尾组成，表头可以是任意数据类型，表尾必须是另一个广义表。广义表可以表示复杂的层次结构，如树、图等。

(2), 广义表表示

广义表通常用括号表示，表头和表尾之间用逗号分隔。例如，(a, (b, c), d) 表示一个广义表，其中 a 是表头，(b, c) 是表尾，d 是另一个表头。

(3), 广义表操作

• 创建：根据括号表示法构建广义表。
• 插入：在指定位置插入元素或子列表。
• 删除：从指定位置删除元素或子列表。
• 查找：按层次结构查找特定元素或子列表。
• 遍历：递归地访问所有元素和子列表。

class GeneralizedList {
private:
    struct GLNode {
        int tag; // 0 atom, 1 list
        union {
            char atom;
            vector<GLNode*>* sub;
        };
        GLNode(char c) : tag(0), atom(c) {}
        GLNode() : tag(1), sub(new vector<GLNode*>()) {}
        ~GLNode() { if(tag==1) delete sub; }
    };

    GLNode* head = nullptr;

public:
    ~GeneralizedList(){ clear(head); }

    void create(string s){
        int i=0;
        clear(head);
        head = parse(s, i);
    }

    void print(){ print(head);cout<<endl; }

    int length(){ return head && head->tag==1 ? head->sub->size() : 1; }

    int depth(){ return depth(head); }

private:
    void clear(GLNode* p){
        if(!p) return;
        if(p->tag==1){
            for(auto x:*p->sub) clear(x);
        }
        delete p;
    }

    GLNode* parse(string& s, int& i){
        if(s[i]=='('){
            i++; // skip '('
            GLNode* p=new GLNode();
            while(s[i]!=')'){
                p->sub->push_back(parse(s,i));
                if(s[i]==',') i++;
            }
            i++; // skip ')'
            return p;
        }else{
            return new GLNode(s[i++]);
        }
    }

    void print(GLNode* p){
        if(!p) return;
        if(p->tag==0) cout<<p->atom;
        else{
            cout<<"(";
            for(int i=0;i<p->sub->size();i++){
                print((*p->sub)[i]);
                if(i+1<p->sub->size()) cout<<",";
            }
            cout<<")";
        }
    }

    int depth(GLNode* p){
        if(!p) return 0;
        if(p->tag==0) return 1;
        int mx=0;
        for(auto x:*p->sub) mx=max(mx,depth(x));
        return mx+1;
    }
};

10, 树（Tree）

(1), 二叉树 (Binary Tree)

二叉树定义

二叉树是每个结点最多有两个子树的树结构。它可以是空树，也可以有根节点和两个不相交的左、右子树。

二叉树操作

• 创建：根据给定的数据构建二叉树。
• 插入：在指定位置插入新元素。
• 删除：从指定位置删除元素。
• 遍历：前序、中序、后序或层次遍历。
• 查找：按值查找特定元素的位置。
• 高度与深度：计算树的高度和任意节点的深度。

template <typename ElemType>
class BinaryTree {
private:
public:
    struct BTNode {
        ElemType data;          // 数据域
        BTNode* lchild;         // 左孩子指针
        BTNode* rchild;         // 右孩子指针
        // 结点构造函数
        BTNode(ElemType val = 0) : data(val), lchild(nullptr), rchild(nullptr) {}
    };
    BTNode* root;  // 根结点指针
    // 构造函数（初始化空树）
    BinaryTree() : root(nullptr) {}

    // 析构函数（递归释放所有结点）
    ~BinaryTree() { destroy(root); }

    // 核心接口声明
    void destroy(BTNode* node) {
        if (node == nullptr) return;
        destroy(node->lchild);
        destroy(node->rchild);
        delete node;
    }                // 递归销毁树（内部辅助）
    bool isEmpty() const {
        return root == nullptr;
    }                      // 判断树是否为空
    BTNode* getRoot() const {
        return root;
    }                  // 获取根结点指针
    void createByPreorder(vector<ElemType>& preorder, vector<ElemType>& inorder) {
        unordered_map<ElemType, int> mp;
        for (int i = 0; i < inorder.size(); ++i) {
            mp[inorder[i]] = i;
        }

        function<BTNode* (int&, vector<ElemType>&, int, int)> create = [&](int& i, vector<ElemType>& inorder, int l, int r) -> BTNode* {
            if (l > r) return nullptr;
            int mid = mp[preorder[i]];
            auto* node = new BTNode(preorder[i]);
            ++i;
            node->lchild = create(i, inorder, l, mid - 1);
            node->rchild = create(i, inorder, mid + 1, r);
            return node;
        };
        int i = 0;
        root = create(i, inorder, 0, inorder.size() - 1);
    } // 按先序中序序列创建（含空标记）

    void createByBackorder(vector<ElemType>& backorder, vector<ElemType>& inorder) {
        unordered_map<ElemType, int> mp;
        for (int i = 0; i < inorder.size(); ++i) {
            mp[inorder[i]] = i;
        }

        function<BTNode* (int&, vector<ElemType>&, int, int)> create = [&](int& i, vector<ElemType>& inorder, int l, int r) -> BTNode* {
            if (l > r) return nullptr;
            int mid = mp[backorder[i]];
            BTNode* node = new BTNode(backorder[i]);
            --i;
            node->rchild = create(i, inorder, mid + 1, r);
            node->lchild = create(i, inorder, l, mid - 1);
            return node;
        };
        int i = backorder.size() - 1;
        root = create(i, inorder, 0, inorder.size() - 1);
    } // 按后序序中序序列创建（不含空标记）

    void createByFullBinaryTree(const ElemType* arr, int len) {
        function<BTNode* (int)> create = [&](int i) -> BTNode* {
            if (i >= len) return nullptr;
            BTNode* node = new BTNode(arr[i]);
            node->lchild = create(2 * i + 1);
            node->rchild = create(2 * i + 2);
            return node;
        };

        root = create(0);
    } // 按满二叉树编号创建

    // 遍历算法（递归版）
    void preorderTraverse(void (*visit)(ElemType)) const {
        function<void (BTNode*)> preorder = [&](BTNode* node) {
            if (node == nullptr) return;
            visit(node->data);
            preorder(node->lchild);
            preorder(node->rchild);
        };
        preorder(root);
    } // 先序遍历（V-L-R）

    void inorderTraverse(void (*visit)(ElemType)) const {
        function<void (BTNode*)> inorder = [&](BTNode* node) {
            if (node == nullptr) return;
            inorder(node->lchild);
            visit(node->data);
            inorder(node->rchild);
        };
        inorder(root);
    } // 中序遍历（L-V-R）

    void postorderTraverse(void (*visit)(ElemType)) const {
        function<void (BTNode*)> postorder = [&](BTNode* node) {
            if (node == nullptr) return;
            postorder(node->lchild);
            postorder(node->rchild);
            visit(node->data);
        };
        postorder(root);
    } // 后序遍历（L-R-V）

    void levelorderTraverse(void (*visit)(ElemType)) const {
        queue<BTNode*> q;
        q.push(root);
        while (!q.empty()) {
            BTNode* node = q.front();
            q.pop();
            if (node == nullptr) continue;
            visit(node->data);
            q.push(node->lchild);
            q.push(node->rchild);
        }
    } // 层次遍历（自上而下、自左至右）

    // 遍历算法（非递归版）
    void preorderTraverseNonRec(void (*visit)(ElemType)) const {
        stack<BTNode*> s;
        s.push(root);
        while (!s.empty()) {
            BTNode* node = s.top();
            s.pop();
            if (node == nullptr) continue;
            visit(node->data);
            s.push(node->rchild);
            s.push(node->lchild);
        }
    }

    void inorderTraverseNonRec(void (*visit)(ElemType)) const {
        stack<BTNode*> s;
        BTNode* node = root;
        while (node != nullptr || !s.empty()) {
            if (node != nullptr) {
                s.push(node);
                node = node->lchild;
            } else {
                node = s.top();
                s.pop();
                visit(node->data);
                node = node->rchild;
            }
        }
    }

    void postorderTraverseNonRec(void (*visit)(ElemType)) const {
        stack<BTNode*> s;
        BTNode* node = root;
        BTNode* lastVisited = nullptr;
        while (node != nullptr || !s.empty()) {
            if (node != nullptr) {
                s.push(node);
                node = node->lchild;
            } else {
                node = s.top();
                if (node->rchild == nullptr || node->rchild == lastVisited) {
                    visit(node->data);
                    lastVisited = node;
                    s.pop();
                    node = nullptr;
                } else {
                    node = node->rchild;
                }
            }
        }
    }

    // 常用操作
    int getHeight() const {
        function<int (BTNode*)> getHeight = [&](BTNode* node) {
            if (node == nullptr) return 0;
            return max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
        };
        return getHeight(root);
    } // 获取树的高度（深度）
    int getLeafCount() const {
        function<int (BTNode*)> getLeafCount = [&](BTNode* node) {
            if (node == nullptr) return 0;
            if (node->lchild == nullptr && node->rchild == nullptr) return 1;
            return getLeafCount(node->lchild) + getLeafCount(node->rchild);
        };
        return getLeafCount(root);
    } // 统计叶子结点个数
    BTNode* findNode(ElemType val) const {
        function<BTNode* (BTNode*)> findNode = [&](BTNode* node) -> BTNode* {
            if (node == nullptr) return nullptr;
            if (node->data == val) return node;
            BTNode* left = findNode(node->lchild);
            if (left != nullptr) return left;
            return findNode(node->rchild);
        };
        return findNode(root);
    } // 查找值为val的结点
    void setRoot(BTNode *pNode) {
        root = pNode;
    }
};

(2), 二叉树与树与森林 (Tree and Forest)

树（Tree）

树是一种非线性的数据结构，由n（n>=0）个结点组成，其中有一个特殊的结点称为根结点，其余结点可分为m（m>=0）个互不相交的子树。树是递归定义的，即树的结点也可以是树。

森林（Forest）

森林是m（m>=0）棵互不相交的树的集合。

树与二叉树的转换

树与二叉树的转换是树与二叉树之间的一种重要关系。树与二叉树之间的转换关系如下：

• 树转换为二叉树：将树的根结点作为二叉树的根结点，然后将树的每个结点的第一个孩子作为二叉树的左孩子，将每个结点的其他孩子作为二叉树的右孩子，依次递归进行，直到所有结点都被转换为二叉树的结点。这样得到的二叉树称为树的二叉树表示。
• 二叉树转换为树：将二叉树的根结点作为树的根结点，然后将二叉树的每个结点的左孩子作为树的第一个孩子，将每个结点的右孩子作为树的其他孩子，依次递归进行，直到所有结点都被转换为树的结点。这样得到的树称为二叉树的树表示。
• 树的森林转换为二叉树：将树的森林中的每棵树转换为二叉树，然后将这些二叉树的根结点连接起来，作为森林的根结点。这样得到的二叉树称为树的森林的二叉树表示。
• 二叉树转换为树的森林：将二叉树的根结点作为森林的根结点，然后将二叉树的每个结点的左孩子作为森林的第一棵树的根结点，将每个结点的右孩子作为森林的其他树的根结点，依次递归进行，直到所有结点都被转换为树的结点。这样得到的树的森林称为二叉树的树的森林表示。

template <typename ElemType>
class TreeForest {
private:
public:
    typedef typename BinaryTree<ElemType>::BTNode BTNode;
    struct CSNode {
        ElemType data;          // 数据域
        vector<CSNode*> children;     // 孩子指针
        explicit CSNode(ElemType val = 0) : data(val) {}
    };

    BTNode* treeToBinaryTree(CSNode* treeRoot) {
        function<BTNode* (CSNode*)> treeToBinaryTree = [&](CSNode* tree) -> BTNode *{
            if (tree == nullptr) return nullptr;
            auto * binary = new BTNode(tree->data);
            if (tree->children.empty()) return binary;
            binary->lchild = treeToBinaryTree(tree->children[0]);
            BTNode* cur = binary->lchild;
            for (int i=1; i<tree->children.size(); i++) {
                cur->rchild = treeToBinaryTree(tree->children[i]);
                cur = cur->rchild;
            }
            return binary;
        };
        return treeToBinaryTree(treeRoot);
    } // 树转换为二叉树
    CSNode* binaryTreeToTree(BTNode* binaryRoot) {
        function<CSNode* (BTNode*)> binaryTreeToTree = [&](BTNode* binary) -> CSNode*  {
            if (binary == nullptr) return nullptr;
            CSNode* tree = new CSNode(binary->data);
            if (binary->lchild == nullptr) return tree;
            tree->children.push_back(binaryTreeToTree(binary->lchild));
            BTNode* cur = binary->lchild;
            while (cur->rchild != nullptr) {
                tree->children.push_back(binaryTreeToTree(cur->rchild));
                cur = cur->rchild;
            }
            return tree;
        };

        return binaryTreeToTree(binaryRoot);
    } // 二叉树还原为树
    BTNode* forestToBinaryTree(vector<CSNode*>& forest) {
        if (forest.empty()) return nullptr;
        BTNode* binaryRoot = treeToBinaryTree(forest[0]);
        BTNode* cur = binaryRoot;
        for (int i=1; i<forest.size(); i++) {
            cur->rchild = treeToBinaryTree(forest[i]);
            cur= cur->rchild;
        }
        return binaryRoot;
    } // 森林转换为二叉树
    vector<CSNode*> binaryTreeToForest(BTNode* binaryRoot) {
        vector<CSNode*> forestRoots;
        if (binaryRoot == nullptr) return forestRoots;
        BTNode * cur = binaryRoot;
        while (cur != nullptr) {
            BTNode * tmp = cur->rchild;
            cur->rchild = nullptr;
            forestRoots.push_back(binaryTreeToTree(cur));
            cur = tmp;
        }
        return forestRoots;
    } // 二叉树还原为森林

    // 树的遍历（孩子兄弟表示法）
    void treePreorderTraverse(CSNode* root, void (*visit)(ElemType)) const {
        visit(root->data);
        for (CSNode* child : root->children) {
            treePreorderTraverse(child, visit);
        }
    } // 树的先序遍历
    void treePostorderTraverse(CSNode* root, void (*visit)(ElemType)) const {
        for (CSNode* child : root->children) {
            treePostorderTraverse(child, visit);
        }
        visit(root->data);
    } // 树的后序遍历
    void forestPreorderTraverse(vector<CSNode*>& forest, void (*visit)(ElemType)) const {
        for (auto &tree : forest)
            treePreorderTraverse(tree, visit);
    } // 森林先序遍历
};

(3), 二叉搜索树 (Binary Search Tree)

定义

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，它满足以下性质：

• 每个结点的值大于其左子树中所有结点的值；
• 每个结点的值小于其右子树中所有结点的值；

操作

• 查找：从根结点开始，如果根结点的值等于查找的值，则查找成功；如果查找的值小于根结点的值，则在左子树中继续查找；如果查找的值大于根结点的值，则在右子树中继续查找。如果查找的值不在树中，则查找失败。
• 插入：在二叉搜索树中插入一个结点，需要找到该结点的父结点，然后根据其值与父结点值的比较结果确定是作为左子结点还是右子结点。
• 删除：在二叉搜索树中删除一个结点，需要找到该结点的父结点，然后根据其值与父结点值的比较结果确定是作为左子结点还是右子结点。如果被删除的结点是叶子结点，则直接删除；如果被删除的结点只有一个子结点，则用该子结点替换被删除的结点；如果被删除的结点有两个子结点，则用其右子树中的最小结点替换被删除的结点。

template <typename KeyType, typename ElemType>
class BinarySearchTree {
private:
    struct BSTNode {
        KeyType key;            // 关键字（查找依据）
        ElemType data;          // 数据域
        BSTNode* lchild;        // 左子树（关键字小于当前）
        BSTNode* rchild;        // 右子树（关键字大于当前）
        BSTNode(KeyType k, ElemType val) : key(k), data(val), lchild(nullptr), rchild(nullptr) {}
    };

    BSTNode* root;              // 根结点指针

    BSTNode* search(BSTNode* node,KeyType key) const {
        if (node == nullptr || node->key == key) return node;
        if (key < node->key) return search(node->lchild, key);
        else return search(node->rchild, key);
    }

    void insert(BSTNode*& node, KeyType k, ElemType e) const {
        if (node == nullptr) return;
        if (k < node->key) {
            if (node->lchild == nullptr) node->lchild = new BSTNode(k, e);
            else insert(node->lchild, k, e);
        } else if (k > node->key) {
            if (node->rchild == nullptr) node->rchild = new BSTNode(k, e);
            else insert(node->rchild, k, e);
        } else {
            node->data = e;
        }
    }

    void remove(BSTNode*& node, KeyType key) {
        if (node == nullptr) return;
        if (key < node->key) remove(node->lchild, key);
        else if (key > node->key) remove(node->rchild, key);
        else {
            if (node->lchild == nullptr) {
                BSTNode *temp = node;
                node = node->rchild;
                delete temp;
            } else if (node->rchild == nullptr) {
                BSTNode *temp = node;
                node = node->lchild;
                delete temp;
            } else {
                BSTNode *temp = node->rchild;
                while (temp->lchild != nullptr) temp = temp->lchild;
                node->key = temp->key;
                node->data = temp->data;
                remove(node->rchild, temp->key);
            }
        }
    }

    void inorderTraverse(BSTNode* node, void (*visit)(KeyType, ElemType)) const {
        if (node == nullptr) return;
        inorderTraverse(node->lchild, visit);
        visit(node->key, node->data);
        inorderTraverse(node->rchild, visit);
    }

public:
    // 构造函数
    BinarySearchTree() : root(nullptr) {}
    // 析构函数
    ~BinarySearchTree() { destroy(root); }

    // 核心接口声明
    void destroy(BSTNode* node) {
        if (node == nullptr) return;
        destroy(node->lchild);
        destroy(node->rchild);
        delete node;
    }                // 递归销毁树
    bool isEmpty() const {
        return root == nullptr;
    }                      // 判断树是否为空
    BSTNode* search(KeyType key) const {
        return search(root, key);
    }        // 查找关键字为key的结点（递归）
    BSTNode* searchNonRec(KeyType key) const {
        BSTNode* node = root;
        while (node != nullptr && node->key != key) {
            if (key < node->key) node = node->lchild;
            else node = node->rchild;
        }
        return node;
    }  // 查找关键字为key的结点（非递归）
    void insert(KeyType key, ElemType data) {
        if (root == nullptr) {
            root = new BSTNode(key, data);
            return;
        }
        insert(root, key, data);
    }    // 插入结点（保持BST性质）
    void remove(KeyType key) {
        remove(root, key);
    }                  // 删除结点（保持BST性质）
    void inorderTraverse(void (*visit)(KeyType, ElemType)) const {
        inorderTraverse(root, visit);
    } // 中序遍历（得到有序序列）
};

(4), 平衡二叉树 (AVl树)

定义

AVL树是一种自平衡的二叉搜索树，它满足以下性质：

• 每个结点的左子树和右子树的高度差不超过1；
• 每个结点的左子树和右子树都是AVL树；

操作

在二叉搜索树的基础上，增加以下操作：

• 平衡化：在插入或删除结点后，检查每个结点的平衡因子，如果平衡因子超过1，则进行相应的旋转操作，以保持AVL树的性质。
• 旋转操作：包括左旋、右旋、左右旋和右左旋四种操作，用于调整树的结构，以保持AVL树的性质。

template <typename KeyType, typename ElemType>
class AVLTree {
private:
    struct AVLNode {
        KeyType key;            // 关键字
        ElemType data;          // 数据域
        AVLNode* lchild;        // 左子树
        AVLNode* rchild;        // 右子树
        int height;
        AVLNode(KeyType k, ElemType val) : key(k), data(val), lchild(nullptr), rchild(nullptr), height(1) {}
    };

    AVLNode* root;              // 根结点指针

    // 平衡化旋转（内部辅助）
    AVLNode* leftRotate(AVLNode* node) {
        if (node== nullptr) return nullptr;

        auto right = node->rchild;
        node->rchild = right->lchild;
        right->lchild = node;

        // 关键补充：先更新原节点高度，再更新新根高度
        updateHeight(node); // node 是原根，结构先变化
        updateHeight(right); // right 是新根，依赖原根的高度

        return right;
    }
    AVLNode* rightRotate(AVLNode* node) {
        if (node== nullptr) return nullptr;
        auto left=node->lchild;
        node->lchild=left->rchild;
        left->rchild=node;

        updateHeight(node);
        updateHeight(left);

        return left;
    }
    AVLNode* leftRightRotate(AVLNode* node) {
        if (node== nullptr) return nullptr;
        node->lchild=leftRotate(node->lchild);
        return rightRotate(node);
    }    // LR型旋转（先左后右）
    AVLNode* rightLeftRotate(AVLNode* node) {
        if (node== nullptr) return nullptr;
        node->rchild= rightRotate(node->rchild);
        return leftRotate(node);
    }    // RL型旋转（先右后左）
    int getHeight(AVLNode* node) const {
        if (node == nullptr){
            return 0;
        }
        return node->height;
    }         // 获取结点子树高度
    void updateHeight(AVLNode* node) {
        if (node== nullptr) return;
        node->height=std::max(getHeight(node->lchild), getHeight(node->rchild))+1;
    }
    int getBalance(AVLNode* node) const {
        if (node== nullptr) return 0;
        return getHeight(node->lchild)- getHeight(node->rchild);
    }        // 计算结点平衡因子

    void balance(AVLNode*& node) {
        int b= getBalance(node);
        if (b>1) {
            if (getBalance(node->lchild)<0) {
                node = leftRightRotate(node);
            } else {
                node = rightRotate(node);
            }
        } else if (b<-1) {
            if (getBalance(node->rchild)>0) {
                node = rightLeftRotate(node);
            } else {
                node = leftRotate(node);
            }
        }

//        updateHeight(node);
    }

    void insertNode(AVLNode*& node, KeyType key, ElemType data) {
        if (node== nullptr) {
            node = new AVLNode(key, data);
            return;
        }
        if (key < node->key) {
            insertNode(node->lchild, key, data);
        } else if (key > node->key) {
            insertNode(node->rchild, key, data);
        } else {
            node->data = data;
        }

        updateHeight(node);
        balance(node);
    } // 递归插入（维护平衡）
    void removeNode(AVLNode*& node, KeyType key) {
        if (node== nullptr) {
            return;
        }
        if (key < node->key) {
            removeNode(node->lchild, key);
        } else if (key > node->key) {
            removeNode(node->rchild, key);
        } else {
            if (node->lchild== nullptr&&node->rchild== nullptr) {
                delete node;
                node = nullptr;
            } else if (node->lchild== nullptr) {
                auto temp = node;
                node = node->rchild;
                delete temp;
            } else if (node->rchild== nullptr) {
                auto temp = node;
                node = node->lchild;
                delete temp;
            } else {
                auto temp = node->rchild;
                while (temp->lchild!= nullptr) {
                    temp = temp->lchild;
                }
                node->key = temp->key;
                node->data = temp->data;
                removeNode(node->rchild, temp->key);
            }
        }

        updateHeight(node);
        balance(node);
    } // 递归删除（维护平衡）

    AVLNode* search(AVLNode* node, KeyType key) const {
        if (node== nullptr) return nullptr;
        if (key < node->key) {
            return search(node->lchild, key);
        } else if (key > node->key) {
            return search(node->rchild, key);
        } else {
            return node;
        }
    }

    void inorderTraverse(AVLNode* node ,void (*visit)(KeyType, ElemType)) const {
        if (node== nullptr) return;
        inorderTraverse(node->lchild, visit);
        visit(node->key, node->data);
        inorderTraverse(node->rchild, visit);
    }

public:
    // 构造函数
    AVLTree() : root(nullptr) {}
    // 析构函数
    ~AVLTree() { destroy(root); }

    // 核心接口声明
    void destroy(AVLNode* node) {
        if (node== nullptr) return;
        destroy(node->lchild);
        destroy(node->rchild);
        delete node;
    }               // 递归销毁树
    [[nodiscard]] bool isEmpty() const {
        return root== nullptr;
    }                     // 判断树是否为空
    AVLNode* search(KeyType key) const {
        return search(root, key);
    }         // 查找关键字
    void insert(KeyType key, ElemType data) {
        insertNode(root, key,data);
    }     // 插入结点（自动平衡）
    void remove(KeyType key) {
        removeNode(root, key);
    }                    // 删除结点（自动平衡）
    void inorderTraverse(void (*visit)(KeyType, ElemType)) const {
        inorderTraverse(root, visit);
    } // 中序遍历（有序序列）
    [[nodiscard]] bool isAVLTree() const {
        return abs(getBalance(root))<=1;
    }                    // 验证是否为合法AVL树
};

(5), 哈夫曼树 (Huffman Tree)

哈夫曼树定义

哈夫曼树（Huffman Tree）是一种特殊的二叉树，它是一种带权路径长度（WPL）最短的二叉树。哈夫曼树是一种最优二叉树，它的带权路径长度（WPL）是所有带权路径长度中最小的。

哈夫曼树的构造

哈夫曼树的构造过程如下：

1. 创建N个权值均为W的叶子结点。
2. 将这些结点构造成一个森林。

哈夫曼树的性质

1. 哈夫曼树的每个结点都有两个子结点。
2. 哈夫曼树的每个结点的权值都大于等于其子结点的权值。
3. 哈夫曼树的带权路径长度（WPL）是所有带权路径长度中最小的。

哈夫曼树的应用

1. 哈夫曼编码：哈夫曼树可以用于构造哈夫曼编码，哈夫曼编码是一种无损压缩编码，它可以有效地减少数据的存储空间。
2. 哈夫曼树可以用于数据压缩和解压缩。
3. 哈夫曼树可以用于数据传输和通信。

class HuffmanTree {
private:
    struct HuffmanNode {
        int weight;        // 权值（字符频度等）
        bool isLeaf;         // 是否为叶子结点

```cpp
class HuffmanTree {
private:
    struct HuffmanNode {
        int weight;        // 权值（字符频度等）
        bool isLeaf;         // 是否为叶子结点
        char ch;              // 字符（仅叶子结点有效）
        HuffmanNode* lchild;             // 左孩子
        HuffmanNode* rchild;             // 右孩子
        // 构造函数
        HuffmanNode(int w = 0) : weight(w),isLeaf(false), ch('\0') ,lchild(nullptr), rchild(nullptr) {}
    };

    HuffmanNode* ht;           // 哈夫曼树结点数组

public:
    // 构造函数（按权值数组创建哈夫曼树）
    HuffmanTree() {
    }
    // 析构函数
    ~HuffmanTree() { destroyHuffman(ht); }

    // 核心接口声明
    int getWPL() const {
        int wpl=0;
        function<void(HuffmanNode*)> dfs = [&](HuffmanNode* node) {
            if (node== nullptr) return;
            wpl += node->weight;
            dfs(node->lchild);
            dfs(node->rchild);
        };
        dfs(ht);
        return wpl;
    }                   // 计算带权路径长度（WPL）
    void generateHuffmanCode(string& code) {
        vector<int> cnt(256, 0);
        for (auto c : code) {
            cnt[c]++;
        }
        for (int i = 0; i < 256; i++) {
            if (cnt[i] > 0) {
                cout << (char) i << ": " << cnt[i] << endl;
            }
        }

        priority_queue<HuffmanNode*, vector<HuffmanNode*>, function<bool(HuffmanNode*, HuffmanNode*)>> pq(
                [](HuffmanNode* a, HuffmanNode* b) { return a->weight < b->weight; });

        for (int i=0;i<256;i++) {
            if (cnt[i] > 0) {
                HuffmanNode* node = new HuffmanNode(cnt[i]);
                node->ch = (char) i;
                node->isLeaf = true;
                pq.push(node);
            }
        }

        while (pq.size() > 1) {
            HuffmanNode* left = pq.top();
            pq.pop();
            HuffmanNode* right = pq.top();
            pq.pop();
            HuffmanNode* parent = new HuffmanNode(left->weight + right->weight);
            parent->lchild = left;
            parent->rchild = right;
            pq.push(parent);
        }

        ht = pq.top();
    }   // 生成哈夫曼编码（每个字符对应编码串）

    string getHuffmanCode(char ch) const {
        string code;
        function<void(HuffmanNode*, string)> dfs = [&](HuffmanNode* node, const string& path) {
//            cout<<node<<endl;
            if (node == nullptr) return;
            if (node->isLeaf ) {
//                cout<<node->ch<<' '<<path<<endl;
                if (node->ch == ch) {
                    code = path;
                }
                return;
            }
            dfs(node->lchild, path + "0");
            if (!code.empty()) return;
            dfs(node->rchild, path + "1");
        };
        dfs(ht, "");
        return code;
    }   // 获取指定字符的哈夫曼编码

    void destroyHuffman(HuffmanNode* node) {
        if (node== nullptr) return;
        destroyHuffman(node->lchild);
        destroyHuffman(node->rchild);
        delete node;
    } // 销毁哈夫曼编码数组
};

(6), B-, B+树 (B-Tree, B+Tree)

B-树定义

B-树是一种自平衡的多路搜索树，它满足以下性质：

• 每个结点最多有m个孩子（m阶B-树）；
• 根结点至少有2个孩子（m阶B-树）；
• 每个非根结点至少有ceil(m/2)-1个关键字（m阶B-树）；
• 每个非根结点最多有m-1个关键字（m阶B-树）；
• 所有叶子结点都在同一层；

B+树定义

B+树是一种自平衡的多路搜索树，它满足以下性质：

• 每个结点最多有m个孩子（m阶B+树）；
• 根结点至少有2个孩子（m阶B+树）；
• 每个非根结点至少有ceil(m/2)-1个关键字（m阶B+树）；
• 每个非根结点最多有m-1个关键字（m阶B+树）；
• 所有叶子结点都在同一层；

B-树和B+树的比较

B-树和B+树都是自平衡的多路搜索树，它们都满足以下性质：

• 每个结点最多有m个孩子（m阶B-树）；
• 根结点至少有2个孩子（m阶B-树）；
• 每个非根结点至少有ceil(m/2)-1个关键字（m阶B-树）；
• 每个非根结点最多有m-1个关键字（m阶B-树）；
• 所有叶子结点都在同一层；

不同点

• B-树每个结点最多有m-1个关键字，而B+树每个结点最多有m-2个关键字（因为B+树的叶子结点不存储关键字）；
• B-树每个结点的子树指针数=关键字数+1，而B+树每个结点的子树指针数=关键字数（因为B+树的叶子结点不存储关键字）；
• B-树的非叶子结点只用于索引，而B+树的非叶子结点只用于索引，而叶子结点存储实际数据；

B-树和B+树的用途

B-树和B+树都是自平衡的多路搜索树，它们都广泛应用于数据库和文件系统中。B-树和B+树的主要用途包括：

• 数据库索引：B-树和B+树都可以用于数据库索引，它们可以有效地提高数据库的查询性能。
• 文件系统：B-树和B+树都可以用于文件系统，它们可以有效地提高文件系统的读写性能。

// B-树类（m阶）
class BTree {
private:
    struct BTreeNode {
        vector<int> keys;          // 关键字数组（有序）
        vector<BTreeNode*> children;   // 子树指针数组（个数=keyNum+1）
        int keyNum;                    // 关键字个数
        bool isLeaf;            // 是否为叶子结点
        // 构造函数（m阶：关键字最大个数=m-1，子树最大个数=m）
        BTreeNode(int m, bool leaf = false) : keys(m-1), children(m),keyNum(0) ,isLeaf(leaf) {
            for (int i = 0; i < m; i++) children[i] = nullptr;
        }
    };

    BTreeNode* root;            // 根结点指针
    int order;                  // B-树的阶（m）
    int minKeyNum;              // 非根结点最小关键字个数（ceil(m/2)-1）

    // 内部辅助操作
    void splitChild(BTreeNode* parent, int idx) const {
        if (parent == nullptr || idx < 0 || idx >= parent->children.size() || parent->children[idx] == nullptr) {
            return;
        }
        BTreeNode* child = parent->children[idx];
        int splitPos = minKeyNum; // 分裂点：minKeyNum = ceil(m/2)-1

        // 创建1个新节点（原代码错误创建2个，B-树分裂仅需1个）
        BTreeNode* newChild = new BTreeNode(order, child->isLeaf);

        // 拆分关键字：newChild 存 [splitPos+1, m-2]
        for (int i = splitPos + 1; i < order - 1; i++) {
            newChild->keys[i - (splitPos + 1)] = child->keys[i];
            newChild->keyNum++;
        }
        child->keyNum = splitPos; // 原节点保留 [0, splitPos]

        // 拆分子节点（非叶子节点）
        if (!child->isLeaf) {
            for (int i = splitPos + 1; i < order; i++) {
                newChild->children[i - (splitPos + 1)] = child->children[i];
                child->children[i] = nullptr;
            }
        }

        // 父节点插入分裂点关键字 + 新子节点指针
        // 移动父节点关键字
        for (int i = parent->keyNum; i > idx; i--) {
            if (i < parent->keys.size()) {
                parent->keys[i] = parent->keys[i - 1];
            }
        }
        parent->keys[idx] = child->keys[splitPos]; // 分裂点关键字提升到父节点
        parent->keyNum++;

        // 移动父节点子指针
        for (int i = parent->keyNum; i > idx + 1; i--) {
            if (i < parent->children.size()) {
                parent->children[i] = parent->children[i - 1];
            }
        }
        parent->children[idx + 1] = newChild;

        // 释放原节点（仅清空指针）
//        child = nullptr;
    } // 分裂子结点
    void insertNonFull(BTreeNode* node, int key) {
        int i = node->keyNum - 1;
        if (node->isLeaf) {
            while (i >= 0 && key < node->keys[i]) {
                node->keys[i+1] = node->keys[i];
                i--;
            }
            node->keys[i+1] = key;
            node->keyNum++;
        } else {
            while (i >= 0 && key < node->keys[i]) i--;
            i++;
            if (node->children[i]->keyNum == order - 1) {
                splitChild(node, i);
                if (key > node->keys[i]) i++;
            }
            insertNonFull(node->children[i], key);
        }
    } // 向非满结点插入关键字
    bool removeKey(BTreeNode* node, BTreeNode*& father, int key, int childIdx) {
        int i = 0;
        while (i < node->keyNum && key > node->keys[i]) i++;

        // 情况1：key 在当前节点
        if (i < node->keyNum && key == node->keys[i]) {

            // 1.1 叶子节点：直接删
            if (node->isLeaf) {
                for (int j = i; j < node->keyNum - 1; j++)
                    node->keys[j] = node->keys[j + 1];
                node->keyNum--;
                return true;
            }

            // 1.2 内部节点：用前驱替换
            BTreeNode* cur = node->children[i];
            while (!cur->isLeaf) cur = cur->children[cur->keyNum];
            int pred = cur->keys[cur->keyNum - 1];
            node->keys[i] = pred;
            return removeKey(node->children[i], node, pred, i);
        }

        // 情况2：key 不在当前节点
        if (node->isLeaf) return false;

        // 选子树
        int child = i;

        // 递归前保证子节点至少 minKeyNum+1 个关键字
        if (node->children[child]->keyNum == minKeyNum) {
            if (child > 0 && node->children[child - 1]->keyNum > minKeyNum) {
                borrowFromLeft(node, child);
            }
            else if (child < node->keyNum && node->children[child + 1]->keyNum > minKeyNum) {
                borrowFromRight(node, child);
            }
            else {
                if (child < node->keyNum) mergeChild(node, child);
                else mergeChild(node, child - 1), child--;
            }
        }

        return removeKey(node->children[child], node, key, child);
    }
    // 从结点中删除关键字
    int getPredecessor(BTreeNode* node, int idx) {
        if (node== nullptr) return -1;
        BTreeNode * child = node->children[idx];
        if (child== nullptr) return -1;
        while (!child->isLeaf) {
            child = child->children[child->keyNum];
        }
        return child->keys[child->keyNum-1];
    } // 获取前驱关键字

    // 合并子结点【修复父节点指针偏移+内存释放】
    void mergeChild(BTreeNode* parent, int idx) {
        BTreeNode* left = parent->children[idx];
        BTreeNode* right = parent->children[idx + 1];

        left->keys[left->keyNum++] = parent->keys[idx];
        for (int i = 0; i < right->keyNum; i++)
            left->keys[left->keyNum++] = right->keys[i];

        if (!left->isLeaf) {
            for (int i = 0; i <= right->keyNum; i++)
                left->children[left->keyNum - right->keyNum + i] = right->children[i];
        }

        for (int i = idx; i < parent->keyNum - 1; i++)
            parent->keys[i] = parent->keys[i + 1];
        parent->keyNum--;

        for (int i = idx + 1; i <= parent->keyNum; i++)
            parent->children[i] = parent->children[i + 1];
        parent->children[parent->keyNum + 1] = nullptr;

        delete right;
    }

    void borrowFromLeft(BTreeNode* parent, int idx) {
        if (parent == nullptr || idx <= 0) throw runtime_error("Error: No left sibling");
        BTreeNode* child = parent->children[idx];     // 缺关键字的节点
        BTreeNode* leftSib = parent->children[idx-1]; // 左兄弟节点
        if (child == nullptr || leftSib == nullptr || leftSib->keyNum <= minKeyNum) return;

        for (int i = child->keyNum; i > 0; --i) {
            child->keys[i] = child->keys[i-1];
        }
        child->keys[0] = parent->keys[idx-1];
        if (!child->isLeaf) {
            for (int i = child->keyNum + 1; i > 0; --i) {
                child->children[i] = child->children[i-1];
            }
            child->children[0] = leftSib->children[leftSib->keyNum];
        }
        child->keyNum++;
        parent->keys[idx-1] = leftSib->keys[leftSib->keyNum-1];
        leftSib->keyNum--;

    } // 向左兄弟借关键字
    int getSuccessor(BTreeNode* node, int idx) {
        if (node == nullptr) return -1;
        BTreeNode* child = node->children[idx];
        if (child == nullptr) return -1;
        while (!child->isLeaf) {
            child = child->children[0];
        }
        return child->keys[0];
    } // 获取后继关键字

    void borrowFromRight(BTreeNode* parent, int idx) {
        BTreeNode* c = parent->children[idx];
        BTreeNode* r = parent->children[idx + 1];

        c->keys[c->keyNum] = parent->keys[idx];
        if (!c->isLeaf) c->children[c->keyNum + 1] = r->children[0];
        c->keyNum++;

        parent->keys[idx] = r->keys[0];

        for (int i = 0; i < r->keyNum - 1; i++) r->keys[i] = r->keys[i + 1];
        if (!r->isLeaf)
            for (int i = 0; i < r->keyNum; i++) r->children[i] = r->children[i + 1];

        r->keyNum--;
    }
    // 向右兄弟借关键字

    pair<BTreeNode*,int> findFather(BTreeNode* node, BTreeNode* child) {
        if (node == nullptr || child == nullptr) return {nullptr, -1};
        int i=0;
        for (; i <= node->keyNum; ++i) {
            if (node->children[i] == child) return {node, i};
            if (i < node->keyNum && node->keys[i] > child->keys[0]) break;
        }
        return findFather(node->children[i], child);
    } // 查找父节点

    void fixNodeUnderflow(BTreeNode* parent, int idx) {
        if (parent == nullptr || idx < 0 || idx > parent->keyNum) return;
        BTreeNode* curNode = parent->children[idx];
        if (curNode == nullptr || curNode->keyNum >= minKeyNum) return;

        // 方案1：向左兄弟借关键字（左兄弟存在且有多余）
        if (idx > 0 && parent->children[idx-1]->keyNum > minKeyNum) {
            borrowFromLeft(parent, idx);
        }
            // 方案2：向右兄弟借关键字（右兄弟存在且有多余）
        else if (idx < parent->keyNum && parent->children[idx+1]->keyNum > minKeyNum) {
            borrowFromRight(parent, idx);
        }
            // 方案3：借位失败 → 合并子节点
        else {
            if (idx == parent->keyNum) idx--; // 合并最后两个节点
            mergeChild(parent, idx);
            // 父节点合并后可能下溢，递归修复（根节点除外）
            if (parent->keyNum < minKeyNum) {
                auto [father,i] = findFather(root, parent);
                if (father != nullptr) {
                    fixNodeUnderflow(father, i);
                }
            }
        }
    }

    bool isKeyExist(BTreeNode* node, int key) const {
        if (node == nullptr) return false;
        int i=0;
        for (; i < node->keyNum; ++i) {
            if (node->keys[i] == key) return true;
            if (node->keys[i] > key) break;
        }
        if (node->isLeaf) return false;
        return isKeyExist(node->children[i], key);
    } // 查找关键字
public:
    // 构造函数（指定阶数m）
    BTree(int m) : order(m), minKeyNum((m + 1) / 2 - 1), root(new BTreeNode(m, true)) {}
    // 析构函数
    ~BTree() { destroy(root); }

    // 核心接口声明
    void destroy(BTreeNode* node) {
        if (node == nullptr) return;
        for (int i = 0; i <= node->keyNum; ++i) {
            destroy(node->children[i]);
        }
        delete node;
        node= nullptr;
    }              // 递归销毁树
    bool search(int key) const {
        return isKeyExist(root, key);
    }             // 查找关键字
    void insert(int key) {
        if (root->keyNum == order - 1) {
            BTreeNode* newRoot = new BTreeNode(order, false);
            newRoot->children[0] = root;
            splitChild(newRoot, 0);
            root = newRoot;
        }
        insertNonFull(root, key);
    }                    // 插入关键字
    bool remove(int key) {
        BTreeNode* tmpFather = nullptr;
        bool state = removeKey(root, tmpFather, key, -1);
        if (root->keyNum == 0 && !root->isLeaf) {
            BTreeNode* oldRoot = root;
            root = root->children[0];
            delete oldRoot;
        }
        return state;
    }                    // 删除关键字
    // 对外接口：层次遍历打印树结构（完全重构，打印正确）
    void printTree() const {
        if (root == nullptr || root->keyNum == 0) {
            cout << "B-Tree is empty!" << endl;
            return;
        }
        vector<BTreeNode*> curLayer;
        curLayer.push_back(root);
        int level = 1;
        while (!curLayer.empty()) {
            vector<BTreeNode*> nextLayer;
            cout << "Level " << level << ": ";
            for (auto node : curLayer) {
                if (node == nullptr || node->keyNum == 0) continue;
                // 打印当前节点所有关键字
                for (int i = 0; i < node->keyNum; ++i) {
                    cout << node->keys[i] << " ";
                }
                cout << "| ";
                // 收集下一层子节点
                for (int i = 0; i <= node->keyNum; ++i) {
                    if (node->children[i] != nullptr) {
                        nextLayer.push_back(node->children[i]);
                    }
                }
            }
            cout << endl;
            curLayer = nextLayer;
            level++;
        }
    }
};

class BPlusTree {
private:
    struct BPlusNode {
        vector<int> keys;
        vector<BPlusNode*> children;
        int keyNum;
        bool isLeaf;
        BPlusNode* nextLeaf;
        explicit BPlusNode(int m,bool leaf=false):keys(m),children(m+1),keyNum(0),isLeaf(leaf),nextLeaf(nullptr){
            fill(children.begin(),children.end(),nullptr);
        }
    };

    int order, minKeyNum;
    BPlusNode* root;
    BPlusNode* headLeaf;

    /* ---------- split ---------- */
    void splitChild(BPlusNode* p,int idx){
        BPlusNode* y=p->children[idx];
        BPlusNode* z=new BPlusNode(order,y->isLeaf);
        int mid=order/2;

        if(y->isLeaf){
            for(int i=mid;i<y->keyNum;i++) z->keys[z->keyNum++]=y->keys[i];
            y->keyNum=mid;
            z->nextLeaf=y->nextLeaf;
            y->nextLeaf=z;
            for(int i=p->keyNum;i>idx;i--) p->keys[i]=p->keys[i-1];
            p->keys[idx]=z->keys[0];
        }else{
            for(int i=mid+1;i<y->keyNum;i++) z->keys[z->keyNum++]=y->keys[i];
            for(int i=mid+1;i<=y->keyNum;i++) z->children[i-(mid+1)]=y->children[i];
            int up=y->keys[mid];
            y->keyNum=mid;
            for(int i=p->keyNum;i>idx;i--) p->keys[i]=p->keys[i-1];
            p->keys[idx]=up;
        }
        for(int i=p->keyNum+1;i>idx+1;i--) p->children[i]=p->children[i-1];
        p->children[idx+1]=z;
        p->keyNum++;
    }

    /* ---------- insert ---------- */
    void insertNonFull(BPlusNode* x,int k){
        int i=x->keyNum-1;
        if(x->isLeaf){
            while(i>=0 && k<x->keys[i]){
                x->keys[i+1]=x->keys[i]; i--;
            }
            x->keys[i+1]=k;
            x->keyNum++;
        }else{
            while(i>=0 && k<x->keys[i]) i--;
            i++;
            if(x->children[i]->keyNum==order){
                splitChild(x,i);
                if(k>x->keys[i]) i++;
            }
            insertNonFull(x->children[i],k);
        }
    }

    /* ---------- search ---------- */
    BPlusNode* findLeafNode(int k) const{
        BPlusNode* cur=root;
        while(!cur->isLeaf){
            int i=0;
            while(i<cur->keyNum && k>=cur->keys[i]) i++;
            cur=cur->children[i];
        }
        return cur;
    }

    /* ---------- borrow & merge ---------- */
    void borrowFromLeft(BPlusNode* p,int idx){
        BPlusNode* c=p->children[idx];
        BPlusNode* l=p->children[idx-1];
        if(c->isLeaf){
            for(int i=c->keyNum;i>0;i--) c->keys[i]=c->keys[i-1];
            c->keys[0]=l->keys[--l->keyNum];
            p->keys[idx-1]=c->keys[0];
            c->keyNum++;
        }else{
            for(int i=c->keyNum;i>0;i--) c->keys[i]=c->keys[i-1];
            c->keys[0]=p->keys[idx-1];
            p->keys[idx-1]=l->keys[--l->keyNum];
            for(int i=c->keyNum+1;i>0;i--) c->children[i]=c->children[i-1];
            c->children[0]=l->children[l->keyNum+1];
            c->keyNum++;
        }
    }

    void borrowFromRight(BPlusNode* p,int idx){
        BPlusNode* c=p->children[idx];
        BPlusNode* r=p->children[idx+1];
        if(c->isLeaf){
            c->keys[c->keyNum++]=r->keys[0];
            for(int i=0;i<r->keyNum-1;i++) r->keys[i]=r->keys[i+1];
            r->keyNum--;
            p->keys[idx]=r->keys[0];
        }else{
            c->keys[c->keyNum++]=p->keys[idx];
            p->keys[idx]=r->keys[0];
            for(int i=0;i<r->keyNum-1;i++) r->keys[i]=r->keys[i+1];
            for(int i=0;i<=r->keyNum;i++) r->children[i]=r->children[i+1];
            r->keyNum--;
        }
    }

    void mergeChild(BPlusNode* p,int idx){
        BPlusNode* l=p->children[idx];
        BPlusNode* r=p->children[idx+1];
        if(l->isLeaf){
            for(int i=0;i<r->keyNum;i++) l->keys[l->keyNum++]=r->keys[i];
            l->nextLeaf=r->nextLeaf;
        }else{
            l->keys[l->keyNum++]=p->keys[idx];
            for(int i=0;i<r->keyNum;i++) l->keys[l->keyNum++]=r->keys[i];
            for(int i=0;i<=r->keyNum;i++) l->children[l->keyNum-r->keyNum+i]=r->children[i];
        }
        for(int i=idx;i<p->keyNum-1;i++) p->keys[i]=p->keys[i+1];
        for(int i=idx+1;i<=p->keyNum;i++) p->children[i]=p->children[i+1];
        p->keyNum--;
        delete r;
    }

    void fixUnderflow(BPlusNode* p,int idx){
        if(p->children[idx]->keyNum>=minKeyNum) return;
        if(idx>0 && p->children[idx-1]->keyNum>minKeyNum) borrowFromLeft(p,idx);
        else if(idx<p->keyNum && p->children[idx+1]->keyNum>minKeyNum) borrowFromRight(p,idx);
        else{
            if(idx==p->keyNum) idx--;
            mergeChild(p,idx);
            if(p!=root && p->keyNum<minKeyNum){
                auto [fa,i]=findFather(root,p);
                if(fa) fixUnderflow(fa,i);
            }
        }
    }

    pair<BPlusNode*,int> findFather(BPlusNode* cur,BPlusNode* child){
        if(cur->isLeaf) return {nullptr,-1};
        for(int i=0;i<=cur->keyNum;i++){
            if(cur->children[i]==child) return {cur,i};
            if(i<cur->keyNum && child->keys[0]<cur->keys[i]) break;
        }
        return findFather(cur->children[cur->keyNum],child);
    }

public:
    explicit BPlusTree(int m):order(m),minKeyNum(m/2),root(new BPlusNode(m,true)),headLeaf(root){}

    void insert(int k){
        if(root->keyNum==order){
            BPlusNode* s=new BPlusNode(order,false);
            s->children[0]=root;
            splitChild(s,0);
            root=s;
        }
        insertNonFull(root,k);
    }

    bool search(int k) const{
        BPlusNode* l=findLeafNode(k);
        for(int i=0;i<l->keyNum;i++) if(l->keys[i]==k) return true;
        return false;
    }

    bool remove(int k){
        BPlusNode* leaf=findLeafNode(k);
        int i=0;
        while(i<leaf->keyNum && leaf->keys[i]!=k) i++;
        if(i==leaf->keyNum) return false;
        for(int j=i;j<leaf->keyNum-1;j++) leaf->keys[j]=leaf->keys[j+1];
        leaf->keyNum--;
        if(leaf!=root && leaf->keyNum<minKeyNum){
            auto [fa,idx]=findFather(root,leaf);
            if(fa) fixUnderflow(fa,idx);
        }
        if(root->keyNum==0 && !root->isLeaf){
            BPlusNode* old=root;
            root=root->children[0];
            delete old;
        }
        return true;
    }

    void printLeafLink(){
        BPlusNode* p=root;
        while(!p->isLeaf) p=p->children[0];
        while(p){
            for(int i=0;i<p->keyNum;i++) cout<<p->keys[i]<<" ";
            p=p->nextLeaf;
        }
        cout<<"\n";
    }
};

11, 图

(1), 广搜与深搜（图的遍历）

定义

• 广搜（BFS）：从图的某个顶点出发，先访问该顶点，然后依次访问该顶点的所有未被访问过的邻接顶点，再按此规则访问这些邻接顶点的未被访问过的邻接顶点，直到所有顶点都被访问过。
• 深搜（DFS）：从图的某个顶点出发，先访问该顶点，然后依次访问该顶点的所有未被访问过的邻接顶点，再按此规则访问这些邻接顶点的未被访问过的邻接顶点，直到所有顶点都被访问过。

class GraphTraversal {
public:
    // 深度优先搜索（DFS）- 邻接矩阵实现
    static void DFS_AM(const vector<vector<int>>& graph, int startIdx, vector<bool>& visited, void (*visit)(int)) {
        if (visited[startIdx]) return;
        visited[startIdx] = true;
        visit(startIdx);
        for (int i = 0; i < graph[startIdx].size(); ++i) {
            if (graph[startIdx][i] == 1) {
                DFS_AM(graph, i, visited, visit);
            }
        }
    }
    // 深度优先搜索（DFS）- 邻接表实现
    static void DFS_AL(const vector<vector<int>>& graph, int startIdx, vector<bool>& visited, void (*visit)(int)) {
        if (visited[startIdx]) return;
        visited[startIdx] = true;
        visit(startIdx);
        for (int nxt: graph[startIdx]) {
            DFS_AL(graph, nxt, visited, visit);
        }
    }

    // 广度优先搜索（BFS）- 邻接矩阵实现
    static void BFS_AM(const vector<vector<int>>& graph, int startIdx, vector<bool>& visited, void (*visit)(int)) {
        queue<int> q;
        q.push(startIdx);
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            if (visited[cur]) continue;
            visited[cur] = true;
            visit(cur);
            for (int i = 0; i < graph[cur].size(); ++i) {
                if (graph[cur][i] == 1) {
                    q.push(i);
                }
            }
        }
    }
    // 广度优先搜索（BFS）- 邻接表实现
    static void BFS_AL(const vector<vector<int>>& graph, int startIdx, vector<bool>& visited, void (*visit)(int)) {
        queue<int> q;
        q.push(startIdx);
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            if (visited[cur]) continue;
            visited[cur] = true;
            visit(cur);
            for (int nxt: graph[cur]) {
                q.push(nxt);
            }
        }
    }

    // 全图遍历（处理非连通图）
    static void traverseAll_AM(const vector<vector<int>>& graph, void (*visit)(int)) {
        vector<bool> visited(graph.size(), false);
        for (int i = 0; i < graph.size(); ++i) {
            if (!visited[i]) {
                BFS_AM(graph, i, visited, visit);
            }
        }
    }
    static void traverseAll_AL(const vector<vector<int>>& graph, void (*visit)(int)) {
        vector<bool> visited(graph.size(), false);
        for (int i = 0; i < graph.size(); ++i) {
            if (!visited[i]) {
                BFS_AL(graph, i, visited, visit);
            }
        }
    }
};

(2), 最小生成树

Prim算法介绍

Prim算法是一种贪心算法，用于在加权无向图中找到最小生成树（MST）。给定一个加权无向图，该算法从一个顶点开始，逐步扩展生成树，每次选择一个与生成树相连且权重最小的顶点加入生成树，直到所有顶点都被包含在生成树中。使用与稠密图相关的邻接矩阵表示图，时间复杂度为O(V^2)，其中V为顶点数。

Kruskal算法介绍

Kruskal算法也是一种贪心算法，用于在加权无向图中找到最小生成树（MST）。该算法按照边的权重从小到大排序，依次选择权重最小的边加入生成树，直到所有顶点都被包含在生成树中。使用并查集数据结构来判断加入边是否会形成环，时间复杂度为O(ElogV)，其中E为边数，V为顶点数。

并查集

并查集是一种数据结构，用于处理一些不相交集合的合并及查询问题。它支持两种操作：查找（Find）和合并（Union）。查找操作可以确定一个元素所属的集合，合并操作可以将两个集合合并为一个集合。并查集通常用于解决图论中的连通性问题，例如判断图中是否存在环。

// 并查集
class Union {
    vector<int> father;
    int n;
public:
    Union(int n) : father(n), n(n) {
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }

    int find(int x) {
        if (father[x] == x) {
            return x;
        }
        father[x] = find(father[x]);
        return father[x];
    }

    void join(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            father[fx] = fy;
        }
    }

    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};

class GraphConnectivity {
public:
    static void Prim(const vector<vector<pair<int, int>>>& graph) {
        if (graph.empty()) return; // Return directly for empty graph
        int n = graph.size();      // Total number of vertices
        vector<vector<int>> resEdges; // Store edges of Minimum Spanning Tree {u, v, weight}
        vector<bool> inMST(n, false); // Mark if a vertex is added to MST set
        long long totalWeight = 0;    // Total weight of MST (use long long to prevent overflow)

        // Start building MST from vertex 0 (any starting vertex is optional for Prim's algorithm)
        inMST[0] = true;
        // MST requires exactly n-1 edges, loop for n-1 times (more efficient than while)
        for (int cnt = 0; cnt < n - 1; ++cnt) {
            int minWeight = INT_MAX;
            int u = -1, v = -1;      // Record two endpoints of the edge with minimum weight

            // Traverse all vertices that have been added to MST set
            for (int i = 0; i < n; ++i) {
                if (!inMST[i]) continue; // Skip vertices not in MST set

                // Traverse all adjacent edges of vertex i
                for (auto& edge : graph[i]) {
                    int neighbor = edge.first;  // Adjacent vertex number
                    int weight = edge.second;   // Weight of the edge
                    // Core condition: neighbor not in MST & smaller edge weight
                    if (!inMST[neighbor] && weight < minWeight) {
                        minWeight = weight;
                        u = i;
                        v = neighbor;
                    }
                }
            }

            // Boundary check: no valid edge found → the graph is disconnected, MST does not exist
            if (minWeight == INT_MAX) {
                cout << "The graph is disconnected, Minimum Spanning Tree does not exist!" << endl;
                return;
            }

            // Add the minimum weight edge to result, add vertex v to MST set
            resEdges.push_back({u, v, minWeight});
            totalWeight += minWeight;
            inMST[v] = true;
        }

        // Output edges and total weight of MST
        cout << "Edges of Minimum Spanning Tree (start vertex  end vertex)：" << endl;
        for (auto& e : resEdges) {
            cout << e[0] << " " << e[1] << endl;
        }
        cout << "Total weight of Minimum Spanning Tree: " << totalWeight << endl;
    }
/**
 * 使用Kruskal算法计算最小生成树的函数
 */
    static void Kruskal(int n,vector<vector<int>>& edges) {
        sort(edges.begin(), edges.end(), [](vector<int>& a, vector<int>& b) {
            return a[2] < b[2];
        });
        Union uf(n);
        vector<vector<int>> resEdges;
        long long totalWeight = 0;
        for (auto& edge: edges) {
            if (uf.isConnected(edge[0], edge[1])) continue;
            uf.join(edge[0], edge[1]);
            resEdges.push_back(edge);
            totalWeight += edge[2];
        }
        for (auto& edge: resEdges) {
            cout<<edge[0] << " " << edge[1] << endl;
        }
        cout << totalWeight << endl;
    }
};

(3), 拓扑排序与关键路径

定义

拓扑排序是对有向无环图（DAG）的顶点进行排序，使得对于图中的每一条有向边 (u, v)，顶点 u 在排序中都出现在顶点 v 之前。拓扑排序的结果可以唯一确定一个拓扑序列

应用场景

关键字路径问题：在项目中，关键路径指的是从开始到结束的一系列活动（或任务），这些活动的完成顺序不能改变，否则整个项目将无法按时完成。
找到第i个关键路径：在拓扑排序的基础上，可以找到从源点到汇点的最长路径。
找到每个节点的 最早开始时间和最晚开始时间，从而确定关键路径。

class DAGApplications {
public:
    // 1. 拓扑排序（邻接表实现，返回拓扑序列）
    static vector<int> topologicalSort(const vector<vector<int>>& graph) {
        vector<int> inDegrees(graph.size(), 0);
        vector<int> res;
        for (int i=0;i<graph.size();i++){
            for (int j:graph[i]){
                inDegrees[j]++;
            }
        }
        queue<int> q;
        for (int i = 0; i < inDegrees.size(); ++i) {
            if (inDegrees[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            res.push_back(cur);
            for (int nxt: graph[cur]) {
                inDegrees[nxt]--;
                if (inDegrees[nxt] == 0) {
                    q.push(nxt);
                }
            }
        }
        return res;
    }

    // 2. 关键路径（AOE网，邻接表实现）
    // 参数：graph=AOE网，criticalEdges=存储关键边（v1,v2），edgeCount=关键边数量
    static void criticalPath(const vector<vector<pair<int, int>>>& graph, vector<vector<int>>& criticalEdges, int& projectTime) {
        int n=graph.size();
        vector<int> inDegrees(graph.size(), 0);
        for (int i=0;i<graph.size();i++){
            for (auto [j, w] : graph[i]){
                inDegrees[j]++;
            }
        }

        vector<int> VE(n,0);

        queue<int> q;
        int c=0;
        for (int i = 0; i < inDegrees.size(); ++i) {
            if (inDegrees[i] == 0) {
                q.push(i);
                VE[i] = 0;
            }
        }

        while (!q.empty()) {
            int cur=q.front();
            q.pop();
            c++;

            for (auto [nxt, w]:graph[cur]){
                inDegrees[nxt]--;
                if (inDegrees[nxt] == 0) {
                    q.push(nxt);
                }
                VE[nxt]=max(VE[nxt],VE[cur]+w);
            }
        }

        if (c != n) {
            cout << "The graph is not a DAG." << endl;
            return;
        }

        vector<int> VL(n,INT_MAX);
        vector<int> outDegrees(graph.size(), 0);
        vector<vector<pair<int, int>>> reverseGraph(n);
        for (int i=0;i<graph.size();i++){
            for (auto [j, w] : graph[i]){
                outDegrees[i]++;
                reverseGraph[j].push_back({i,w});
            }
        }

        projectTime=0;

        for (int i = 0; i < outDegrees.size(); ++i) {
            if (outDegrees[i] == 0) {
                q.push(i);
                VL[i]=VE[i];
                projectTime=max(projectTime,VL[i]);
            }
        }

        while (!q.empty()) {
            int cur=q.front();
            q.pop();

            for (auto [pre, w]:reverseGraph[cur]){
                outDegrees[pre]--;
                if (outDegrees[pre]== 0) {
                    q.push(pre);
                }
                VL[pre]=min(VL[pre],VL[cur]-w);
            }
        }

        for (int i=0;i<n;i++){
            for (auto [j, w]:graph[i]){
                if (VE[i]+w==VL[j]){
                    criticalEdges.push_back({i,j});
                }
            }
        }
    }
};

(4), 最短路径

定义

最短路径问题是指在一个加权图中，找到从源点到汇点的最短路径。最短路径问题有多种算法，包括Dijkstra算法、Bellman-Ford算法和Floyd-Warshall算法。

应用场景

1. 地图导航：在地图导航中，最短路径算法可以用于计算从起点到终点的最短路径。
2. 网络路由：在网络中，最短路径算法可以用于计算从一个路由器到另一个路由器的最佳路径。
3. 项目管理：在项目中，最短路径算法可以用于计算从项目开始到结束的最短时间。

class ShortestPath {
public:
    // 2. 单源最短路径 - Dijkstra算法（邻接表实现）
    static void Dijkstra(const vector<vector<pair<int, int>>>& graph, int startIdx, vector<int>& dist) {
        dist.resize(graph.size(), INT_MAX);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
        pq.push({0,startIdx});
        dist[startIdx]=0;
        while (!pq.empty()) {
            auto [d, cur] = pq.top();
            pq.pop();
            if (d > dist[cur]) continue;
            for (auto [nxt, w]: graph[cur]) {
                if (dist[cur] + w<dist[nxt]) {
                    dist[nxt] = dist[cur] + w;
                    pq.push({dist[nxt], nxt});
                }
            }
        }
    }


    // 3. 多源最短路径 - Floyd算法（邻接矩阵实现）
    // 参数：graph=带权图，dist=存储任意两点间最短路径长度，path=存储路径中间节点
    static void Floyd(int n,const vector<vector<int>>& edges, vector<vector<int>>& dist, vector<vector<int>>& path) {
        dist.resize(n,vector<int>(n,INT_MAX));
        path.resize(n,vector<int>(n,-1));

        for (int i=0;i<n;i++) {
            dist[i][i]=0;
        }
        for (auto& edge:edges){
            dist[edge[0]][edge[1]]=edge[2];
            path[edge[0]][edge[1]]=-2;
        }
        for (int k=0;k<n;k++){
            for (int i=0;i<n;i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k]!=INT_MAX && dist[k][j]!=INT_MAX && dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = k;
                    }
                }
            }
        }
    }

    // 辅助接口：打印最短路径（从源点start到终点end）
    static void printPath(int start, int end, vector<vector<int>>& paths, vector<int>& path) {
        if (start==end) {
            path.push_back(start);
            return;
        }
        int mid=paths[start][end];
        if (mid==-1){
            cout<<"Not reachable"<<endl;
            return;
        }
        if (mid==-2){
            path.push_back(start);
            path.push_back(end);
            return;
        }
        printPath(start,mid,paths,path);
        path.pop_back();
        printPath(mid,end,paths,path);
    }
};

12, 搜索

(1), 线性探测哈希

这里用一个有限map来表示

当发生哈希冲突时，线性探测会顺序检查下一个下标，直到找到空闲位置或遍历完所有下标。

// 哈希表：开放定址法（线性探测）实现，固定容量BASE
template <typename K, typename V>
class Unordered_Map_Limit {
private:
    static constexpr int BASE = 1000; // 编译期常量，更高效
    vector<pair<K, V>> data;         // 存储键值对的核心数组
    bool* is_occupied;               // 标记下标是否被占用（解决删除后查找失效）

    // 哈希函数：映射key到[0, BASE-1]的整数
    int hash(const K& key) const {
        size_t hash_val = std::hash<K>{}(key);
        return static_cast<int>(hash_val % BASE);
    }

    // 查找函数：返回key对应下标，未找到返回-1
    int find(const K& key) const {
        int idx = hash(key);
        for (int i = 0; i < BASE; ++i) {
            int cur_idx = (idx + i) % BASE;
            if (!is_occupied[cur_idx]) return -1;
            if (data[cur_idx].first == key) return cur_idx;
        }
        return -1; // 哈希表满，未找到
    }

public:
    // 构造函数：初始化数组+占用标记
    Unordered_Map_Limit() : data(BASE), is_occupied(new bool[BASE]{false}) {}

    // 析构函数：释放动态内存，防止泄漏
    ~Unordered_Map_Limit() {
        delete[] is_occupied;
    }

    // 插入/更新键值对：存在则更新，不存在则插入
    void insert(const K& key, const V& value) {
        int idx = find(key);
        if (idx != -1) {
            data[idx].second = value;
            return;
        }
        int hash_idx = hash(key);
        for (int i = 0; i < BASE; ++i) {
            int cur_idx = (hash_idx + i) % BASE;
            if (!is_occupied[cur_idx]) {
                data[cur_idx] = make_pair(key, value);
                is_occupied[cur_idx] = true;
                break;
            }
        }
    }

    // 删除指定key：成功true，失败false
    bool erase(const K& key) {
        int idx = find(key);
        if (idx == -1) return false;
        is_occupied[idx] = false; // 逻辑删除，保留探测链
        return true;
    }

    // 查找key：存在则赋值value并返回true，否则false
    bool get(const K& key, V& value) const {
        int idx = find(key);
        if (idx == -1) return false;
        value = data[idx].second;
        return true;
    }

    // 重载[]运算符：支持map[key]读写，与std库行为一致
    V& operator[](const K& key) {
        int idx = find(key);
        if (idx != -1) return data[idx].second;

        int hash_idx = hash(key);
        for (int i = 0; i < BASE; ++i) {
            int cur_idx = (hash_idx + i) % BASE;
            if (!is_occupied[cur_idx]) {
                data[cur_idx] = make_pair(key, V());
                is_occupied[cur_idx] = true;
                return data[cur_idx].second;
            }
        }
        throw std::out_of_range("Unordered_Map_Limit is full!");
    }

    // 判断哈希表是否为空
    bool empty() const {
        for (int i = 0; i < BASE; ++i) {
            if (is_occupied[i]) return false;
        }
        return true;
    }

    // 获取有效键值对数量
    int size() const {
        int cnt = 0;
        for (int i = 0; i < BASE; ++i) {
            if (is_occupied[i]) cnt++;
        }
        return cnt;
    }
};

(2), 无序字典（Unordered Dictionary）

使用哈希函数，当发生哈希冲突时，使用链地址法解决。

// 哈希表：链地址法实现，无容量上限，冲突处理更友好
template <typename K, typename V>
class Unordered_Map {
private:
    static constexpr int BASE = 1000;
    vector<vector<pair<K, V>>> data; // 桶数组：每个桶是一个键值对链表
    const pair<K, V> EMPTY_NODE;     // 空节点标记

    // 哈希函数：映射key到桶下标
    int hash(const K& key) const {
        size_t hash_val = std::hash<K>{}(key);
        return static_cast<int>(hash_val % BASE);
    }

    // 查找key：返回对应桶的下标，未找到返回-1（核心修复）
    int find_index(const K& key) const {
        int idx = hash(key);
        for (const auto& bucket : data[idx]) {
            if (bucket.first == key) return idx;
        }
        return -1;
    }

    // 查找迭代器：返回桶内目标元素的迭代器（核心修复）
    typename vector<pair<K, V>>::iterator find_iter(const K& key) {
        int idx = hash(key);
        for (auto it = data[idx].begin(); it != data[idx].end(); ++it) {
            if (it->first == key) return it;
        }
        return data[idx].end();
    }

    // 更新key对应的value
    void update(const K& key, const V& value) {
        auto it = find_iter(key);
        if (it != data[hash(key)].end()) {
            it->second = value;
        }
    }

public:
    // 构造函数：初始化桶数组+空节点
    Unordered_Map() : data(BASE), EMPTY_NODE(K(), V()) {}

    // 析构函数：vector自动释放内存，无需手动操作
    ~Unordered_Map() = default;

    // 插入/更新键值对
    void insert(const K& key, const V& value) {
        if (find_index(key) != -1) {
            update(key, value);
            return;
        }
        int hash_idx = hash(key);
        data[hash_idx].emplace_back(key, value);
    }

    // 删除指定key
    bool erase(const K& key) {
        int idx = hash(key);
        auto it = find_iter(key);
        if (it == data[idx].end()) return false;
        data[idx].erase(it); // 迭代器直接删除，安全无失效
        return true;
    }

    // 查找key的value，未找到返回默认值
    V get(const K& key) const {
        int idx = hash(key);
        for (const auto& bucket : data[idx]) {
            if (bucket.first == key) return bucket.second;
        }
        return EMPTY_NODE.second;
    }

    // 重载[]运算符：支持map[key]读写（修复引用返回问题）
    V& operator[](const K& key) {
        int idx = hash(key);
        auto it = find_iter(key);
        if (it != data[idx].end()) return it->second;

        data[idx].emplace_back(key, V());
        return data[idx].back().second;
    }

    // 判断哈希表是否为空
    bool empty() const {
        for (int i = 0; i < BASE; ++i) {
            if (!data[i].empty()) return false;
        }
        return true;
    }

    // 获取有效键值对数量
    int size() const {
        int cnt = 0;
        for (int i = 0; i < BASE; ++i) {
            cnt += data[i].size();
        }
        return cnt;
    }
};

// 哈希集合：链地址法实现，存储唯一key，无value
template <typename K>
class Unordered_Set {
private:
    static constexpr int BASE = 1000;
    vector<vector<K>> data; // 桶数组：每个桶是一个key链表
    const K EMPTY_NODE;     // 空节点标记

    // 哈希函数：映射key到桶下标
    int hash(const K& key) const {
        size_t hash_val = std::hash<K>{}(key);
        return static_cast<int>(hash_val % BASE);
    }

    // 查找key：存在返回true，否则false
    bool find(const K& key) const {
        int idx = hash(key);
        for (const auto& val : data[idx]) {
            if (val == key) return true;
        }
        return false;
    }

public:
    // 构造函数：初始化桶数组+空节点
    Unordered_Set() : data(BASE), EMPTY_NODE(K()) {}

    // 析构函数：自动释放内存
    ~Unordered_Set() = default;

    // 插入key：已存在则跳过，保证唯一性
    void insert(const K& key) {
        if (find(key)) return;
        int hash_idx = hash(key);
        data[hash_idx].push_back(key);
    }

    // 删除指定key：成功true，失败false（核心修复）
    bool erase(const K& key) {
        int idx = hash(key);
        for (auto it = data[idx].begin(); it != data[idx].end(); ++it) {
            if (*it == key) {
                data[idx].erase(it);
                return true;
            }
        }
        return false;
    }

    // 判断key是否存在
    bool exist(const K& key) const {
        return find(key);
    }

    // 判断集合是否为空
    bool empty() const {
        for (int i = 0; i < BASE; ++i) {
            if (!data[i].empty()) return false;
        }
        return true;
    }

    // 获取集合中元素数量
    int size() const {
        int cnt = 0;
        for (int i = 0; i < BASE; ++i) {
            cnt += data[i].size();
        }
        return cnt;
    }
};

13, 排序

(1), 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历列表的工作是重复地进行直到没有再需要交换，也就是说该列表已经排序完成。

void bubbleSort(vector<int>& arr, bool log=false) {
    for (int i=0;i<arr.size()-1;i++){
        for (int j=0;j<arr.size()-1-i;j++){
            if (arr[j]>arr[j+1]) {
                swap(arr[j],arr[j+1]);
            }
        }
        if (log) {
            for (int j: arr) {
                cout<<j<<" ";
            }
            cout<<endl;
        }
    }
}

(2), 选择排序

选择排序是一种简单的排序算法，它的工作原理是每次从待排序的元素中选择最小（或最大）的一个，存放到排序序列的起始位置，直到全部待排序的元素排完。

void selectionSort(vector<int>& arr, bool log=false) {
    for (int i=0;i<arr.size()-1;i++){
        int minIdx = i;
        for (int j=i+1;j<arr.size();j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[i], arr[minIdx]);
        if (log) {
            for (int j: arr) {
                cout << j << " ";
            }
            cout << endl;
        }
    }
}

(3), 插入排序

插入排序是一种简单的排序算法，它的工作原理是将待排序的元素一个一个地插入到已经排序的序列中，从而得到一个新的排序序列。

void insertionSort(vector<int>& arr, bool log = false) {
    if (arr.empty() || arr.size() <= 1) return;
    vector<int> sorted;
    sorted.reserve(arr.size()); // ✅ 优化：预分配内存，提升效率
    for (int i = 0; i < arr.size(); i++) {
        int l = 0, r = (int)sorted.size() - 1;
        int idx = (int)sorted.size();
        // 二分查找插入位置（优化版插入排序，你的设计亮点保留）
        while (l <= r) {
            int mid = l + (r - l) / 2; // ✅ 修复：防整数溢出
            if (arr[i] <= sorted[mid]) {
                idx = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        sorted.insert(sorted.begin() + idx, arr[i]);
    }
    arr = move(sorted); // ✅ 致命修复：将排序结果回写到原数组
    if (log) {
        for (int num : arr) cout << num << " ";
        cout << endl;
    }
}

(4), 希尔排序

希尔排序是一种基于插入排序的排序算法，它的工作原理是先将待排序的元素按照一定的间隔分组，对每组元素进行插入排序，然后逐渐缩小间隔，重复以上过程，直到间隔为1，最后进行一次插入排序。

void shellSort(vector<int>& arr, bool log=false) {
    for (int gap = arr.size()/2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.size(); i++) {
            int j = i;
            int temp = arr[i];
            while (j >= gap && arr[j-gap] > temp) {
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
    if (log) {
        for (int num: arr) {
            cout<<num<<" ";
        }
        cout<<endl;
    }
}

(5), 快速排序

快速排序是一种基于分治法的排序算法，它的工作原理是选择一个基准元素，将待排序的元素分为两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行快速排序，最后将两部分合并起来。

void quickSort(vector<int>& arr, bool log=false, int randomType = 0) {
    function<void (int, int)> quickSort = [&](int left, int right) {
//            cnt++;
        if (left >= right) {
            return;
        }

        int pivot = getPivot(arr, left, right, randomType);

        int i = left, j = right;
        while (i <= j) {
            while (arr[i] < pivot)  i++;
            while (arr[j] > pivot)  j--;
            if (i <= j) {
                swap(arr[i], arr[j]);
                i++;
                j--;
            }
        }
        quickSort(left, j);
        quickSort(i, right);

        if (log) {
            for (int num: arr) {
                cout<<num<<" ";
            }
            cout<<endl;
        }
    };

    quickSort(0, arr.size()-1);
//        cout<<cnt<<endl;
}
int getPivot(vector<int>& arr, int left, int right, int type) {
    int pivotIdx = left;
    switch (type) {
        case 0: pivotIdx = left; break;    // 左端点为基准
        case 1: pivotIdx = right; break;   // 右端点为基准
        case 2: pivotIdx = left + (right - left) / 2; break; // 中点为基准（防溢出）
        case 3: // ✅ 新增：随机基准（最优，推荐），解决有序数组退化问题
            srand((unsigned)time(nullptr));
            pivotIdx = left + rand() % (right - left + 1);
            break;
    }
    return arr[pivotIdx];
}

(6), 归并排序

归并排序是一种基于分治法的排序算法，它的工作原理是将待排序的元素分为两部分，分别对这两部分进行归并排序，最后将两部分合并起来。

void mergeSort(vector<int>& arr, bool log=false) {
    function<void (int, int)> mergeSort = [&](int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;
        while (i <= mid || j <= right) {
            if (i== mid+1) {
                temp[k++] = arr[j++];
            } else if (j == right+1) {
                temp[k++] = arr[i++];
            } else if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }

        for (int m=0;m<temp.size();m++) {
            arr[left+m] = temp[m];
        }
    };
    mergeSort(0, arr.size()-1);
    if (log) {
        for (int num:arr) {
            cout<<num<<" ";
        }
        cout<<endl;
    }
}

(7), 堆排序

堆排序是一种基于堆数据结构的排序算法，它的工作原理是将待排序的元素构建成一个大顶堆（或小顶堆），然后将堆顶元素与堆底元素交换，将最大（或最小）元素放到正确的位置，然后对剩余的元素重新构建堆，重复以上过程，直到堆为空。

void heapSort(vector<int>& arr, bool log = false) {
    function<void (int ,int, bool)> heapify = [&](int cur,int n, bool type) {
        if (type) {
            while (cur && arr[cur] < arr[(cur-1)/2]) {
                swap(arr[cur], arr[(cur-1)/2]);
                cur = (cur-1)/2;
            }
        } else {
            while (cur*2+1<n) {
                int left = cur*2+1;
                int right = cur*2+2;
                int maxIdx = left;
                if (right<n && arr[right]<arr[maxIdx]) {
                    maxIdx = right;
                }
                if (arr[cur]>arr[maxIdx]) {
                    swap(arr[cur], arr[maxIdx]);
                    cur = maxIdx;
                } else {
                    break;
                }
            }
        }

    };

    for (int i=0;i<arr.size();i++) {
        heapify(i, i+1, true);
    }

    vector<int> sortedArr;

    for (int i=0;i<arr.size();i++) {
        sortedArr.push_back(arr[0]);
        swap(arr[0], arr[arr.size()-1-i]);
        heapify(0, arr.size()-1-i, false);
        if (log) {
            for (int j: sortedArr) {
                cout<<j<<" ";
            }
            cout<<endl;
        }
    }
    arr = sortedArr;
}

通过这个，产生有限队列

// 通用优先级队列（堆实现）
// ElemType: 元素类型
// STL: 底层存储容器（默认vector，需支持push_back/pop_back/[]/size/empty）
// Compare: 比较器（默认less<ElemType>，实现大顶堆；greater则为小顶堆）
template <typename ElemType,
        typename STL = std::vector<ElemType>,
        typename Compare = std::less<ElemType>>
class PriorityQueue {
private:
    STL heap;          // 底层存储容器（堆的物理结构）
    Compare cmp;       // 比较器（决定堆的类型：大顶/小顶）

    // 向上调整（插入元素后，维护堆性质）
    void up(int idx) {
        // idx为当前元素下标，从0开始
        while (idx > 0) {
            int parent = (idx - 1) / 2;  // 父节点下标
            // 若父节点不满足比较规则，则交换并继续向上
            if (cmp(heap[parent], heap[idx])) {
                std::swap(heap[parent], heap[idx]);
                idx = parent;
            } else {
                break;  // 堆性质已满足，退出
            }
        }
    }

    // 向下调整（删除堆顶后，维护堆性质）
    void down(int idx) {
        int size = heap.size();
        while (true) {
            int left = 2 * idx + 1;   // 左子节点
            int right = 2 * idx + 2;  // 右子节点
            int target = idx;         // 记录需要交换的节点（初始为自身）

            // 找到子节点中满足比较规则的最大/最小节点
            if (left < size && cmp(heap[target], heap[left])) {
                target = left;
            }
            if (right < size && cmp(heap[target], heap[right])) {
                target = right;
            }

            // 若目标节点不是自身，交换并继续向下
            if (target != idx) {
                std::swap(heap[idx], heap[target]);
                idx = target;
            } else {
                break;  // 堆性质已满足，退出
            }
        }
    }

public:
    // 默认构造函数
    PriorityQueue() = default;

    // 禁用拷贝（如需拷贝可自行实现深拷贝）
    PriorityQueue(const PriorityQueue&) = delete;
    PriorityQueue& operator=(const PriorityQueue&) = delete;

    // 移动构造/赋值（提高性能）
    PriorityQueue(PriorityQueue&&) = default;
    PriorityQueue& operator=(PriorityQueue&&) = default;

    // 析构函数（依赖容器自身的析构）
    ~PriorityQueue() = default;

    /**
     * @brief 插入元素到优先级队列
     * @param val 待插入的元素
     */
    void push(const ElemType& val) {
        heap.push_back(val);          // 插入到容器尾部
        up(heap.size() - 1);          // 向上调整，维护堆性质
    }

    // 移动版本push（优化右值引用）
    void push(ElemType&& val) {
        heap.push_back(std::move(val));
        up(heap.size() - 1);
    }

    /**
     * @brief 弹出堆顶元素（优先级最高的元素）
     * @throw out_of_range 队列为空时抛出
     */
    void pop() {
        if (empty()) {
            throw std::out_of_range("PriorityQueue::pop: queue is empty");
        }
        // 堆顶与最后一个元素交换，删除最后一个元素
        std::swap(heap[0], heap.back());
        heap.pop_back();
        // 向下调整堆顶，维护堆性质
        if (!empty()) {
            down(0);
        }
    }

    /**
     * @brief 获取堆顶元素（不弹出）
     * @return 堆顶元素的引用
     * @throw out_of_range 队列为空时抛出
     */
    ElemType& top() {
        if (empty()) {
            throw std::out_of_range("PriorityQueue::top: queue is empty");
        }
        return heap[0];
    }

    // const版本top
    const ElemType& top() const {
        if (empty()) {
            throw std::out_of_range("PriorityQueue::top: queue is empty");
        }
        return heap[0];
    }

    /**
     * @brief 判断队列是否为空
     * @return 空返回true，否则false
     */
    bool empty() const noexcept {
        return heap.empty();
    }

    /**
     * @brief 获取队列中元素个数
     * @return 元素个数
     */
    size_t size() const noexcept {
        return heap.size();
    }

    /**
     * @brief 清空队列
     */
    void clear() noexcept {
        heap.clear();
    }
};

结束~