当前位置：文档之家 › 哈夫曼编码课程设计报告

哈夫曼编码课程设计报告

  • 格式：doc
  • 大小：161.00 KB
  • 文档页数：18

多媒体课程设计报告基于哈夫曼树的文件压缩/解压程序2009-11-10一需求分析1.课题要求（实现文件的压缩与解压并计算压缩率）A.描述压缩基本符号的选择方法B.运行时压缩原文件的规模应不小于5K2.设计目标A软件名称：基于哈夫曼编码的文件压缩实用程序系统B软件组成：huffman.exeC制作平台及相关调试工具：Windows XP sp3 Microsoft Visual C++ 6.0D运行环境：dos/ win2K/win2003/winxp/E性能特点：1.软件由一个可执行文件组成huffman.exe为dos系统应用程序，体积小，高效快捷，适用范围广。

2. 对单字节（256叶子）进行哈夫曼编码，压缩率良好3. 使用二级缓冲压缩/解压技术，速度比一般算法高4. 可压缩最大体积为4G的文件，达到Fat32文件系统极限5. 文件索引体积比常规算法小50%二概要设计1.相关函数介绍1. bool InitFromFile(string fileadd) 从文件中初始化哈夫曼树函数2. void HTCreat(HTNode ht[],int n) 构造哈夫曼树函数3. void HCCreat(HTNode ht[],HCode hcd[],int n) 构造哈夫曼编码函数4. void ConvertFile(HCode hcd[],string fileadd,string fileadd2) 压缩and 写入文件函数5. void DecompressionFile(string fileadd2,string fileadd3) 文件解压函数6. string Compression(string fileadd) 压缩函数7. string Decompression(string fileadd2) 解压函数2.函数调用示意图三详细设计1.压缩算法部分A核心算法：Huffman编码是一种可变长编码方式，是由美国数学家David Huffman 创立的，是二叉树的一种特殊转化形式。

编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。

Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。

B哈夫曼树构造算法：Huffman树是二叉树的一种特殊转化形式。

以下是构件Huffman树的例子：比如有以下数据， ABFACGCAHGBBAACECDFGFAAEABBB先进行统计A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括号里面的是统计次数生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root) 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表中运算的过程如下：1:D+H(2)2:DE+H(4)3:F+G(6)4:C+DEH(8)5:B+FG(12)6:A+CDEH(16)7:ACDEH+BFG(28)那么转化为Huffman树就是Huffman树层数Root┌┴┐ACDEH BFG 1┌┴┐┌┴┐CDEH A B FG 2┌┴┐┌┴┐DEH C F G 3┌┴┐DH E 4┌┴┐D H 5取左面是1 右面是0 则有。

注：层数就是位数或者说是代码长度，权值=代码长度*该字的统计次数。

代码位数权值A = 10 2 16B = 01 2 12C = 110 3 12D = 11111 5 5E = 1110 4 8F = 001 3 9G = 000 2 6H = 11110 5 5可以看出Huffman代码是唯一可解的(uniquely decodable)，如果你读到110就一定是C ，不会有任何一个编码是以110开始的。

如果不使用Huffman算法，而使用普通的编码，结果是什么呢？Huffman树层数Root┌┴┐ABCD EFGH 1┌┴┐┌┴┐AB CD EF GH 2┌┴┐┌┴┐┌┴┐┌┴┐A B C D E F G H 3取左面是1 右面是0 则有代码位数权值A = 111 3 24B = 110 3 18C = 101 3 12D = 100 3 3E = 011 3 6F = 010 3 9G = 001 3 9H = 000 3 3利用Huffman编码得到的权值累计是 73，如果利用普通定长编码的话，则要用84字符长度。

从这个比较，可以看出，Huffman是怎么进行压缩的。

C哈夫曼编码结构及算法编码：将ABCDEFGH用Huffman树产生的编码对应着写到文件中，并且保留原始的Huffman树，主要是编码段的信息。

一般要编码256个元素的话需要511个单位来储存Huffman树，每个Huffman树都必须有以下的结构：code,char,left,right,probability(出现次数)，通常情况是利用一个数组结构。

因为在解码的时候只需要用到code，所以只需要记录每个元素的编码就可以了。

解码：利用文件中保存的Huffman编码，一一对应，解读编码，把可变长编码转换为定长编码。

