数据结构实验三实验报告教程.docx
文本预览下载声明
三题目：哈夫曼编/译码器
班级： 姓名： 学号： 完成日期：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(m0)，对于任意j≠k(≤j,k≤m)有Dj∩Dk=NULL,且对任意的i(1≤i≤m)，唯一存在数据元素xi∈Di有root,xi∈H;
(3) 对应于D-{root}的划分，H-{root,xi,?,root,xm}有唯一的一个划分H1，H2,?,Hm(m0)，
对任意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++)
{
cinht[i].data;//输入数据
}
for(i=1;i=n;i++)
{
cinht[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].weights1)
{
s2=s1;
r=l;
s1=ht[k].weight;
l=k;
}
else if(ht[k].weights2)
{
s2=ht[k].weight;
r=k;
}
}
}
ht[l].parent=i;
ht[r].parent=i;
ht[i].weight=ht[l].weight+ht[r].weight;
ht[i].lchild=l;
ht[i].rchild=r;
}
6.创建构造哈夫曼编码的伪代码算法
void creatlist()
{
for(i=1;i=n;i++)//逐个字符求哈夫曼编码
{
d.start=n+1;//编码结束位置
显示全部