Huffman编码与译码-数据结构设计性实验

成绩

数据结构设计性实验

Huffman编码与译码

2007120302

学 号 13 姓 名 班 级

范 高 华 信息 072

设计性实验—Huffman编码与译码

一．实验目的：

在掌握相关基础知识的基础上，学会自己设计实验算法，熟练掌握Huffman树的建立方法，Huffman编码的方法，进而设计出Huffman译码算法，并编程实现。

二、实验要求：

在6学时以内，制作出能够实现基于26个英文字母的任意字符串的编译码。写出技术工作报告并附源程序。

三．实验内容及任务：

1．设字符集为26个英文字母，其出现频度如下表所示。 字符 空格 频度 字符 频度 字符 t 频度

a 64 k 5 u 23

b 13 l 32 v 8

c 22 m 20 w 18

d 32 n 57 x 1

e 103 o 63 y 16

f 21 p 15 z 1

1

g 15 q

h 47 r 48

i 57 s 51

186 j 1

80

2．建Huffman树； 3．利用所建Huffman树对任一字符串文件进行编码——即设计一个Huffman编码器；

4．对任一字符串文件的编码进行译码——即设计一个Huffman译码器。 实现步骤：

1．数据存储结构设计； 2．操作模块设计； 3．建树算法设计； 4．编码器设计；

5． 译码器设计；

分析及设计步骤

1. 分析问题

1) 首先学习二叉树的知识，了解二叉树的路径、权数以及带权路径长度计算。 2) 认识霍夫曼树，了解霍夫曼树的定义，构造霍夫曼树构造算法

① 又给定的n个权值{w1，w2，w3，……，wn}构造根节点的二

叉树，从而得到一个二叉树森林F={T1，T2，T3，……Tn}。

② 在二叉树森里选取根节点全职最小和此最小的两棵二叉树作为左右

节点构造新的二叉树，此时新的二叉树的根节点权值为左右子树权值之和。

③ 在二叉树森林中删除作为新二叉树的根节点左右子树的两棵二叉树，

将新的二叉树加入到二叉树森林F中。

④ 重复?和?，当二叉树森林F只剩下一棵二叉树时，这棵二叉树是所

构造的霍夫曼树。

3) 练习通过普通树来构造霍夫曼树。 4) 根据以上分析过程设计相应的算法。

5) 了解霍夫曼树与霍夫曼编码的关系，准备设计相应的算法。 2. 算法设计

1． 数据结构

霍夫曼树的节点结构 typedef struct { int weight; int flag; int parent; int leftChild; int rightChild; } HaffNode; 霍夫曼编码的结构 typedef struct { unsigned int bit[MaxN]; int start; int weight; } Code;

2.设计构造霍夫曼树的算法：

void Haffman(int weight[],int n,HaffNode haffTree[])

{

int i,j,m1,m2,x1,x2; for(i=0;i<2*n-1;i++) {if(i

haffTree[i].weight=weight[i]; else

haffTree[i].weight=0; haffTree[i].parent=-1; haffTree[i].flag=0; haffTree[i].leftChild=-1; haffTree[i].rightChild=-1;} for(i=0;i

for(j=0;j

{if(haffTree[j].weight

m1=haffTree[j].weight; x1=j; }

else if(haffTree[j].weight

haffTree[x1].parent=n+i; haffTree[x2].parent=n+i; haffTree[x1].flag=1; haffTree[x2].flag=1;

haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild=x1; haffTree[n+i].rightChild=x2; } }

3.设计编码的算法：void HaffCode(HaffNode haffTree[],int n,Code haffCode[]) {

Code *cd=(Code *)malloc(sizeof(Code));