D写入算法的优化——使用二级1024K缓冲器在写入编码的过程中，宏观的过程是：以字节形式读取原文件，然后找到该字节的编码，进而以字节形式写到压缩文件中去。

不停的字节读写会给cpu带来频繁的中断并且硬盘的磁头来回在磁道扇区中移动，减慢了速度。

而如果以数据块的形式读写则可以有效地利用到DMA通讯，减少了cpu中断，并使硬盘磁头连续移动，显著加快了速度。

而c++语言的iofstream类的read（）与write（）成员函数为此思想的实现提供了可能。

所以，可以开辟一个1024K的缓冲区，先将文件前1024K的字节读入内存缓冲区中，编码后的字节也不急于写入文件中，而是先写到另一个二级缓冲区中，当其足够1024K时再以数据块的形式写到压缩文件中。

然后清空缓冲区，继续做下一个1024K的编码写入。

而缓冲区本身，其实就是二个整形数组，read_buffer[1048576]和write_buffer[1048576]。

不过这样的数组声明已经太大了，可以用STL的vector向量类来代替这个数组（vector结构实际也就是一个封装了的加强型数组）。

2．解压缩算法部分A.基于字符匹配的解压算法读出结点数就能知道哈夫曼树存入部分的总长，方便读出树哈夫曼树（子结点值和权值），就能由次些信息重新构造完整的哈夫曼树，和各结点的哈夫曼编码。

解压时，读取一个字节（8 bit）用一个函数转换为8个字符（用一个数组记录，其元素只是一个0或一个1），然后按哈夫曼树从顶向下查找，如果到达叶子结点，就读出该叶子结点的值，放入缓冲区中，如果不是，则继续找，如此重复，直到缓冲区满了，就写入到解压文件中，再循环以上过程，直到处理完所有数据。

B.缓冲输入输出和压缩时采用1M二级缓冲相同，如果的压缩时也采用此技术，也会有很大的速度优化，当然程序也变得更加复杂。

四调试分析五用户使用说明1.运行huffman.exe程序，出现下面的界面2.选择相应的功能，输入正确文件路径，对文件进行压缩、解压缩六测试结果各种类型文件的压缩率测试以上测试环境：CPU:AMD 4400+ 2.31GHz,内存：DDRⅡ 2048M,硬盘：160GB （7200rpm）,系统：windows XP.七设计心得体会通过这次课题实验的程序实践，我实在获益匪浅！数据结构是上个学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。

同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。

这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。

因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。

虽然如此，但是通过自己的努力与老师的指导，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。

这一个多月的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。

非常感谢在背后一直给我指导的老师和同学，他们的支持和鼓励让我在遇到挫折时能够站起来战胜它，也让我走到了今天这一步，完成了实验的设计。

今后，我会更加努力的学习专业知识，提高自我的能力。

八附录程序清单在此，给出huffman.exe的程序清单。

