halfuman/hal.cpp

#include <iostream>
#include <fstream>
#include <cassert>
#include <string>
#include <string.h>
using namespace std;
struct HNode
{
    HNode *parent;
    HNode *lch, *rch;
    int weight,codelen;
    char data;  
    char *code; //<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
};
//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͣ<EFBFBD>ָ<EFBFBD>룩
typedef HNode* HTree;
typedef HNode* ElemType;
//˳<><CBB3><EFBFBD>
typedef struct
{
    ElemType *elem;
    int length; //<2F><>ǰ<EFBFBD><C7B0><EFBFBD>ݵ<EFBFBD>ʵ<EFBFBD>ʳ<EFBFBD><CAB3><EFBFBD>(<28>ж<EFBFBD><D0B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>)
} seqList;
//<2F><><EFBFBD><EFBFBD>˳<EFBFBD><CBB3><EFBFBD>ht<68><74><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ź<EFBFBD><C5B9><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ľ<EFBFBD><C4BD>
seqList ht;

//<2F><>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҷ<EFBFBD>ӽ<EFBFBD><D3BD><EFBFBD><EFBFBD>Ϣ<EFBFBD><CFA2><EFBFBD>뵽˳<EBB5BD><CBB3><EFBFBD>
//a:Ȩֵ<C8A8><D6B5>b<EFBFBD><62>Ҷ<EFBFBD><D2B6><EFBFBD><EFBFBD>ַ<EFBFBD><D6B7><EFBFBD>n<EFBFBD><6E>Ҷ<EFBFBD><D2B6><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
void input(int a[], char b[], int n)
{
    for (int i = 0; i < n; i++)
    {
        HNode *tmp = new HNode;
        tmp->parent = NULL;
        tmp->weight = a[i];
        tmp->data = b[i];
        tmp->lch = NULL;
		tmp->rch = NULL;
        ht.elem[i]=tmp;
        ht.length++;
    }
}
// n:<3A>±<EFBFBD>Ϊ[0~n)<29><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>n<EFBFBD><6E><EFBFBD><EFBFBD>˳<EFBFBD><CBB3><EFBFBD>ht<68><74> 0~n<><6E>ѡ<EFBFBD><D1A1>2<EFBFBD><32>Ȩֵ<C8A8><D6B5>С<EFBFBD>Ľ<EFBFBD>㣬<EFBFBD><E3A3AC><EFBFBD><EFBFBD>±<EFBFBD><C2B1>ŵ<EFBFBD>s1,s2<73><32>
void selectMin(int n, int &s1, int &s2)
{   		
    int m1 = 0x7fff;
	int m2 = 0x7fff;			// m1ȡ<31><C8A1>СȨ<D0A1>أ<EFBFBD>m2ȡ<32><C8A1>СȨ<D0A1><C8A8>
    int lnode = 0;
	int rnode = 0;     		// lnode, rnode<64>ֱ<EFBFBD>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD><EFBFBD><EFBFBD>СȨ<D0A1>صĽ<D8B5><C4BD>λ<EFBFBD><CEBB>
    for(int k=0; k<n; k++){
	    if(ht.elem[k]->parent==NULL){
			if(ht.elem[k]->weight<m1) {
	            m2 = m1;  rnode=lnode;
				m1 = ht.elem[k]->weight;  lnode=k;
			}
			else if(ht.elem[k]->weight<m2) {
				m2 =ht.elem[k]->weight;
				rnode = k;
			}
        }
	}
	s1=lnode;
	s2=rnode;
}
//<2F><><EFBFBD><EFBFBD>n<EFBFBD><6E>Ҷ<EFBFBD>ӽ<EFBFBD>㴴<EFBFBD><E3B4B4><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>cht<68><74>
void creatHt(HTree &cht, int n)
{
    HNode tNode;
    int m = 2 * n - 1;
    int s1, s2;
    //<2F><>ʼ0~n-1<><31>ѡ
    for (int i = n; i < m; i++)
    {
        HNode *r = new HNode;
        r->parent = NULL;
        selectMin(i, s1, s2);
        r->weight=ht.elem[s1]->weight+ht.elem[s2]->weight;
        r->lch=ht.elem[s1];
        r->rch=ht.elem[s2];
        ht.elem[s1]->parent=r;
        ht.elem[s2]->parent=r;
        ht.elem[i]=r;
        ht.length++;
    }
    cht = ht.elem[m-1];
}
void printHfTreePre(HTree t)//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> 
{
    if (t != NULL)
    {
        if (t->lch == NULL && t->rch == NULL)
        {
            cout << "weight:" << t->weight << " " << t->data << ":" <<t->code <<  endl;//
        }
        printHfTreePre(t->lch);
        printHfTreePre(t->rch);
    }
}
void hufmadecode(char* filename,HTree t,char *ziped,int len){//<2F><><EFBFBD><EFBFBD>ѹ<EFBFBD><D1B9><EFBFBD>ĵ<EFBFBD> 
	ifstream infile(filename);
	if(!infile.is_open()){
		cerr<<"ifstream open file error\n";
		return;
	}
	infile.seekg(0,ios_base::end);
	int length = infile.tellg();
	infile.seekg(ios_base::beg);
	char* buff=new char[length+1]();
	infile.read(buff,length+1);
	int count =0;
	for(int i=0;i<length+1;i++){
		for(int j=0;j<len;j++){
			if(buff[i]==ht.elem[j]->data){
				strcpy(ziped+count,ht.elem[j]->code);
				count+=ht.elem[j]->codelen;
				break;
			}
		}
	}
	ziped[count+1]='\0';
	infile.close();
}

