html网站注册页面,网络优化工程师能干一辈子吗,制作企业网站页面html,app排名优化D 哈夫曼树
题目要求
编写一个哈夫曼编码译码程序。针对一段文本#xff0c;根据文本中字符出现频率构造哈夫曼树#xff0c;给出每个字符的哈夫曼编码#xff0c;并进行译码#xff0c;计算编码前后文本大小。 为确保构建的哈夫曼树唯一#xff0c;本题做如下限定… D 哈夫曼树
题目要求
编写一个哈夫曼编码译码程序。针对一段文本根据文本中字符出现频率构造哈夫曼树给出每个字符的哈夫曼编码并进行译码计算编码前后文本大小。 为确保构建的哈夫曼树唯一本题做如下限定
选择根结点权值最小的两棵二叉树时选取权值较小者作为左子树。若多棵二叉树根结点权值相等则先生成的作为左子树后生成的作为右子树具体来说i) 对于单结点二叉树优先选择根结点对应字母在文本中最先出现者如文本为cba三个字母均出现1次但c在文本中最先出现b第二出现故则选择c作为左子树b作为右子树。ii) 对于非单结点二叉树先生成的二叉树作为左子树后生成的二叉树作为右子树。iii. 若单结点和非单结点二叉树根结点权值相等优先选择单结点二叉树。生成哈夫曼编码时哈夫曼树左分支标记为0右分支标记为1。
输入格式:
输入为3行。第1行为一个字符串包含不超过5000个字符至少包含两个不同的字符每个字符为a-z的小写字母。第2、3行为两个由0、1组成的字符串表示待译码的哈夫曼编码。
输出格式:
输出第一行为用空格间隔的2个整数分别为压缩前后文本大小以字节为单位一个字符占1字节8个二进制位占1字节若压缩后文本不足8位则按1字节算。输出从第二行开始每行为1个字符的哈夫曼编码按各字符在文本中出现次数递增顺序输出若多个字符出现次数相同则按其在文本出现先后排列。每行格式为“字母:编码”。最后两行为两行字符串表示译码结果若译码失败则输出INVALID。
输入样例:
cbaxyyzz
0100
011
输出样例:
8 3
c:100
b:101
a:110
x:111
y:00
z:01
zy
INVALID
题目分析
要点1原文本字符数据整理
根据输入的字符串整理字符的种类数以及各字符的个数并将其按照出现次数从小到大进行排列若次数相同则先出现的仍在前。
//数据预处理
//计算输入的文本出现的所有不同的字符和对应数量
const int N 5010;
int h[N], idx,w[N]; //w数组存储字符在文本中出现的个数idx最终保存不同的字符种类数h数组存储对应字符的下标
char da[N]; //da数组存储字符
int PreLengh; //初始文本的长度
string line; //初始文本
void input() {cin line;PreLengh line.size();for (char ch : line) { //遍历文本中的每一个字符if (w[h[ch]] 0) { //字符的权重为0该字符第一次出现da[idx] ch;h[ch] idx;w[idx] 1;}else {w[h[ch]]; //否则不是第一次出现权重1}}//数据录入结束进行排序//冒泡排序从小到大排列权重相同的原来在前仍在前for (int i 1; i idx; i) {for (int j 1; j idx - 1; j) {if (w[j] w[j 1]) {swap(w[j], w[j 1]);swap(da[j], da[j 1]); //权重和数据都要交换}}}
}
要点2构建huffman树
1.在森林中取权值最小的两个根结点s和nl合并成一棵二叉树并生成一个新结点T作为这两个结点的父亲T的权值是它的两个子结点的权值之和。
2.对新森林重复上一步操作直至森林中只有唯一的根结点时终止操作。
//创建哈夫曼树
HuffmanTree* createHuffmanTree(char data[],int weight[],int n) {HuffmanTree* treenew HuffmanTree;tree-m n; //结点总数tree-H new HuffmanNode * [tree-m 1];HuffmanNode* p1, * p2, * p, * t;//初始化结点for (int i 1; i tree-m; i) {tree-H[i] new HuffmanNode;tree-H[i]-INFO data[i];tree-H[i]-Weight weight[i];tree-H[i]-LLINK NULL;tree-H[i]-RLINK NULL;}//组合结点int i, j;for (int i 1; i tree-m; i) { //遍历所有结点t new HuffmanNode;p1 tree-H[i]; //选取最小的两个结点作为左右子树p2 tree-H[i 1];t-LLINK p1;t-RLINK p2;t-Weight p1-Weight p2-Weight;p t;j i 2;//比较排列仍要保证从小到大排列while (j tree-m (p-Weight) tree-H[j]-Weight) {tree-H[j - 1] tree-H[j];j;}//将新生成的树放入森林中tree-H[j - 1] p;}return tree;
}
要点3Huffman编码
要输出所有字符的编码遍历思想走左子树则0走右子树则1直至走到叶结点为字符存储为对应字符的Huffman编码。
//Huffman编码
//char标志字符与其对应的Huffman编码
typedef unordered_mapchar, string UMCS;
UMCS HuffmanCode;
void CreateHuffmanCode(HuffmanNode* root, string code) {if (root NULL) return;if (!root-LLINK !root-RLINK) { //如果是叶结点遍历到字符HuffmanCode[root-INFO] code; }CreateHuffmanCode(root-LLINK, code 0); //左子树0CreateHuffmanCode(root-RLINK, code 1); //右子树1
} 要点4对二进制进行译码
读入一整串的二进制数遇到0就走左子树遇到1就走右子树直至走到叶结点为字符一个字符到此译码成功将该字符串到总答案中。若此时还有编码剩余则重新从树根开始继续译码直至读入全部二进制编码。
若全部二进制读入完毕但此时指针不位于叶结点证明译码失败没有正确结束。输出INVALID。
//对二进制进行译码
void TransHuffmanCode(HuffmanNode* root) {HuffmanNode* t root;for (int num 2; num 0; num--) {string op,ans;cin op; //读入整串的二进制编码for (int i 0; i op.size(); i) {char k op[i];if (k 0) t t-LLINK; //如果是0就走左指针if (k 1) t t-RLINK; //如果是1就走右指针if (!t-LLINK !t-RLINK) { //走到叶结点译码成功串入答案ansans ans t-INFO;if (i ! op.size() - 1) t root; //若还有编码未译完重新返回树根继续译码}}if (!(!t-LLINK !t-RLINK)) coutINVALID; //如果译码到最后没有走到叶结点证明译码失败else cout ans;cout endl;t root;}
}
完整代码
#include iostream
#include cstring
#include unordered_map
using namespace std;//Huffman结点
typedef struct HuffmanNode {char INFO; //信息域int Weight; //权值HuffmanNode* LLINK; //左链接HuffmanNode* RLINK; //右链接
}HuffmanNode;//Huffman树的构建
typedef struct HuffmanTree {HuffmanNode** H; //存储哈夫曼树结点的数组Hint m; //哈夫曼树结点总数
}HuffmanTree;//数据预处理
//计算输入的文本出现的所有不同的字符和对应数量
const int N 5010;
int h[N], idx,w[N]; //w数组存储字符在文本中出现的个数idx最终保存不同的字符种类数h数组存储对应字符的下标
char da[N]; //da数组存储字符
int PreLengh; //初始文本的长度
string line; //初始文本
void input() {cin line;PreLengh line.size();for (char ch : line) { //遍历文本中的每一个字符if (w[h[ch]] 0) { //字符的权重为0该字符第一次出现da[idx] ch;h[ch] idx;w[idx] 1;}else {w[h[ch]]; //否则不是第一次出现权重1}}//数据录入结束进行排序//冒泡排序从小到大排列权重相同的原来在前仍在前for (int i 1; i idx; i) {for (int j 1; j idx - 1; j) {if (w[j] w[j 1]) {swap(w[j], w[j 1]);swap(da[j], da[j 1]); //权重和数据都要交换}}}
}//创建哈夫曼树
HuffmanTree* createHuffmanTree(char data[],int weight[],int n) {HuffmanTree* treenew HuffmanTree;tree-m n; //结点总数tree-H new HuffmanNode * [tree-m 1];HuffmanNode* p1, * p2, * p, * t;//初始化结点for (int i 1; i tree-m; i) {tree-H[i] new HuffmanNode;tree-H[i]-INFO data[i];tree-H[i]-Weight weight[i];tree-H[i]-LLINK NULL;tree-H[i]-RLINK NULL;}//组合结点int i, j;for (int i 1; i tree-m; i) { //遍历所有结点t new HuffmanNode;p1 tree-H[i]; //选取最小的两个结点作为左右子树p2 tree-H[i 1];t-LLINK p1;t-RLINK p2;t-Weight p1-Weight p2-Weight;p t;j i 2;//比较排列仍要保证从小到大排列while (j tree-m (p-Weight) tree-H[j]-Weight) {tree-H[j - 1] tree-H[j];j;}//将新生成的树放入森林中tree-H[j - 1] p;}return tree;
}//Huffman编码
//char标志字符与其对应的Huffman编码
typedef unordered_mapchar, string UMCS;
UMCS HuffmanCode;
void CreateHuffmanCode(HuffmanNode* root, string code) {if (root NULL) return;if (!root-LLINK !root-RLINK) { //如果是叶结点遍历到字符HuffmanCode[root-INFO] code; }CreateHuffmanCode(root-LLINK, code 0); //左子树0CreateHuffmanCode(root-RLINK, code 1); //右子树1
}//计算压缩后文本的大小
int PostLength 0;
void PostNum(UMCS HuffmanCode) {for (char k : line) { //从头到位按照原文本的逐一计算PostLength HuffmanCode[k].size();}PostLength (PostLength 7) / 8; //以字节为单位计算不足8位按一字节算
}//打印输出huffman编码
void printHuffmanCode() {for (int i 1; i idx; i) { //da数组内存储的即为数据字符cout da[i] : HuffmanCode[da[i]] endl;}
}//对二进制进行译码
void TransHuffmanCode(HuffmanNode* root) {HuffmanNode* t root;for (int num 2; num 0; num--) {string op,ans;cin op; //读入整串的二进制编码for (int i 0; i op.size(); i) {char k op[i];if (k 0) t t-LLINK; //如果是0就走左指针if (k 1) t t-RLINK; //如果是1就走右指针if (!t-LLINK !t-RLINK) { //走到叶结点译码成功串入答案ansans ans t-INFO;if (i ! op.size() - 1) t root; //若还有编码未译完重新返回树根继续译码}}if (!(!t-LLINK !t-RLINK)) coutINVALID; //如果译码到最后没有走到叶结点证明译码失败else cout ans;cout endl;t root;}
}
int main() {//数据预处理input();//创建Huffman树HuffmanTree* tree createHuffmanTree(da, w, idx);//构造Huffman编码CreateHuffmanCode(tree-H[idx], );//计算编码后文本大小PostNum(HuffmanCode);//输出压缩前后文本大小cout PreLengh PostLength endl;//输出各字符的Huffman编码printHuffmanCode();//对输入的Huffman二进制编码进行译码TransHuffmanCode(tree-H[idx]);return 0;
} 提交结果