#include<fstream>#include<iostream>#include<String>#include<cmath>using namespace std;struct HTNode{char data; //节点数据int weight; //权值int parent; //父亲int lchild; //左孩子int rchild; //右孩子};typedef char* Code;HTNode *ht;Code *hcd;int maplist[256]; //建立字符与哈夫曼编码的映射int nodenum=0; //哈夫曼树结点数int rearnum=0; //哈夫曼编码尾补码int textlen=0; //需压缩的文件长度int codelen=0; //压缩后的文件的哈夫曼编码总长度int const bufferlen=1024; //设置读取缓冲区长度int clean(); //清空节点及编码指针内容void dtobin(int num,int bin[8]); //十进制变换成二进制void HTCreate(HTNode ht[],int n); //建立哈夫曼树void HCCreat(HTNode ht[],Code hcd[],int n); //提取哈夫曼编码void WriteFile(char *tmp); //写入文件unsigned char ConvertBinary(char *tmp); //变换二进制文件void ConvertFile(Code hcd[],string fileadd,string fileadd2); //压缩并解压文件bool InitFromFile(string fileadd); //初始化文件void DecompressionFile(string fileadd2,string fileadd3); //解压文件string Compression(string fileadd); //压缩文件string Decompression(string fileadd2); //解压文件子函数///////////////十进制转二进制函数/////////////////int clean(){delete[] ht;delete[] hcd;return 1;}void dtobin(int num,int bin[8]){int i=0;for(i=0;i<8;i++){bin[i]=0;}i=0;while(num>0){bin[8-1-i]=num%2;num=num/2;i++;}}//////////////////压缩和写入文件//////////////////void ConvertFile(Code hcd[],string fileadd,string fileadd2){////////////////////////////////////////fstream infile(fileadd.c_str(),ios::in|ios::binary);fstream outfile(fileadd2.c_str(),ios::out|ios::binary);if(!infile) cout<<"open file fail!"<<endl;if(!outfile) cout<<"creat file fail!"<<endl;//unsignedchar ch;/////////////写入哈夫曼树//////////////ch=nodenum;outfile.write(&ch,1); ///写入结点数ch=8;outfile.write(&ch,1); ///写入补位数(预写入)codelen=0;outfile.write((char *)&codelen,4); //写入压缩后的文件的哈夫曼编码总长度(预写入) int h=0;for(h=0;h<nodenum;h++){outfile.write((char*)&ht[h].data,sizeof(char));outfile.write((char*)&ht[h].weight,sizeof(int));}///////////////////////////char tmp[8]; //设置缓冲区char outbuffer[bufferlen]; //设置写入缓冲区char *tmpcd;int i=0,j,k,last=0;char inbuffer[bufferlen];int readlen=0;//infile.seekg(i,ios::beg);h=0;do{infile.read(inbuffer,bufferlen);readlen=infile.gcount();tmpcd=hcd[maplist[(unsigned char)inbuffer[i]]];for(i=0;i<readlen;){for(j=last;j<8 && *tmpcd!='\0';j++){tmp[j]=*tmpcd;tmpcd++;}if(j==8 && *tmpcd=='\0'){last=0;i++;ch=ConvertBinary(tmp);//cout<<':'<<(unsigned int)ch<<' ';outbuffer[h]=ch;h++;codelen++; //压缩文件长度加一if(h==bufferlen){outfile.write(outbuffer,bufferlen);h=0;}if(i<readlen) tmpcd=hcd[maplist[(unsigned char)inbuffer[i]]];else{i=0;break;}}else if(j<8 && *tmpcd=='\0'){last=j;i++;if(i<readlen) tmpcd=hcd[maplist[(unsigned char)inbuffer[i]]];else{ i=0;break;}/////继续循换////}else if(j==8 && *tmpcd!='\0'){last=0;//WriteFile(tmp);ch=ConvertBinary(tmp);outbuffer[h]=ch;h++;codelen++; //压缩文件长度加一if(h==bufferlen){outfile.write(outbuffer,bufferlen);h=0;}}}}while(readlen==bufferlen);if(j==8 && readlen<bufferlen){outfile.write(outbuffer,h);}else if(j<8 && readlen<bufferlen){for(k=j;k<8;k++){tmp[k]='0';}ch=ConvertBinary(tmp);outbuffer[h]=ch;h++;outfile.write(outbuffer,h);codelen++; //压缩文件长度加一}cout<<endl;ch=8-j;rearnum=8-j;outfile.seekp(1,ios::beg);outfile.write(&ch,1); //写入真正的补位数outfile.seekp(2,ios::beg);outfile.write((char*)&codelen,4); //写入真正的压缩后的文件的哈夫曼编码总长度长度outfile.close();infile.close();}//////////////构造哈夫曼树////////////void HTCreate(HTNode ht[],int n){int i,k,lnode,rnode;int min1,min2;for(i=0;i<2*n-1;i++){ht[i].parent=ht[i].rchild=ht[i].lchild=-1;}for(i=n;i<2*n-1;i++){min1=min2=2147483647;lnode=rnode=-1;for(k=0;k<=i-1;k++){if(ht[k].parent==-1){if(ht[k].weight<min1){min2=min1;min1=ht[k].weight;rnode=lnode;lnode=k;}else if(ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}}///////////构造哈夫曼编码/////////////void HCCreat(HTNode ht[],Code hcd[],int n){int i,p,c;Code hc;hc=new char[n];int start,tmplen;for(i=0;i<n;i++){tmplen=0;start=n-1;hc[start]='\0';c=i;p=ht[i].parent;while(p!=-1){if(ht[p].lchild==c) //是左孩子结点{hc[--start]='0';tmplen++;}else{hc[--start]='1';tmplen++;}c=p;p=ht[p].parent;}hcd[i]=new char[n-start];strcpy(hcd[i],&hc[start]);}delete[] hc;}void WriteFile(char *tmp){int i;for(i=0;i<8;i++)cout<<tmp[i];cout<<' ';tmp="";}unsigned char ConvertBinary(char *tmp){char ch=0;int i;for(i=0;i<8;i++){ch=(unsigned char)pow(2.0,8-i-1)*(tmp[i]-48)+ch;}return ch;}//////////////打开文件//////////////bool InitFromFile(string fileadd){fstream infile(fileadd.c_str(),ios::binary|ios::in);if(!infile){cout<<"error!"<<endl;return 0;}int table[256];int i,j;int len=0,num=0;unsigned char ch;for(i=0;i<256;i++) {table[i]=0;maplist[i]=-1;}int readlen=0;char buffer[bufferlen]; //设置读取缓冲区,加快读取速度do{infile.read(buffer,bufferlen);i=0;readlen=infile.gcount();while(i<readlen){ch=(unsigned char)buffer[i];table[ch]++;len++;i++;}}while(readlen==bufferlen);for(i=0;i<256;i++){if(table[i]!=0) num++;}ht=new HTNode[2*num-1];hcd=new Code[num];for(i=0,j=0;i<256;i++){if(table[i]!=0){ht[j].data=i;ht[j].weight=table[i];maplist[i]=j; //建立字符与哈夫曼编码的映射j++;}}nodenum=num;textlen=len;infile.clear();infile.close();return 1;}/////////////从文件解压////////////////////void DecompressionFile(string fileadd2,string fileadd3){//cout<<"............解压并输出新文件过程:"<<endl;fstream infile(fileadd2.c_str(),ios::in|ios::binary);fstream outfile(fileadd3.c_str(),ios::out|ios::binary);cout<<endl;/////////////////读出哈夫曼树的数据/////////////int h=0;char buffer[bufferlen]; //读入文件的缓冲区char outbuffer[bufferlen]; //写入文件的缓冲区infile.read(buffer,1);nodenum=(unsigned char)*buffer;//哈夫曼树结点数if(nodenum==0) nodenum=256;infile.read(buffer,1);rearnum=(unsigned char)*buffer;infile.read((char*)&codelen,4);//cout<<" 读出哈夫曼树数据...."<<endl;ht=new HTNode[2*nodenum-1];hcd=new Code[nodenum];//hcdlen=new int[nodenum];for(h=0;h<nodenum;h++){infile.read(&ht[h].data,1);infile.read((char*)&ht[h].weight,4);}//////构走哈夫曼树///////HTCreate(ht,nodenum);//////构造哈夫曼编码/////HCCreat(ht,hcd,nodenum);//////////////////////////////////////////////////////////////////////解压并输出解压文件////////////////////////char *buffertmp=new char;int bin[8],j=0,i=0;int coderead=0; //记录以度的长度,用于判断何时达到文件最后一字节(用codelen比较) int readlen=0;int child=0;int last=2*nodenum-2; //解压时记录上次指示器的位置child=last;unsigned char outp;h=0;do{infile.read(buffer,bufferlen);readlen=infile.gcount();for(j=0;j<readlen;j++){coderead++;outp=buffer[j];dtobin(outp,bin);if(coderead==codelen) //达到文件尾{for(i=0;i<=8-rearnum;i++){if(ht[child].lchild==-1 && ht[child].rchild==-1){//cout<<ht[child].data;outbuffer[h]=ht[child].data;h++;if(h==bufferlen) {outfile.write(outbuffer,bufferlen);h=0;} last=2*nodenum-2;if(i==8-rearnum){if(h!=0) outfile.write(outbuffer,h);child=last;break;}else i--;}else if(i!=8){ if(bin[i]==0) last=ht[child].lchild;else if(bin[i]==1) last=ht[child].rchild;}child=last;}}else //没达到文件尾{for(i=0;i<=8;i++){if(ht[child].lchild==-1 && ht[child].rchild==-1){//cout<<ht[child].data;outbuffer[h]=ht[child].data;h++;if(h==bufferlen){outfile.write(outbuffer,bufferlen);h=0;}last=2*nodenum-2;if(i==8){child=last;break;}else i--;}else if(i!=8){ if(bin[i]==0) last=ht[child].lchild;else if(bin[i]==1) last=ht[child].rchild;}child=last;}}}}while(readlen==bufferlen);//cout<<j<<endl;infile.close();outfile.close();}string Compression(string fileadd){int i;for(i=0;i<fileadd.length();i++)if(fileadd[i]=='\\') fileadd[i]='/';string fileadd2;fileadd2=fileadd+".rax";InitFromFile(fileadd); //从文件中初始化哈夫曼树HTCreate(ht,nodenum); //构造哈夫曼树HCCreat(ht,hcd,nodenum); //构造哈夫曼编码ConvertFile(hcd,fileadd,fileadd2); //压缩并写入文件clean();return fileadd2;}string Decompression(string fileadd2){int i;for(i=0;i<fileadd2.length();i++)if(fileadd2[i]=='\\') fileadd2[i]='/';string fileclass;string fileadd3;for(i=fileadd2.length()-5;fileadd2[i]!='.' && i>0;i--)fileclass.insert(0,fileadd2.substr(i,1));if(i!=0)fileadd3=fileadd2.substr(0,i)+"_"+'.'+fileclass;elsefileadd3=fileadd2.substr(0,fileadd2.length()-4)+"_";DecompressionFile(fileadd2,fileadd3);clean();return fileadd3;}int main(){cout<<"缓冲区长度:"<<bufferlen<<"Bytes."<<endl<<endl;cout<<"\t*******************************************************\n";cout<<"\t* *\n";cout<<"\t* 数据结构课程设计*\n";cout<<"\t* 基于哈夫曼的文件压缩解压程序*\n";cout<<"\t* *\n";cout<<"\t*******************************************************\n";string fileadd;string fileadd2;char usage;do{cout<<""<<endl;cout<<"(1)压缩C"<<endl;cout<<"(2)解压D"<<endl;cout<<"(3)退出Q "<<endl;cout<<""<<endl;cout<<"*请输入选项:";cin>>usage;if(usage=='C' || usage=='c'){cout<<"请输入压缩文件的路径:";cin>>fileadd;cout<<"压缩文件开始...";fileadd2=Compression(fileadd);cout<<"压缩文件完毕,压缩后文件的路径是:"<<fileadd2<<endl<<endl;}else if(usage=='D' || usage=='d'){cout<<"请输入解压文件的路径:";cin>>fileadd;cout<<"解压文件开始...";fileadd2=Decompression(fileadd);cout<<"解压文件完毕,解压后文件的路径是:"<<fileadd2<<endl<<endl;}else if(usage=='Q' || usage=='q') return 0;}while(1);return 0;}。

