loading2009级数据结构实验报告
实验名称： 实验三——哈夫曼编/解码器的实现 学生姓名：陈聪捷
日 期： 2010年11月28日
1．实验要求
一、实验目的：
了解哈夫曼树的思想和相关概念；
二、实验内容：
利用二叉树结构实现哈夫曼编/解码器
1.初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。
2.建立编码表：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。 3.编码：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4.译码：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。 5.打印：以直观的方式打印哈夫曼树。
6.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。 7.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。
2. 程序分析
存储结构
二叉树
template
public: char code[100] BiTree(); 始化函HuffmanTree::Init(string char dataT data char characterT lchild T rchildunsigned int count T parentbool used 数（void Node* next Input)） 算法伪代码：
1.初始化链表的头结点
2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)
3.从字符串第2个字符开始，逐个取出字符串中的字符
将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的
字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。
如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到
链表尾部，同时n++
=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数) 5.创建哈夫曼树 6.销毁链表
源代码：
void HuffmanTree::Init(string Input)
{ Node *front=new Node; 建哈夫曼树（void HuffmanTree::CreateCodeTable(Node *p)） 算法伪代码：
1. 创建一个长度为2*tSize-1的三叉链表
2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点
的data域，并将对应结点的孩子域和双亲域赋为空 3. 从三叉链表的第tSize个结点开始，i=tSize
3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下
标x,y。
3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点
3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i
结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空
4. 根据哈夫曼树创建编码表
源代码：
void HuffmanTree::CreateHTree(Node *p,int n) {
root= new BiNode
int New1,New2; for(i=n;i<2*n-1;i++) { SelectMin(New1,New2,0,i); arent=root[New2].parent=i; ata=root[New1].data+root[New2].data;child=New1; root[i].rchild=New2; root[i].parent=-1; } CreateCodeTable(p); 始化编码表 2.初始化一个指针，从链表的头结点开始，遍历整个链表 将链表中指针当前所指的结点包含的字符写入编码表中 得到该结点对应的哈夫曼树的叶子结点及其双亲
如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0
如果不止一个叶子结点，从当前叶子结点开始判断
2.4.1 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否则为1
2.4.2 child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复的操作
将已完成的编码倒序 取得链表中的下一个字符 3．输出编码表 源代码：
void HuffmanTree::CreateCodeTable(Node *p)
{
HCodeTable=new HCode[tSize]; ata=front->character; arent; ode[k]='0'; k++; } while(parent!=-1) child) ode[k]='0'; else
HCodeTable[i].code[k]='1'; k++; child=parent; parent=root[child].parent; } HCodeTable[i].code[k]='\\0'; Reverse(HCodeTable[i].code); ata<<' '< 时间复杂度： 需要遍历哈夫曼树获取编码，时间复杂度为O（n^2） 4. 选择两个最小权值的函数（void HuffmanTree::SelectMin(int &New1,int &New2,int begin,int end)） 算法伪代码： 1. 从下标为begin的结点开始，寻找第一个没用过的结点 2. 遍历哈夫曼树中从下标为begin到下标为end的结点序列，寻找没用过的 同时权值又是最小的结点。 3. 暂时改变找到的权值最小结点的双亲域，防止第2次找到相同的结点。 4. 将权值最小结点的下标记录下来。 5. 重复步骤1~4，找到第2个权值最小的结点 源代码： void HuffmanTree::SelectMin(int &New1,int &New2,int begin,int end) { int min; for(int j=0;j<2;j++) arent==-1) ata; sign=i; break; } } for(i=begin;i root[sign].parent=0;将字符串倒序的函数（void HuffmanTree::Reverse(char *pch)） 算法伪代码： 1． 得到字符串的长度 2． 初始化两个记录下标的变量，一个为字符串开头字符所在的下标i，另一 个为字符串结尾字符所在的下标j 3． 将下标为i和j的字符交换 4． i++,j - - 时间复杂度： 时间复杂度为O（n） 6.编码函数（void HuffmanTree::Encode(string &s,string &d)） 算法伪代码： 1. 从s开头的字符开始，逐一对s中的字符进行编码 2. 在编码表中查找与当前字符对应的字符 3．如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末 尾。 4. 重复以上步骤，直到所有待编码串中的字符都编码完毕 5. 输出编码后的字符串 源代码： void HuffmanTree::Encode(string &s,string &d) { for(int j=0;j<();j++) ata) { (HCodeTable[i].code); 码函数（void HuffmanTree::Decode(string &s,string &d)） 算法伪代码： 1. 得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针 2. 逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向 当前结点的左孩子，若为1，则指向当前结点的右孩子 3. 指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点 的指针的孩子结点为空 4. 如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的 字符 5. 如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对 应的字符追加到解码串中。 6. 输出解码串 源代码： void HuffmanTree::Decode(string &s,string &d) { for(int i=0;i<();) { int parent=2*tSize-1-1; child!=-1) child; else child; i++; } if(tSize==1) ata);计算哈夫曼编码的压缩比（void HuffmanTree::Calculate(string s1,string s2)） 算法伪代码： 1. 获得编码前字符串的长度，即其占用的字节数 2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字 节数 3. 压缩比将两个相除 源代码： void HuffmanTree::Calculate(string s1,string s2) { int cal1=(); int cal2=(); cal2=ceill((float)cal2/8); 打印哈夫曼树（void HuffmanTree::PrintTree(int TreeNode,int layer) ） 算法伪代码： 1. 如果待打印结点为空，则返回 2. 递归调用函数打印当前结点的右子树 3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打 印当前结点的权值 4. 递归调用函数打印当前结点的左子树 源代码： void HuffmanTree::PrintTree(int TreeNode,int layer) { if(TreeNode==-1) child,layer+1); ata< child,layer+1); 菜单函数（void HuffmanTree::Menu()） 算法伪代码： 1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的 string变量中，直到读到回车输入符为止 2. 删除string变量末尾的回车输入符 3．利用string变量创建哈夫曼树，初始化编码表。