数据结构课程设计报告基于堆的哈夫曼编码问题正文终稿.doc

东北大学信息科学与工程学院
数据结构课程设计报告

题目 基于堆的哈夫曼编码问题

课题组长 黄红清

课题组成员 王帅 邢伟
专业名称 计算机科学与技术

班级 计1307

指导教师 杨雷

2015 年 1月

课程设计任务书
题目：
基于堆的哈夫曼编码问题
问题描述：
优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。
设计要求：
设计基于堆的优先队列的哈夫曼编码程序。
（1）采用STL的堆、向量等数据结构。
（2）用堆实现STL的优先队列类。
（3）实现优先队列的哈夫曼树和哈夫曼编码。

指导教师签字：
年　　月　　日

目录
1 课题概述 4
1.1 课题任务 4
1.2 课题原理 4
1.3 相关知识 4
2 需求分析 5
2.1 课题调研 5
2.2 用户需求分析 5
3 方案设计 6
3.1 总体功能设计 6
3.2 数据结构设计 6
3.3 函数原型设计 8
3.4 主算法设计 10
3.5 用户界面设计 11
4 方案实现 12
4.1 开发环境与工具 12
4.2 程序设计关键技术 12
4.3 个人设计实现（按组员分工）
4.3.1 黄红清设计实现 12
4.3.2 邢伟设计实现 15
4.3.3 王帅设计实现 18
5 测试与调试 24
5.1 个人测试（按组员分工） 26
5.1.1 黄红清测试 24
5.1.2 邢伟测试 24
5.1.3 王帅测试 24
5.2 组装与系统测试 24
5.3 系统运行 24
6 课题总结 26
6.1 课题评价 26
6.2 团队协作 26
6.3 个人设计小结（按组员分工） 26
6.3.1 黄红清设计小结 26
6.3.2 邢伟设计小结 26
6.3.3 王帅设计小结 27
7 附录A 课题任务分工 28
A-1 课题程序设计分工 28
A-2 课题报告分工 30
附录B 课题设计文档（光盘） 31
B-1课程设计报告（电子版） 31
B-2源程序代码（*.H，*.CPP） 31
B-3工程与可执行文件） 31
B-4屏幕演示录像文件（可选） 31
附录C 用户操作手册（可选） 32
C.1 运行环境说明 32
C.2 操作说明 32

1 课题概述
1.1 课题任务
【问题描述】
优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。

【设计要求】
设计基于堆的优先队列的哈夫曼编码程序。
（1）采用STL的堆、向量等数据结构。
（2）用堆实现STL的优先队列类。
（3）实现优先队列的哈夫曼树和哈夫曼编码。

1.2 课题原理
利用STL设计基于堆的优先队列，应用二叉树的存储结构，并利用优先队列求得哈夫曼树和哈夫曼编码。

1.3相关知识
（1） STL的二叉树及其操作；
（2） STL的堆及其优先队列的设计实现和操作；
（3） 基于堆的优先队列概念和哈夫曼树、编码的概念和编程方法；

2 需求分析
2.1 课题调研
使用百度百科了解了什么是基于堆的优先队列，学习力STL编程方法，参考了哈夫曼树和哈夫曼编码的基本原理和知识后，进行程序设计。

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左孩子和右孩子节点的值。而我们会用到最小堆：根结点的键值是所有堆结点键值中最小者。

而普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。

基于这样的优先队列，可以实现哈夫曼树的生成吗，进而求得哈夫曼编码。

2.2 用户需求分析

哈夫曼树以及哈夫曼编码在计算机和通信领域有着相当重要的应用地位，既是压缩和解压缩的基础方法，又是通信传输的编码方案。而堆又是十分方便和快捷的一种存储结构，堆的优先队列更可以很好地实现最小元素和最大元素的出入队操作。利用优先队列来实现哈夫曼编码是一种可行的方案，对于以后的应用有着深刻的意义和重要的价值。

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统能够对待传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每段都需要一个完整的编/译系统。所以哈夫曼树和哈夫曼编码的实现，显得尤为需要。

3 方案设计
3.1 总体功能设计
（1） 实现堆的优先队列；
（2） 利用堆的优先队列实现哈夫曼树的生成，输出中序、前序（或后序）遍历结果检查哈夫曼树的正确性；
（3） 利用生成的哈夫曼树实现哈夫曼编码，进一步检验其正确性；

