数据结构实验三实验报告

三题目:哈夫曼编/译码器

班级: 姓名: 学号: 完成日期:15.11.14

一、题目要求

描述: 写一个哈夫曼码的编/译码系统,要求能对要传输的报文进行编码和解码。构造哈夫曼树时,权值小的放左子树,权值大的放右子树,编码时右子树编码为1,左子树编码为0.

输入: 输入表示字符集大小为n(n <= 100)的正整数,以及n个字符和n个权值(正整数,值越大表示该字符出现的概率越大); 输入串长小于或等于100的目标报文。

输出: 经过编码后的二进制码,占一行;

以及对应解码后的报文,占一行; 最后输出一个回车符。

输入样例: 5 a b c d e 12 40 15 8 25

bbbaddeccbbb

输出样例:

00011111110111010110110000 bbbaddeccbbb 提示: 利用编码前缀性质。

二、概要设计

1.设计需要的数据结构:树型结构

2.需要的抽象数据类型: ADT Tree{

数据对象D:D是具有相同特性的数据元素的集合。 数据关系R:若D为空集,则称为空树;

若D仅含有一个数据元素,则R为空集,否则R={H},H是如下二元关系: (1) 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2) 若D-{root}≠NULL,则存在D-{root}的一个划分D1,D2,D3,?,Dm(m>0),对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m),唯一存在数据元素xi?Di有?H; (3) 对应于D-{root}的划分,H-{,?,}有唯一的一个划分H1,H2,?,Hm(m>0), 对任意j≠k(1≤j,k≤m)有Hj∩Hk=NULL,且对任意i(1≤i≤m),Hi是Di上的二元关系,(Di,{Hi}) 是一棵符合本定义的树,称为根root的子树。

基本操作:

InitTree(&T);

操作结果:构造空树T。

DestroyTree(&T); 初始条件:树T存在。

操作结果:销毁树T。 CreateTree(&T,definition);

初始条件:definition给出树T的定义。 操作结果:按definition构造树T。

三、详细设计

算法设计

1.设计一个存储数据的数组结构体 typedef struct{

char cd[200];//最大的数据 int start; }HuffmanCode;

2.设计一个结构体数组:在表示哈夫曼树时,用如下的结构体保存哈夫曼树中个结构体的信息,根据二叉树的性质可知,具有N个节点的哈夫曼树共有2n-1个节点。 typedef struct{ int weight; char data; unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree;

3.设置全局变量 HTNode ht[2*200];

HuffmanCode hcd[200],d; int i, k, f, l, r, n, c, s1, s2; char a;

4.创建输入函数 void creatsz() { for(i=1;i<=n;i++) { cin>>ht[i].data;//输入数据 } for(i=1;i<=n;i++) { cin>>ht[i].weight;//输入数据的权重 } }

5.创建构造哈夫曼树的伪代码算法 void creattree() { for(i=n+1;i<=2*n-1;i++) { s1=s2=100000; l=r=0;

for(k=1;k<=i-1;k++)//建立哈夫曼树 { if(ht[k].parent==0) { if(ht[k].weight

6.创建构造哈夫曼编码的伪代码算法 void creatlist() { for(i=1;i<=n;i++)//逐个字符求哈夫曼编码 { d.start=n+1;//编码结束位置 c=i; f=ht[i].parent; while(f!=0)//从叶子到根逆向求编码 { if(ht[f].lchild==c)

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4