合集下载

哈夫曼实验报告实验目的(3篇)

哈夫曼实验报告实验目的(3篇)

5. 使用哈夫曼编码对实验数据进行压缩。
6. 对压缩数据进行解压缩，验证哈夫曼编码的正确性。
7. 分析实验结果，对比压缩前后数据的差异。
五、实验总结
通过本次实验，我们掌握了哈夫曼编码的原理和构造方法，学会了如何使用哈夫曼编码进行数据压缩和解压缩。实验结果表明，哈夫曼编码能够有效降低数据的冗余，提高数据压缩效果。同时，本次实验也加深了我们对数据结构中树形结构及其应用的理解，提高了算法设计和实现能力。在今后的学习和工作中，我们将继续探索哈夫曼编码及其应用，为相关领域的研究和发展贡献自己的力量。
二、实验内容
1. 理解哈夫曼编码的原理，掌握哈夫曼树的构造方法。
2. 编写程序实现哈夫曼树的构建、编码和解码过程。
3. 对给定的字符集进行哈夫曼编码，并分析编码后的结果。
4. 对编码后的数据进行解码，验证解码结果的正确性。
5. 比较哈夫曼编码与其他编码方法在数据压缩方面的性能。
三、实验原理
哈夫曼编码是一种基于字符频率的变长编码方法。在哈夫曼编码中，每个字符都被赋予一个唯一的编码，编码的长度与其在原始数据中的频率成反比。频率高的字符编码较短，频率低的字符编码较长。这样，哈夫曼编码在保证数据完整性的同时，实现了数据压缩的目的。
2. 能够编写程序实现哈夫曼编码和解码，提高编程能力。
3. 分析哈夫曼编码在不同场景下的压缩效果，为实际应用提供参考。
4. 了解哈夫曼编码在实际应用中的优势和局限性，为解决实际问题提供思路。
5. 培养实验操作能力，提高解决实际问题的能力。
通过本次实验，我们希望学员能够全面掌握哈夫曼编码的原理、构造方法及其在实际应用中的价值，为今后的学习和工作打下坚实的基础。
第2篇
一、实验目的
1. 理解哈夫曼编码的原理及其在数据压缩中的应用。
数据结构 哈夫曼编码器课程设计报告