3.2 数据结构设计
class MinHeap//最小堆优先队列数据结构设计
{
private:
T *heap; //元素数组，0号位置也储存元素
int CurrentSize; //目前元素个数
int MaxSize; //可容纳的最多元素个数

void FilterDown(const int start, const int end); //自上往下调整，使关键字小的节点在上
void FilterUp(int start); //自下往上调整

public:
MinHeap(int n = 1000);
~MinHeap();
bool Insert(const T &x); //插入元素

T RemoveMin(); //删除最小元素
T GetMin(); //取最小元素

bool IsEmpty() const;
bool IsFull() const;
void Clear();
};

template<class T>
struct BTNode//二叉树结点的数据结构
{
T data;
BTNode<T> *lChild, *rChild;

BTNode()
{
lChild = rChild = NULL;
}

BTNode(const T &val, BTNode<T> *Childl = NULL, BTNode<T> *Childr = NULL)
{
data = val;
lChild = Childl;
rChild = Childr;
}
}

template<class T>
class BinaryTree//二叉树的数据结构
{
public:
BTNode<T> *root;
BinaryTree();
~BinaryTree();

void Pre_Order();
void In_Order();
void Post_Order();

int TreeHeight()const;
int TreeNodeCount()const;

void DestroyTree();
void MakeTree(T pData, BinaryTree<T> leftTree, BinaryTree<T> rightTree);

void TreeCoding();

private:
void Destroy(BTNode<T> *&r);
void PreOrder(BTNode<T> *r);
void InOrder(BTNode<T> *r);
void PostOrder(BTNode<T> *r);

int Height(const BTNode<T> *r)const;
int NodeCount(const BTNode<T> *r)const;

void Coding(BTNode<T> *r);
};

template<class Type>
class Huffman//哈夫曼树的数据结构
{
friend BinaryTree<int> HuffmanTree(Type[], int);
public:
operator Type() const//类型转换操作符
{
return weight;
}
//private:
BinaryTree<int> tree;
Type weight;
};

3.3 函数原型设计
template<class T>
MinHeap<T>::MinHeap(int n)//最小堆构造函数

template<class T>
MinHeap<T>::~MinHeap()//最小堆析构函数

template<class T>
void MinHeap<T>::FilterUp(int start) //自下往上调整

template<class T>
void MinHeap<T>::FilterDown(const int start, const int end) //自上往下调整，使关键字小的节点在上

template<class T>
bool MinHeap<T>::Insert(const T &x)//插入结点

template<class T>
T MinHeap<T>::RemoveMin()//删除最小结点

template<class T>
T MinHeap<T>::GetMin()//获得当前最小结点

template<class T>
bool MinHeap<T>::IsEmpty() const//判空

template<class T>
bool MinHeap<T>::IsFull() const//判断堆是否已满

template<class T>
void MinHeap<T>::Clear()//清空堆

template<class T>
BinaryTree<T>::BinaryTree()//二叉树构造函数

template<class T>
BinaryTree<T>::~BinaryTree()//二叉树析构函数

template<class T>
void BinaryTree<T>::Pre_Order()//前序遍历二叉树，调用PreOrder

template<class T>
void BinaryTree<T>::In_Order()//中序遍历二叉树，调用InOrder

template<class T>
void BinaryTree<T>::Post_Order()//后序遍历二叉树，调用PostOrder

template<class T>
int BinaryTree<T>::TreeHeight()const//求树的深度

template<class T>
int BinaryTree<T>::TreeNodeCount()const//求树的总结点

template<class T>
void BinaryTree<T>::DestroyTree()//销毁二叉树

template<class T>
void BinaryTree<T>::TreeCoding()//二叉树编码

template<class T>
void BinaryTree<T>::PreOrder(BTNode<T> *r)//前序遍历二叉树

template<class T>
void BinaryTree<T>::Coding(BTNode<T> *r)//二叉树编码

template<class T>
void BinaryTree<T>::InOrder(BTNode<T> *r)//中序遍历二叉树

template<class T>
void BinaryTree<T>::PostOrder(BTNode<T> *r)//后序遍历二叉树

template<class T>
int BinaryTree<T>::NodeCount(const BTNode<T> *r)const//节点计数

template<class T>
int BinaryTree<T>::Height(const BTNode<T> *r)const//求二叉树的深度

template<class T>
void BinaryTree<T>::Destroy(BTNode<T> *&r)//销毁二叉树

template<class T>
void BinaryTree<T>::MakeTree(T pData, BinaryTree<T> leftTree, BinaryTree<T> rightTree)//生成二叉树

template<class Type>
BinaryTree<int> HuffmanTree(Type f[], int n);//求哈弗曼树

3.4 主算法设计

3.5 用户界面设计
采用命令行界面，提示用户输入字符、权值（频率），然后输出哈夫曼树的前序遍历和中序遍历结果，以及相应的哈夫曼编码。

