…累了,一会更新,写正文,写思路,最好能画画图
代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include <string>
using namespace std;
typedef struct {
int val;
int weight;
int parent, lchild, rchild;
}HuffmanNode;
static bool cmp(vector<int> a, vector<int> b) {
return a[1] > b[1];
}
void calculate(vector<vector<int>>& check) {
FILE* file;
file = fopen("a.txt", "r");
char c;
while ((c = fgetc(file)) != EOF) {
if (c >= 'a' && c <= 'z') {
check[1]++;
}
else if (c >= 'A' && c <= 'Z') {
check[1]++;
}
else if (c == ' ') {
check[52][1]++;
}
else if (c == ',') {
check[53][1]++;
}
else if (c == '.') {
check[54][1]++;
}
}
sort(check.begin(), check.end(), cmp);
}//统计呈现字母的频率
void initHuffmanTree(HuffmanNode* HT, int n, int m, vector<vector<int>>& check) {
int j = 1;
for (int i = n - 1; i >= 0; i--) {
HT[j++] = {check[i][0], check[i][1],0,0,0};
}
for (; j <= m; j++) {
HT[j] = { 0,0,0,0,0 };
}
}//初始化哈夫曼树
void select(HuffmanNode* HT,int endLoc, int& node1, int& node2) {
int min1 = INT_MAX - 1, min2 = INT_MAX;
for (int i = 1; i <= endLoc; i++) {
if (HT[i].parent == 0) {
if (HT[i].weight < min1) {
min1 = HT[i].weight;
node1 = i;
}
else if (HT[i].weight < min2) {
min2 = HT[i].weight;
node2 = i;
}
}
}
}//选出两个最小的节点
void createHuffmanTree(HuffmanNode* HT, int n, int m) {
int loc;
int node1, node2;
for (int i = n + 1; i <= m; i++) {
select(HT, i - 1, node1, node2);
HT[i].lchild = node2;
HT[i].rchild = node1;
HT[i].weight = HT[node1].weight + HT[node2].weight;
HT[node1].parent = HT[node2].parent = i;
}
}//建设哈夫曼树
void encode(HuffmanNode* HT, int n, map<int, string>& huffmanCode) {
int par; //父节点
int son; //子节点地位
for (int i = 1; i <= n; i++) {
son = i;
par = HT[i].parent;
string code = "";
while (par != 0) {
if (HT[par].lchild == son) {
code.insert(code.begin(), '0');
}
if (HT[par].rchild == son) {
code.insert(code.begin(), '1');
}
son = par;
par = HT[par].parent;
}//向上找,直到没有parent
huffmanCode[HT[i].val] = code;
}
}//生成哈夫曼码
void encodeTxtToHuffmanCode(map<int, string>& huffmanCode) {
FILE* readFile = fopen("a.txt", "r");
FILE* writeFile = fopen("b.txt", "w");
char c = fgetc(readFile);
while (c != EOF) {
int i;
if (c >= 'a' && c <= 'z') {
i = c - 'a';
}
else if (c >= 'A' && c <= 'Z') {
i = c - 'A' + 26;
}
else if (c == ' ') {
i = 52;
}
else if (c == ',') {
i = 53;
}
else if (c == '.') {
i = 54;
}
for (int j = 0; j < huffmanCode[i].size(); j++) {
fputc(huffmanCode[i][j], writeFile);
}
c = fgetc(readFile);
}
fclose(readFile);
fclose(writeFile);
}
void decode(HuffmanNode* HT, int n) {
FILE* readFile = fopen("b.txt", "r");
FILE* writeFile = fopen("c.txt", "w");
char c = fgetc(readFile);
int i = 2 * n - 1;
while (c != EOF) {
if (c == '0') {
i = HT[i].lchild;
}
else if (c == '1') {
i = HT[i].rchild;
}
if (HT[i].lchild == 0 || HT[i].rchild == 0) {
char c;
if (HT[i].val >= 0 && HT[i].val <= 25) {
c = 'a' + HT[i].val;
}
else if (HT[i].val >= 26 && HT[i].val <= 51) {
c = 'A' + HT[i].val - 26;
}
else if (HT[i].val == 52) {
c = ' ';
}
else if (HT[i].val == 53) {
c = ',';
}
else if (HT[i].val == 54) {
c = '.';
}
fputc(c, writeFile);
i = 2 * n - 1;
}
c = fgetc(readFile);
}
fclose(readFile);
fclose(writeFile);
}//哈夫曼码翻译成文章
int main() {
vector<vector<int>> check(55,vector<int>(2,0));
for (int i = 0; i < check.size(); i++) {
check[i][0] = i;
}
calculate(check);
int n = 0; //叶子个数(呈现的字母个数)
for (int i = 0; i < check.size(); i++) {
if (check[i][1] != 0) n++;
}
int m = 2 * n - 1; //Huffman节点
HuffmanNode* HT;
HT = (HuffmanNode*)malloc((m + 1) * sizeof(HuffmanNode)); //第0个节点不必
initHuffmanTree(HT, n, m, check);
createHuffmanTree(HT, n, m);
/*for (int i = 1; i <= m; i++) {
cout << HT[i].val << " " << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
}*/
map<int, string> huffmanCode;
encode(HT, n, huffmanCode);
/*for (auto x : huffmanCode) {
cout << x.first << " " << x.second << endl;
}*/
encodeTxtToHuffmanCode(huffmanCode);
decode(HT, n);
}