最优编码。具体要求:从命令行获得源文件名和目标文件名,按字节统计源文件中每个字节的出现次数,以每个字节为叶结点,出现次数为权值,构造哈夫曼编码,并对源文件进行编码,将编码结果写到目标文件中。写出完整C++代码
时间: 2024-10-27 21:08:53 浏览: 20
最优编码,通常指的就是霍夫曼编码(Huffman Coding)。这是一种用于数据压缩的无损编码方法,通过构建一棵霍夫曼树来生成每个字符的独特编码。以下是使用C++实现这个过程的一个简化版代码示例:
```cpp
#include <iostream>
#include <fstream>
#include <map>
#include <queue>
#include <bitset>
// 霍夫曼树节点结构
struct HuffmanNode {
char data;
int freq;
HuffmanNode* left = nullptr;
HuffmanNode* right = nullptr;
HuffmanNode(char d, int f)
: data(d), freq(f) {}
};
// 比较两个节点频率
bool compareNodes(const HuffmanNode* a, const HuffmanNode* b) {
return a->freq > b->freq;
}
// 构建霍夫曼树
HuffmanNode* buildHuffmanTree(std::map<char, int>& freqMap) {
std::priority_queue<HuffmanNode*, std::vector<HuffmanNode*>, decltype(compareNodes)> pq(compareNodes);
for (auto& pair : freqMap) {
pq.push(new HuffmanNode(pair.first, pair.second));
}
while (pq.size() > 1) {
HuffmanNode* left = pq.top(); pq.pop();
HuffmanNode* right = pq.top(); pq.pop();
HuffmanNode* newNode = new HuffmanNode('\0', left->freq + right->freq);
newNode->left = left;
newNode->right = right;
pq.push(newNode);
}
return pq.top();
}
// 生成霍夫曼编码
std::string huffmanCode(HuffmanNode* root, char data) {
std::string code;
HuffmanNode* current = root;
while (current != nullptr) {
if (data == current->data) {
return code; // 返回当前字符的编码
}
code += '0' + (current->left ? 1 : 0); // 根据左孩子还是右孩子决定添加0或1
current = current->left ? current->left : current->right;
}
throw std::runtime_error("Character not found in the tree");
}
int main(int argc, char* argv[]) {
if (argc < 3) {
std::cerr << "Usage: program input_file output_file" << std::endl;
return 1;
}
std::ifstream inputFile(argv[1], std::ios::binary);
if (!inputFile.is_open()) {
std::cerr << "Error opening source file." << std::endl;
return 1;
}
std::map<char, int> freqMap;
char byte;
while (inputFile.read(reinterpret_cast<char*>(&byte), 1)) {
++freqMap[byte];
}
inputFile.close();
HuffmanNode* huffmanRoot = buildHuffmanTree(freqMap);
std::ofstream outputFile(argv[2], std::ios::binary);
if (!outputFile.is_open()) {
std::cerr << "Error opening target file." << std::endl;
delete huffmanRoot;
return 1;
}
for (const auto& pair : freqMap) {
char data = pair.first;
std::string encoded = huffmanCode(huffmanRoot, data);
outputFile.write(encoded.c_str(), encoded.length());
}
delete huffmanRoot;
outputFile.close();
阅读全文
相关推荐


