4 方案实现
4.1 开发环境与工具
采用VS2013进行C++ STL编程。

4.2 程序设计关键技术
（1） 最小堆优先队列的实现技术。最小堆可以每次筛选出权值最小的结点，而哈夫曼树的构造恰恰需要的就是权值最小的结点，利用最小堆的优先队列可以十分快捷地选取两个权值最小的结点从而组件哈夫曼树。

（2） 哈夫曼树的生成算法。

4.3 个人设计实现（按组员分工）
4.3.1 黄红清设计实现
（1）主函数
int main()
{
char c[N + 2] = { "0" };
char cc[N + 1];
int f[N+1];//下标从1开始
cout << "输入6个字符：" << endl;
cin >> cc;
strcat_s(c, cc);//使c下表从1开始
cout << "依次输入它们的频率：" << endl;
for (int i = 1; i < N + 1; i++)
cin >> f[i];
cout << "字符频率：" << endl;
for (int i = 1; i <= N; i++)
{
cout << c[i] << ":" << f[i] << " ";
}
cout << endl;

BinaryTree<int> t = HuffmanTree(f, N);
cout << "已生成哈夫曼树。" << endl;

cout << "前序遍历哈夫曼树：" << endl;
t.Pre_Order();
cout << endl;

cout << "中序遍历哈夫曼树：" << endl;
t.In_Order();
cout << endl;

cout << "按前序遍历输出各点哈夫曼编码：" << endl;
t.TreeCoding();

t.DestroyTree();
return 0;
}
（2）利用最小堆的优先队列实现生成哈夫曼树
具体实现：
template<class Type>
BinaryTree<int> HuffmanTree(Type f[], int n)
{
//生成单节点树
Huffman<Type> *w = new Huffman<Type>[n + 1];
BinaryTree<int> z, zero;

for (int i = 1; i <= n; i++)
{
z.MakeTree(i, zero, zero);
w[i].weight = f[i];
w[i].tree = z;
}

//建优先队列
MinHeap<Huffman<Type>> Q(n);
for (int i = 1; i <= n; i++) Q.Insert(w[i]);

//反复合并最小频率树
Huffman<Type> x, y;
for (int i = 1; i<n; i++)
{
x = Q.RemoveMin();
y = Q.RemoveMin();
z.MakeTree(0, x.tree, y.tree);
x.weight += y.weight;
x.tree = z;
Q.Insert(x);
}

x = Q.RemoveMin();

delete[] w;

return x.tree;
}

（3） 二叉树编码
void BinaryTree<T>::TreeCoding()
{
Coding(root);
}
void BinaryTree<T>::Coding(BTNode<T> *r)
{
static char c[N + 1] = { "" };
static int a=N+1;
if (r != NULL)
{
strcat_s(c, "0");
Coding(r->lChild);
int j = 0;
for (; c[j] != '\0'; j++);
c[j - 1] = '\0';
if (r->data&&r->data!=a)
{
cout << r->data << " : " << c << endl;
a = r->data;
}
strcat_s(c, "1");
Coding(r->rChild);
int i = 0;
for (; c[i]!='\0'; i++);
c[i - 1] = '\0';
if (r->data&&r->data != a)
{
cout << r->data << " : " << c << endl;
a = r->data;
}
}
}

4.3.2 邢伟的设计实现
我进行了最小堆的设计，用STL实现了优先队列及其基本操作：
template<class T>
class MinHeap
{
private:
T *heap; //元素数组，0号位置也储存元素
int CurrentSize; //目前元素个数
int MaxSize; //可容纳的最多元素个数

void FilterDown(const int start, const int end); //自上往下调整，使关键字小的节点在上
void FilterUp(int start); //自下往上调整

public:
MinHeap(int n = 1000);
~MinHeap();
bool Insert(const T &x); //插入元素

T RemoveMin(); //删除最小元素
T GetMin(); //取最小元素

bool IsEmpty() const;
bool IsFull() const;
void Clear();
};

template<class T>
MinHeap<T>::MinHeap(int n)
{
MaxSize = n;
heap = new T[MaxSize];
CurrentSize = 0;
}

template<class T>
MinHeap<T>::~MinHeap()
{
delete[]heap;
}

template<class T>
void MinHeap<T>::FilterUp(int start) //自下往上调整
{
int j = start, i = (j - 1) / 2; //i指向j的双亲节点
T temp = heap[j];

while (j>0)
{
if (heap[i] <= temp)
break;
else
{
heap[j] = heap[i];
j = i;
i = (i - 1) / 2;
}
}
heap[j] = temp;
}

