免费网站建设无广告新东方英语培训机构官网

利用huffman树实现对文件A先编码后解码，范围为ASCII码0-255的值，如何解决特殊符号问题是一个难点，注意应使用unsigned char存储数据，否则ASCII码128-255的值可能会出问题：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<string>
#include<map>
#include<vector>
const int N = 1e4;
using namespace std;
struct HuffmanNode
{int data;double weigh;int parent, lchild, rchild;
};
class HuffTree
{
private:vector<HuffmanNode>hufftree;map<int, vector<int>>eachcode;int n;//字符结点数
public:HuffTree() { hufftree.resize(0), n = 0; }void createHuffTree(vector<HuffmanNode>& 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(vector<HuffmanNode>& 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 rchar=hufftree[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();*/map<int, int>m;ifstream ifs_2("random.txt", ios::binary);char ch_1;while (ifs_2.get(reinterpret_cast<char&>(ch_1))){int data = static_cast<unsigned char>(ch_1);m[data]++;}ifs_2.close();map<int, double>m2;for (auto it = m.begin(); it != m.end(); it++){//m2[it->first] = static_cast<double>(it->second) / N;m2[it->first] = static_cast<double>(it->second);cout << it->first << "频率:" << m2[it->first] << endl;}HuffTree t;vector<HuffmanNode>leafs;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_cast<unsigned 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;
}