内容发布更新时间 : 2024/4/26 17:19:57星期一 下面是文章的全部内容请认真阅读。

数据结构课程设计报告

题 目： 哈夫曼编/译码器

院 （系）： 计算机工程学院 专 业： 信息与计算科学 班 级： 0902 学 生： 陈辉 指导教师：

2010年 12月

目 录

1实验目的 .................................................................................................................... 2 2概要设计 .................................................................................................................... 2

2.1 总体功能结构 ······················································································· 2 2.2 数据结构设计 ······················································································· 4 2.3 方法及原理 ·························································································· 5

3详细设计和实现 ........................................................................................................ 6

3.1 创建Huffman树 ···················································································· 6 3.2 编码 ··································································································· 9 3.3 译码 ·································································································· 11

4调试与操作说明 ...................................................................................................... 13 总 结 ................................................................................................................. 14

1

1实验目的

设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 【基本要求】

(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树； (2)编码：利用建好的哈夫曼树生成哈夫曼编码； (3)输出编码； (4)译码功能；

(5)设字符集及频度如下表：

字符 空格 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1

通过此次课程设计主要达到以下目的：

1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 本程序采用Visual C++编程实现。

2概要设计

2.1 总体功能结构

本程序的主要功能是实现对用户输入的字符编码，然后再把编码结果翻译

成原字符。但在进行这些操作之前必须做一项工作，就是创建Huffman树。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带

2

权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。 总体功能流程如下图：

3

2.2 数据结构设计

2.2.1 Huffman结点结构

Huffman结点结构是本程序的基本结构，所有操作都在此上进行。其中包

括存储字符的元素data，字符的权值weight，以及左右孩子指针和父指针。 typedef struct {

char data; int weight; int parent; int left;

//结点值 //权值 //父结点指针 //左孩子结点指针 //右孩子结点指针

int right; }huffnode;

2.2.2 编码结构

编码结构用于存储每个字符的编码，包括用于存储编码的数组和用于记录编码个数的元素。整个结构相当于一个栈结构，采用栈形式存储编码。

typedef struct {

int cd[M]; int top; }huffcode;

//编码串

//串的大小

4