实验九 哈夫曼编码-译码器
实验十 哈夫曼编/译码器
一、 实验目的
(1)掌握哈夫曼树的构造和应用
(2)利用哈夫曼
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
及其编/译码技术实现对传输信息编码/译码系统 二、 实验内容
[问题描述](
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
性实验)
哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20,至90,，其压缩效率取决于被压缩文件的特征。
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时，降低传输成本。但是，这
要求
对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗
在发送端通过一个编码系统对待传送电文须预先编码，在接收须将传送来的数据进行译码。请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。并实现以下报文的编码和译码:“this program is my favorite”。 [测试数据]
某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示:
[实现提示]如何创建哈夫曼树及如何求得各结点对应的哈夫曼编码算法:参见ppt。
1、设计思想描述
(1) 问题
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
。
(2) 哈夫曼树中各结点的结构描述(提示:图示)。
(3) 哈夫曼树的存储结构描述(提示:分析采用顺序存储还是利用链式存储等)。
2、主要算法设计与实现
[要求]
1)、利用类
模板
个人简介word模板免费下载关于员工迟到处罚通告模板康奈尔office模板下载康奈尔 笔记本 模板 下载软件方案模板免费下载
来实现。
2)、类中各成员函数要求给出自行设计的算法步骤描述及主要设计思想。
3)、给出类中各成员函数算法设计实现。 4)、对自行设计的各算法进行评估(提示:时间复杂度、空间复杂度等)。
#include
#include
using namespace std;
const int MAX = 1000;
class HTree;
class HTNode
{
friend class HTree;
unsigned int weight;
unsigned int parent, lchild, rchild;
};
class HuCode
{
friend class HTree;
char *ch; //字符的编码
char data;//被编码的字符
};
//动态分配数组存储哈夫曼编码表。
class HTree
{
HTNode *HT;//动态数组
HuCode *HC;
int n;
public:
HTree(int w[], int n);
void Select(int k, int &s1, int &s2);
void QHuffmanCode(char ch[], int n);
//求出n个字符的赫夫曼编码HC
void printHuffmantree(int n);
void printHuffmanCode(int n);
char *MessageCoding(char *s1, int n);//对报文进行编码,n为字符集中字符的个数
char *MessageEnCoding(char *s1, int n);//对报文的编码进行译码，n为字符集中字符的个数
};
HTree::HTree(int w[], int n)
{
//w存放n个字符的权值(均>0),构造赫夫曼树HT
int i, m, s1, s2;
if (n <= 1)
{
cout << "error!";
exit(0);
}
m = 2 * n - 1;
//注:有n个字符,其构造成一颗Huffman树后,将有n+n-1个结点.
HT = new HTNode[m + 1];//0号单元未使用
for (i = 1; i <= n; ++i)
{
//初始化Huffman树的各叶子结点
HT[i].weight = w[i];
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
}
for (; i <= m; ++i)
{
//初始化其它树结点;
HT[i].weight = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
HT[i].parent = 0;
}
for (i = n + 1; i <= m; ++i)
{//建赫夫曼树,在HT[1..i-1]选择parent为0且weight最小的两个结点,其序号分别为s1和s2;
Select(i - 1, s1, s2);
HT[s1].parent = i;
HT[s2].parent = i;//孩子结点的修改
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
//双亲结点的修改
}
}
void HTree::Select(int k, int &s1, int &s2) {
//在HT[1..k]中选出没有双亲的结点,且其权值最小的两个结点的下标赋给s1,s2.
int w1, w2, i = 1;
w1 = w2 = MAX;
s1 = s2 = i;
for (i = 1; i <= k; i++)
{
if (!HT[i].parent)
{
if (HT[i].weightn) //不属于该字符集，则原样照抄
{
*c2 = *c; c2++;
}
else
{
len = strlen(HC[j].ch);
strcpy(c2, HC[j].ch);
c2 += len;//复制编码
}
}
*c2 = '\0';
return s2;
}
char *HTree::MessageEnCoding(char *s1, int n) { //对报文的编码进行译码，n为字符集中字符的个数
int m = 2 * n - 1, i, num = 0;
char *c = s1, *s2, *s3; //S2中保存译码结果
s2 = new char;
i = m;//从根往下搜索
while (*c != '\0')
{
num++;
s3 = new char[num + 1];
for (int nn = 0; nnn)
{//HT[1..n]均为叶子结点
if (!*c)
{
cout << "code error!";
exit(0);
}//编码有误
if ((*c != '0') && (*c != '1'))
{
cout << "code error!";
exit(0);
}
//还未到叶子结点途中遇到非0,1值，则认为非法
if (*c == '0')
i = HT[i].lchild;//判往左走还是往右走
else
i = HT[i].rchild;
c++;
}
s2[num - 1] = HC[i].data;
//译码结果插入s2串中。译码结果为:叶子结点所对应的字符
i = m;
}//endif
}//endwhile
s2[num] = '\0';
return s2;
}
void main()
{
int a[28] = { 0, 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 };
char ch[28] = { 0, ' ', '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' };
HTree ht(a, 27);
ht.printHuffmantree(27);
ht.QHuffmanCode(ch, 27);
ht.printHuffmanCode(27);
char *s1 = "this program is my favorite";
char *s2 = ht.MessageCoding(s1, 27);
cout << "this program is my favorite的编码结果为:" << endl;
cout << s2 << endl;
char *s3 = ht.MessageEnCoding(s2, 27);
cout << s2 << "的译码结果为:" << endl;
cout << s3 << endl;
}
三、实验心得(含上机中所遇问题的解决办法，所使用到的编程技巧、创新点及编程的心得)
浙公网安备 33021202002483