数据结构各种算法的c++实现

### 数据结构各种算法的C++实现 #### 一、顺序表 **知识点：** - **定义与特性**：顺序表是一种线性表的数据结构，它通过连续的内存空间来存储数据元素，支持随机访问。 - **操作实现**： - **构造函数与析构函数**：初始化一个顺序表，分配指定大小的内存空间；释放顺序表占用的内存资源。 - **获取长度**：返回当前顺序表中的元素数量。 - **查找**：在顺序表中查找特定元素的位置。 - **判断元素是否存在**：检查某个元素是否存在于顺序表中。 - **插入数据**：将新元素插入到顺序表的指定位置。 - **删除数据**：从顺序表中移除指定元素。 - **判断是否为空**：检查顺序表是否没有任何元素。 - **判断是否已满**：检查顺序表是否已达到其最大容量。 - **获取指定位置的元素**：返回顺序表中指定位置的元素值。 - **打印顺序表**：输出顺序表中的所有元素。 **代码示例**： ```cpp template<typename Type> class SeqList { public: SeqList(int sz = DefaultSize) : m_nmaxsize(sz), m_ncurrentsize(-1) { if (sz > 0) { m_elements = new Type[m_nmaxsize]; } } ~SeqList() { delete[] m_elements; } int Length() const { return m_ncurrentsize + 1; } int Find(Type x) const; int IsElement(Type x) const; int Insert(Type x, int i); int Remove(Type x); int IsEmpty() { return m_ncurrentsize == -1; } int IsFull() { return m_ncurrentsize == m_nmaxsize - 1; } Type Get(int i) { return (i < 0 || i > m_ncurrentsize) ? (std::cout << "can't find the element" << std::endl, Type()) : m_elements[i]; } void Print(); private: Type* m_elements; const int m_nmaxsize; int m_ncurrentsize; }; template<typename Type> int SeqList<Type>::Find(Type x) const { for (int i = 0; i < m_ncurrentsize; i++) { if (m_elements[i] == x) { // 返回元素位置 } } // 如果未找到，则返回特定值 } ``` #### 二、单链表 **知识点：** - **定义与特性**：单链表是通过节点之间的指针链接构成的线性表，每个节点包含数据部分和指向下一个节点的指针。 - **操作实现**： - **创建节点**：创建包含数据的新节点。 - **添加节点**：在链表的头部或尾部添加新节点。 - **删除节点**：根据键值或位置删除节点。 - **查找节点**：根据键值或位置查找节点。 - **遍历链表**：从前向后访问链表中的每一个节点。 **代码示例**： ```cpp struct ListNode { Type data; ListNode* next; ListNode(Type val) : data(val), next(nullptr) {} }; class SingleList { public: SingleList() : head(nullptr) {} ~SingleList(); void AddNode(Type val); void DeleteNode(Type val); ListNode* FindNode(Type val); void PrintList(); private: ListNode* head; }; ``` #### 三、双向链表 **知识点：** - **定义与特性**：双向链表与单链表类似，但每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。 - **操作实现**：双向链表的操作与单链表相似，但需要处理额外的前驱指针。 **代码示例**： ```cpp struct NodeList { Type data; NodeList* prev; NodeList* next; NodeList(Type val) : data(val), prev(nullptr), next(nullptr) {} }; class DoubleList { public: DoubleList() : head(nullptr) {} ~DoubleList(); void AddNode(Type val); void DeleteNode(Type val); NodeList* FindNode(Type val); void PrintList(); private: NodeList* head; }; ``` #### 四、循环链表 **知识点：** - **定义与特性**：循环链表是一种特殊的链表形式，最后一个节点的next指针指向头节点，形成一个闭环。 - **操作实现**：循环链表的操作类似于普通链表，但需要注意循环结构。 **代码示例**： ```cpp struct ListNode { Type data; ListNode* next; ListNode(Type val) : data(val), next(nullptr) {} }; class CircularList { public: CircularList() : head(nullptr) {} ~CircularList(); void AddNode(Type val); void DeleteNode(Type val); ListNode* FindNode(Type val); void PrintList(); private: ListNode* head; }; ``` #### 五、顺序栈 **知识点：** - **定义与特性**：顺序栈是一种基于顺序表实现的栈，栈顶元素位于数组的末尾。 - **操作实现**：包括入栈、出栈、查看栈顶元素等。 **代码示例**： ```cpp template<typename Type> class SeqStack { public: SeqStack(int size = DefaultSize) : top(-1), max_size(size) { elements = new Type[max_size]; } ~SeqStack() { delete[] elements; } bool Push(Type val); Type Pop(); Type Top() const; bool IsEmpty() const { return top == -1; } bool IsFull() const { return top == max_size - 1; } private: Type* elements; int top; int max_size; }; ``` #### 六、链式栈 **知识点：** - **定义与特性**：链式栈是一种基于链表实现的栈，使用单链表作为基础数据结构。 - **操作实现**：包括入栈、出栈、查看栈顶元素等。 **代码示例**： ```cpp struct StackNode { Type data; StackNode* next; StackNode(Type val) : data(val), next(nullptr) {} }; template<typename Type> class LinkStack { public: LinkStack() : top(nullptr) {} ~LinkStack(); bool Push(Type val); Type Pop(); Type Top() const; bool IsEmpty() const { return top == nullptr; } private: StackNode* top; }; ``` #### 七、顺序队列 **知识点：** - **定义与特性**：顺序队列是一种基于顺序表实现的队列，队头和队尾分别对应数组的起始位置和当前尾部位置。 - **操作实现**：包括入队、出队、查看队头元素等。 **代码示例**： ```cpp template<typename Type> class SeqQueue { public: SeqQueue(int size = DefaultSize) : front(0), rear(0), max_size(size) { elements = new Type[max_size]; } ~SeqQueue() { delete[] elements; } bool Enqueue(Type val); Type Dequeue(); Type Front() const; bool IsEmpty() const { return front == rear; } bool IsFull() const { return (rear + 1) % max_size == front; } private: Type* elements; int front; int rear; int max_size; }; ``` #### 八、链式队列 **知识点：** - **定义与特性**：链式队列是一种基于链表实现的队列，使用单链表作为基础数据结构。 - **操作实现**：包括入队、出队、查看队头元素等。 **代码示例**： ```cpp struct QueueNode { Type data; QueueNode* next; QueueNode(Type val) : data(val), next(nullptr) {} }; template<typename Type> class LinkQueue { public: LinkQueue() : front(nullptr), rear(nullptr) {} ~LinkQueue(); bool Enqueue(Type val); Type Dequeue(); Type Front() const; bool IsEmpty() const { return front == nullptr; } private: QueueNode* front; QueueNode* rear; }; ``` #### 九、优先级队列 **知识点：** - **定义与特性**：优先级队列是一种特殊的队列，其中元素按照优先级排序。 - **操作实现**：通常使用堆（如最小堆或最大堆）来实现高效插入和删除操作。 **代码示例**： ```cpp template<typename Type, typename Compare> class PriorityQueue { public: PriorityQueue() {} ~PriorityQueue(); bool Enqueue(Type val); Type Dequeue(); Type Top() const; bool IsEmpty() const { return heap.IsEmpty(); } private: struct QueueNode { Type data; QueueNode(Type val) : data(val) {} }; struct Compare { bool operator()(const QueueNode& a, const QueueNode& b) const; }; MinHeap<QueueNode, Compare> heap; }; ``` #### 十、串 **知识点：** - **定义与特性**：串是一种特殊的数据结构，用于表示字符序列。 - **操作实现**：包括字符串的创建、复制、连接、比较等。 **代码示例**： ```cpp template<typename CharType> class MyString { public: MyString(const CharType* str = "") { Copy(str); } ~MyString() { delete[] data; } MyString(const MyString& other); MyString& operator=(const MyString& other); void Copy(const CharType* str); MyString Concat(const MyString& other) const; int Compare(const MyString& other) const; bool IsEqual(const MyString& other) const; int Length() const; private: CharType* data; }; ``` #### 十一、二叉树 **知识点：** - **定义与特性**：二叉树是一种树形结构，其中每个节点最多有两个子节点。 - **操作实现**：包括创建二叉树、遍历（前序、中序、后序）、查找、删除节点等。 **代码示例**： ```cpp template<typename Type> struct BinTreeNode { Type data; BinTreeNode* left; BinTreeNode* right; BinTreeNode(Type val) : data(val), left(nullptr), right(nullptr) {} }; template<typename Type> class BinaryTree { public: BinaryTree() : root(nullptr) {} ~BinaryTree(); void Insert(Type val); BinTreeNode<Type>* Find(Type val); void PreOrderTraversal(BinTreeNode<Type>* node) const; void InOrderTraversal(BinTreeNode<Type>* node) const; void PostOrderTraversal(BinTreeNode<Type>* node) const; private: BinTreeNode<Type>* root; }; ``` #### 十二、线索二叉树 **知识点：** - **定义与特性**：线索二叉树是在二叉树的基础上进行优化的一种数据结构，通过将空指针指向其后续节点（前驱或后继），以减少遍历时的递归调用。 - **操作实现**：包括创建线索二叉树、线索化过程、遍历等。 **代码示例**： ```cpp template<typename Type> struct ThreadNode { Type data; ThreadNode* left; ThreadNode* right; bool lThread; bool rThread; ThreadNode(Type val) : data(val), left(nullptr), right(nullptr), lThread(false), rThread(false) {} }; template<typename Type> class ThreadTree { public: ThreadTree() : root(nullptr) {} ~ThreadTree(); void MakeThreaded(); ThreadNode<Type>* Find(Type val); void InOrderTraversal(ThreadNode<Type>* node) const; private: ThreadNode<Type>* root; }; ``` #### 十三、堆 **知识点：** - **定义与特性**：堆是一种完全二叉树结构，分为最小堆和最大堆，通常用来实现优先级队列。 - **操作实现**：包括构建堆、插入元素、删除根节点、调整堆等。 **代码示例**： ```cpp template<typename Type, typename Compare> class MinHeap { public: MinHeap() {} ~MinHeap(); void Insert(Type val); Type ExtractMin(); void AdjustDown(int start, int end); private: struct Compare { bool operator()(const Type& a, const Type& b) const; }; std::vector<Type> heap; }; ``` #### 十四、哈夫曼树 **知识点：** - **定义与特性**：哈夫曼树是一种带权路径长度最短的二叉树，广泛应用于数据压缩领域。 - **操作实现**：包括构建哈夫曼树、生成编码表、编码解码等。 **代码示例**： ```cpp template<typename Type> class Huffman { public: Huffman() {} ~Huffman(); void BuildTree(); void GenerateCodeTable(); std::string Encode(const std::string& text); std::string Decode(const std::string& encodedText); private: struct BinTreeNode { Type data; BinTreeNode* left; BinTreeNode* right; BinTreeNode(Type val) : data(val), left(nullptr), right(nullptr) {} }; MinHeap<BinTreeNode<Type>, Compare> heap; std::unordered_map<Type, std::string> codeTable; }; ``` #### 十五、树 **知识点：** - **定义与特性**：树是一种非线性的层次数据结构，由多个节点组成，每个节点可以有任意数量的子节点。 - **操作实现**：包括创建树、遍历（先序、中序、后序）、查找节点等。 **代码示例**： ```cpp template<typename Type> struct TreeNode { Type data; TreeNode* parent; std::vector<TreeNode*> children; TreeNode(Type val) : data(val), parent(nullptr) {} }; template<typename Type> class Tree { public: Tree() : root(nullptr) {} ~Tree(); void Insert(Type val); TreeNode<Type>* Find(Type val); void PreOrderTraversal(TreeNode<Type>* node) const; void PostOrderTraversal(TreeNode<Type>* node) const; private: TreeNode<Type>* root; }; ``` #### 十六、B+树 **知识点：** - **定义与特性**：B+树是一种自平衡的树形数据结构，常用于数据库和文件系统中，支持高效的查找、插入和删除操作。 - **操作实现**：包括构建B+树、插入数据、查找数据、删除数据等。 **代码示例**： ```cpp template<typename Type> struct BTreeNode { std::vector<Type> keys; std::vector<BTreeNode*> children; BTreeNode(int t) : order(t) {} int order; }; template<typename Type> class BTree { public: BTree(int t) : order(t), root(nullptr) {} ~BTree(); void Insert(Type val); BTreeNode<Type>* Search(Type val); void SplitChild(BTreeNode<Type>* child, int i); private: int order; BTreeNode<Type>* root; }; ``` #### 十七、图 **知识点：** - **定义与特性**：图是由顶点集和边集组成的集合，可以是有向图或无向图。 - **操作实现**：包括创建图、添加顶点和边、遍历（深度优先搜索、广度优先搜索）等。 **代码示例**： ```cpp template<typename VertexType, typename EdgeType> class Graph { public: Graph() {} ~Graph(); void AddVertex(VertexType val); void AddEdge(VertexType v1, VertexType v2, EdgeType weight); void DepthFirstSearch(VertexType start); void BreadthFirstSearch(VertexType start); private: struct Vertex { VertexType data; std::vector<EdgeType> edges; Vertex(VertexType val) : data(val) {} }; std::unordered_map<VertexType, Vertex> vertices; }; ``` #### 十八、排序 **知识点：** - **定义与特性**：排序是将一组数据按特定顺序排列的过程，常用的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。 - **操作实现**：包括实现各种排序算法，并提供统一的接口。 **代码示例**： ```cpp template<typename Type> class Sort { public: Sort() {} void BubbleSort(std::vector<Type>& arr); void SelectionSort(std::vector<Type>& arr); void InsertionSort(std::vector<Type>& arr); void QuickSort(std::vector<Type>& arr, int low, int high); void MergeSort(std::vector<Type>& arr, int left, int right); private: void Swap(Type& a, Type& b); }; ``` 以上是对数据结构及算法的C++实现的相关知识点概述，每种数据结构都有其独特的特性和应用场景，在实际开发过程中可以根据需求灵活选择合适的数据结构来解决问题。