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

### 数据结构各种算法实现(C++模板) #### 一、顺序表 **知识点：** - **定义与特性**：顺序表是一种线性结构，其元素在内存中是连续存储的，通常使用数组实现。 - **成员变量**：`m_elements`（指向数组的指针），`m_nmaxsize`（数组的最大容量），`m_ncurrentsize`（当前元素个数）。 - **构造函数**：初始化顺序表，设定最大容量，默认为100，动态分配数组空间。 - **析构函数**：释放动态分配的数组空间。 - **方法**： - `Length()`：返回当前顺序表的长度。 - `Find(x)`：查找元素`x`的位置，若不存在则返回-1。 - `IsElement(x)`：判断元素`x`是否在列表中。 - `Insert(x, i)`：在位置`i`插入元素`x`，需确保列表未满。 - `Remove(x)`：删除元素`x`，需确保列表非空且元素存在。 - `IsEmpty()`：判断列表是否为空。 - `IsFull()`：判断列表是否已满。 - `Get(i)`：获取第`i`个元素，越界时输出错误信息并返回默认值。 #### 二、单链表 **知识点：** - **定义与特性**：单链表是一种线性结构，通过指针链接元素，每个节点包含数据和指向下一个节点的指针。 - **成员变量**：`head`（指向头结点的指针），`tail`（指向尾结点的指针），`size`（链表大小）。 - **构造函数**：初始化链表，设定头结点和尾结点为空，链表大小为0。 - **方法**： - 插入、删除、查找、遍历等基本操作。 #### 三、双向链表 **知识点：** - **定义与特性**：双向链表是在单链表的基础上增加了前驱指针，便于双向遍历和操作。 - **成员变量**：与单链表类似，但节点包含前驱指针。 - **构造函数与方法**：同上，重点在于维护前后节点之间的链接。 #### 四、循环链表 **知识点：** - **定义与特性**：循环链表的尾结点指向头结点，形成闭环，方便遍历整个链表。 - **成员变量**：`head`（指向头结点的指针），`size`（链表大小）。 - **构造函数与方法**：同上，循环遍历需特别注意链表的结束条件。 #### 五、顺序栈 **知识点：** - **定义与特性**：顺序栈基于顺序表实现，遵循后进先出(LIFO)原则。 - **成员变量**：`top`（栈顶指针），`size`（栈大小），`capacity`（栈容量）。 - **方法**：`Push()`（入栈），`Pop()`（出栈），`IsEmpty()`（判断是否为空），`IsFull()`（判断是否已满）。 #### 六、链式栈 **知识点：** - **定义与特性**：链式栈基于链表实现，无需固定容量，适合动态调整。 - **成员变量**：`top`（指向栈顶节点的指针）。 - **方法**：同上。 #### 七、顺序队列 **知识点：** - **定义与特性**：顺序队列基于顺序表实现，遵循先进先出(FIFO)原则。 - **成员变量**：`front`（队首指针），`rear`（队尾指针），`size`（队列大小），`capacity`（队列容量）。 - **方法**：`Enqueue()`（入队），`Dequeue()`（出队），`IsEmpty()`，`IsFull()`。 #### 八、链式队列 **知识点：** - **定义与特性**：链式队列基于链表实现，适用于频繁的入队和出队操作。 - **成员变量**：`front`，`rear`。 - **方法**：同上。 #### 九、优先级队列 **知识点：** - **定义与特性**：优先级队列允许根据元素的优先级进行插入和删除操作。 - **成员变量**：优先级队列通常基于堆或平衡树实现，具有`min()`或`max()`操作用于访问最高优先级的元素。 #### 十、串 **知识点：** - **定义与特性**：串是一种特殊的线性表，其元素为字符。 - **成员变量**：字符数组。 - **方法**：字符串的基本操作如连接、分割、比较等。 #### 十一、二叉树 **知识点：** - **定义与特性**：二叉树是一种非线性结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。 - **成员变量**：`left`（左子节点指针），`right`（右子节点指针），`data`（节点数据）。 - **方法**：遍历（前序、中序、后序）、搜索、插入、删除。 #### 十二、线索二叉树 **知识点：** - **定义与特性**：线索二叉树通过对空指针进行改造，使其指向父节点或特定节点，提高查找效率。 - **成员变量**：`ltag`和`rtag`（标记左右子节点是否为线索）。 #### 十三、堆 **知识点：** - **定义与特性**：堆是一种完全二叉树结构，分为大顶堆和小顶堆，满足父节点值总是大于（或小于）其子节点的值。 - **成员变量**：数组表示的堆结构。 - **方法**：`Push()`，`Pop()`，`Adjust()`（调整堆结构）。 #### 十四、哈夫曼树 **知识点：** - **定义与特性**：哈夫曼树是一种带权路径长度最短的二叉树，常用于编码和压缩领域。 - **成员变量**：权重值。 - **方法**：构建哈夫曼树，编码和解码。 #### 十五、树 **知识点：** - **定义与特性**：树是非线性结构，由一个根节点和若干个子树组成，子树本身也是一个树。 - **成员变量**：`children`（指向子节点的链表）。 - **方法**：遍历（层次、深度优先、广度优先）。 #### 十六、B+树 **知识点：** - **定义与特性**：B+树是多路搜索树，每个节点可有多个子节点，广泛应用于数据库索引。 - **成员变量**：`keys`（键值集合），`pointers`（指向子节点的指针集合）。 - **方法**：插入、删除、查找。 #### 十七、图 **知识点：** - **定义与特性**：图是由顶点和边组成的集合，可以是有向图或无向图，表示实体间的关系。 - **成员变量**：邻接矩阵或邻接表。 - **方法**：深度优先搜索(DFS)、广度优先搜索(BFS)、最短路径算法（Dijkstra、Floyd）等。 #### 十八、排序 **知识点：** - **定义与特性**：排序算法用于将一组元素按特定顺序排列。 - **常见排序算法**：冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序、计数排序、基数排序等。 - **性能分析**：时间复杂度、空间复杂度、稳定性等。 以上数据结构和算法的实现均采用C++模板，支持多种数据类型，提供了灵活而强大的功能，是理解和掌握计算机科学基础知识的重要工具。