queue.h
#ifndef QUEUE_H
#define QUEUE_H
template <typename T>
class queue
{
public:
virtual ~queue();
virtual bool empty() const = 0;
// 返回 true，当且仅当当前队列为空
virtual int size() const = 0;
// 返回队列中元素个数
virtual T& front() = 0;
// 返回头元素的引用
virtual T& back() = 0;
// 返回尾元素的引用
virtual void pop() = 0;
// 删除首元素
virtual void push(const T& theElement) = 0;
// 把元素 theElement 加入队尾
};
#endif // !QUEUE_H
arrayQueue.h
#ifndef ARRAYQUEUE_H
#define ARRAYQUEUE_H
#include "queue.h"
#include "myExceptions.h"
#include <sstream>
using namespace std;
template<class T>
class arrayQueue : public queue<T>
{
public:
arrayQueue(int initialCapacity = 10);
~arrayQueue() {delete [] queue;}
bool empty() const {return theFront == theBack;}
int size() const
{return (theBack - theFront + arrayLength) % arrayLength;}
T& front()
{// 返回头元素的引用
if (theFront == theBack)
throw queueEmpty();
return queue[(theFront + 1) % arrayLength];
}
T& back()
{// 返回尾元素的引用
if (theFront == theBack)
throw queueEmpty();
return queue[theBack];
}
void pop()
{// 删除队列首元素
if (theFront == theBack)
throw queueEmpty;
theFront = (theFront + 1) % arrayLength;
queue[theFront].~T(); // 给 T 析构
}
void push(const T& theElement); // 把元素 theElement 加入队尾
private:
int theFront; // 逆时针方向，指向列首元素的下一个位置
int theBack; // 尾元素的位置
int arrayLength; // 队列容量
T *queue; // 元素数组
};
template<class T>
arrayQueue<T>::arrayQueue(int initialCapacity)
{// Constructor.
if (initialCapacity < 1)
{ostringstream s;
s << "Initial capacity = " << initialCapacity << " Must be > 0";
throw illegalParameterValue(s.str());
}
arrayLength = initialCapacity;
queue = new T[arrayLength];
theFront = 0;
theBack = 0;
}
template<typename T>
void arrayQueue<T>::push(const T& theElement)
{// 把元素 theElement 加入队列
if ((theBack + 1) % theFront == theFront)
{// 加倍数组长度
// 分配新的数组空间
T* newQueue = new T[theFront * 2];
// 把原数组复制到新数组
int start = (theFront + 1) % arrayLength;
if (start < 2)
// 没有形成环
copy(queue + start, queue + arrayLength, newQueue);
else
{// 队列形成环
copy(queue + start, queue + theFront, newQueue);
copy(queue, queue + theBack + 1, newQueue + arrayLength - start);
}
theFront = 2 * arrayLength - 1;
theBack = arrayLength - 2; // 队列长度 - 1
arrayLength *= 2;
delete [] queue;
queue = newQueue;
}
// 把元素 theElement 插入队列的尾部
theBack = (theBack + 1) % arrayLength;
queue[theBack] = theElement;
}
#endif
changeLength1D.h
// 更改数组的长度
#ifndef CHANGELENGTH1D_H
#define CHANGELENGTH1D_H
#include "myExceptions.h"
using namespace std;
template<class T>
void changeLength1D(T*& a, int oldLength, int newLength)
{
if (newLength < 0)
throw illegalParameterValue("new length must be >= 0");
T* temp = new T[newLength]; // 新阵列
int number = min(oldLength, newLength); // 要复制的编号
copy(a, a + number, temp);
delete [] a; // 释放旧内存
a = temp;
}
#endif
myExceptions.h
// 各种错误类型的异常类
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H
#include <string>
using namespace std;
// 非法参数值
class illegalParameterValue
{
public:
illegalParameterValue(string theMessage = "Illegal parameter value")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 非法输入数据
class illegalInputData
{
public:
illegalInputData(string theMessage = "Illegal data input")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 非法索引
class illegalIndex
{
public:
illegalIndex(string theMessage = "Illegal index")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 矩阵索引越界
class matrixIndexOutOfBounds
{
public:
matrixIndexOutOfBounds
(string theMessage = "Matrix index out of bounds")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 矩阵大小不匹配
class matrixSizeMismatch
{
public:
matrixSizeMismatch(string theMessage =
"The size of the two matrics doesn't match")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 堆栈是空的
class stackEmpty
{
public:
stackEmpty(string theMessage =
"Invalid operation on empty stack")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 队列为空
class queueEmpty
{
public:
queueEmpty(string theMessage =
"Invalid operation on empty queue")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 哈希表已满
class hashTableFull
{
public:
hashTableFull(string theMessage =
"The hash table is full")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 边权重未定义
class undefinedEdgeWeight
{
public:
undefinedEdgeWeight(string theMessage =
"No edge weights defined")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
// 方法未定义
class undefinedMethod
{
public:
undefinedMethod(string theMessage =
"This method is undefined")
{message = theMessage;}
void outputMessage() {cout << message << endl;}
private:
string message;
};
#endif
minPriorityQueue.h
// 抽象类最小优先级队列
// 所有方法都是纯虚函数
#ifndef MINPRIORITYQUEUE_H
#define MINPRIORITYQUEUE_H
using namespace std;
template<class T>
class minPriorityQueue
{
public:
virtual ~minPriorityQueue() {}
virtual bool empty() const = 0;
// 返回真iff队列为空
virtual int size() const = 0;
// 返回队列中的元素数
virtual const T& top() = 0;
// 返回对min元素的引用
virtual void pop() = 0;
// 删除栈顶
virtual void push(const T& theElement) = 0;
// 将元素添加到队列中
};
#endif
binaryTreeNode.h
#ifndef BINARYTREENODE_H
#define BINARYTREENODE_H
#include <iostream>
using namespace std;
template<typename T>
struct binaryTreeNode
{
T element;
binaryTreeNode<T> *leftChild, // 左子树
*rightChild; // 右子树
binaryTreeNode() {leftChild = rightChild = nullptr;}
binaryTreeNode(const T& theElement) : element(theElement)
{
leftChild = rightChild = nullptr;
}
binaryTreeNode(const T& theElement, binaryTreeNode *theLeftChild, binaryTreeNode *theRightChild) : element(theElement)
{
leftChild = theLeftChild;
rightChild = theRightChild;
}
};
#endif // !BINARYTREENODE_HbinaryTree.h
#ifndef BRNARYTREE_H
#define BRNARYTREE_H
#include <iostream>
using namespace std;
template<typename T>
class binaryTree
{
public:
virtual ~binaryTree(){}
virtual bool empty() const = 0;
virtual int size() const = 0;
virtual void preOrder(void (*) (T *)) = 0;
virtual void inOrder(void (*) (T *)) = 0;
virtual void postOrder(void (*) (T*)) = 0;
virtual void levelOrder(void (*) (T *)) = 0;
};
#endif // !BRNARYTREE_HlinkedBinaryTree.h
#ifndef LINKEDBINARYTREE_H
#define LINKEDBINARYTREE_H
#include <iostream>
#include "binaryTree.h"
#include "binaryTreeNode.h"
#include "arrayQueue.h"
using namespace std;
template<typename E>
class linkedBinaryTree : public binaryTree<binaryTreeNode<E>>
{
public:
linkedBinaryTree() {root = nullptr; treeSize = 0;}
~linkedBinaryTree() {erase();}
bool empty() const {return treeSize == 0;}
int size() const {return treeSize;}
// 用指定的根和左右子树来构造一棵二叉树
void makeTree(const E& element, linkedBinaryTree<E>&, linkedBinaryTree<E>&);
void preOrder(void(*theVisit)(binaryTreeNode<E>*)) // theVisit是个函数指针，指向一个没有参数没有返回值的函数
{ visit = theVisit; preOrder(root); }
void inOrder(void(*theVisit)(binaryTreeNode<E>*))
{ visit = theVisit; inOrder(root); }
void postOrder(void(*theVisit)(binaryTreeNode<E>*))
{ visit = theVisit; postOrder(root); }
void levelOrder(void(*)(binaryTreeNode<E>*));
void erase()
{
postOrder(dispose);
root = nullptr;
treeSize = 0;
}
int height() const { return height(root); }
int height(binaryTreeNode<E> *t) const;
private:
binaryTreeNode<E> *root; // 指向根的指针
int treeSize; // 树的节点个数
static void (*visit)(binaryTreeNode<E> *); // 访问函数
static void preOrder(binaryTreeNode<E> *t);
static void inOrder(binaryTreeNode<E> *t);
static void postOrder(binaryTreeNode<E> *t);
static void dispose(binaryTreeNode<E> *t) {delete t;}
static void output(binaryTreeNode<E> *t)
{ cout << t->element<< ' '; }
};
template<class E>
void linkedBinaryTree<E>::makeTree(const E& element, linkedBinaryTree<E>& left, linkedBinaryTree<E>& right)
{// 将left、right和element组合在一起以创建新树
// 左，右，这一定是不同的树。
// 创建组合树
root = new binaryTreeNode<E> (element, left.root, right.root);
treeSize = left.treeSize + right.treeSize + 1;
// 拒绝左右树的访问
left.root = right.root = NULL;
left.treeSize = right.treeSize = 0;
}
template<typename E>
void linkedBinaryTree<E>::preOrder(binaryTreeNode<E> *t)
{// 前序遍历
if (t != nullptr)
{
linkedBinaryTree<E>::visit(t);
preOrder(t->leftChild);
preOrder(t->rightChild);
}
}
template<typename E>
void linkedBinaryTree<E>::inOrder(binaryTreeNode<E> *t)
{// 中序遍历
if (t != nullptr)
{
inOrder(t->leftChild);
linkedBinaryTree<E>::visit(t);
inOrder(t->rightChild);
}
}
template<typename E>
void linkedBinaryTree<E>::postOrder(binaryTreeNode<E> *t)
{// 后序遍历
if (t != nullptr)
{
postOrder(t->leftChild);
postOrder(t->rightChild);
linkedBinaryTree<E>::visit(t);
}
}
template<typename E>
void levelOrder(binaryTreeNode<E> *t)
{// 层次遍历
arrayQueue<binaryTreeNode<E>*> q;
while (t != nullptr)
{
linkedBinaryTree<E>::visit(t); // 访问 t
// 将 t 的孩子插入队列
if (t->leftChild != nullptr)
q.push(t->leftChild);
if (t->rightChild != nullptr)
q.push(t->rightChild);
// 提取下一个要访问的节点
try{ t = q.front(); }
catch (queueEmpty) { return; }
q.pop(); // 删除首元素
}
}
template<typename E>
int linkedBinaryTree<E>::height(binaryTreeNode<E> *t) const
{// 返回根位 *t 的树的高度
if (t == nullptr)
return 0; // 空树
int hl = height(t->leftChild); // 左树高
int hr = height(t->rightChild); // 右树高
if (hl > hr)
return ++hl;
else
return ++hr;
}
#endif // !LINKEDBINARYTREE_HhuffmanNode.h
#ifndef HUFFMANNODE_H
#define HUFFMANNODE_H
template<class T>
struct huffmanNode
{
linkedBinaryTree<int> *tree;
T weight; // 权值域
operator T () const {return weight;}
};
#endif
minHeap.h
#ifndef MINHEAP_H
#define MINHEAP_H
#include "changeLength1D.h"
#include "minPriorityQueue.h"
#include "myExceptions.h"
#include <sstream>
#include <algorithm>
using namespace std;
template<class T>
class minHeap : public minPriorityQueue<T>
{
public:
minHeap(int initialCapacity = 10);
~minHeap() {delete [] heap;}
bool empty() const {return heapSize == 0;}
int size() const
{return heapSize;}
const T& top()
{// 返回最大元素
if (heapSize == 0)
throw queueEmpty();
return heap[1];
}
void pop();
void push(const T&);
void initialize(T *, int);
void deactivateArray()
{heap = NULL; arrayLength = heapSize = 0;}
void output(ostream& out) const;
private:
int heapSize; // 队列中的元素数
int arrayLength; // 队列容量 + 1
T *heap; // 元素数组
};
template<class T>
minHeap<T>::minHeap(int initialCapacity)
{// 构造函数
if (initialCapacity < 1)
{ostringstream s;
s << "Initial capacity = " << initialCapacity << " Must be > 0";
throw illegalParameterValue(s.str());
}
arrayLength = initialCapacity + 1;
heap = new T[arrayLength];
heapSize = 0;
}
template<typename T>
void minHeap<T>::push(const T& theElement)
{// 把元素 theElement 加入堆
// 必要时增加数组长度
if (heapSize == arrayLength - 1)
{// 长度 * 2
changeLength1D(heap, arrayLength, 2 * arrayLength);
arrayLength *= 2;
}
// 为元素 theElement 寻找插入位置
// currentNode 从新叶子向上移动
int currentNode = ++heapSize;
while (currentNode != 1 && heap[currentNode / 2] > theElement)
{
// 不能把元素 theElement 插入在 heap[currentNode]
heap[currentNode] = heap[currentNode / 2]; // 把元素向下移动
currentNode /= 2; // currentNoed 移向双亲
}
heap[currentNode] = theElement;
}
template<typename T>
void minHeap<T>::pop()
{// 删除最大元素
// 如果堆为空，抛出异常
if (heapSize == 0) // 堆空
throw queueEmpty();
// 删除最大元素
heap[1].~T();
// 删除最后一个元素，然后重建堆
T lastElement = heap[heapSize--];
// 从根开始，为最后一个元素寻找位置
int currentNode = 1,
child = 2; // currentNode 的孩子
while (child <= heapSize)
{
// heap[child] 应该是 currentNode 的更大的孩子
if (child < heapSize && heap[child] > heap[child + 1])
child++;
// 可以把 lastElement 放在 heap[currentNode] 吗？
if (lastElement <= heap[child])
break; // 可以
// 不可以
heap[currentNode] = heap[child]; // 把孩子 child 向上移动
currentNode = child; // 向下移动一层寻找位置
child *= 2;
}
heap[currentNode] = lastElement;
}
template<typename T>
void minHeap<T>::initialize(T *theHeap, int theSize)
{// 在数组 theHeap[1:theSize] 中建小根堆
delete [] heap;
heap = theHeap;
heapSize = theSize;
// 堆化
for (int root = heapSize / 2; root >= 1; root--)
{
T rootElement = heap[root];
// 为元素 rootElement 寻找位置
int child = 2 * root; // 孩子 child 的双亲是元素 rootElement 的位置
while (child <= heapSize)
{
// heap[child] 应该是兄弟中较大者
if (child < heapSize && heap[child] > heap[child + 1])
child++;
// 可以把元素 rootElement 放在 heap[child / 2] 吗
if (rootElement <= heap[child])
break;
// 不可以
heap[child / 2] = heap[child]; // 把孩子向上移
child *= 2; // 移到下一层
}
heap[child / 2] = rootElement;
}
}
template<class T>
void minHeap<T>::output(ostream& out) const
{// 将列表放入流中并输出
copy(heap + 1, heap + heapSize + 1, ostream_iterator<T>(cout, " "));
}
// 重载 <<
template <class T>
ostream& operator<<(ostream& out, const minHeap<T>& x)
{x.output(out); return out;}
#endif // !MAXHEAP_H
huffmanTree.h
#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H
#include "linkedBinaryTree.h"
#include "huffmanNode.h"
#include "minHeap.h"
template<typename T>
linkedBinaryTree<T>* huffmanTree(T weight[], int n)
{// 用权 weight[1:n] 生成霍夫曼树，n >= 1
// 创建一组单节点树
huffmanNode<T> *hNode = new huffmanNode<T> [n + 1];
linkedBinaryTree<T> emptyTree;
for (int i = 1; i <= n; i++)
{
hNode[i].weight = weight[i];
hNode[i].tree = new linkedBinaryTree<int>;
hNode[i].tree->makeTree(i, emptyTree, emptyTree);
}
// 使一组单节点树构成小根堆
minHeap<huffmanNode<T>> heap(1);
heap.initialize(hNode, n);
// 不断从小根堆中提取两个树合并，直到剩下一棵树
huffmanNode<T> w, x, y;
linkedBinaryTree<int> *z;
for (int i = 1; i < n; i++)
{
// 从小根堆中取出两个最轻的树
x = heap.top();
heap.pop();
y = heap.top();
heap.pop();
// 合并成一棵树
z = new linkedBinaryTree<int>;
z->makeTree(0, *x.tree, *y.tree);
w.weight = x.weight + y.weight;
w.tree = z;
heap.push(w);
delete x.tree;
delete y.tree;
}
}
#endif // !HUFFMANTREE_H
huffmanTree 函数的复杂性：
创建数组 hNode 的时间是 Ο(n)。第一个 for 循环和堆的初始化时间也是 O(n)。在第二个 for 循环中，共有 2(n-1) 次的 top 操作、2(n-1) 次的 pop 操作和 n-1 次的 push 操作，时间为 O(nlogn)。其余部分的时间为 Θ(n)。因此 huffmanTree 函数的总时间 O(nlogn)。
版权声明：本文为w188123135原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。