哈夫曼编码实验报告

北京邮电大学信息与通信工程学院第6页北京邮电大学电信工程学院第1页数据结构实验报告实验名称：实验三——哈夫曼编码学生姓名：牛佳宁班级：2010211107班内序号：27学号：10210213日期：2011年12月10日1．实验要求利用二叉树结构实现赫夫曼编/解码器。1、读入一串字符，统计字符个数及权值。2、建立哈夫曼树。3、根据哈夫曼树建立哈夫曼表。4、将字符串进行编码。5、输入一串01数，进行解码。2.程序分析2.1存储结构哈夫曼树为正则二叉树，有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的数组来储存哈夫曼树的各个结点，如图weightLchildRChildparent2-1-1-13-1-1-16-1-1-19-1-1-1对应的编码表可用如图所示结构datacodeZ100C101B112.2关键算法分析一、创建哈夫曼树1、根据权值初始化哈夫曼树for(inti=0;i<n;i++) { HTree[i].weight=a[i]; HTree[i].LChild=-1; HTree[i].RChild=-1; HTree[i].parent=-1；}2、开始建立哈夫曼树，intx,y; for(inti=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; }二、建立哈夫曼编码表voidHuffman::CreateCodeTable(charb[],intn){ HCodeTable=newHCode[n]; for(inti=0;i<n;i++) { HCodeTable[i].data=b[i];//生成编码表 intchild=i; intparent=HTree[i].parent; intk=0; while(parent!=-1) { if(child==HTree[parent].LChild) HCodeTable[i].code[k]='0';//左孩子标‘0’ else HCodeTable[i].code[k]='1';//右孩子标‘1’ k++; child=parent; parent=HTree[child].parent; } HCodeTable[i].code[k]='\0'; char*b=newchar[k];//将编码字符逆置,再初始化一个数组倒着储存编码数组，再将该数组重新赋给编码数组 for(intj=0;j<k;j++) { b[j]=HCodeTable[i].code[k-1-j]; } for(intjj=0;jj<k;jj++) { HCodeTable[i].code[jj]=b[jj]; } }}三、编码函数：根据编码表进行编码，从编码表中第一个开始遍历，若找到要编码的字符则输出编码，并进行下一个字符的查找voidHuffman::Encode(char*s,intn){ while(*s!='\0') { for(inti=0;i<n;i++) { if(*s==HCodeTable[i].data) { cout<<HCodeTable[i].code; s++; } } } cout<<endl;}四、解码：利用哈夫曼树进行解码，编码串左到右依次逐位判断，从根结点开始根据每一位是0还是1，确定是左分支还是右分支，直到到叶子节点为止，从编码表中找到对应字符并输出voidHuffman::Decode(char*s,char*d,intn)//s为编码串，{ while(*s!='\0') { intparent=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++; } cout<<endl;}五、利用STL中的排序函数选择两个权值最小结点intHuffman::SelectMin(intx,y,o,i)//选择两个最小的{ list<int>ilist; for(intj=0;j<i;j++) { if(HTree[j].parent=-1) ilist.push_back(HTree[j].weight); } ilist.sort(); list<int>::iteratorit=ilist.begin(); x=*it; y=*++it; returnx,y;}六、建立数组不重复的储存字符并且统计出现次数即权值：利用循环链表来实现，每插入一个结点之前先定义节点指针指向第一个结点，边向后移动边比较储存的字符是否相同，若相同则使该节点权值加一，不同则将该节点加入到循环链表中，直到遍历整个字符串，代码如下voidLinklist::Construct(chars[])//建立循环链表存放字符串{ rear=newNode; rear->next=rear; for(unsignedinti=0;i<strlen(s);i++) { if(rear->next==rear)//放入第一个字符 { Node*p=newNode; p->data=s[0]; p->weight=1; p->next=rear->next; rear->next=p; rear=p; } else { 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=newNode; r->data=s[i]; r->weight=1; r->next=rear->next; rear->next=r; rear=r; } } }}qq时间复杂度计算：select函数的时间复杂度为O(n),则建立哈夫曼树的时间按复杂度为Ｏ（ｎ＾２）建立哈夫曼编码表的时间复杂度为O（n）。编码的函数时间复杂度为O（n）。解码函数的时间复杂度为O（n^2）。程序运行结果运行环境为vc6.0编码前的长度为32编码后的长度为22，压缩比为22/32=68.75%4.总结在调试过程中遇到过很多困难，比如在写选择权重最小的两个节点的编码时，就出现了选择出最大的输出两遍等问题你，逻辑上有些麻烦，但是使用STL后，程序变得简单多了，而且不用考虑那些过于细致的问题。吸取上次八皇后问题编码时使用递归函数容易出现停止递归的条件不明显等问题，这次选择了用循环来实现递归，虽然代码变长，但是思维变得清晰起来，也不太容易出