×

霍夫曼编码例题及答案

霍夫曼编码例题及答案（题目：哈夫曼编码，译码系统）

admin admin 发表于2023-09-16 11:38:20 浏览39 评论0

抢沙发发表评论

本文目录

题目：哈夫曼编码，译码系统

/* 哈夫曼编码*/#include “graphics.h“#include “stdlib.h“#include “Stdio.h“#include “Conio.h“#define MAX 53char bmfile;char a;typedef struct{char c,s;}MM;MM mm;typedef struct /*以数组存储哈夫曼树时的结点类型*/{char ch; int w,lcd,rcd,pt; /*权值、左孩子、右孩子、双亲*/}HuffNode;HuffNode Hm.rcd;i++;} } } void Huffmanjm(int n,HuffNode Hm) /*哈夫曼解码。n为哈夫曼树的叶子数*/{ int m=n; char *a,ch; printf(“\n1-对文件解码；2-对字符解码;3-退出;\n“); while(1) switch(ch=getch()) {case ’1’:wjjm(m,a);return 0; case ’2’:zfjm(m,a);return; case ’3’:return 0; } }void HuffmanTree() /*生成哈夫曼树*/{ int i,j,x,y,n; char c; n=charTJ(); for(i=0;i《n-1;i++) { x=0; while((Hm+x)-》pt》=0)x++; /*搜索第一个未处理的结点*/ y=x+1; while((Hm+y)-》pt》=0)y++; /*搜索第二个未处理的结点*/ j=y; if((Hm+x)-》w》(Hm+y)-》w){j=y;y=x;x=j;} for(j=j+1;j《n+i;j++) /*搜索两个未处理且权值最小的结点*/ { if((Hm+j)-》pt《0&&(Hm+j)-》w《(Hm+x)-》w) {y=x;x=j;} else if((Hm+j)-》pt《0&&(Hm+j)-》w《(Hm+y)-》w) y=j; } (Hm+x)-》pt=n+i;(Hm+y)-》pt=n+i;(Hm+n+i)-》w=(Hm+x)-》w+(Hm+y)-》w; (Hm+n+i)-》lcd=x;(Hm+n+i)-》rcd=y;(Hm+n+i)-》pt=-1; } puts(“\n1-显示字符的编码;2-编码;3-解码;4-退出;“); while(1) switch(c=getch()) {case ’1’:Huffmanshu(n);break; case ’2’:Huffmanbm(n,Hm);break; case ’3’:Huffmanjm(n,Hm);break; case ’4’:return; }}int main(){ char c; gotoxy(29,1); puts(“文件编码解码系统“); window(1,3,80,25); HuffmanTree(); getch(); clrscr();}

关于哈夫曼编码试题的计算

太复杂了，楼主一会记得多给我点分！谢谢啦！ 先设权w=(31,22,18,14,10,4,1),n=7,则m=13,按照哈夫曼算法可以构造一棵哈夫曼树如下： 100 40 60 22 18 31 29 14 15 10 5 4 1 末端结点为22，18，31，14，10，4，1，你自己把上面的加上线连成一棵二叉树就行，记得左分支标0，右分支标1（为了得出后面的哈夫曼编码HC） 然后需要列出HT初态表和HT终态表，如下： HT初态表 HT终态表 weight parent lchild rchild weight parent lchild rchild 1 31 0 0 0 31 12 0 0 2 22 0 0 0 22 11 0 0 3 18 0 0 0 18 11 0 0 4 14 0 0 0 14 10 0 0 5 10 0 0 0 10 9 0 0 6 4 0 0 0 4 8 0 0 7 1 0 0 0 1 8 0 0 8 - 0 0 0 5 9 6 7 9 - 0 0 0 15 10 5 8 10 - 0 0 0 29 12 4 9 11 - 0 0 0 40 13 2 3 12 - 0 0 0 60 13 1 10 13 - 0 0 0 100 0 11 12 最后得出哈夫曼编码HC： 1——》10 2——》00 3——》01 4——》110 5——》1110 6——》11110 7——》11111 平均码字长度为（0.31＋0.22＋0.18）×2＋0.14×3＋0.1×4 ＋（0.04＋0.01）×5＝2.47 编码效率为/2.47=1.21 解答完毕！ 补充：对于其中的编码效率问题本人有点淡忘，我选择的是用 普通平均编码长度除上了哈夫曼平均编码长度得出，不知对否。 辛苦半天，望楼主能赐我分数，不胜感激！注：提交后发现格式不太规整，对于哈夫曼树谁是谁的左孩子、右孩子比较容易分出（左右孩子结点相加可知父亲结点），对于HT初态表和HT终态表1列1列的看就行！其中数字第一列为序号，从第2列到第9列分别对应HT初态表的weight parent lchild rchild 和HT终态表的weight parent lchild rchild 。

题目：哈夫曼编码系统 设计任务：

