成绩
数据结构设计性实验
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));
相关推荐：
loading