#include <iostream>
#include <fstream>
#include <unordered_map>
#include <queue>
#include <bitset>
using namespace std;
struct Node
{
char ch;
int freq;
Node *left, *right;
Node(char ch, int freq) : ch(ch), freq(freq), left(nullptr), right(nullptr) {}
bool isLeaf()
{
return left == nullptr && right == nullptr;
}
};
struct Compare
{
bool operator()(Node *l, Node *r)
{
return l->freq > r->freq;
}
};
void getFrequency(string inputFile, unordered_map<char, int> &freq)
{
ifstream in(inputFile);
char ch;
while (in >> noskipws >> ch)
{
freq[ch]++;
}
in.close();
}
Node *buildHuffmanTree(unordered_map<char, int> &freq)
{
priority_queue<Node *, vector<Node *>, Compare> heap;
for (auto pair : freq)
{
heap.push(new Node(pair.first, pair.second));
}
while (heap.size() > 1)
{
Node *left = heap.top();
heap.pop();
Node *right = heap.top();
heap.pop();
Node *parent = new Node('\0', left->freq + right->freq);
parent->left = left;
parent->right = right;
heap.push(parent);
}
return heap.top();
}
void generateCodes(Node *root, string str, unordered_map<char, string> &codes)
{
if (root == nullptr)
{
return;
}
if (root->isLeaf())
{
codes[root->ch] = str;
}
generateCodes(root->left, str + "0", codes);
generateCodes(root->right, str + "1", codes);
}
void compress(string inputFile, string outputFile, unordered_map<char, string> &codes)
{
ifstream in(inputFile);
ofstream out(outputFile, ios::binary);
char ch;
while (in >> noskipws >> ch)
{
string code = codes[ch];
for (char bit : code)
{
out << bit;
}
}
in.close();
out.close();
}
void decompress(string inputFile, string outputFile, Node *root)
{
ifstream in(inputFile, ios::binary);
ofstream out(outputFile);
Node *current = root;
char ch;
while (in >> ch)
{
if (ch == '0')
{
current = current->left;
}
else
{
current = current->right;
}
if (current->isLeaf())
{
out << current->ch;
current = root;
}
}
in.close();
out.close();
}
int main()
{
unordered_map<char, int> freq;
getFrequency("input.txt", freq);
Node *root = buildHuffmanTree(freq);
unordered_map<char, string> codes;
generateCodes(root, "", codes);
compress("input.txt", "output.bin", codes);
decompress("output.bin", "decompressed.txt", root);
return 0;
}
首先使用 getFrequency
函数读取文件并统计每个字符的出现频率。然后使用 buildHuffmanTree
函数构建哈夫曼树。接下来,使用 generateCodes
函数生成哈夫曼编码。最后,使用 compress
和 decompress
函数进行压缩和解压缩。
你可以根据你的需要来修改这份代码,例如添加菜单选项。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define n 5
#define m 2*n-1
#define MIN 100
typedef struct
{
float weight;
int lchild,rchild,parent;
}hfmtree;
hfmtree tree[m];
typedef struct
{
char bits[n];
int start;
char ch;
}codetype;
codetype code[n];
void hfm(void)
{
//int n = 5;
int i,j,p1,p2;
float s1,s2,f;
//m个节点初始化
for(i = 0;i<m;i++){
tree[i].parent = -1;
tree[i].lchild = -1;
tree[i].rchild = -1;
tree[i].weight = 0;
}
//输入n个节点的权值
printf("请输入n个权值,空格隔开回车结束\n");
for(i = 0;i<n;i++){
scanf("%f",&f);
getchar();
tree[i].weight = f;
}
//合并成m个节点
for(i = n;i<m;i++){
p1 = -1; //小的下标
p2 = -1; //第二小的下标
s1 = MIN; //小的权值
s2 = MIN+1; //第二小的权值
//找出前面的最小权值和第二小权值
for(j =0;j<i;j++){
if(tree[j].parent == -1){
if(tree[j].weight<=s1){
s2 = s1;
s1 = tree[j].weight;
p2 = p1;
p1 = j;
}
else if(tree[j].weight<=s2){
s2 = tree[j].weight;
p2 = j;
}
}
}
tree[p1].parent = i;
tree[p2].parent = i;
tree[i].lchild = p1;
tree[i].rchild = p2;
tree[i].weight = tree[p1].weight+tree[p2].weight;
tree[i].parent = -1;
}
for(i=0;i<n;i++)
printf("第%d个的权值是%f\n",i,tree[i].weight);
}
void hfm_code(void)
{
int i,j,p1,p2,k;
char c;
codetype ct;
//输入对应的字符
printf("请输入对应的字符,空格隔开回车结束\n");
for(i=0;i<n;i++){
scanf("%c",&c);
getchar();
code[i].ch = c;
}
//编码0或者1
for(i=0;i<n;i++){
ct.start = n;
p1 = tree[i].parent;
p2 = i;
//从叶子开始编码
while(p1 != -1){
//n个节点最多有n-1个编码
ct.start--;
if(tree[p1].lchild==p2)
ct.bits[ct.start] = '0';
else if(tree[p1].rchild==p2)
ct.bits[ct.start] = '1';
p2 = p1;
p1 = tree[p2].parent;
}
//保存编码
k = 0;
for(j=ct.start;j<n;j++){
code[i].bits[k] = ct.bits[j];
k++;
}
code[i].start = ct.start;
}
//打印编码
printf("编码表为\n");
for (i=0; i<n; i++){
printf ("%c 's HFM code is: ", code[i].ch);
for (j=0;j<(n-code[i].start);j++){
printf ("%c", code[i].bits[j]);
}
printf ("\n");
}
}
//解码
void hfm_decode(char arr[])
{
int i,j,k;
char temp[n];
k = 0;
i = 0;
//遍历输入的编码,从编码表查找。
while(arr[i]!='\0'){
if(arr[i]=='\0')
break;
temp[k] = arr[i];
k++;
temp[k] = '\0';
//从编码表中找出相应的字符
for(j=0;j<n;j++){
if(!(strcmp(temp,code[j].bits))){
k = 0;
printf("%c",code[j].ch);
break;
}
}
if(k>n)
printf("这串编码有问题,请重新检查!!\n");
i++;
}
printf("\n");
}
int main()
{
int i = 0;
char c,arr[1024];
hfm();
hfm_code();
//输入需要解码的一串码
printf("请输入一段编码序列,Ctrl+Z结束\n");
while(scanf("%c",&c)!=EOF){
arr[i] = c;
i++;
}
arr[i-1] = '\0';
hfm_decode(arr);
return 0;
}