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

摘要 哈夫曼编码是根据字符的使用率的高低对字符进行不等长的编码，从而使使用率高的字符占用较少的空间，从而在传输的过程中大大提高了数据的空间传输效率。本设计采用二叉链表的存储结构，建立哈夫曼树；用递归调用的方式对哈夫曼树的节点进行编码，生成与字符对应的哈夫曼编码。本设计完全采用C++语言进行编程，并在XCode 6编译器上调试运行通过。本程序使用中文界面，并有相应的提示信息，便于操作和程序运行。 关键词：哈夫曼树;哈夫曼编码;递归调用;二叉链表 Abstract Huffman 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 the 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 completely write with C++ language and has Chinese explanatory note. What’s 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 and easy to be operated. Keywords: Huffman Tree; Huffman code; Recursive call; Binary List 目 录 摘要 1 Abstract 2 一、问题描述（内容格式参考下面的描述，以下类似） 4 1、问题描述： 4 2、基本要求： 4 二、需求分析 4 2.1 设计目标 4 2.2 设计思想 4 三、概要设计 5 3.1程序结构 5 3.2 初始化算法： 5 3.3 编码算法： 5 3.4 译码算法： 5 四、数据结构设计 5 五、算法设计 6 1、算法分析（必须要用语言进行描述） 6 2、算法实现 7 六、程序测试与实现 12 1、主程序 12 2、测试数据 13 3、测试结果 14 生成哈夫曼树运行结果图： 14 哈夫曼编码运行结果图： 15 编码函数运行结果图： 15 译码函数运行结果图： 15 平均编码长度函数运行结果图： 15 七、调试分析 15 程序调试的步骤： 15 调试体会： 16 八、遇到的问题及解决办法 16 九、心得体会 16 一、问题描述（内容格式参考下面的描述，以下类似） 1、问题描述： 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试写一个哈夫曼编/译码系统。 2、基本要求： 一个完整的系统应具有以下功能： （1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 （2）编码。利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文件中。 （3）译码。利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 （4）完成数据测试，要求编码字符不低于15个，编码文件的长度不低于50个字符。 （5） 二、需求分析 2.1 设计目标 一个完整的系统应具有以下功能： 1）初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件Tree.out中。输出哈夫曼树，及各字符对应的编码。 2）输入（Input）。从终端读入需要编码的字符串s，将字符串s存入文件Orinigal.txt中。 3）编码（Encode）与译码（Decode）。 编码（Encode）。利用已建好的哈夫曼树（如不在内存，则从文件Tree.out 中读入），对文件Orinigal.txt中的正文进行编码，然后将结果存入文件CodeOrinig