数据结构 哈夫曼编码器课程设计报告

数据结构哈夫曼编码器课程设计报告数据结构哈夫曼编码器课程设计报告1.引言1.1 编写目的本文档旨在详细介绍数据结构课程设计中的哈夫曼编码器的设计过程和实现方法。

1.2 背景哈夫曼编码是一种常用的数据压缩技术，通过构建变长编码表，将频率较高的字符用较短的编码表示，从而减小数据的存储和传输开销。

1.3 参考资料[1] 斯科特·梅耶, 数据结构与算法分析[C], 机械工业出版社, 2014.[2] Thomas H.Cormen, Charles E.Leiserson, RonaldL.Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press, 2009.2.需求分析2.1 功能需求①输入文件用户可以输入需要进行哈夫曼编码的文件路径。

②编码操作系统根据输入的文件，相应的哈夫曼编码，并显示编码结果。

③解码操作用户可以输入已经编码过的文件，系统将根据编码表进行解码，并显示解码结果。

2.2 非功能需求①性能要求系统在处理大规模文件时需要具备较高的性能，保证编码和解码的效率。

②用户友好性系统需要提供简洁明了的界面，方便用户操作。

③可扩展性系统需要具备良好的扩展性，满足未来需求变化的需要。

3.概要设计3.1 总体设计系统采用面向对象的设计方法，主要包含以下几个类：① HuffmanEncoder该类负责对输入文件进行哈夫曼编码的操作。

