为一则电报设计哈夫曼编码

2024-03-22 00:41| 来源: 网络整理| 查看: 265

1.题目

哈夫曼树的应用要传输一则报文内容如下： “AAAAAAAAAAAAAAABBBBBBBBBCCCCCCCCDDDDDDDDDDDDEEEEEEEEEEFFFFF” 请为这段报文设计哈夫曼编码，要求如下：

请计算出每个字符出现的概率，并以概率为权重来构造哈夫曼树，写出构造过程、画出最终的哈夫曼树，得到每个字符的哈夫曼编码。请将上述设计哈夫曼编码的过程，用代码来实现，并输出各个字母的哈夫曼编码。（有代码，有运行结果的截图）请分析算法的效率，至少包括时间复杂度和空间复杂度等。 2.分析题目

这段文长59，其中6个字符的个数和概率：

字符 A B C D E F 个数 15 9 8 12 10 5 概率 0.254 0.153 0.136 0.203 0.169 0.085 3.构建二叉树

1)选择6个字母中概率最小的两个，C和F构成二叉树。然后就生成一个新结点，权值为0.221.

在这里插入图片描述 2）在剩下的字母和这个新结点中选择最小的两个结点，B,E生成新结点,权值为0.322。

在这里插入图片描述 3）接着选出剩下的结点中最少的两个，0.221和D（0.203），又组合生成二叉树，产生新的结点0.424.

在这里插入图片描述 4）再选择剩下的结点中最小两个，0.321和A（0.254）生成新的二叉树，新结点0.576.

5）最后将两个二叉树组合起来，就是哈夫曼树。在这里插入图片描述所以，编码为：

字符 A B C D E F 编码 10 110 011 00 111 010 4.代码 #include #include #define MAX 106 #define MAXLEAF 6 //定于哈夫曼树中叶子结点个数 #define MAXNODE MAXLEAF*2-1//n个叶子结点中又2n-1个结点 typedef struct { int weight; //结点权重 int parent,lchild,rchild;//双亲和左孩子、右孩子下标 }HTNode; typedef struct code { int bits[MAXLEAF]; int start; char ch; }HTCode; HTNode tree[MAXNODE];//数组二叉树 HTCode HFCode[MAXLEAF];//每个字母编码 void CreatHuffmanTree(int n,int weight[])//创建哈夫曼树数组 { if(n

【本文地址】

公司简介

联系我们