实验四 哈夫曼树与哈夫曼编码

一、实验内容

[问题描述]

已知n个字符在原文中出现的频率，求它们的哈夫曼编码。 [基本要求]

1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman

树。（具体算法可参见教材P147的算法6.12）

2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。

对给定的待编码字符序列进行编码。

二、概要设计

算法设计：

要是实现哈夫曼树的操作，首先创建一个哈夫曼树，在创建哈夫曼树的时候，对哈夫曼树的叶子和非叶子结点进行初始化，而在建立哈夫曼树时，最难的该是选择权值最小的两个顶点，然后两个结点的权值和作为新的权值，再选择两个权值最小的作为新的两个结点创建一个小的二叉树的子树；创建哈夫曼树后，进行编码，在编码过程中，先找到根，然后遍历，左孩子用0标记，右孩子用1标记，最后将编码好的哈夫曼树进行输出，就可以知道哈夫曼树的编码了。

流程图：

开始 输入哈弗曼树的带权结点数目 n 输入相应的权值和对应的字符 建立哈夫曼树Huffmantree(HT,w,n,e) 显示哈夫曼树outputHuffman(HT,m哈夫曼树的编码 CHuffmancode(HT,HC,n) 结束 算法：

主函数 Huffmantree(HuffmanTree &HT,int*w,int n,char *e)*hc, CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int outputHuffman(HuffmanTree HT, int m) select(HuffmanTree *ht,int n, int *s1, int *s2) 模块：

在分析了实验要求和算法分析之后，将程序分为四个功能函数，分别如下：

首先建立一个哈夫曼树和哈夫曼编码的存储表示： typedef struct { int weight;

int parent,lchild,rchild; char elem;

}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树

typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表CrtHuffmanTree(HuffmanTree *ht , int *w, int n)：w存放n个字符的权值，构造哈夫曼树HT。先将叶子初始化，再将非叶子结点初始化，然后构造哈夫曼树。 构造哈夫曼树：

开始 叶子初始化 非叶子初始化 调用select函数选择权值最小的两个 这两个权值最小的两个字符非别作为同一个结点的左右孩子，其父母的权值为两个字符的权值之和 结束 for(i=n+1;i<=m;++i)

{//在HT[1……i]选择parent为0且weight最小的两个 Select(HT,i-1,&s1,&s2);

HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weig ht+HT

[Select(HuffmanTree &HT,int n,int *s1,int *s2)：在所给的权值中，选择出权值最小的两个值。

int i, min;

for(i=1;i<=n;i++) { if(HT[i].parent==0) { min=i; i=n+1; } }

for(i=1;i<=n;i++) { if(HT[i].parent==0) { if(HT[i].weight在选择s2的时候和s1相似，只有在判断是否为最小的时候就，要加上一个条件：if(HT[i].parent==0&&i!=*s1)，就可以了，否则，选出来的最小权值和s1 就相等了，失去了选择的意义了。

CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n)：从叶子到根逆向求编码：左孩子为0，右孩子为1，这样一直循环下去，而最重要的是：

for(int i=1;i<=n;++i) { star=n-1; //从右向左逐位存放编码，首先存放编码结束符 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根结点求编码 if(HT[f].lchild==c) cd[--star]='0'; //左分支标0 else cd[--star]='1';//右分支标1 HC[i]=new char[n-star]; //为第i个编码分配空间 strcpy(HC[i],&cd[star]);//从cd复制编码串到HC }

开始 从叶子到根结点求编码 c=i f=HT[i].parent f!=0 是 c=f,f=HT[f].parent HT[f].lchild==c 是 将0输入到cd数组将1输入到cd数组 否 输出字符权值相应的编码 否 从cd复制编码串到HC 结束

outputHuffman(HuffmanTree HT, int m)：显示出哈夫曼树的编码和字

符以及权重，与二叉树的遍历相似：

if(m!=0) {

cout<三 、测试数据

测试一：字符为：A B C 权重：10 12 8

测试数据二：字符为：ABCDEFG权重为：7 8 8 12 15 9 6 四、结果调试 调试一：

调试二：

五．总结

在进行这个程序的编写的时候，其实有点毫无头绪，只是知道在书上的算法就可以编写成功。但是在一次又一次的过程，还是一次又一次的错误，最后在进行理解才稍微理解了哈夫曼树的编码过程，但是选择权值最小的过程还是不太理解，进行了调试才明白也一些，但是还是没有明白透彻。在这次的实验过程中，我明白了调试的重要性，不要在自己遇到问题的时候就去问同学，因为那样会养成自己的依赖性，在自己不会的时候，不会进行深

层次的了解就去问，那样对自己没有太大的提高，只有自己理解和同学的讲解相结合，才能有所提高。 六、附录：

#include #include typedef struct { int weight;

int parent,lchild,rchild; char elem;

}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树

typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表 ////////////////////////求赫夫曼编码

void Select(HuffmanTree &HT,int n,int *s1,int *s2) {

int i, min;

for(i=1;i<=n;i++) { if(HT[i].parent==0) { min=i; i=n+1; } }

for(i=1;i<=n;i++) { if(HT[i].parent==0) { if(HT[i].weightfor(i=1; i<=n; i++) {

if(HT[i].parent == 0 && i!=*s1) {

min = i; i = n+1; } }

for(i=1;i<=n;i++) { if(HT[i].parent==0&&i!=*s1) { if(HT[i].weight*s2=min;

}

////////////////////

void Huffmantree(HuffmanTree &HT,int*w,int n,char *e)

{ //w存放n个字符的权值，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC int m,i,s1,s2; if(n<=1) return; m=2*n-1;//总的结点 HT=new HTNode[m+1]; for(i=1;i<=n;++i) {/*1-n号放叶子结点，初始化*/ HT[i].weight=w[i]; HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; HT[i].elem=e[i]; } for(i=n+1;i<=m;++i) {/*非叶子结点初始化*/ HT[i].weight=0; HT[i].lchild=0; HT[i].rchild=0; HT[i].parent=0; HT[i].elem=0; } for(i=n+1;i<=m;++i) {//在HT[1……i]选择parent为0且weight最小的两个 Select(HT,i-1,&s1,&s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } }

////////////////////////////////////////////////////////

void CHuffmancode(HuffmanTree &HT,HuffmanCode &HC,int n) { char *cd; int c,f,star; HC=new char*[n+1]; cd=new char[n]; cd[n-1]='\\0';//编码结束符 for(int i=1;i<=n;++i) { star=n-1; //从右向左逐位存放编码，首先存放编码结束符 for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根结点求编码

if(HT[f].lchild==c) cd[--star]='0'; //左分支标0 else cd[--star]='1';//右分支标1 HC[i]=new char[n-star]; //为第i个编码分配空间 strcpy(HC[i],&cd[star]);//从cd复制编码串到HC } delete cd;//释放工作空间 for(i=1;i<=n;i++) cout<//////////////////////////// /////////////////////////

void outputHuffman(HuffmanTree HT, int m) { if(m!=0) {

cout<void main() {

HuffmanTree HT; HuffmanCode HC; int *w; char *e; char c; int i,n,m,wei; cout<<\"请输入赫夫曼树的带权数目：\"; cin>>n; w=new int[n+1]; e=new char[n+1]; for(i=1;i<=n;i++) { cout<<\"请输入第\"<>wei; w[i]=wei; cout<<\"请输入第\"<>c; e[i]=c; }

Huffmantree(HT,w,n,e); m=2*n-1;

outputHuffman(HT,m); CHuffmancode(HT,HC,n); }