huffman压缩文件

Love The Way You Lie 2022-05-05 06:28 179阅读 0赞

#include <iostream>
    #include <math.h>
    #include <map>
    #include <queue>
    #include <stdlib.h>
    #include <fstream>
    #include <string.h>
    using namespace std;
    
    typedef struct node{
    	char ch;
    	int val;
    	char num;
    	struct node *self,*left,*right;
    	friend bool operator < (const node &a,const node &b)
    	{
    		return a.val > b.val;
    	}
    }node;
    
    priority_queue<node> p;
    char res[30];
    char code[10000];
    string s[256];		//哈夫曼编码 
    string str;			//文件编码01集合 
    string myCode;		//压缩过后编码 
    void dfs(node *root,int level)  //对huffman树编码 
    {
    	if(root->left == root->right)
    	{
    		if(level == 0)
    		{
    			res[0] = '0';
    			level++;
    		}
    		res[level] = '\0';
    		printf("%c => %s\n",root->ch,res);
    		for(int i = 0;res[i]!='\0';i++)
    		{
    			s[(int)root->ch] += res[i];
    		}
    	}
    	else
    	{
    		res[level] = '0';
    		dfs(root->left,level+1);
    		res[level] = '1';
    		dfs(root->right,level+1);
    	}
    }
    
    void huffman(int *hash)   //生成huffman树 
    {
    	node *root,fir,sec;
    	for(int i = 0 ; i < 256; i++)
    	{
    		if(!hash[i])
    			continue;
    		root=(node *)malloc(sizeof(node));
    		root->self = root;
    		root->left = root->right = NULL;
    		root->ch = i;
    		root->val = hash[i];
    		p.push(*root);
    		
    	}
    	while(p.size()>1)
    	{
    		fir = p.top();
    		p.pop();
    		sec = p.top();
    		p.pop();
    		root = (node *)malloc(sizeof(node));
    		root->self = root;
    		root->left = fir.self;
    		root->right = sec.self;
    		root->left->num = '0';
    		root->right->num = '1';
    		root->val = fir.val+sec.val;
    		p.push(*root);
    	}
    	fir=p.top();
    	p.pop();
    	dfs(fir.self,0);
    }
    
    int read_file()  //读取文件 
    {
    	int length=0;
    	ifstream inf("12345.txt");
    	while(!inf.eof())
    	{
    		inf >> code[length++];
    	}
    	inf.close();
    	return length;
    }
    
    void write_file()
    {
    	for(int i=0;code[i]!='\0';i++)
    	{
    		str += s[(int)code[i]];
    	}
    	cout << str << endl;
    	int sum = 0;
    	for(int i = 0,j = 0; i < str.length(); i++,j++,j = j % 7)
    	{
    		sum += pow((str[i]-'0')*2,6-j);
    		if(j==6)
    		{
    			myCode += (char)sum;
    			cout << sum << endl;
    			sum = 0;
    		}
    	}
    	ofstream open("myCode");
    	open << myCode;
    	open.close();
    }
    
    int main()
    {
    	read_file();
    	int hash[256];
    	memset(hash,0,sizeof(hash));
    	for(int i=0;code[i]!='\0';i++)
    	{
    		hash[(int)code[i]]++;
    	}
    	node* huffm = huffman(hash);
    	write_file();
    	
    	return 0;
    }