-
哈夫曼树和哈夫曼编码
2020-06-26 10:32:49哈夫曼编码方法,把各个字符作为结点,权值是字符出现的频率,构造出哈夫曼树,各个字符最终都出现在叶子节点上,然后从根节点到某字符的路径,向左为0,向右为1,得到哈夫曼编码 E为00 B为010 ...哈夫曼树构造方法,把一开始的各个点看作一颗颗树,取权值最小的两棵树组成一颗新二叉树,新树权值为两点之和,放入森林中取代原来的两个结点。一直重复直至只剩最后一颗树
哈夫曼编码方法,把各个字符作为结点,权值是字符出现的频率,构造出哈夫曼树,各个字符最终都出现在叶子节点上,然后从根节点到某字符的路径,向左为0,向右为1,得到哈夫曼编码
E为00
B为010 -
C++ 哈夫曼树和哈夫曼编码
2020-07-27 17:32:36C++ 哈夫曼树和哈夫曼编码 哈夫曼树又称最优二叉树是树的结构应用之一。 哈夫曼树的构建: ...从结点开始,左分支路径记0,右分支路径记1,从根结点到目标叶结点路径上的编号序列就是哈夫曼编码 ... -
哈夫曼树和哈夫曼编码译码
2020-06-10 15:48:011、编程思想 哈夫曼树 ...哈夫曼编码 对哈夫曼树中的前n个节点进行编码,从根节点开始,位于左子树的为0,右子树为1。编程就是通过符号找到其对应的是左子树还是有子树。 输入与权值对应的编码,找到code1、编程思想
哈夫曼树
哈夫曼树是最小的WPL值,也就是最小带权路径。编程就是将n个权值进行比较,用最小的两个组成一个新的节点。
用数组接收输入的n个节点的权值,将输入的编码进行整理,将最小的两个权值进行合并,多出n-1个新节点。用一个临时的数ct保存其左右子树以及父节点。通过临时的节点,将所有排序好的节点存放到tree[]数组中。哈夫曼编码
对哈夫曼树中的前n个节点进行编码,从根节点开始,位于左子树的为0,右子树为1。编程就是通过符号找到其对应的是左子树还是有子树。
输入与权值对应的编码,找到code[]与tree[]之间的映射,从tree[]开始向上遍历。将编码整合到code[].bits[]中。并且输出编码表。译码
译码就是通过输入的一串编码进行分割,在编码表中找到对应的匹配。
#include<stdio.h> #include<stdlib.h> #include<string.h> #define n 5 #define m 2*n-1 #define MIN 100 typedef struct { float weight; int lchild,rchild,parent; }hfmtree; hfmtree tree[m]; typedef struct { char bits[n]; int start; char ch; }codetype; codetype code[n]; void hfm(void) { //int n = 5; int i,j,p1,p2; float s1,s2,f; //m个节点初始化 for(i = 0;i<m;i++){ tree[i].parent = -1; tree[i].lchild = -1; tree[i].rchild = -1; tree[i].weight = 0; } //输入n个节点的权值 printf("请输入n个权值,空格隔开回车结束\n"); for(i = 0;i<n;i++){ scanf("%f",&f); getchar(); tree[i].weight = f; } //合并成m个节点 for(i = n;i<m;i++){ p1 = -1; //小的下标 p2 = -1; //第二小的下标 s1 = MIN; //小的权值 s2 = MIN+1; //第二小的权值 //找出前面的最小权值和第二小权值 for(j =0;j<i;j++){ if(tree[j].parent == -1){ if(tree[j].weight<=s1){ s2 = s1; s1 = tree[j].weight; p2 = p1; p1 = j; } else if(tree[j].weight<=s2){ s2 = tree[j].weight; p2 = j; } } } tree[p1].parent = i; tree[p2].parent = i; tree[i].lchild = p1; tree[i].rchild = p2; tree[i].weight = tree[p1].weight+tree[p2].weight; tree[i].parent = -1; } for(i=0;i<n;i++) printf("第%d个的权值是%f\n",i,tree[i].weight); } void hfm_code(void) { int i,j,p1,p2,k; char c; codetype ct; //输入对应的字符 printf("请输入对应的字符,空格隔开回车结束\n"); for(i=0;i<n;i++){ scanf("%c",&c); getchar(); code[i].ch = c; } //编码0或者1 for(i=0;i<n;i++){ ct.start = n; p1 = tree[i].parent; p2 = i; //从叶子开始编码 while(p1 != -1){ //n个节点最多有n-1个编码 ct.start--; if(tree[p1].lchild==p2) ct.bits[ct.start] = '0'; else if(tree[p1].rchild==p2) ct.bits[ct.start] = '1'; p2 = p1; p1 = tree[p2].parent; } //保存编码 k = 0; for(j=ct.start;j<n;j++){ code[i].bits[k] = ct.bits[j]; k++; } code[i].start = ct.start; } //打印编码 printf("编码表为\n"); for (i=0; i<n; i++){ printf ("%c 's HFM code is: ", code[i].ch); for (j=0;j<(n-code[i].start);j++){ printf ("%c", code[i].bits[j]); } printf ("\n"); } } //解码 void hfm_decode(char arr[]) { int i,j,k; char temp[n]; k = 0; i = 0; //遍历输入的编码,从编码表查找。 while(arr[i]!='\0'){ if(arr[i]=='\0') break; temp[k] = arr[i]; k++; temp[k] = '\0'; //从编码表中找出相应的字符 for(j=0;j<n;j++){ if(!(strcmp(temp,code[j].bits))){ k = 0; printf("%c",code[j].ch); break; } } if(k>n) printf("这串编码有问题,请重新检查!!\n"); i++; } printf("\n"); } int main() { int i = 0; char c,arr[1024]; hfm(); hfm_code(); //输入需要解码的一串码 printf("请输入一段编码序列,Ctrl+Z结束\n"); while(scanf("%c",&c)!=EOF){ arr[i] = c; i++; } arr[i-1] = '\0'; hfm_decode(arr); return 0; }
运行结果
-
java哈夫曼编码与译码_哈夫曼编码和译码
2021-02-27 19:40:231 #include 2 using namespacestd;34 const int max = 8;56 struct CodeNode { //存储 编码的 0 1 字符串7 charch;8 charbit[max];9 intlength;10 };11 struct HuffmanNode { //HuffmanTree 的...1 #include
2 using namespacestd;3
4 const int max = 8;5
6 struct CodeNode { //存储 编码的 0 1 字符串
7 charch;8 charbit[max];9 intlength;10 };11 struct HuffmanNode { //HuffmanTree 的结点数据
12 chardata;13 intparent, lchild, rchild, weight;14 };15
16 classHuffmanTree {17 public:18 HuffmanTree();19 ~HuffmanTree();20 void _enCode(char *, int *, int); //编码
21 void _deCode(char *); //译码
22 void _getMin(int, int &, int &); //返回最小的两个 下标值: 索引长度 最小值 次小值
23 void _ShowdeCode(); //将存储在数组中的元素输出 验证 是否成功编码
24 void _getIndex(int &, int &);25 private:26 HuffmanNode nodes[2 * max - 1]; //数组存储二叉树的所有结点数据
27 CodeNode charCode[max]; //数组存储二叉树结点编码的数据
28 char data_deColde[50]; //将翻译所得的字符放入其中
29 int nodeNumber; //有效结点的个数
30 };31
32 voidmain() {33
34 cout << "赫夫曼编码、译码:设置最大为 max = 8 个结点数据,最大存储译码字符为50个" <
39 char ch[100];40 int i = 0;41 cin >>ch[i];42 while (ch[i] != '#') {43 ++i;44 cin >>ch[i];45 }46
47 HT._deCode(ch);48 HT._ShowdeCode();49
50 system("pause");51 }52
53 HuffmanTree::HuffmanTree() {54 cout << "char 输入字符串结点:";55 chardata[max];56 cin >>data;57 cout << "int 输入各结点权值:";58 intwight[max];59 int i = 0;60 while (data[i] != '\0') {61 cin >> wight[i++]; //注意 i++ 表示先用再加, i 最后代表着这个数组的有效元素个数
62 }63 nodeNumber =i;64 _enCode(data, wight, i);65
66 }67 HuffmanTree::~HuffmanTree() {68 nodeNumber = 0;69 }70
71 void HuffmanTree::_deCode(char *ch) {72 int i = 0;73 int j = 1;74 int size = 0;75 bool flag = true;76 int index = 2 * nodeNumber - 2; //下标,初始化是根所在下标 2 * nodeNumber - 2
77 while (ch[i] != '#') { //对字符串一个个的匹配78 //只有当左右孩子下标为 -1 的时候表示已经到了叶子结点处,故对应了一个编码字符
79 while (nodes[index].lchild != -1 || nodes[index].rchild != -1) {80 if (ch[i] == '1') { //字符 1 向右 否则为1 向左
81 index =nodes[index].rchild;82 }83 else{84 index =nodes[index].lchild;85 }86 if (ch[i] == '#') { //为了:当用户未输入完代码时,将导致 下表 i 不能退出循环判断 ch[i]的值,故在此加上一个判断
87 data_deColde[size++] = 22; //由于是未输入完,加入其它字符(字符十进制为22的) 提示用户含有一个未解析的代码串
88 flag = false; //由于结束了,不再放入其它字符 flag置为 false, 而且 nodes[index].data也不是需要的字符
89 break;90 }91 i++;92 }93 if (flag == true)94 data_deColde[size++] = nodes[index].data; //将翻译获得的字符放入 data_deCode中
95 index = 2 * nodeNumber - 2; //再次返回到根下标去,即从根开始继续循环执行
96 if (nodeNumber == 1) ++i; //目的是为了: 当只编码一个 字符的时候,将不能执行 while循环而导致 i 永远为 初始值0,不能自加
97 }98 data_deColde[size] = '#'; //作为输出结束符
99 }100
101 void HuffmanTree::_enCode(char * Data, int * Wight, intlen) {102 //初始化 nodes结点数组, 父、左、右全为 -1
103 int i = 0;104 while (Data[i] != '\0') {105 nodes[i].data =Data[i];106 nodes[i].weight =Wight[i];107 nodes[i].parent = nodes[i].lchild = nodes[i].rchild = -1;108 i++;109 }110 //创建 HuffmanTree
111 int m1, m2; //m1 存储最小值 , m2 其次
112 for (i = len; i < 2 * len - 1; ++i) {113 _getMin(i, m1, m2);114 nodes[i].lchild = m1; //设置左、右 孩子 下标
115 nodes[i].rchild =m2;116
117 nodes[i].weight = nodes[m1].weight + nodes[m2].weight; //设置 两结点之和后的父结点权值
118 nodes[i].parent = -1; //暂无父结点 ,置为 -1
119 nodes[m1].parent = nodes[m2].parent = i; //设置 左、右孩子的 父结点
120 }121
122 //对 HuffmanTree进行编码 左结点为1 右结点为0
123 for (i = 0; i < len; ++i) {124 int tem =nodes[i].parent;125 int m = i; //m 作为孩子结点所在的下标,不能直接用 i,因为 i 表示的是叶子结点
126 charCode[i].ch =nodes[i].data;127 charCode[i].length =len;128 while (tem != -1) { //parent == -1的只有根结点, i 到 len 的都是叶子结点
129 if (nodes[tem].lchild == m) //当前结点 nodes[i]的是父结点的左孩子 为 1
130 charCode[i].bit[--charCode[i].length] = '0';131 else //当前结点 nodes[i]的是父结点的右孩子 为 0
132 charCode[i].bit[--charCode[i].length] = '1';133 m = tem; //
134 tem =nodes[tem].parent;135 }136 //对编码以后的代码进行输出验证:
137 cout << charCode[i].ch << ":";138 for (int j = charCode[i].length; j < len; ++j) {139 cout <
145 void HuffmanTree::_getMin(int len, int& m1, int&m2) {146 bool flag = true;147 int min1 = INT_MAX, min2 =INT_MAX, tem;148 for (int i = 0; i < len; ++i) {149 if (nodes[i].parent == -1 && flag) { //保留第一位未操作的元素
150 min1 =nodes[i].weight;151 m1 =i;152 flag = false;153 }154 else if (nodes[i].parent == -1) {155 if (nodes[i].weight
169 }170 }171
172 voidHuffmanTree::_ShowdeCode() {173 int i = 0;174 cout << "译码:" <
-
哈夫曼编码
2020-08-12 15:21:17从根逆向求,如果是parent的左孩子就是0,右孩子就是1。编码倒叙存储,正序输出即为哈夫曼编码。 typedef struct { int weight;//权值 int parent, lchild, rchild; }HTNode, * HuffmanTree; typedef -
哈夫曼树和哈夫曼编码的实现
2020-07-29 01:08:20//哈夫曼编码 typedef struct mesage//在优先级队列中用到的结构体 { mesage(int index = 0, int weight = 0) :index(index), weight(weight) {} int index;//下标,用来标识是哪个叶节点 int w -
哈夫曼树与哈夫曼编码
2020-10-23 15:25:54基本概念 哈夫曼树:给定N个权值作为N个叶子结点,构造...哈夫曼编码,即将字符出现概率当成叶子结点权值,进行构造哈夫曼树,而后所有父结点的左子树为0,右子树为1,对字符进行编码的方法,称之为哈夫曼编码 哈夫曼 -
C++ 实现哈夫曼树和哈夫曼编码
2020-12-20 15:04:47C++ 实现哈夫曼树哈夫曼树的定义 哈夫曼树的定义 将树中的结点赋予一个有某种意义的数值,称此数值为该结点的权。...其中,n0表示叶子结点的数目,wi和li(1<=i<=n0)分别表示叶子结点ki的权值和根ki之间的 -
有关哈夫曼树和哈夫曼编码的一些问题和总结
2020-03-12 23:35:47*有关哈夫曼树和哈夫曼编码的一些问题和总结 一些简单的介绍: 哈夫曼树又称为最优二叉树 是一种带权路径最短的二叉树 可以实现无损压缩和恢复(解压) 带权路径 树的带权路径就是树中所有的叶节点的权值乘上其到... -
C/C++实现哈夫曼树和生成哈夫曼编码
2019-07-01 14:52:39用C语言实现哈夫曼树和生成哈夫曼编码,首先生成哈夫曼树,哈夫曼树是从中选取权值最小的两个...生成哈夫曼编码,如果是左子树的话为0,右子树的话为1,从父节点还是往下找。然后这串代码就是哈夫曼编码。 上代码 #... -
数据结构学习之哈夫曼树和哈夫曼编码
2019-05-24 10:43:00数据结构学习之哈夫曼树和哈夫曼编码 0x1 前言 终于完成作业了,有点小开心,虽然翘了一上午的课。 0x2 题目 0x2.1 题目要求 假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为7,19,2,6,32,... -
哈夫曼(huffman)树和哈夫曼编码
2019-04-14 13:19:43哈夫曼树是最优二叉树,树的结点度只有0和2,没有度为1的结点。n个叶子结点的哈夫曼树含有2*n-1个结点。 需要注意的点: (1)满二叉树不一定是哈夫曼树; (2)哈夫曼树中权越大的叶子结点距离根越近; (3)具有... -
哈夫曼编码详解
2020-06-02 14:47:42而哈夫曼编码,则是从根节点开始,左节点标记为0,右节点标记为1. 例: **a,b,c,d,e 对应出现的频率为4,6,11,13,15,则a,b,c,e,d的哈夫曼编码是? 先把出现频率当成权重,选出权重最低了两个相加。 a和b相加,4+... -
哈夫曼树和哈夫曼编码源代码
2020-11-30 10:26:38#include<stdio.h> #define n 8 #define m (2*n-1) //创建结点结构体 typedef struct huffnode { int weight; int parent;... int start = 0; char co[n + 1]; char ch; }huffcode; //存放每一个树 -
java哈夫曼编码
2020-03-06 16:55:42哈夫曼编码 有些童鞋有个大误区:哈夫曼编码其实不是一个统一的编码,只不过是编码设计算法而已啦!...我也无奈啊计算机只认识0和1,别的都不认识QwQ 唵嘛嘛嘛嘛呢呢叭咪吽Huffman:0001010101011110...