#include《string.h》#include《stdlib.h》#include《string》#include《limits》#include《iostream》#include《fstream》using namespace std;struct HuffmanNode //哈夫曼树的一个结点{ int weight; int parent; int lchild,rchild; char sourcecode; //存放源文字符集里的一个字符，如’a’ std::string code; //存放字符sourcecode对应的编码};class HuffmanTree //哈夫曼树{private: HuffmanNode *Node; //Node存放哈夫曼树 int LeafNum; //哈夫曼树的叶子个数，也是源码个数public: HuffmanTree(); ~HuffmanTree(); void CreateHuffmanTree(); void CreateHuffmanTreeFromKeyboard(); void CreateHuffmanTreeFromFile(); void Encoder(); void Decoder(); void PrintCodeFile(); void PrintHuffmanTree(); void PrintHuffmanTree_aoru(int T,int layer=1); };//////////////////////////////////////////////////////////////////////////////// 构造函数// 函数功能：初始化哈夫曼树//函数参数：无//参数返回值：无HuffmanTree::HuffmanTree(){ Node=NULL; LeafNum=0; }//////////////////////////////////////////////////////////////////////////////// 析构函数// 函数功能：将哈夫曼的数组的空间释放//函数参数：无//参数返回值：无HuffmanTree::~HuffmanTree(){ delete Node; }//////////////////////////////////////////////////////////////////////////////// 建立哈夫曼树函数// 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）//函数参数：无//参数返回值：无void HuffmanTree::CreateHuffmanTree() { char Choose; cout《《“你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？“; cin》》Choose; if(Choose==’2’) { //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard(); }//choose==’2’ else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 CreateHuffmanTreeFromFile(); }}//////////////////////////////////////////////////////////////////////////////// 从键盘建立哈夫曼树函数// 函数功能：从键盘建立哈夫曼树//函数参数：无//参数返回值：无void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num; cout《《“\n请输入源码字符集个数：“; cin》》Num; if (Num《=1) { cout《《“无法建立少于2个叶子结点的哈夫曼树。\n\n“; return; } LeafNum=Num; Node=new HuffmanNode.rchild,layer+1); }}int main(){ HuffmanTree huftree; char Choose; while(1){ cout《《“\n**********************欢迎使用哈夫曼编码/译码系统**********************\n“; cout《《“* 您可以进行以下操作: *\n“; cout《《“* 1.建立哈夫曼树 *\n“; cout《《“* 2.编码(源文已在文件ToBeTran中，或键盘输入) *\n“; cout《《“* 3.译码(码文已在文件CodeFile中) *\n“; cout《《“* 4.显示码文 *\n“; cout《《“* 5.显示哈夫曼树 *\n“; cout《《“* 6.退出 *\n“; cout《《“***********************************************************************\n“; cout《《“请选择一个操作:“; cin》》Choose; switch(Choose) { case ’1’: huftree.CreateHuffmanTree(); break; case ’2’: huftree.Encoder(); break; case ’3’: huftree.Decoder(); break; case ’4’: huftree.PrintCodeFile(); break; case ’5’: huftree.PrintHuffmanTree(); break; case ’6’: cout《《“\n**********************感谢使用本系统!*******************\n\n“; system(“pause“); return 0; }//switch }//while}//main

霍夫曼编码

首先说明，这道题目的答案不是唯一的。我做的只是其中的一种。从左到右的编码依次为：00 011 010 101 111 10010 100111 110 1000 100110平均长度为=2*0.19+3*（0.12+0.10+0.13+0.17+0.15）+4*0.08+5*0.03+6*（0.01+0.02） =3.04第二题有压力啊！还是另请高明吧。

数据结构试题：根据以下字符在文件中出现的次数构造哈夫曼树，写出这些字符的哈夫曼编码 A(23),

74 / \ 32 42 / \ / \ 17 15 19 23 / \ 9 8 / \2 7霍夫曼编码：A: 11B:0000C:0001D:001E:01F:10

霍夫曼编码求平均码长 急！！！

霍夫曼编码的例题不要太多.两个最小的概率相加, 然后再按照大小排列. 同等概率的符号可以随便分0还是1, 并不影响平均码长.自己画一棵二叉树一样的就知道了.

在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对（ 4 ）个字

因为前缀编码，而且长度不超过3，假设左边为0，右边为1，则该huffman树最深如下： x / \ x x / \ x x / \ x x / \ / \ x x x x剩下的编码为1100 1101 1110 1111

有8个待编码的符号A,B,C,D,E,F,G，H,使用霍夫曼编码算法

1、将A到H按其概率的大小，从上到下依次排列写出。2、每次都将两个最小的概率合并成一个概率，然后重新按概率从大到小排列。例如：第一次需要将H(0.01)和G(0.03)合并，合并后概率为0.04，这时从大到小排列0.04最小，且有两个0.04,一个为F的概率，一个为H和G合并后的概率。此时，再将两个0.04合并，重复以上步骤。3、重复步骤2，直至概率合并为1。4、将被合并的两个消息分支分别赋予0和1。5、从概率为1的一头向其自身概率一头读数。具体答案：A 1B 011C 010D 001E 0001F 00001G 000001H 000000

请各位大虾提供以下具体的霍夫曼编码方法，要有具体说明和例题~~~

属于数字压缩编码技术： 霍夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。下面引证一个定理，该定 理保证了按字符出现概率分配码长，可使平均码长最短。� 定理：在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平 均码字长度为最小。� 现在通过一个实例来说明上述定理的实现过程。设将信源符号按出现的概率大小顺序排列为 ： � U： ( a1 a2 a3 a4 a5 a6 a7 ) 0.20 0.19 0.18 0.17 0.15 0.10 0.01 � 给概率最小的两个符号a6与a7分别指定为“1”与“0”，然后将它们的概率相加再与原来的 a1~a5组合并重新排序成新的原为：U′： ( a1 a2 a3 a4 a5 a6′ ) 0.20 0.19 0.18 0.17 0.15 0.11 � 对a5与a′6分别指定“1”与“0”后，再作概率相加并重新按概率排序得U〃：（0.26 0.20 0.19 0.18 0.17）…� 直到最后得 U〃〃：（0.61 0.39）� 分别给以“0”，“1”为止，如图4－4所示。}� 霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。 � 例如a7从左至右，由U至U〃〃，其码字为0000；� a6按践线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为0001…� 用霍夫曼编码所得的平均比特率为：∑码长×出现概率� 上例为：� 0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit� 可以算出本例的信源熵为2.61bit，二者已经是很接近了。