能不能给我个程序,程序实在不会,用哈夫曼编码实现文件压缩和结压缩的C语言,程序,江湖救急
读一原来文本文件
能压缩生成一压缩文件
能计算出压缩率
删除原文本文件后,能用压缩文件还原出文本文件
能不能给我个程序,程序实在不会,用哈夫曼编码实现文件压缩和结压缩的C语言,程序,江湖救急
读一原来文本文件
能压缩生成一压缩文件
能计算出压缩率
删除原文本文件后,能用压缩文件还原出文本文件
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
//#include <bitset>
#include <fstream>
#include <ctime>
const int maxCodeNum = 256;
using namespace std;
//哈夫曼树的树节点
struct HaffTreeNode{
HaffTreeNode * lNode;
HaffTreeNode * rNode;
string haffCode;
int value;
int alpha;
HaffTreeNode()
:lNode(NULL), rNode(NULL), haffCode(""), value(0), alpha(0){;}
};
//链表节点,用于生成哈夫曼树
struct ListNode{
struct HaffTreeNode HaffTreeNode;
ListNode *nextListNode;
ListNode()
:nextListNode(NULL){;}
};
//用与保存输入文件统计信息的hash表
typedef struct HashTable{
int value;
int alpha;
HashTable()
:value(0), alpha(0){}
//比较函数用于排序使用
inline friend int operator-(const HashTable & a, const HashTable & b){
return a.value - b.value;
}
} HashTable;
HashTable charHashTable[maxCodeNum];
//排序使用的比较大小的函数
int hashComp(const void * a, const void * b)
{
return *((HashTable *)a) - *((HashTable *)b);
}
//创建一个哈夫曼树
HaffTreeNode * createHaffTreeNodeTree(HashTable table[])
{
ListNode *root = new ListNode;
ListNode *next = root;
for(int i = 0; /*i < maxCodeNum - 1*/; ++i){
if(table[i].value == 0)//如果对应的码不为0,就为其分配一个树节点
continue;
next->HaffTreeNode.alpha = table[i].alpha;
next->HaffTreeNode.value = table[i].value;
if(i ==maxCodeNum - 1)
break;
next->nextListNode = new ListNode;
next = next->nextListNode;
}
while(root->nextListNode != NULL){
ListNode * currNode = new ListNode;
currNode->HaffTreeNode.value = root->HaffTreeNode.value + root->nextListNode->HaffTreeNode.value;
currNode->HaffTreeNode.lNode = &(root->HaffTreeNode);
currNode->HaffTreeNode.rNode = &(root->nextListNode->HaffTreeNode);
root = root->nextListNode->nextListNode; //概率最小的两个码相加组成一个新的节点
ListNode * nextNode = root;
ListNode * prevNode = NULL;
while(nextNode != NULL && currNode->HaffTreeNode.value > nextNode->HaffTreeNode.value){
prevNode = nextNode;
nextNode = nextNode->nextListNode;
}
if(prevNode == NULL){//将这个新的节点插入到所有节点之前(currNode目前还是最小的)
currNode->nextListNode = nextNode;
root = currNode;
}else{//插入到节点中间或者节点之后的位置
prevNode->nextListNode = currNode;
currNode->nextListNode = nextNode;
}
}//在这个list中所有的元素遍历完成之后返回
return &(root->HaffTreeNode);//返回书的根节点的哈弗满节点,这个节点已经构造成为了一棵树
}
string huffmanCodeTable[maxCodeNum];
string haffCode;
//给哈夫曼树编码
void createHaffmanTable(HaffTreeNode * root)
{
if(root->lNode == NULL && root->rNode == NULL){
huffmanCodeTable[root->alpha] = haffCode;
haffCode.erase(haffCode.length() - 1);
return;
}//给各个节点赋予相应的哈夫曼编码
haffCode.append("0");
createHaffmanTable(root->lNode);
haffCode.append("1");
createHaffmanTable(root->rNode);
if(!haffCode.empty()){
haffCode.erase(haffCode.length() - 1);
}
return;
}
//将生成的二进制长串编码转换成字符用于存储在压缩文件中
unsigned char StrToBin(string str)
{
unsigned int ans =0;
int tmpNum = atoi(str.c_str());
int multiNum = 1;
while(tmpNum != 0){
ans += tmpNum%10*multiNum;
tmpNum/=10;
multiNum *= 2;
}
return (unsigned char) ans;
}
//用于将压缩文件的字符转换成huffman编码
string BinToStr(unsigned char c)
{
string tmpNumStr;
while(c != 0){
tmpNumStr.insert(tmpNumStr.begin(), (unsigned char)(c%2 + '0'));
c /= 2;
}
if(tmpNumStr.length() < 8){
tmpNumStr.insert(tmpNumStr.begin(), 8 - tmpNumStr.length(), '0');
}
return tmpNumStr;
}
//下面是将huffman码译成原字符的程序
char huffDecode(HaffTreeNode * root, string & code)
{
unsigned int i;
for( i = 0; i < code.length(); ++i){
if(root->alpha == 0)
root = (code[i] - '0')?root->rNode:root->lNode;
else{
code.erase(0, i);
return root->alpha;
}
}
if(root->alpha !=0){
code.erase(0, i);
return root->alpha;
}
code.clear();
return '\0';
}
int main(int argc, char ** argv)
{
if(argc != 3){
printf("Error number of arguments!\n");
}
FILE * fin = fopen(argv[1], "r");
int c = 0;
while((c = fgetc(fin)) != EOF && c != '\n'){
putchar(c);
putchar('*');
charHashTable[c].alpha = c;
charHashTable[c].value++;
}
qsort(charHashTable, sizeof(charHashTable)/sizeof(charHashTable[0]),
sizeof(charHashTable[0]), hashComp);
/*建立有关本文件的huffman树*/
HaffTreeNode * haffTreeRoot = createHaffTreeNodeTree(charHashTable);
createHaffmanTable(haffTreeRoot);
cout << "Char\tTimes\tCodes";
for(int i = 0; i < maxCodeNum; ++i){
if(charHashTable[i].value != 0){
cout << (char)charHashTable[i].alpha << "\t" << charHashTable[i].value
<< "\t" << huffmanCodeTable[charHashTable[i].alpha] << "\n";
}
}
FILE * fout;
if((fout = fopen(argv[2], "w")) == NULL){
perror("open output file error!\n");
}
rewind(fin);
string buf;
while((c = fgetc(fin)) != EOF){ /*将文件通过huffman码转来进行压缩*/
//printf("The char is %c ", c);
buf += huffmanCodeTable[c];
cout << buf << endl;
if(buf.length() > 8){ //当转换的字符得到的huffman码达到8的时候转换成一个字符填入目标文件
fputc(StrToBin(buf.substr(0, 8)), fout);
buf.erase(0, 8);
}
}
int leftZero = 0; //保存不到8位的余留位的个数
if(!buf.empty()){
buf.append((leftZero = 8 - buf.length()), '0');
fputc(StrToBin(buf), fout);
}
if(fclose(fin) == -1)
perror("close file error!\n");
if(fclose(fout) == -1)
perror("close file error!\n");
if((fin = fopen(argv[2], "rb")) == NULL)//打开压缩文件,开始解码
perror("Open file error!\n");
if((fout = fopen("huffmanDecompose.txt", "w")) == NULL)
perror("Open file error!\n");
//开始解码
int bin;
buf.clear();
while((bin = fgetc(fin)) != EOF){
buf.append(BinToStr(bin));
}
while(buf.length() - leftZero != 0 && !buf.empty()){
fputc(huffDecode(haffTreeRoot, buf), fout);
}
if(fclose(fin) != 0)
perror("close file error!\n");
if(fclose(fout) != 0)
perror("close file error!\n");
return 0;
}