② HuffmanDecoder该类负责对已编码文件进行解码的操作。

③ HuffmanTree该类是哈夫曼树的实现，用于构建编码和解码所需的编码表。

3.2 类的详细设计① HuffmanEncoder3.①属性●inputFile: 输入文件路径●codeTable: 编码表3.②方法●setInput: string): 设置输入文件路径●generateCodeTable(): 编码表●encodeFile(): 对输入文件进行编码② HuffmanDecoder3.①属性●encodedFile: 已编码文件路径●codeTable: 编码表3.②方法●setEncoded: string): 设置已编码文件路径●setCodeTable(table: object): 设置编码表●decodeFile(): 对已编码文件进行解码③ HuffmanTree3.①属性●root: 哈夫曼树的根节点3.②方法●buildTree(frequencies: object): 根据字符频率构建哈夫曼树●buildCodeTable(): 构建字符与编码的对应关系表4.详细设计4.1 HuffmanEncoder类①属性●inputFile: string，输入文件路径●codeTable: object，编码表②方法4.① setInput: string)●作用：设置输入文件路径●输入：，string类型，输入文件路径●输出：无4.② generateCodeTable()●作用：编码表●输入：无●输出：无4.③ encodeFile()●作用：对输入文件进行编码●输入：无●输出：无5.实现6.测试与验证7.项目总结8.附件8.1 源代码文件8.2 测试文件9.法律名词及注释9.1 哈夫曼编码哈夫曼编码是一种变长编码方法，通过构建树形结构，将频率较高的字符用较短的编码表示。

哈夫曼编码设计报告

哈夫曼编码设计报告

哈夫曼编码综合设计报告LD摘要 (I)Abstract (II)第一章课题背景 (1)1.1 课题背景 (1)1.2 课题内容 (1)第二章设计简介及设计方案论述 (2)2.1 设计简介 (2)2.2 问题分析 (2)2.3 设计方案 (3)第三章详细设计 (4)3.1 主要流程图 (4)3.2 主要类及函数介绍 (7)第四章设计结果及分析 (8)4.1 设计结果 (8)总结 (11)致谢 (12)参考文献 (13)附录主要程序代码 (14)数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。

