《数据结构实验三——Huffman编码》由会员分享，可在线阅读，更多相关《数据结构实验三——Huffman编码（25页珍藏版）》请在金锄头文库上搜索。
1、四川大学计算机学院多媒体课程实验报告实验名称： Huffman 编码（二叉树应用）指导教师： 沈琳姓名：侯静学号： 0943041267班级： 09403014日期： 2010.12.10一、实验号题目:Huffman编码（二叉树应用）二、实验的目的和要求:1. 要求对文件进行Huffman编码的算法，以及对乙编码文件 进行解码的算法,为简单起见,可以假设文件是存放在一 个字符向量;2. 熟练掌握二叉树的应用;3. 熟练掌握计算机系统的基本操作方法，了解如何编辑、编 译、链接和运行一个C+程序及二叉树上的基本运算； 具体要求如下:最小冗余码/哈夫曼码 ASCII码/定长码ab12: 01100
2、001 01100010 00110001 0011001097 98 49 50 哈夫曼码/不定长码能按字符的使用频度，使文本代码的总长度具有最小 值。例. 给定有18个字符组成的文本：A A D A T A R A E F R T A A F T E R字符ADEFTR频度712233求各字符的哈夫曼码。(1) 统计：(2)构造 Huffman 树:622552排疗4 C?CQ台并吕和冷CD 合书岳耐】&(2)构造 Huffman 树:(3) 在左分枝标0,右分枝标1:(4)确定Huffman编码:字符ADEFTR频度712233编码010101011100110111特点：任一编码不是其
3、它编码的前缀例. 给定代码序列:0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 10 文本为：A A F A R A D E T4. 上机调试程序,掌握查错、排错使程序能正确运行。三、实验的环境:1. 硬件环境：intel core i5 460处理器,2G内存2. 软件环境：windows 7， Visual Studio 2010 Ultimate四、算法描述:1主函数流程图否结束 开始构建 huffma n树并 初始化； char c=0coutendl1.Huffman compress.;coutendl2.Huffman decompress. cout
4、endl3.Exit.;coutendlPlease select:; cinc;用函数Code ()对指定文件进行编码*用函数UnCode ()对指定文件进行解码2函数Code ()流程图开始)char infName256,outfName256coutPlease input source file name(size less than 4GB); cininfName;是.(infp=fopen(infNa k-me, rb)=NULL-coutCan not openfile:infNameendl;exit(l);否是feof(infp)!=0exit;coutEmpty sou
5、rcefile:infNameendl;结束X._XCoutPlease input code file name:;cinoi/exit(1); 叫 结束丿是tfName;coutCan not open file:outfNameendl;否coutPocessing.endl;unsigned char ch;unsigned int i,c;i=0;i二n;i+ HuffmanCodei二NULL;CreatFromSo用函数Stat()统计字符出现频度并过滤掉频度为零的字符urceFile()由被压缩文件建立huffman树，并将树结构存入编码文件的文件头部中3.函数UnCodeO流
6、程图五、源程序清单:Huffman.hconst unsigned int n=256;/字符数const unsigned int m=256*2-1;/结点总数struct HTNodeunsigned long weight;/压缩用 Huffman 树结点/字符频度（权值）/字节缓冲压缩用 Huffman 树 /字节/实际比特数class HuffmanTreepublic:void Code();void UnCode(); private:HTNode HTm+1;unsigned int parent,lchild,rchild; ;struct Bufferchar ch; u
7、nsigned int bits;/Huffman 树/编码/译码/树结点表（HT1到HTm）char Leafn+1;char *HuffmanCoden+1; *HuffmanCoden)unsigned int count;unsigned int char_indexn;到 char_indexn-1)unsigned long size;FILE *infp,*outfp;Buffer buf;void Stat();/叶结点对应字符(leafl到leafn)/ 叶 结 点 对 应 编 码 (*HuffmanCode1 到/频度大于零的字符数/字符对应在树结点表的下标 (char_i
8、ndex0/被压缩文件长度/输入/出文件/字符缓冲/统计字符出现频度并过滤掉频度为零的字符/在HTOHTk中选择parent为-1，树值最小的两个结点s1,s2void Select(unsigned int k, unsigned int &sl, unsigned int &s2);void Writ e(unsigned int bit);/向 outfp 中写入一个比特void Write(unsigned int num,unsigned int k);/向 outfp 中写入 k 个比特void WriteToOutfp();/强行写入 outfpvoid Read(unsigne
9、d int &bit);/从 infp 中读出一个比特void Read(unsigned int &num unsigned int k);/从 infp 中读出 k 个比特int NToBits(unsigned int num); /0num 之间的整数用二进位表示所需的最少 位数void CreateFromCodeFile();/由编码文件中存储的树结构建立Huffman树/由被压缩文件建立Huffman树，将树结构存入编码文件的文件头部中,并求每个字符 的 Huffman 编码void CreateFromSourceFile();void HuffmanTree:Code()/编
10、码char infName256,outfName256;coutinfName;if(infp=fopen(infName,rb)=NULL)coutCan not open file:infNameendl; exit(1);if(feof(infp)!=0) coutEmpty source file:infNameendl; exit(1);coutoutfName;if(outfp=fopen(outfName,wb)=NULL)coutCan not open file:outfNameendl; exit(1);coutPocessing.endl;unsigned char c
11、h;unsigned int i,c;for(i=0;i=n;i+)HuffmanCodei=NULL;CreateFromSourceFile();rewind(infp);ch=fgetc(infp);while(feof(infp)=0)c=char_indexch;for(i=0;istrlen(HuffmanCodec);i+) if(HuffmanCodeci=0)Write(0); else Write(1); ch=fgetc(infp);WriteToOutfp();fclose(infp);fclose(outfp);coutProcess end.endlendl;void HuffmanTree:UnCode()char infName256,outfName256;coutinfName; if(infp=fopen(infName,rb)=NULL) coutCan not open file:infNameendl; exit(1);if(feof(infp)!=0)coutEmpty code file:infNameendl; exit(1);coutoutfName;if(outfp=fopen(outfName,wb)=NULL)coutCan not open file:outfNameendl;exit(1);coutPocessing.
