哈夫曼编码译码器设计与实现

唐 山 学 院

数据结构 课 程 设 计

题 目 哈夫曼编码译码器设计与实现 系 (部) 计算机科学与技术系 班 级 12计本2班 姓 名 xxxx 学 号 xxxxx 指导教师 xxx

2013 年 12 月 30 日至 1 月 10 日 共 2 周

2014

年 1 月 10 日

数据结构 课程设计任务书

一、设计题目、内容及要求 1、设计题目：哈夫曼编码译码器设计与实现。 2、设计内容及要求： （1）根据输入的权值建立哈夫曼树。 （2）利用建好的哈夫曼树生成哈夫曼编码，并显示生成的各字符的哈夫曼编码。 （3）根据输入的字符进行译码。 二、要求的设计成果（课程设计说明书、设计实物、图纸等） 1、用C语言进行程序设计，实现程序的功能。注重算法效率，代码要有适当的注释； 2、撰写课程设计说明书一份，不少于2000字。课程设计说明书应包括封面、任务书、成绩评定表、正文（设计思路、设计步骤等）、参考文献（资料）、附录（程序代码）等内容。 三、进程安排 12月30日：进行需求分析，确定系统的主要功能和算法思路； 12月31日～1月2日：进行详细设计，确定各模块的算法思路； 1月3日～1月6日：进行编码实现； 1月7日～1月9日：进行测试调试，完善设计；撰写设计说明书，准备答辩； 1月10日：答辩。 四、主要参考资料 1.严蔚敏，吴伟民.数据结构.清华大学出版社，2007. 2.苏仕华.数据结构课程设计.机械工业出版社，2010. 3.滕国文.数据结构课程设计.清华大学出版社，2010. 指导教师（签名）： 教研室主任（签名）：

课程设计成绩评定表

出勤 情况 成 绩 评 定 提问 （答辩） 问题 情况 出勤天数 缺勤天数 出勤情况及设计过程表现（20分） 课设答辩（20分） 设计成果（60分） 总成绩（100分） 综 合 评 定 指导教师签名： 年 月 日 唐山学院课程设计

1引言

哈夫曼是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率，加快信息传输速度，降低传输成本。数据压缩的过程称为编码，解压的过程称为译码。进行信息传递时，发送端通过一个编码系统对待传数据（明文）预先编码，而接受端将传来的数据（密文）进行译码。要求数据这样一个简单的哈夫曼编码译码器。其主要功能有：(1) 可根据输入的权值及字符建立哈夫曼树。(2) 利用建好的哈夫曼树生成哈夫曼编码，并显示生成的各字符的哈夫曼编码。(3) 输入密文进行译码。 本次设计使用的编程语言是C语言。采用了数据结构里的链式存贮结构和顺序存储结构。以及以孩子父亲三叉链表存储哈夫曼树。

2问题分析

要完成哈夫曼编码译码器需要完成下面几个部分： (1) 本题目主要设计到数组的操作和线性表。

(2) 在建立哈夫曼树时要以数组的形式来存储哈夫曼树，因为要逆向求哈夫曼树，所以用

数组的存储方式，操作起来更加的方便快捷。设有parent，lchlid，rchild。

(3) 在哈夫曼编码译码时，由于输入的字符大小不定，所以采用了链表的存储方式，实现

动态存储分配。

3总体设计

设计哈夫曼编码译码器的总体思路：

(1) 首先建立哈夫曼树，将哈夫曼树初始化，输入权值及字符建立哈夫曼树。 (2) 输出哈夫曼的被编码的字符及对应的编码。 (3) 输入要译码的哈夫曼编码字符串进行译码。

1