template<class T>
void MinHeap<T>::FilterDown(const int start, const int end) //自上往下调整，使关键字小的节点在上
{
int i = start, j = 2 * i + 1;
T temp = heap[i];
while (j <= end)
{
if ((j<end) && (heap[j]>heap[j + 1]))
j++;
if (temp <= heap[j])
break;
else
{
heap[i] = heap[j];
i = j;
j = 2 * j + 1;
}
}
heap[i] = temp;
}

template<class T>
bool MinHeap<T>::Insert(const T &x)
{
if (CurrentSize == MaxSize)
return false;

heap[CurrentSize] = x;
FilterUp(CurrentSize);

CurrentSize++;
return true;
}

template<class T>
T MinHeap<T>::RemoveMin()
{
T x = heap[0];
heap[0] = heap[CurrentSize - 1];

CurrentSize--;
FilterDown(0, CurrentSize - 1); //调整新的根节点

return x;
}

template<class T>
T MinHeap<T>::GetMin()
{
return heap[0];
}

template<class T>
bool MinHeap<T>::IsEmpty() const
{
return CurrentSize == 0;
}

template<class T>
bool MinHeap<T>::IsFull() const
{
return CurrentSize == MaxSize;
}

template<class T>
void MinHeap<T>::Clear()
{
CurrentSize = 0;
}

4.3.3王帅的设计实现
我设计的是成员的的创建，添加，删除，组的创建，添加，删除，前序，后序，先序遍历。树的销毁。
struct BTNode
{
T data;
BTNode<T> *lChild, *rChild;

BTNode()
{
lChild = rChild = NULL;
}

BTNode(const T &val, BTNode<T> *Childl = NULL, BTNode<T> *Childr = NULL)
{
data = val;
lChild = Childl;
rChild = Childr;
}

BTNode<T>* CopyTree()
{
BTNode<T> *nl, *nr, *nn;

if (&data == NULL)
return NULL;

nl = lChild->CopyTree();
nr = rChild->CopyTree();

nn = new BTNode<T>(data, nl, nr);
return nn;
}
};

class BinaryTree
{
public:
BTNode<T> *root;
BinaryTree();
~BinaryTree();

void Pre_Order();
void In_Order();
void Post_Order();

int TreeHeight()const;
int TreeNodeCount()const;

void DestroyTree();
void MakeTree(T pData, BinaryTree<T> leftTree, BinaryTree<T> rightTree);
void Change(BTNode<T> *r);

void TreeCoding();

private:
void Destroy(BTNode<T> *&r);
void PreOrder(BTNode<T> *r);
void InOrder(BTNode<T> *r);
void PostOrder(BTNode<T> *r);

int Height(const BTNode<T> *r)const;
int NodeCount(const BTNode<T> *r)const;

void Coding(BTNode<T> *r);
};

template<class T>
BinaryTree<T>::BinaryTree()
{
root = NULL;
}
BinaryTree<T>::~BinaryTree()
{

}

template<class T>
void BinaryTree<T>::Pre_Order()
{
PreOrder(root);
}

template<class T>
void BinaryTree<T>::In_Order()
{
InOrder(root);
}

template<class T>
void BinaryTree<T>::Post_Order()
{
PostOrder(root);
}

template<class T>
int BinaryTree<T>::TreeHeight()const
{
return Height(root);
}

template<class T>
int BinaryTree<T>::TreeNodeCount()const
{
return NodeCount(root);
}

template<class T>
void BinaryTree<T>::DestroyTree()
{
Destroy(root);
}

template<class T>

void BinaryTree<T>::PreOrder(BTNode<T> *r)
{
if (r != NULL)
{
cout << r->data << ' ';
PreOrder(r->lChild);
PreOrder(r->rChild);
}
}
void BinaryTree<T>::InOrder(BTNode<T> *r)
{
if (r != NULL)
{
InOrder(r->lChild);
cout << r->data << ' ';
InOrder(r->rChild);
}
}

template<class T>
void BinaryTree<T>::PostOrder(BTNode<T> *r)
{
if (r != NULL)
{
PostOrder(r->lChild);
PostOrder(r->rChild);
cout << r->data << ' ';
}
}

template<class T>
int BinaryTree<T>::NodeCount(const BTNode<T> *r)const
{
if (r == NULL)
return 0;
else
return 1 + NodeCount(r->lChild) + NodeCount(r->rChild);
}

template<class T>
int BinaryTree<T>::Height(const BTNode<T> *r)const
{
if (r == NULL)
return 0;
else
{
int lh, rh;
lh = Height(r->lChild);
rh = Height(r->rChild);
return 1 + (lh>rh ? lh : rh);
}
}

