DataStructure

数据结构-C++实现

C++模板实现常用数据结构，包括向量、链表、栈、队列、二叉树、二叉搜索树、平衡二叉树、优先队列（堆）、图、排序算法等。 本代码库主要参考了青岛大学周强老师的MOOC《数据结构与算法实战》，课程可在该链接查看： https://www.icourse163.org/course/QDU-1206503801 。

本仓库代码侧重于数据结构实现，对C++类的拷贝控制、隐式构造等方面不予考虑，因此代码在内存管理方面存在一些bug，仅做学习使用。

下面介绍每个文件对应数据结构：

1.向量

头文件： Vector.h
测试函数： arrayList.cpp

2.单向链表

链表节点： templateNode.h
头文件： LinkedList.h
测试函数： linkedList.cpp

3.栈

头文件： Stack.h
测试函数： stack.cpp

4.队列

头文件： Queue.h
测试函数： queue.cpp

5.二叉树

二叉树节点： BinaryTreeNode.h
头文件： BinaryTree.h
测试函数：binaryTree.cpp

6.二叉搜索树

头文件： BSTree.h
测试函数：bstree.cpp

7.平衡二叉搜索树

头文件： AVLTree.h
测试函数：avlTree.cpp

8.优先队列（堆）

头文件： PriorityQueue.h
测试函数：priorityQueue.cpp

9.不相交集

头文件： DisjointSet.h
测试函数： disjointSet.cpp

10.哈希表

头文件： HashTable.h
测试函数： hashTable.cpp

11.排序

头文件： sortAlgorithm.h
测试函数： SortAlgorithm.cpp
包括以下排序算法：简单选择排序、简单插入排序、冒泡排序、希尔排序、堆排序、归并排序、快速排序、基数排序

12.图

基类： Graph.h
邻接矩阵图： MGraph.h
邻接表图： LGraph.h
测试函数： graph.cpp
实现功能包括：图的多种构造方式、插入顶点、插入边、删除边、深度优先搜索、广度优先搜索、拓扑排序、Dijkstra算法、带负权边最短路径算法、Prim算法、Kruskal算法

13.算法设计

13.1 贪心策略（哈夫曼树）

头文件：HuffmanTree.h
测试函数： huffmanTree.cpp

13.2 回溯（八皇后）

八皇后问题： NQueen.cpp

13.3 分治策略（查找第k大数）

查找第k大数： findKmax.cpp

13.4 动态规划（多源最短路径问题 Floyd算法）

多源最短路径问题： floyd.cpp

---

更新

按照数据结构类别整理为文件夹

文件夹命名即为相应数据结构实现。