因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。

通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

建立在数据结构的基础上，利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。

综合设计的任务是：设计一个哈夫曼编码/译码系统，使学生掌握哈夫曼编码的特点、存储方法和基本原理，培养学生利用C++语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。

程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。

本次课设主要是学习程序设计的方法，进行程序设计的基本训练，巩固基础知识，通过思考，和大量的阅读，来构造一个完整的程序。

关键词：数据结构；哈夫曼编码/译码；程序设计AbstractData structure as a major research subject of various logical structure of data and storage structure, and various operations on the data.Therefore, there are three main aspects: the logical structure of data; the data of the physical storage structure; operations on data (or algorithm).Typically, the algorithm design depends on the logical data structure, algorithm implementation depends on the data of the physical storage structure.A data structure of information organization, its purpose is to improve the efficiency of the algorithm, it is usually set with a set of algorithms corresponding to this set of algorithms through the collection of data structures can be some kind of data operation.Established on the basis of the data structure, the use of Huffman coding can greatly improve the communication channel utilization, reduce transmission time information, reducing transmission costs.Integrated design of the task: design a Huffman encoding / decoding system that allows students to master the characteristics of Huffman coding, storage methods and basic principles, students write programs using C language and ability to debug programs using the data structure of knowledgethe ability to solve practical problems for the computer professional courses of study follow-up and lay a solid foundation.Program design is to exercise our practical ability, to a certain extent, but also increase our knowledge of all aspects, especially in some of the curriculum with practice, it needs to complete a large number of accumulated knowledge of their usual and need to be diligentability to think and passion.The main lesson is to learn programming based methods, the basic training program designed to consolidate basic knowledge, through thinking, and a lot of reading, to construct a complete program.Keywords：Data structure; Huffman encoding / decoding; Programming第一章课题背景1.1课题背景《数据结构》在计算机科学中是一门核心专业基础课，在整个计算机课程体系中处于承上启下的核心地位，它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法，一方面为进一步学习其它专业课奠定坚实的理论与实践基础。

哈夫曼编译码课程设计报告

哈夫曼编译码课程设计报告

见附录
四、参考文献
1.数据结构（C 语言版） 147 页——赫夫曼树和赫夫曼树编码的存 储表示，及求赫夫曼编码的算法 2.C 语言设计（第三版） 371 页—377 页 附录 E C 库函数——用 于程序的开始 3.网络——赫夫曼译码
五、附录
程序清单 :
Honor Code ： #include <stdio.h> #include <stdlib.h> #include <string.h> //--------哈夫曼树和哈夫曼编码的储存表示-------typedef struct { int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组储存哈夫曼树 typedef char ** HuffmanCode; //动态分配数组储存哈夫曼编码表
7
//-------------在 HT[1..n]中选择 parent 为 0 的且 weight 最小的两个节点 s1 和 s2--------void Select(HuffmanTree HT,int n,int & s1,int &s2){ for(int i=1;i<=n;i++) //任取两个 parent 为 0 的 节点赋值给 s1 和 s2 if(!HT[i].parent){ s1=i; break; } for(i++;i<=n;i++) if(!HT[i].parent){ s2=i; break; } if(HT[s1].weight-HT[s2].weight){ int temp; temp=s1; s1=s2; s2=temp; } for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点 if(!HT[i].parent){ if(HT[i].weight<HT[s1].weight){ s2=s1; s1=i;} else if(HT[i].weight<HT[s2].weight&&i!=s1) s2=i; } } //---------w 存放 n 个字符的权值(均>0)，构造哈夫曼树 HT，并求出 n 个字 符的哈夫曼编码 HC---------void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ if(n<=1) return; int s1,s2,i,num=2*n-1; HuffmanTree p; HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode)); //0 号单元未用 for(p=HT+1,i=1;i<=n;i++,p++,w++) {//对静态链表初赋值 p->weight=*w; p->lchild=NULL; p->parent=NULL; p->rchild=NULL; } for(;i<=num;p++,i++){ p->weight=0; p->lchild=NULL; p->parent=NULL; p->rchild=NULL; } for(i=n+1;i<=num;i++){ // 建立哈夫曼树 Select(HT,i-1,s1,s2); //选择两个权值最小的节点 HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1;