哈夫曼树应用课程的设计报告.doc

数据结构 课程设计报告 设计题目：哈夫曼树应用 专 业 ： 软件工程 班 级 ： 软件 学 生 ： 学 号 ： 指导教师 ： 罗作民 / 张翔 起止时间 ：2011-07-04—2011-07-08 2011 年 春季 学期 目 录 一．具体任务 …..2 1功能……………………………………………………………………………...2 2分步实施………………………………………………………………………...2. 3要求……………………………………………………………………………...2 二．哈夫曼编码 2 1问题描述 2 2.基本要求 3 3实现提示 3 三．设计流程图 4 1建立哈夫曼树…………………………………………………………………...4 2编码……………………………………………………………………………...5 3译码……………………………………………………………………………...6 4主程序…………………………………………………………………………...7 四．设计概要 8 1问题哈夫曼的定义..............................................................................................8.. 2所实现的功能函数如下………………………………………………………..8 3功能模块………………………………………………………………………..8 五．源程序 9 六．调试分析 15 七．心得与体会 18 八．参考文献 18 一、任务 题目：哈夫曼树应用 1.功能： 1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行 编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。 3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。 2.分步实施： 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数； 完成最低要求：完成功能1； 进一步要求：完成功能2和3。有兴趣的同学可以自己扩充系统功能。 3.要求： 1）界面友好，函数功能要划分好 2）总体设计应画一流程图 3）程序要加必要的注释 要提供程序测试方案 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。 二、哈夫曼编码 1. 问题描述 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 基本要求 一个完整的系统应具有以下功能： (1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 (2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 实现提示 (1) 编码结果以文本方式存储在文件Codefile中。 (2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 (3) 在程序的一次执行过程中，第一次执行I， D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。 三、设计流程图 建立哈夫曼树： 编码： 译码： 主程序： 四、概要设计 1）问题哈夫曼