哈夫曼编码实验报告

北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验三——哈夫曼编码 学生姓名： 牛佳宁 班 级： 2010211107 班内序号： 27 学 号： 10210213

日 期： 2011年12月10日

1．实验要求

利用二叉树结构实现赫夫曼编/解码器。

1、读入一串字符，统计字符个数及权值。 2、建立哈夫曼树。

3、根据哈夫曼树建立哈夫曼表。 4、将字符串进行编码。

5、输入一串01数，进行解码。

2. 程序分析

2.1 存储结构

哈夫曼树为正则二叉树，有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的数组来储存哈夫曼树的各个结点，如图 weight 2 3 6 9 data Z C B Lchild -1 -1 -1 -1 code 100 101 11 RChild -1 -1 -1 -1 parent -1 -1 -1 -1 对应的编码表可用如图所示结构

2.2 关键算法分析

第1页

北京邮电大学信息与通信工程学院

一、创建哈夫曼树

1、根据权值初始化哈夫曼树 for(int i=0;i

}

2、开始建立哈夫曼树，

int x,y;

for (int i=n;i<2*n-1;;i++) { selectMin(x,y,o,i);//从1到i选择两个权值最小的 HTree[x].parent=HTree[y].parent=i; HTree[i].weight=HTree[x].weight+HTree[y].weight; HTree[i].LChild=x; HTree[i].parent=-1; }

二、建立哈夫曼编码表

void Huffman::CreateCodeTable(char b[],int n) { HCodeTable=new HCode [n]; for (int i=0;i

第2页

北京邮电大学信息与通信工程学院

b[j]=HCodeTable[i].code[k-1-j]; } for(int jj=0;jj

三、编码函数：根据编码表进行编码，从编码表中第一个开始遍历，若找到要编码的字符则输出编码，并进行下一个字符的查找 void Huffman::Encode(char*s,int n) { while(*s!='\\0') { for(int i=0;i

四、解码：利用哈夫曼树进行解码，编码串左到右依次逐位判断，从根结点开始根据每一位是0还是1，确定是左分支还是右分支，直到到叶子节点为止，从编码表中找到对应字符并输出

void Huffman::Decode(char*s,char*d,int n)//s为编码串， { while(*s!='\\0') { int parent=2*n-1-1;//根节点在HTree中的下标； while(HTree[parent].LChild!=-1) { if(*s=='0') parent=HTree[parent].LChild; else parent=HTree[parent].RChild; s++; } *d=HCodeTable[parent].data; cout<<*d; d++;

第3页

北京邮电大学信息与通信工程学院

}

}

cout<

五、利用STL中的排序函数选择两个权值最小结点 int Huffman::SelectMin(int x,y,o,i)//选择两个最小的 { list ilist; for(int j=0;j::iterator it=ilist.begin(); x=*it; y=*++it; return x,y; }

六、建立数组不重复的储存字符并且统计出现次数即权值： 利用循环链表来实现，每插入一个结点之前先定义节点指针指向第一个结点，边向后移动边比较储存的字符是否相同，若相同则使该节点权值加一，不同则将该节点加入到循环链表中，直到遍历整个字符串，代码如下

void Linklist::Construct(char s[])//建立循环链表存放字符串 { rear=new Node; rear->next=rear; for(unsigned int i=0;inext==rear)//放入第一个字符 { Node *p=new Node; p->data=s[0]; p->weight=1; p->next=rear->next ; rear->next=p; rear=p; } else {

第4页

北京邮电大学信息与通信工程学院

法插入 } }

}

Node *q=rear->next->next;//q指向第一个字符

while(q!=rear->next )//遍历链表看q存储的字符是否有与要插入的字符相同的 { if(q->data==s[i]) { q->weight++;//若有则权值加一 break; } else q=q->next; }

if(q==rear->next )//若链表中无与要插入字符相同的字符，则将该字符使用头插{ }

Node *r=new Node; r->data=s[i]; r->weight=1;

r->next =rear->next ; rear->next =r; rear=r;

q

时间复杂度计算：select函数的时间复杂度为O(n),则建立哈夫曼树的时间按复杂度为Ｏ（ｎ

第5页

北京邮电大学信息与通信工程学院

＾２）建立哈夫曼编码表的时间复杂度为O（n）。编码的函数时间复杂度为O（n）。解码函数的时间复杂度为O（n^2）。

3. 程序运行结果 运行环境为vc6.0

编码前的长度为32编码后的长度为22，压缩比为22/32=68.75%

4. 总结

在调试过程中遇到过很多困难，比如在写选择权重最小的两个节点的编码时，就出现了选择出最大的输出两遍等问题你，逻辑上有些麻烦，但是使用STL后，程序变得简单多了，而且不用考虑那些过于细致的问题。

吸取上次八皇后问题编码时使用递归函数容易出现停止递归的条件不明显等问题，这次选择了用循环来实现递归，虽然代码变长，但是思维变得清晰起来，也不太容易出现错误 通过这次编程是我对哈夫曼编码有了更深刻的理解，并且学会了将之前学过的循环链表等数据存储结构运用到程序中来，并且有了解了STL的排序功能，又一次见识到了STL的方便快捷。但本实验仍有很多不足：

1、 在解码时仍缺少差错能力，使解码有误

2、 在统计字符权重时使用循环链表虽然有比较与统计长度方便等优点，但仍不够简洁，应

该还存在着更为简单的方法 3、 未能实现菜单的交互

第6页