数据结构各种算法实现(C++模板)

### 数据结构各种算法实现(C++模板) #### 一、顺序表 **定义与特性：** 顺序表是一种线性数据结构，其元素在内存中连续存储，通过数组来实现。顺序表支持快速随机访问，但插入和删除操作相对较慢，因为它们可能需要移动大量元素。 **C++模板实现：** `Seqlist.h` 文件定义了顺序表的类 `SeqList`，它使用模板参数 `Type` 来存储任何类型的元素。构造函数接受一个可选参数 `sz`，表示列表的最大容量，默认为100。成员函数包括： - `Length()`：返回列表长度。 - `Find(x)`：查找元素 x 的位置。 - `IsElement(x)`：判断 x 是否在列表中。 - `Insert(x, i)`：在指定位置 i 插入元素 x。 - `Remove(x)`：删除元素 x。 - `IsEmpty()`：检查列表是否为空。 - `IsFull()`：检查列表是否已满。 - `Get(i)`：获取第 i 个元素。 - `Print()`：打印列表内容。 #### 二、单链表 **定义与特性：** 单链表是一种线性数据结构，其中每个节点包含数据和指向下一个节点的指针。单链表允许在任何位置插入或删除元素，但随机访问效率较低。 **C++模板实现：** `ListNode.h` 和 `SingleList.h` 分别定义了链表节点和链表类。`test.cpp` 文件用于测试单链表功能。 #### 三、双向链表 **定义与特性：** 双向链表是链表的一种变体，每个节点除了包含指向下一个节点的指针外，还包含指向前一个节点的指针，使得可以在两个方向上遍历链表。 **C++模板实现：** `NodeList.h` 和 `DoubleList.h` 定义了双向链表的节点和链表类。`Test.cpp` 用于测试双向链表的功能。 #### 四、循环链表 **定义与特性：** 循环链表是链表的一种变体，其中最后一个节点的指针指向头节点，形成一个循环。这简化了一些操作，如遍历整个链表。 **C++模板实现：** `ListNode.h` 和 `CircularList.h` 定义了循环链表的节点和链表类。`Test.cpp` 用于测试循环链表的功能。 #### 五、顺序栈 **定义与特性：** 栈是一种后进先出（LIFO）的数据结构，通常用于保存函数调用的上下文或解决表达式求值问题。 **C++模板实现：** `SeqStack.h` 定义了基于数组的栈类。`Test.cpp` 用于测试栈的功能。 #### 六、链式栈 **定义与特性：** 链式栈是基于链表实现的栈，相比顺序栈，它可以动态调整大小。 **C++模板实现：** `StackNode.h` 和 `LinkStack.h` 定义了链式栈的节点和栈类。`Test.cpp` 用于测试链式栈的功能。 #### 七、顺序队列 **定义与特性：** 队列是一种先进先出（FIFO）的数据结构，通常用于任务调度或缓存管理。 **C++模板实现：** `SeqQueue.h` 定义了基于数组的队列类。`Test.cpp` 用于测试队列的功能。 #### 八、链式队列 **定义与特性：** 链式队列是基于链表实现的队列，可以动态调整大小。 **C++模板实现：** `QueueNode.h` 和 `LinkQueue.h` 定义了链式队列的节点和队列类。`Test.cpp` 用于测试链式队列的功能。 #### 九、优先级队列 **定义与特性：** 优先级队列是一种特殊的队列，其中每个元素都有一个优先级，高优先级的元素总是被优先处理。 **C++模板实现：** `QueueNode.h`、`Compare.h` 和 `PriorityQueue.h` 定义了优先级队列的节点、比较器和队列类。`Test.cpp` 用于测试优先级队列的功能。 #### 十、串 **定义与特性：** 串是一系列字符的序列，通常用于文本处理。 **C++模板实现：** `MyString.h` 和 `MyString.cpp` 定义了字符串类及其成员函数。`test.cpp` 用于测试字符串类的功能。 #### 十一、二叉树 **定义与特性：** 二叉树是一种非线性数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。 **C++模板实现：** `BinTreeNode.h` 和 `BinaryTree.h` 定义了二叉树的节点和树类。`Test.cpp` 用于测试二叉树的功能。 #### 十二、线索二叉树 **定义与特性：** 线索二叉树是对二叉树进行线索化后的结果，其中空指针被用来指向前驱或后继节点，提高了树的遍历效率。 **C++模板实现：** `ThreadNode.h`、`ThreadTree.h` 和 `ThreadInorderIterator.h` 定义了线索二叉树的节点、树和中序迭代器类。`test.cpp` 用于测试线索二叉树的功能。 #### 十三、堆 **定义与特性：** 堆是一种完全二叉树，分为最大堆和最小堆，其中每个父节点的值都大于等于（最大堆）或小于等于（最小堆）其子节点的值。 **C++模板实现：** `MinHeap.h` 定义了最小堆类。`test.cpp` 用于测试堆的功能。 #### 十四、哈夫曼树 **定义与特性：** 哈夫曼树是一种最优前缀码的生成树，常用于数据压缩。 **C++模板实现：** `BinTreeNode.h`、`BinaryTree.h`、`MinHeap.h` 和 `Huffman.h` 定义了哈夫曼树相关的节点、树、堆和编码类。`Test.cpp` 用于测试哈夫曼树的功能。 #### 十五、树 **定义与特性：** 树是一种非线性数据结构，由根节点和零个或多个子树组成，其中子树本身也是树。 **C++模板实现：** `QueueNode.h`、`LinkQueue.h`、`TreeNode.h` 和 `Tree.h` 定义了树的节点、队列、树节点和树类。`test.cpp` 用于测试树的功能。 #### 十六、B+树 **定义与特性：** B+树是一种自平衡的树数据结构，常用于数据库索引和文件系统。 **C++模板实现：** `BTreeNode.h` 和 `BTree.h` 定义了 B+树的节点和树类。`test.cpp` 用于测试 B+树的功能。 #### 十七、图 **定义与特性：** 图是由顶点和边组成的集合，用于表示实体之间的关系。 **C++模板实现：** `MinHeap.h`、`Edge.h`、`Vertex.h` 和 `Graph.h` 定义了图相关的堆、边、顶点和图类。`test.cpp` 用于测试图的功能。 #### 十八、排序 **定义与特性：** 排序是将一组数据按照一定的规则排列的过程，常见的有冒泡排序、选择排序、插入排序、归并排序等。 **C++模板实现：** `Data.h`、`QueueNode.h`、`LinkQueue.h` 和 `Sort.h` 定义了排序相关的数据、队列和排序类。`test.cpp` 用于测试排序算法的功能。