//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±<EFBFBD><C2B1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
void hufEncode(HTree t, int k, char *code)
{
    if (t == NULL)
        return;
    if (t->lch == NULL && t->rch == NULL)
    {
        code[k] = '\0';
        t->code = new char[k + 1];
        strncpy(t->code, code ,k + 1); 
        t->codelen=k;
    }
    if(t->lch != NULL){
    	code[k]='0';
    	hufEncode(t->lch, k+1, code);
	}
	if(t->rch != NULL){
    	code[k]='1';
    	hufEncode(t->rch, k+1, code);
	}   
}
//<2F><><EFBFBD><EFBFBD>: <20><><EFBFBD><EFBFBD><EFBFBD>dec<65><63>
void hufDecode(HTree &ht, char str[], char *dec)
{

    HNode *t = ht;
    while (*(str+1))
    {
        if(*str=='0')t=t->lch;
        else t=t->rch;
        if(t->lch==NULL&&t->rch==NULL){
        	cout<<t->data;
        	t=ht;
		}
        str++;
    }
}

int Search(char *a,char ch)
{//<2F><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD>ch<63><68><EFBFBD>ڵ<EFBFBD>λ<EFBFBD>ã<EFBFBD><C3A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±꣬<C2B1><EAA3AC><EFBFBD>򷵻<EFBFBD>-1
	for(int i=0;a[i]!='\0';i++){
        if(a[i]==ch)return i;
    }
    return -1;
}
/*
ͳ<EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD><EFBFBD>ij<EFBFBD><EFBFBD>ִ<EFBFBD><EFBFBD><EFBFBD>
freq<EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ŵ<EFBFBD><EFBFBD><EFBFBD>
letters<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD>
*/

