2007-04-09
全文显示

常用类之四---并查集(Union-Find Sets)

并查集为解决等价类问题提供了一个高效快速的数据结构,在许多涉及到等价类的算法中,他都扮演着 改进算法中使用的数据机构的角色,他对提高算法的效率是可见一斑,例如在带有限期的作业问题中,在求最小生成树Kruskal算法都可以使用并查集高效的实现. const int DefaultSize = 20; class UFSets{ public: UFSets(int s = DefaultSize); ~UFSets(); void Union(int root1,int root2); void WeightUnion(int root1,int root2);//基 ...
2007-04-09
全文显示

最小(大)堆应用---堆排序

堆排序的时间复杂性为nlog(n),空间复杂度为o(1),为比较排序的下界,因此具有非常好的性能,使用堆,也很容易实现堆排序. #include<iostream> #include"MinHeap.h" using namespace std; template<class T> void HeapSort(T a[],int n){ T temp; MinHeap<T> *m_heap = new MinHeap<T>(a,n); for(int i = n-1; i >= 1; i--){//a[0]与a[i]交换,重新调整堆0---> ...
2007-04-09
全文显示

最小堆应用---用最小堆实现huffman树

最小堆应用---用最小堆实现huffman树,huffman是形成huffman编码的基础. #include"MinHeap.h" template<class T> class HuffmanTree; template<class T> class TreeNode{ friend class HuffmanTree<T>; private: T data; TreeNode<T> *left,*right; public: TreeNode(T value){ data = value; left = ...
2007-04-09
全文显示

实用类之二-----最大堆的实现

最小(大)堆是比较常用的数据结构,是实现优先队列和堆排序的基础,也可以实现例如霍夫曼编码,贪心算法等,具有很好的时间复杂性. template<class T> class MaxHeap{ public: MaxHeap(T a[],int n); MaxHeap(int ms); ~MaxHeap(); bool Insert(const T &x);//插入一个元素,如果空返回false，否则返回true bool RemoveMax(T &x);//删除最小的元素，如果空返回false，否则返回true void MakeEmp ...
2007-04-09
全文显示

实用类之一-----最小堆的实现

最小(大)堆是比较常用的数据结构,是实现优先队列和堆排序的基础,也可以实现例如霍夫曼编码,贪心算法等,具有很好的时间复杂性. MinHeap.h文件 template<class T> class MinHeap{ public: MinHeap(T a[],int n); MinHeap(int ms); ~MinHeap(); bool Insert(const T &x);//插入一个元素,如果空返回false，否则返回true bool RemoveMin(T &x);//删除最小的元素，如果空返回false，否则返回true ...
fuliang
搜索本博客
我的相册
53569b0e-134e-31fa-9555-bdfa6932b0e7-thumb
RSS Reader1
共 6 张
存档
最新评论