精华内容
下载资源
问答
  • 哈夫曼编码方法,把各个字符作为结点,权值是字符出现的频率,构造出哈夫曼树,各个字符最终都出现在叶子节点上,然后从根节点到某字符的路径,向左为0,向右为1,得到哈夫曼编码 E为00 B为010 ...

    哈夫曼树构造方法,把一开始的各个点看作一颗颗树,取权值最小的两棵树组成一颗新二叉树,新树权值为两点之和,放入森林中取代原来的两个结点。一直重复直至只剩最后一颗树

    哈夫曼编码方法,把各个字符作为结点,权值是字符出现的频率,构造出哈夫曼树,各个字符最终都出现在叶子节点上,然后从根节点到某字符的路径,向左为0,向右为1,得到哈夫曼编码
    在这里插入图片描述
    E为00
    B为010

    展开全文
  • C++ 哈夫曼树和哈夫曼编码 哈夫曼树又称最优二叉树是树的结构应用之一。 哈夫曼树的构建: ...从结点开始,左分支路径记0,右分支路径记1,从根结点到目标叶结点路径上的编号序列就是哈夫曼编码 ...

    C++ 哈夫曼树和哈夫曼编码

    哈夫曼树又称最优二叉树是树的结构应用之一。

    哈夫曼树的构建:

    从集合中选出最小的两个元素,相加和放入集合。再从集合中选出最小的两个元素,相加和放入集合…

    不说了,直接上图
    在这里插入图片描述

    哈夫曼树的带权路径长度:

    即叶结点权值 * 根结点到该叶结点的路径长度

    路径长度:根结点到第L层结点的路径长度为L-1
    在这里插入图片描述

    哈夫曼编码

    从结点开始,左分支路径记0,右分支路径记1,从根结点到目标叶结点路径上的编号序列就是哈夫曼编码
    在这里插入图片描述

    展开全文
  • 1、编程思想 哈夫曼树 ...哈夫曼编码 对哈夫曼树中的前n个节点进行编码,从根节点开始,位于左子树的为0,右子树为1。编程就是通过符号找到其对应的是左子树还是有子树。 输入与权值对应的编码,找到code

    1、编程思想

    哈夫曼树

    哈夫曼树是最小的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;
    }
    
    

    运行结果

    在这里插入图片描述

    展开全文
  • 1 #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
  • //哈夫曼编码 typedef struct mesage//在优先级队列中用到的结构体 { mesage(int index = 0, int weight = 0) :index(index), weight(weight) {} int index;//下标,用来标识是哪个叶节点 int w
  • 基本概念 哈夫曼树:给定N个权值作为N个叶子结点,构造...哈夫曼编码,即将字符出现概率当成叶子结点权值,进行构造哈夫曼树,而后所有父结点的左子树为0,右子树为1,对字符进行编码的方法,称之为哈夫曼编码 哈夫曼
  • C++ 实现哈夫曼哈夫曼树的定义 哈夫曼树的定义   将树中的结点赋予一个有某种意义的数值,称此数值为该结点的权。...其中,n0表示叶子结点的数目,wili(1<=i<=n0)分别表示叶子结点ki的权值根ki之间的
  • *有关哈夫曼树和哈夫曼编码的一些问题总结 一些简单的介绍: 哈夫曼树又称为最优二叉树 是一种带权路径最短的二叉树 可以实现无损压缩恢复(解压) 带权路径 树的带权路径就是树中所有的叶节点的权值乘上其到...
  • C/C++实现哈夫曼树生成哈夫曼编码

    千次阅读 2019-07-01 14:52:39
    用C语言实现哈夫曼树生成哈夫曼编码,首先生成哈夫曼树,哈夫曼树是从中选取权值最小的两个...生成哈夫曼编码,如果是左子树的话为0,右子树的话为1,从父节点还是往下找。然后这串代码就是哈夫曼编码。 上代码 #...
  • 数据结构学习之哈夫曼树和哈夫曼编码 0x1 前言  终于完成作业了,有点小开心,虽然翘了一上午的课。 0x2 题目 0x2.1 题目要求 ​ 假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为7,19,2,6,32,...
  • 哈夫曼树是最优二叉树,树的结点度只有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的哈夫曼编码是? 先把出现频率当成权重,选出权重最低了两个相加。 ab相加,4+...
  • #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...

空空如也

空空如也

1 2 3 4 5 ... 17
收藏数 323
精华内容 129
关键字:

哈夫曼编码0和1