int countLetter(char* filename, int *freq, char *letters)
{
    ifstream infile(filename);
	if(!infile.is_open()){
		cerr<<"ifstream open file error\n";
		return 0;
	}
	infile.seekg(0,ios_base::end);
	int length = infile.tellg();
	infile.seekg(ios_base::beg);
	char* buff=new char[length+1]();
	infile.read(buff,length+1);
	int count=0;
	for(int i=0;i<length+1;i++){
	//	cout<<buff[i];
        int x=Search(letters,buff[i]);
        if(x==-1){
            letters[count++]=buff[i];
            letters[count]='\0';
        }
        x=Search(letters,buff[i]);
        freq[x]++;
    }
	infile.close();
	return count-1;
}
int main()
{
    HTree htt=NULL;
    int freq[128] = {0};
    char letters[128] = {'\0'};
    int len;
    char dec[10000],code[100],zipped[100000];
    const char *choe="end",*chob="begin",*choz="zipped",*choc="checktree",*chod="decode",*choo="help";
    char s[100];//="C:\\Users\\<5C><>а\\Desktop\\<5C><><EFBFBD><EFBFBD>vc2019\\dev\\hhh.txt";
    cout<<"-----------------------------------------"<<endl;
    cout<<"    <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʾ"<<endl; 
    cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>begin<EFBFBD><EFBFBD>ʼ"<<endl; 
    cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>end<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl; 
    cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>zippedչʾѹ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD>"<<endl; 
    cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>checktree<EFBFBD>鿴<EFBFBD><EFBFBD>Ҷ<EFBFBD>ӽ<EFBFBD><EFBFBD>Ȩ<EFBFBD>غͱ<EFBFBD><EFBFBD><EFBFBD>"<<endl; 
    cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>decode<EFBFBD>鿴<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD>"<<endl; 
    cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>help<EFBFBD>鿴<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl;
    cout<<"-----------------------------------------"<<endl;
    cin>>s;
    while(strcmp(s,choe)){
    	if(strcmp(s,chob)==0){
            cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>txt<EFBFBD>ļ<EFBFBD>·<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"; 
		    cin>>s;
            len = countLetter(s, freq, letters);
            cout<<"-----------------------------------------"<<endl;
            cout<<"<EFBFBD>ַ<EFBFBD>ͳ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϣ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<len<<"<EFBFBD><EFBFBD><EFBFBD>ַ<EFBFBD>"<<endl;
            ht.elem=new ElemType[len*2-1];
            ht.length=0;
			input(freq,letters,len);
            cout<<"˳<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʼ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɣ<EFBFBD>"<<endl;
			creatHt(htt, len);
			cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ɣ<EFBFBD>"<<endl;
			hufEncode(htt, 0, code);
			cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>봴<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl; 
			hufmadecode(s,htt,zipped,len);
			cout<<"<EFBFBD>ļ<EFBFBD>ѹ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl; 
			cout<<"-----------------------------------------"<<endl;
		}
  //  seqListInit(ht,len*2-1);
        else if(strcmp(s,choz)==0){
		    cout<<"-----------------------------------------"<<endl;
        	if(*zipped){
        	    cout<<"ѹ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>£<EFBFBD>"<<endl;
		        cout<<zipped<<endl;
		    }
		    else{
		    	cout<<"<EFBFBD><EFBFBD>û<EFBFBD><EFBFBD>ѹ<EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʹ<EFBFBD><EFBFBD>begin<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl;
			} 
			cout<<"-----------------------------------------"<<endl;
		}
        else if(strcmp(s,choc)==0){
        	cout<<"-----------------------------------------"<<endl;
        	if(htt!=NULL){
        	    cout<<"<EFBFBD><EFBFBD><EFBFBD>ڵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>£<EFBFBD>"<<endl;
		        printHfTreePre(htt);
		    }
		    else{
		    	cout<<"δ<EFBFBD>ҵ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʹ<EFBFBD><EFBFBD>begin<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl; 
			}
		    cout<<"-----------------------------------------"<<endl; 
		}
        else if(strcmp(s,chod)==0){
        	if(*zipped){
        	    cout<<"-----------------------------------------"<<endl; 
        	    cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>£<EFBFBD>"<<endl;
		        hufDecode(htt, zipped, dec);
		        cout<<endl<<"-----------------------------------------"<<endl; 
			}
			else{
				cout<<"-----------------------------------------"<<endl;
				cout<<"<EFBFBD><EFBFBD>û<EFBFBD><EFBFBD>ѹ<EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD><EFBFBD><EFBFBD><EFBFBD>޷<EFBFBD><EFBFBD><EFBFBD><EFBFBD>룡<EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʹ<EFBFBD><EFBFBD>begin<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl;
				cout<<"-----------------------------------------"<<endl;
			} 
		}
        else if(strcmp(s,choo)==0){
        	cout<<"-----------------------------------------"<<endl;
        	cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>begin<EFBFBD><EFBFBD>ʼ"<<endl; 
            cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>end<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl; 
            cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>zippedչʾѹ<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD>"<<endl; 
            cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>checktree<EFBFBD>鿴<EFBFBD><EFBFBD>Ҷ<EFBFBD>ӽ<EFBFBD><EFBFBD>Ȩ<EFBFBD>غͱ<EFBFBD><EFBFBD><EFBFBD>"<<endl; 
            cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>decode<EFBFBD>鿴<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ļ<EFBFBD>"<<endl; 
            cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD>help<EFBFBD>鿴<EFBFBD><EFBFBD><EFBFBD><EFBFBD>"<<endl;
            cout<<"-----------------------------------------"<<endl;
		}
	    else {
	    	cout<<"-------------------------------------------------"<<endl;
	    	cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>룡(<28><><EFBFBD><EFBFBD>help<6C>鿴<EFBFBD><E9BFB4><EFBFBD><EFBFBD>)"<<endl;
	    	cout<<"-------------------------------------------------"<<endl;
		}
		cout<<"<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><EFBFBD>ָ<EFBFBD>"; 
	    cin>>s;
	}
	return 0;
}