哈夫曼编译码器数据结构课程设计.doc

1、摘要哈夫曼编码是根据字符的使用率的高低对字符进行不等长的编码，从而使使用率高的字符占用较少的空间，从而在传输的过程中大大提高了数据的空间传输效率。本设计采用二叉链表的存储结构，建立哈夫曼树；用递归调用的方式对哈夫曼树的节点进行编码，生成与字符对应的哈夫曼编码。本设计完全采用C+语言进行编程，并在XCode 6编译器上调试运行通过。本程序使用中文界面，并有相应的提示信息，便于操作和程序运行。关键词：哈夫曼树;哈夫曼编码;递归调用;二叉链表AbstractHuffman coding is based on the level of usage of characters ranging from

2、 long coding, so that high usage rate of the characters occupy less storage space , in the course of transmission has greatly enhanced the efficiency of data transmission space. This design build the Huffman tree by using Binary Tree storage structure, encoded Huffman tree nodes by recursive calling

3、, and the characters generate the corresponding Huffman coding. The procedure completely write with C+ language and has Chinese explanatory note. Whats more, it was debugged in XCode 6 debugger and run well. The whole procedure, with Chinese interface and the corresponding tips ,is convenient to run

4、 and easy to be operated.Keywords: Huffman Tree; Huffman code; Recursive call; Binary List 目 录摘要1ABSTRACT2一、问题描述（内容格式参考下面的描述，以下类似）41、问题描述：42、基本要求：4二、需求分析42.1 设计目标42.2 设计思想4三、概要设计53.1程序结构53.2 初始化算法：53.3 编码算法：53.4 译码算法：5四、数据结构设计5五、算法设计61、算法分析（必须要用语言进行描述）62、算法实现7六、程序测试与实现121、主程序122、测试数据133、测试结果14生成哈夫曼树

5、运行结果图：14哈夫曼编码运行结果图：15编码函数运行结果图：15译码函数运行结果图：15平均编码长度函数运行结果图：15七、调试分析15程序调试的步骤：15调试体会：16八、遇到的问题及解决办法16九、心得体会16一、问题描述（内容格式参考下面的描述，以下类似）1、问题描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试写一个哈夫曼编/译码系统。2、基本要求：一个完整的系统应具有以下功能：（1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树

6、，并将它存于文件中。（2）编码。利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文件中。（3）译码。利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。（4）完成数据测试，要求编码字符不低于15个，编码文件的长度不低于50个字符。（5）计算平均编码长度。二、需求分析2.1 设计目标一个完整的系统应具有以下功能：1）初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件Tree.out中。输出哈夫曼树，及各字符对应的编码。2）输入（Input）。从终端读入需要编码的字符串s，将字符串s存入文件Orinigal.txt

7、中。3）编码（Encode）与译码（Decode）。编码（Encode）。利用已建好的哈夫曼树（如不在内存，则从文件Tree.out 中读入），对文件Orinigal.txt中的正文进行编码，然后将结果存入文件CodeOrinigal.txt中。译码（Decode）。利用已建好的哈夫曼树将文件CodeOrinigal.txt中的代码进行译码，结果存入文件TextFile中。输出编码文件（Print）。将编码显示在终端上。同时将此字符形式的编码写入文件Code.out中。4）打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符

8、形式的哈夫曼树写入文件Tree.out中。5）计算编码平均长度。计算编码平均长度，并显示在屏幕上。 2.2 设计思想哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位

9、。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。三、概要设计3.1程序结构Main()Initialization()初始化程序EnCode();编码DeCode();译码Code_length()平均编码长度Print()打印数据3.2 初始化算法：程序从文件data.in中获取26个英文字母以及对应的权值。3.3 编码算法：（1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值w1,w2,，wN构成n棵二叉树的集合F=T1,T2,，Tn把它们保存到结构体数组HTn中,

10、其中Ti是按它们的ASC码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。 （2）在HT1.i中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 （3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。 3.4 译码算法： 译码的过程是分解电文中字符串，从根出发，按字符0,或1确定找左孩子或右孩子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。四、数据结构设计1 元素类型，结点类型，指针类型struct element /哈夫曼树结点 cha

