h5建设网站教程,阿里云esc 可以做几个网站,如何搭建一个局域网,seo外包服务DS二叉树–赫夫曼树解码
题目描述 已知赫夫曼编码算法和程序#xff0c;在此基础上进行赫夫曼解码
可以增加一个函数#xff1a;int Decode(const string codestr, char txtstr[]);//输入编码串codestr#xff0c;输出解码串txtstr
该方法如果解码成功则返回1#xff0c…DS二叉树–赫夫曼树解码
题目描述 已知赫夫曼编码算法和程序在此基础上进行赫夫曼解码
可以增加一个函数int Decode(const string codestr, char txtstr[]);//输入编码串codestr输出解码串txtstr
该方法如果解码成功则返回1解码失败则返回-1本程序增加宏定义ok表示1error表示-1
赫夫曼解码算法如下
定义指针p指向赫夫曼树结点指针i指向编码串定义ch逐个读取编码串的字符
初始操作包括读入编码串str设置p指向根结点i为0表示指向串首执行以下循环
1取编码串的第i个字符放入ch
2如果ch是字符0则p跳转到左孩子如果ch是字符1则p跳转到右孩子如果ch非0非1表示编码串有错误报错退出
3如果p指的结点是叶子输出解码字符p跳回根结点i跳步骤1
4如果p指的结点不是叶子且i未到编码串末尾i跳步骤1
5如果p指的结点不是叶子且i到达编码串末尾报错退出
当i到达编码串末尾解码结束。
输入 第一行先输入n表示有n个叶子 第二行输入n个权值权值全是小于1万的正整数 第三行输入n个字母表示与权值对应的字符 第四行输入k表示要输入k个编码串 第五行起输入k个编码串
输出 每行输出解码后的字符串如果解码失败直接输出字符串“error”不要输出部分解码结果
输入样例1 5 15 4 4 3 2 A B C D E 3 11111 10100001001 00000101100
输出样例1 AAAAA ABEAD error
最优二叉树/赫夫曼树
最优二叉树也称哈夫曼树或者霍夫曼树、赫夫曼树给定n个权值作为n个叶子结点(每个叶子结点会有权值)构造一颗二叉树若该树的带权路径长度(wpl)达到最小 赫夫曼树带权路径长度最短的树权值较大的结点离根较进。值都在叶子结点上 构成赫夫曼树的步骤
思路
从小到大进行排序, 将每一个数据每个数据都是一个节点 每个节点可以看成是一颗最简单的二叉树取出根节点权值最小的两颗二叉树组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和再将这颗新的二叉树以根节点的权值大小 再次排序 不断重复 1-2-3-4 的步骤直到数列中所有的数据都被处理就得到一颗赫夫曼树
#includebits/stdc.h
using namespace std;
struct Node
{int weight,left,right,parent;string c;
}tree[105];
int main()
{int n;cinn;for(int i1;in;i) {cintree[i].weight;tree[i].parent0;tree[i].left0;tree[i].right0;}for(int i1;in;i) cintree[i].c;int k;cink;//编码串string s[105];for(int i0;ik;i) cins[i];//要新建n-1个节点for(int in1;i2*n;i){tree[i].parent0;tree[i].weight0;//找两个权值最小的for(int j0;j2;j){int small20000,loc0;for(int k1;ki;k){if(tree[k].parent0tree[k].weightsmall){smalltree[k].weight;lock;}}tree[loc].parenti;//默认左子树小右子树大(j)?tree[i].rightloc:tree[i].leftloc;tree[i].weighttree[loc].weight;}}//解码for(int i0;ik;i){string strs[i];string res;int lenstr.size();int k0,cur2*n-1;bool flag0;while(klen){//错误的 无法解码if(str[k]!0str[k]!1){flag1;break;}//是叶子节点 有值可以参与解码if(tree[cur].left0tree[cur].right0){restree[cur].c;cur2*n-1;continue;}if(str[k]0){if(tree[cur].left0){flag1;break;}curtree[cur].left;k;if(klen){if(tree[cur].left0tree[cur].right0){restree[cur].c;cur2*n-1;}else flag1;}continue;}if(str[k]1){if(tree[cur].right0){flag1;break;}curtree[cur].right;k;if(klen){if(tree[cur].left0tree[cur].right0){restree[cur].c;cur2*n-1;}else flag1;}continue;}}if(flag){couterrorendl;continue;}coutresendl;}return 0;
}