template<class T>
void BinaryTree<T>::Destroy(BTNode<T> *&r)
{
if (r != NULL)
{
Destroy(r->lChild);
Destroy(r->rChild);
delete r;
r = NULL;
}
}
void BinaryTree<T>::MakeTree(T pData, BinaryTree<T> leftTree, BinaryTree<T> rightTree)
{
root = new BTNode<T>();
root->data = pData;
root->lChild = leftTree.root;
root->rChild = rightTree.root;
}

5 测试与调试
5.1 个人测试（按组员分工）
5.1.1 黄红清测试
（1）利用前序遍历和中序遍历的结果画图测试了哈夫曼树生成的正确性，通过调试程序，发现错误主要出现在循环控制条件上，导致缺少了结点，于是进行了修改。

（2）进行了哈夫曼编码的测试，直接在树前序遍历的基础上进行修改，遍历的同时完成哈夫曼编码的输出，与（1）相互共同检查了哈夫曼树的正确性。

5.1.2邢伟的测试
（1）用类建立的小顶堆模型，为建立哈夫曼树提供堆顶元素，方便调用。

（2）在建立小顶堆的调整过程，删除元素和插入元素时，需要不同的调整函数，自上而下的调整函数和自下而上的调整函数。
5.1.3王帅的测试
（1）在执行程序时，不可以直接调用类的私用成员函数，必须从公有处调用。
（2）树的删除时应先将左右孩子删除后，再将双亲节点释放。

5.2 组装与系统测试
操作名称
操作流程
操作结果和输出
输入字符
从键盘键入相应数目字符
字符被保存至字符数组
输入权值
依次输入相应字符权值，空格分开
权值成功输入，显示出字符及其对应权值。并自动进行哈夫曼树和哈夫曼编码。在命令行中显示出哈夫曼树的前序遍历和中序遍历结果，以及哈夫曼编码结果。经校对正确无误。

5.3 系统运行
测试数据如图所示：

首先输入7个结点和他们的权值（频率），此时const N已经设置为7：

然后程序输出哈夫曼树遍历结果和编码结果：

6 课题总结
6.1 课题评价
该课题设计难度较大，我们首先一起利用网络查找了有关堆的优先队列、哈夫曼树、哈夫曼编码的相关知识，接触到了一定的算法基础，然后分工合作，最终完成了程序的功能，能够输出正确的结果。但是哈夫曼编码由于时间紧张，并未采用栈来编码，而是在遍历的基础上直接输出编码结果，来检查哈夫曼树的正确与否。
6.2 团队协作
这次实验分为三个部分：二叉树结构设计和操作、最小堆实现和利用优先队列生成哈夫曼树和编码。我们先一起学习了STL的相关知识，利用它进行编程，二叉树的结构设计和基本操作编程，最小堆部分由组员根据相关知识进行设计，之后由组长整合并完成哈夫曼树的生成和编码。

这次课题结果是简单的，但过程是具有挑战性和意义深刻的，在对课题的理解上，我们相互讨论，共同学习，在明确课题是在做什么后，进行了合理的分工，在各成员自我努力和借鉴资料后，成功编完自己的部分，然后组装到一起运行无误，让我们感受到了合作的喜悦。

6.3 个人设计小结（按组员分工）
6.3.1 黄红清设计小结
（1）这次设计我直接使用了组员设计好的封装好的最小堆类和二叉树类，在此基础上进行编程实现哈夫曼树，感受到了C++封装的方便之处，STL类模板对各种编程更具有普适性。

（2）这次编程比较困难的地方是如何把二叉树、哈夫曼树和优先队列联系起来，我参考了网上的相关知识后，才学会了其中的关系，输入各结点的权值实际上只是一个数组，然后将权值一一建立起“小树”（单节点树）来，利用优先队列来存储这些树的结点，然后利用优先队列的相关操作实现哈夫曼树的组建，生成哈夫曼树。让我对各种数据结构通过类模板的相互联系理解更加深刻。

6.3.2邢伟设计小结
（1）将设计小顶堆各种功能放在小顶堆的类中，方便成员函数和成员之间的互相调用，通过此次实验了解类模块化的重要。

（2）对面向对象类编程有一定了解，可以实现封装，知道了面向对象对象的编程，容易分工并且实现代码重复利用。

（3）堆排列可以大大提高程序的效率。

6.3.3王帅设计小结
（1） 可以用一个树的前序，中序，后序 中的两个将一颗树组建出来。

（2） 程序中多次利用函数的递归，使算法更加高效率。

7 附录A 课题任务分工
A-1 课题程序设计分工

学号
姓名
程序设计函数原型、类
功能说明