专业基础实践报告
题 目 哈夫曼树及应用
起讫日期 2008年6月30日至 2008年7月11日
所在院系 软 件 学 院
学生姓名 专 业 计算机
班 级 学 号
指导教师 职称
所在单位 软 件 学 院
2008年 7 月 11 日
目录
一、 任务及要求··············································1 二、 总体设计················································3 三、 运行效果···············································16 四、 总结···················································22 五、 附录···················································23
参考文献
1. 唐策善 ? 《数据结构---用C语言描述》 ? 高等教育出版社 ?1995 ? p50~p120 2. 谭浩强 ? 《C程序设计》 ? 清华大学出版社 ? 2005 ? p330！p348
一、任务及要求
在本专业基础实践中，综合C语言程序设计、离散数学、数据结构等学过的专业基础课程中的基本概念、基础知识和基本理论，进行软件设计的思想、方法和过程的训练，提高综合素质和动手能力，达到加强专业基础知识理解程度和熟练程度的目的。具体任务及要求如下： 1、任务
（1）给定一个包含10个以上字符的字符串，长度不少于100个字符，统计各个字符的概率，存放在数组中。
（2）根据上面统计的结果建立哈夫曼树。 （3）实现哈夫曼编码。 （4）实现哈夫曼译码。
（5）自己选做1～2个附加的任务。 2、要求
（1）算法中处理的数据要存放在文件中，实现文件的读写操作。 （2）设计程序中的各个C函数、画出模块图。 （3）程序的代码要规范、有详细的注释。
（4）按照指导教师给出的模板进行专业基础实践报告书写。 二、工作量
在2周（10个工作日）时间里，完成15-20个C函数，150-200行代码。并提交专业实践报告一份，字数不少于5000字（包括英文字符）。 三、计划安排
第1个工作日－第2个工作日：查找相关资料、书籍；确定逻辑结构并进行运算的
定义；选择存储结构并进行算法设计。
第3个工作日－第7个工作日：完成程序的编码，并且自己调试、测试。穿插进行
实践报告的撰写。
第8个工作日－第9个工作日：整理并完成专业基础实践报告，提交指导教师。 第10个工作日：由教师检查软件测试效果、审阅实践报告，评定成绩。
指导教师签字：
2008年6月26日
一．总体设计
1．功能模块设计
本C语言程序共包括12个C函数，函数名及其功能如表1所示
表1 函数名及其功能 序号 函数名 主要功能 输入文件名，新建文件，并向文件输出 字符 打开一个已经存在的文件 统计字符文件里所有字符的总数 分别统计文件每个字符的总数 计算文件里每个字符出现的概率 备注 1文件名10个字符内 确保可读 26个字母 5个常用字符 存入No[] 存入gailv[] 存入1 2 3 4 5 6 7 8 9 CREATFILE OPENFILE READ EACHREAD PROBABLY HUFMANTREE 以概率为权建立哈夫曼树 HUFMANCODE OUTCODE CHCODE 根据哈夫曼数对每个字符进行初始化编码 输出每个字符的初始编码到屏幕 对每个编码赋上相应的字符，使字符与编码结合，方便后续应用 即时输入二进制编码，转化为可读的字符文本显示在屏幕 code[i].bits 字符与编码对应输出 字符存入 code[i].ch 翻译 10 DECODE 11 TANSFER 12 13 14 MAIN 即时输入，转换成二进制编码显示在屏幕 加密 主函数，进行功能调用，完成程序 完成程序 - 1 -
2．函数之间的调用关系
函数之间调用的功能模块图如图1所示。 Main() PROBABLY HUFMANCODE OUTPUTCODE READ EACHREAD HUFMANTREE CHCODE CREATFILE
OPENFILE TANSFER DECODE 二、详细设计
1．数据的逻辑结构
本程序主要讨论哈夫曼树的逻辑结构，而简化之即时讨论一般二叉树的逻辑结构。
假设有A ，B ，C， D， E， F， G ，H ,I节点，树形结构如下：
G 用二元组表述则为： 设B=(K,R),r∈R。 K={A,B,C,D,E,F,G,H,I}
r={(A,B),(A,C),(B,D),(D,G),(D,H),(E,E),(C,F),(F,I)}
- 2 -
A B C D E F H I
哈夫曼树及其应用