11、r data; /数据域 int weight; /权值 int lchild, rchild, parent; /左孩子右孩子，父结点 int flag;struct Code /编码 int bitMaxSize; /编码 int start; /开始位置 int weight; /权值;struct Encode /编码 string code; /编码 char data; /编码对应的值 int flag;int wMaxSize; /存放权值的数组int n; /n个字符int root; /根结点Code HuffCodeMaxCode; /哈夫曼编码数组Encode encod

12、eMaxSize; /编码数组element huffmanTreeMaxSize; /哈夫曼树结点2.包含的函数 Huffman(); Huffman() void HuffmanTree(); /建立哈夫曼树 void Initialization(); /初始化程序 void PrintHuffman(element H, element HH, int n); /打印哈夫曼树 void HuffmanCode(); /生成哈夫曼编码 void PrintCode(); /打印哈夫曼编码 void FileCode(); /文件输出哈夫曼编码 void FileHuffman(eleme

13、nt H, element HH, int n); /文件输出哈夫曼树 int getRoot() return root; /获取根结点 void Code_length(); /计算平均编码长度 void EnCode(); /为文件编码 void ReadCode(); /读取字符以及对应的哈夫曼编码 void Decode(); /为编码文件译码五、算法设计 1、算法分析（必须要用语言进行描述）哈夫曼树给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结

14、点离根较近。哈夫曼树的构造一、对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F= T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti的权值Wi的升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。哈夫曼编码哈夫曼编码(Huffman Coding)是一种编码方式，

15、哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。哈夫曼编码步骤：哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。哈夫曼编码平均编码长度：哈夫曼编码平均编码长度=每个字符的权值和该字符对应的哈夫曼编码的长度的乘积的和/权值的总和。 2、算法实现1哈夫曼树的建立：void Huffman:HuffmanTree() /建立哈夫曼树 int i1, i2, m1, m2; for (int i = 0; i 2 * n

16、 - 1; i+) /初始化哈夫曼树 if (i n)huffmanTreei.weight = wi; else huffmanTreei.weight = 0; huffmanTreei.data = /; huffmanTreei.parent = -1; huffmanTreei.lchild = -1; huffmanTreei.rchild = -1; huffmanTreei.flag = 0; for (int i = 0; i n - 1; i+) m1 = m2 = MaxValue; i1 = i2 = 0; for (int j = 0; j n + i; j+) if

17、 (huffmanTreej.weight m1 & huffmanTreej.flag = 0)/查找最小权值m1和标号为x1；m2和x2为此最小 m2 = m1; i2 = i1; m1 = huffmanTreej.weight; i1 = j; else if (huffmanTreej.weight m2 & huffmanTreej.flag = 0) m2 = huffmanTreej.weight; i2 = j; huffmanTreei1.flag = 1; huffmanTreei2.flag = 1; huffmanTreen + i.weight = huffmanT

