网站如何备案工信局,南宁企业网站设计公司,济南做网站优化哪家好,网站开发接活利用huffman树实现对文件A先编码后解码#xff0c;范围为ASCII码0-255的值#xff0c;如何解决特殊符号问题是一个难点#xff0c;注意应使用unsigned char存储数据#xff0c;否则ASCII码128-255的值可能会出问题#xff1a;
#define _CRT_SECURE_NO_WARNINGS 1
#includ…利用huffman树实现对文件A先编码后解码范围为ASCII码0-255的值如何解决特殊符号问题是一个难点注意应使用unsigned char存储数据否则ASCII码128-255的值可能会出问题
#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream
#includefstream
#includecstdlib
#includestring
#includemap
#includevector
const int N 1e4;
using namespace std;
struct HuffmanNode
{int data;double weigh;int parent, lchild, rchild;
};
class HuffTree
{
private:vectorHuffmanNodehufftree;mapint, vectorinteachcode;int n;//字符结点数
public:HuffTree() { hufftree.resize(0), n 0; }void createHuffTree(vectorHuffmanNode leafs);~HuffTree();void GetCode(int c);//第i个符号的编码void SelectSmall(int least, int less, int i);void Decode(ifstream is, ofstream os);void geteachcode();string getcode(int ne);
};
void HuffTree::SelectSmall(int least, int less, int i)
{while ((hufftree[least].parent ! -1 || hufftree[less].parent ! -1)){if ((hufftree[least].parent ! -1) || least less)least;if ((hufftree[less].parent ! -1) || least less) less;}if (hufftree[least].weigh hufftree[less].weigh)swap(least, less);for (int j min(least, less); j i; j){if (j least || j less)continue;if (hufftree[j].parent -1 hufftree[j].weigh hufftree[less].weigh){if (hufftree[j].weigh hufftree[least].weigh){less least;least j;}else{less j;}}}
}
void HuffTree::createHuffTree(vectorHuffmanNode leafs)
{n leafs.size();hufftree.resize(2 * n - 1);for (int i 0; i n; i){hufftree[i].data leafs[i].data;hufftree[i].weigh leafs[i].weigh;hufftree[i].lchild hufftree[i].rchild hufftree[i].parent -1;}for (int i n; i 2 * n - 1; i){int least 0, less 1;SelectSmall(least, less, i);hufftree[least].parent hufftree[less].parent i;hufftree[i].parent -1;hufftree[i].lchild least;hufftree[i].rchild less;hufftree[i].weigh hufftree[least].weigh hufftree[less].weigh;}
}
void HuffTree::GetCode(int c)
{int i 0;for (auto it hufftree.begin(); it ! hufftree.end(); it){if (hufftree[i].data c)break;i;}if (i hufftree.size())return;int p i;int parent hufftree[i].parent;while (parent ! -1){if (hufftree[parent].lchild p)eachcode[c].insert(eachcode[c].begin(), 0);else eachcode[c].insert(eachcode[c].begin(), 1);p parent;parent hufftree[parent].parent;}
}
void HuffTree::geteachcode()
{for (auto it eachcode.begin(); it ! eachcode.end(); it){cout it-first :;for (int i 0; i it-second.size(); i){cout it-second[i];}cout endl;}
}
string HuffTree::getcode(int ne)
{string res;for (int i 0; i eachcode[ne].size(); i){res to_string(eachcode[ne][i]);}return res;
}
void HuffTree::Decode(ifstream is, ofstream os)
{string target ;int root hufftree.size() - 1;int p root;char c;while (is.get(c)){if (c 0)p hufftree[p].lchild;else p hufftree[p].rchild;if (hufftree[p].lchild -1 hufftree[p].rchild -1){unsigned char rcharhufftree[p].data;os rchar;p root;}}
}
HuffTree::~HuffTree()
{}
int main()
{/*srand(time(0));ofstream out(random.txt);if (!out){cerr 无法打开文件 endl;return 1;}for (int i 0; i N; i){unsigned char rchar;rchar rand() % 256;int data rchar;out rchar;}out.close();*/mapint, intm;ifstream ifs_2(random.txt, ios::binary);char ch_1;while (ifs_2.get(reinterpret_castchar(ch_1))){int data static_castunsigned char(ch_1);m[data];}ifs_2.close();mapint, doublem2;for (auto it m.begin(); it ! m.end(); it){//m2[it-first] static_castdouble(it-second) / N;m2[it-first] static_castdouble(it-second);cout it-first 频率: m2[it-first] endl;}HuffTree t;vectorHuffmanNodeleafs;leafs.resize(N);int i 0;for (auto it m2.begin(); it ! m2.end(); it){leafs[i].data it-first;leafs[i].weigh it-second;i;}t.createHuffTree(leafs);for (int k 0; k 255; k){t.GetCode(k);}t.geteachcode();ifstream file(random.txt, ios::binary);string buf;char ch;ofstream os(B.txt, ios::binary);while (file.get(ch)){unsigned char uch static_castunsigned char(ch);int ne uch;string is t.getcode(ne);for (int i 0; i is.size(); i){os is[i];}}os.close();file.close();ofstream ofs(C.txt, ios::binary);ifstream ifs(B.txt, ios::binary);t.Decode(ifs, ofs);ofs.close();ifs.close();cout 文件A与文件C的比较结果为 ;ifstream fileA(random.txt, ios::binary);ifstream fileC(C.txt, ios::binary);char bufA, bufC;while (fileA.get(bufA) fileC.get(bufC)){if (bufA ! bufC){cout 不一致 endl;return 0;}}cout 一致 endl;fileA.close();fileC.close();return 0;
}
