数据结构课程设计报告

1、 . . . word. ? ?数据构造数据构造? ?课程设计报告课程设计报告设计题目：设计题目：哈夫曼编哈夫曼编/ /译码器译码器20212021 年年 1212 月月 3030 日日 摘要摘要哈夫曼编码是根据字符的使用率的上下对字符进展不等长的编码，从而使使用率高的字符占用较少的空间，从而在传输的过程大提高了数据的空间传输效率。本设计采用二叉链表的存储构造，建立哈夫曼树；用递归调用的方式对哈夫曼树的节点进展编码，生成与字符对应的哈夫曼编码。本设计完全采用C+语言进展编程，并在*Code 6 编译器上调试运行通过。本程序使用中文界面，并有相应的提示信息，便于操作和程序运行。关键词：哈夫曼树;

2、哈夫曼编码;递归调用;二叉链表AbstractAbstractHuffman coding is based on the level of usage of characters ranging from 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 t

3、he Huffman tree by using Binary Tree storage structure, encoded Huffman tree nodes by recursive calling, and the characters generate the corresponding Huffman coding. The procedure pletely write with C+ language and has Chinese e*planatory note. Whats more, it was debugged in *Code 6 debugger and ru

4、n well. The whole procedure, with Chinese interface and the corresponding tips ,is convenient to run and easy to be operated.Keywords: Huffman Tree; Huffman code; Recursive call; Binary List 目录摘要摘要 1 1-. zABSTRACTABSTRACT2 2一、问题描述一、问题描述容格式参考下面的描述，以下类似容格式参考下面的描述，以下类似4 41、问题描述：42、根本要求：4二、需求分析二、需求分析 4

5、42.1 设计目标 42.2 设计思想 4三、概要设计三、概要设计 5 53.1 程序构造 53.2 初始化算法：53.3 编码算法：53.4 译码算法：5四、数据构造设计四、数据构造设计 5 5五、算法设计五、算法设计 6 61、算法分析必须要用语言进展描述62、算法实现 7六、程序测试与实现六、程序测试与实现 12121、主程序 122、测试数据 133、测试结果 14生成哈夫曼树运行结果图：14哈夫曼编码运行结果图：15编码函数运行结果图：15译码函数运行结果图：15平均编码长度函数运行结果图：15七、调试分析七、调试分析 1515程序调试的步骤：15调试体会：16八、遇到的问题及解决方

6、法八、遇到的问题及解决方法 1616九、心得体会九、心得体会 1616一、问题描述一、问题描述容格式参考下面的描述，以下类似容格式参考下面的描述，以下类似1 1、问题描述：、问题描述：利用哈夫曼编码进展信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进展译码复原 。试写一个哈夫曼编/译码系统。-. z2 2、根本要求：、根本要求：一个完整的系统应具有以下功能：1初始化。从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件中。2编码。利用已建好的哈夫曼树对文件中的正文进展

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

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

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

10、度，z 则使用了 3 倍多。倘假设我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。-. z三、概要设计三、概要设计3.13.1 程序构造程序构造Main()Initialization()初始化程序EnCode();编码DeCode();译码Code_length()平均编码长度Print()打印数据3.23.2 初始化算法：初始化算法：程序从文件 data.in 中获取 26 个英文字母以及对应的权值。3.33.3 编码算法：编码算法：1对输入的一段欲编码的字符串进展统计各个字符出现的次数，并它们转化为权值w1,w2,，wN构成 n 棵二叉树的集合 F=T

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

12、类型，结点类型，指针类型struct element /哈夫曼树结点 char data; /数据域 int weight; /权值 int lchild, rchild, parent; /左孩子右孩子，父结点 int flag;struct Code /编码 int bitMa*Size; /编码 int start; /开场位置 int weight; /权值;struct Encode /编码 string code; /编码-. z char data; /编码对应的值 int flag;int wMa*Size; /存放权值的数组int n; /n 个字符int root; /根结

13、点Code HuffCodeMa*Code; /哈夫曼编码数组Encode encodeMa*Size; /编码数组element huffmanTreeMa*Size; /哈夫曼树结点2.包含的函数 Huffman(); Huffman() void HuffmanTree(); /建立哈夫曼树 void Initialization(); /初始化程序 void PrintHuffman(element H, element HH, int n); /打印哈夫曼树 void HuffmanCode(); /生成哈夫曼编码 void PrintCode(); /打印哈夫曼编码 void Fi

14、leCode(); /文件输出哈夫曼编码 void FileHuffman(element H, element HH, int n); /文件输出哈夫曼树 int getRoot() return root; /获取根结点 void Code_length(); /计算平均编码长度 void EnCode(); /为文件编码 void ReadCode(); /读取字符以及对应的哈夫曼编码 void Decode(); /为编码文件译码五、算法设计五、算法设计1 1、算法分析、算法分析必须要用语言进展描述必须要用语言进展描述哈夫曼树给定 n 个权值作为 n 的叶子结点，构造一棵二叉树，假设带