18、reei1.weight + huffmanTreei2.weight; huffmanTreei1.parent = n + i; huffmanTreei2.parent = n + i; huffmanTreen + i.lchild = i1; huffmanTreen + i.rchild = i2; 2.哈夫曼编码void Huffman:HuffmanCode() /哈夫曼编码函数 Code cdMaxCode; int i, j, child, parent; for (i = 0; i start = n - 1; cd-weight = huffmanTreei.weigh

19、t; child = i; parent = huffmanTreechild.parent; while (parent != -1) /从叶子出发到根逆序得出哈夫曼编码 if (huffmanTreeparent.lchild = child) cd-bitcd-start = 0; else cd-bitcd-start = 1; cd-start-; child = parent; parent = huffmanTreechild.parent; for (j = cd-start + 1; j bitj; HuffCodei.start = cd-start + 1; HuffCo

20、dei.weight = cd-weight; root = child;3.编码函数void Huffman:EnCode() /编码函数 string en100; int pos = 0, j; int flag = 0; char OriginalMaxChar; memset(Original,0,MaxChar); ifstream ifile; /从文件中读取出原文 ifile.open(Original.in); while(!ifile.eof() ifile Originalpos; pos+; ifile.close(); cout 原文如下: Original endl

21、; /s = new stringpos; for(int i = 0; i n; i+) /遍历得出文件中字符对应的哈夫曼编码 for(j = 0; j pos; j+) if(Originalj = encodei.data) enj = encodei.code; flag+; if (flag = pos) break; ofstream ofile; ofile.open(CodeOriginal.out); /将编译以后的编码写入文件中 cout经过编译后的字符串:; for(int j = 0; j pos; j+) ofile enj; cout enj; cout encop

22、; p+; cout译文如下:; for(int i = pos; i p; i+) tmpf = encoi; t=tmp; for(int j = 0; j n; j+) if(t = encodej.code) coutencodej.data; pos = i+1; memset(tmp, 0, 50); f=-1; break; f+; coutendl;5.求平均编码长度void Huffman:Code_length() double res; double sumWeight = 0 ,Codelength = 0; double num = 0; for(int i = 0;

23、 i n; i+) sumWeight = sumWeight + wi; for(int i = 0; i n; i+) num = 0; for(int j = HuffCodei.start; j n; j+) num+; Codelength = Codelength + num * wi; res = Codelength/sumWeight; cout res endl;3、算法流程图六、程序测试与实现1、主程序void menu() cout*endl;cout* 哈夫曼编译码器 *endl;cout* 1.初始化程序 *endl;cout* 2.编码 *endl;cout* 3

24、.译码 *endl;cout* 4.计算编码平均长度 *endl;cout* 5.退出 *endl; cout*endl;int main() menu(); Huffman H; int choose; for(;) coutchoose; switch(choose) case 1: H.Initialization(); H.HuffmanTree(); H.HuffmanCode(); cout各字符编码如下:endl; H.PrintCode(); H.FileCode(); cout哈夫曼树如下:endl; H.PrintHuffman(H.huffmanTree, H.huffm

25、anTreeH.getRoot(), 0); H.FileHuffman(H.huffmanTree, H.huffmanTreeH.getRoot(), 0); cout文件已保存为Tree.out!endl; break; case 2: H.ReadCode(); H.EnCode(); break; case 3: H.Decode(); break; case 4: cout平均编码长度为:; H.Code_length(); break; default: break; if(choose = 5) break; 2、测试数据ch=AWeight=64ch=BWeight=13ch

26、=CWeight=22ch=DWeight=32ch=EWeight=143ch=FWeight=21ch=GWeight=15ch=HWeight=41ch=IWeight=57ch=JWeight=12ch=KWeight=5 ch=LWeight=1ch=MWeight=20ch=NWeight=57ch=OWeight=66ch=PWeight=15ch=QWeight=1ch=RWeight=48ch=SWeight=51ch=TWeight=80ch=UWeight=23ch=VWeight=8ch=WWeight=18ch=XWeight=120ch=YWeight=16ch=Z

27、Weight=13、测试结果生成哈夫曼树运行结果图：哈夫曼编码运行结果图：编码函数运行结果图：译码函数运行结果图：平均编码长度函数运行结果图：七、调试分析程序调试的步骤：1)对各个模块函数进行单元调试,并测试模块间参数的传递与调用。2)调试主函数和对其他模块函数的调用，并检验最后的输出结果。调试体会： 1)对Huffman编码有了一个很好的认识，通过对Huffman编码的实现，对Huffman编码有了具体的认识和实践，对二叉树又有了一个更新的认识。对文件有了一定的认识，可以进行简单的文件流操作。 2)算法的时间复杂度分析：程序部分用双循环嵌套结构，所以时间复杂度为O（n2）. 3)算法的空间复

28、杂度分析：算法的空间复杂度为O（n）。八、遇到的问题及解决办法程序运用了C+语言以及数据结构的核心思想，由于程序本身比较复杂，在调试实现的过程中花了大量的时间，在解决如何编码的时候，我遇到了很大的问题，经过多次测试后仍然不能实现，因此我参考了别人的结构，构建了一个新的结构体用来传输权值，才解决了这个问题。函数的核心代码是参考教材的思路。九、心得体会这次课程设计不仅让我熟悉了哈夫曼编码以及哈夫曼树，同时也是对自身耐心的磨练，因为在书上只有伪代码，而课程设计的代码却要自己一步一步的写出来。刚开始遇到了许多的困难，在查阅了大量资料以后，将困难一一克服。在此次设计中收获颇多。对于设计过程的每一个步骤、每一个算法、每一次调试都对自己是一次考验。在试验中学习，在设计中找乐趣，在算法中求精炼，在调试中找不足。每一次出错都是一次考验，每一次正确的答案又都是一次动力，每一次成功又都是一次鼓励。