15、权路径长度到达最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。哈夫曼树的构造一、对给定的 n 个权值W1,W2,W3,.,Wi,.,Wn构成 n 棵二叉树的初始集合 F= T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树 Ti 中只有一个权值为 Wi 的根结点，它的左右子树均为空。 为方便在计算机上实现算 法，一般还要求以 Ti 的权值 Wi 的升序排列。 二、在 F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从 F 中删除这两棵树

16、，并把这棵新的二叉树同样以升序排列参加到集合 F 中。四、重复二和三两步，直到集合 F 中只有一棵二叉树为止。哈夫曼编码哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最正确编码，一般就叫做 Huffman 编码有时也称为霍-. z夫曼编码 。哈夫曼编码步骤：哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。哈夫曼编码平均编码长度：哈夫曼编码平均编码长度=每个字符的权值和该字符对应的哈夫曼编码的长度的乘积的和/权值

17、的总和。2 2、算法实现、算法实现1哈夫曼树的建立：void Huffman:HuffmanTree() /建立哈夫曼树 int i1, i2, m1, m2; for (int i = 0; i 2 * n - 1; i+) /初始化哈夫曼树 if (i n)huffmanTreei.weight = wi; else huffmanTreei.weight = 0; huffmanTreei.data = /; huffmanTreei.parent = -1; huffmanTreei.lchild = -1; huffmanTreei.rchild = -1; huffmanTreei

18、.flag = 0; for (int i = 0; i n - 1; i+) m1 = m2 = Ma*Value; i1 = i2 = 0; for (int j = 0; j n + i; j+) if (huffmanTreej.weight m1 & huffmanTreej.flag = 0)/查找最小权值 m1 和标号为*1；m2 和*2 为此最小 m2 = m1; i2 = i1; m1 = huffmanTreej.weight; i1 = j; else if (huffmanTreej.weight m2 & huffmanTreej.flag = 0)

19、m2 = huffmanTreej.weight; i2 = j; -. z huffmanTreei1.flag = 1; huffmanTreei2.flag = 1; huffmanTreen + i.weight = huffmanTreei1.weight + huffmanTreei2.weight; huffmanTreei1.parent = n + i; huffmanTreei2.parent = n + i; huffmanTreen + i.lchild = i1; huffmanTreen + i.rchild = i2; 2.哈夫曼编码void Huffman:Hu

20、ffmanCode() /哈夫曼编码函数 Code cdMa*Code; int i, j, child, parent; for (i = 0; i start = n - 1; cd-weight = huffmanTreei.weight; child = i; parent = huffmanTreechild.parent; while (parent != -1) /从叶子出发到根逆序得出哈夫曼编码 if (huffmanTreeparent.lchild = child) cd-bitcd-start = 0; else cd-bitcd-start = 1; cd-start-

21、; child = parent; parent = huffmanTreechild.parent; for (j = cd-start + 1; j bitj; HuffCodei.start = cd-start + 1; HuffCodei.weight = cd-weight; root = child;3.编码函数void Huffman:EnCode() /编码函数 string en100; int pos = 0, j;-. z int flag = 0; char OriginalMa*Char; memset(Original,0,Ma*Char); ifstream i

22、file; /从文件中读取出原文 ifile.open(Original.in); while(!ifile.eof() ifile Originalpos; pos+; ifile.close(); cout 原文如下: Original endl; /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

23、ofile; ofile.open(CodeOriginal.out); /将编译以后的编码写入文件中 cout经过编译后的字符串:; for(int j = 0; j pos; j+) ofile enj; cout enj; cout encop; 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+;

24、coutendl;5.求平均编码长度void Huffman:Code_length() double res; double sumWeight = 0 ,Codelength = 0; double num = 0; for(int i = 0; i n; i+) sumWeight = sumWeight + wi; for(int i = 0; i n; i+) num = 0; for(int j = HuffCodei.start; j n; j+) num+; -. z Codelength = Codelength + num * wi; res = Codelength/su

25、mWeight; cout res endl;3、算法流程图六、程序测试与实现六、程序测试与实现1 1、主程序、主程序void menu() cout*endl;cout* 哈夫曼编译码器 *endl;cout* 1.初始化程序*endl;cout* 2.编码 *endl;cout* 3.译码 *endl;cout* 4.计算编码平均长度*endl;cout* 5.退出*endl; cout*endl;int main() menu(); Huffman H;-. z int choose; for(;) coutchoose; switch(choose) case 1: H.Initial

26、ization(); H.HuffmanTree(); H.HuffmanCode(); cout各字符编码如下:endl; H.PrintCode(); H.FileCode(); cout哈夫曼树如下:endl; H.PrintHuffman(H.huffmanTree, H.huffmanTreeH.getRoot(), 0); H.FileHuffman(H.huffmanTree, H.huffmanTreeH.getRoot(), 0); cout文件已保存为 Tree.out!endl; break; case 2: H.ReadCode(); H.EnCode(); break

27、; case 3: H.Decode(); break; case 4: cout平均编码长度为:; H.Code_length(); break; default: break; if(choose = 5) break;-. z 2 2、测试数据、测试数据ch=AWeight=64ch=BWeight=13ch=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=R