- #include<iostream>
- #include<fstream>
- #include<string>
- #include<vector>
- using namespace std;
- typedef char **huffmancode;
- struct node
- {
- char ch;
- int weight;
- node():ch('\\0'),weight(0){}
- };
- typedef struct htnode
- {
- node data;
- unsigned parent,left,right;
- htnode():data(),parent(0),left(0),right(0){}
- }*huffman;
- int file_string(string filename,string& svec)
- {
- //________________________________________读文件内容
- ifstream infile(filename.c_str());
- if(!infile)
- {
- return 1;
- }
- string s;
- while(getline(infile,s))
- svec=s;
- infile.close();
- if(infile.eof())
- return 4;
- if(infile.bad())
- return 2;
- if(infile.fail())
- return 3;
- }
- void change(string s,vector<node>& vec)
- {
- //___________________________________________将字符装进vec容器,并统计概率
- vector<node>::iterator j;
- for(string::size_type i=0;i!=s.size();++i)
- {
- node temp;temp.ch=s[i];temp.weight=1;
- for(j=vec.begin();j!=vec.end();j++)
- {
- if(j->ch==temp.ch)
- {
- j->weight++;
- break;
- }
- }
- if(j==vec.end())
- vec.push_back(temp);
- }
- for(vector<node>::size_type i=0;i!=vec.size();++i)
- vec[i].weight=100*vec[i].weight/s.size();
- }
- int min(htnode *ht,int i)
- {
- int j,flag;unsigned k=60000;
- for(j=1;j<=i;++j)
- if(ht[j].data.weight<k&&ht[j].parent==0)
- k=ht[j].data.weight,flag=j;
- ht[flag].parent=1;
- return flag;
- }
- void select(htnode *ht,int i,int &s1,int &s2)
- {
- //_________________________________________选择两个权值最小项
- int j;
- s1=min(ht,i);
- s2=min(ht,i);
- if(s1<s2)
- {
- j=s1;
- s1=s2;
- s2=j;
- }
- }
- void huffmantree(huffman &HT,huffmancode &HC,vector<node> vec,int n)
- {
- //_________________________________________________构造赫夫曼树HT
- int m,i,s1,s2,start;
- unsigned c,f;
- huffman p;
- char *cd;
- if(n<=1)
- return;
- m=2*n-1;
- vector<node>::iterator it;
- HT=(huffman)malloc((m+1)*sizeof(htnode));
- for(p=HT+1,i=1,it=vec.begin();i<=n;++i,++p,++it)
- {
- p->data=*it;
- p->parent=0;
- p->left=0;
- p->right=0;
- }
- for(;i<=m;++i,++p)
- p->parent=0;
- for(i=n+1;i<=m;++i)
- {
- select(HT,i-1,s1,s2);
- HT[s1].parent=HT[s2].parent=i;
- HT[i].left=s1;
- HT[i].right=s2;
- HT[i].data.weight=HT[s1].data.weight+HT[s2].data.weight;
- }
- //___________________________________________________________从叶子到根求每个字符的赫夫曼编码
- HC=(huffmancode)malloc((n+1)*sizeof(char*));
- cd=(char*)malloc(n*sizeof(char));
- cd[n-1]='\\0';
- for(i=1;i<=n;i++)
- {
- start=n-1;
- for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
- if(HT[f].left==c)
- cd[--start]='0';
- else
- cd[--start]='1';
- HC[i]=(char*)malloc((n-start)*sizeof(char));
- strcpy(HC[i],&cd[start]);
- }
- free(cd);
- }
- int main()
- {
- //_____________________________________________________________主函数
- string filename,str;
- cout<<"输入文件名:"<<endl;
- cin>>filename;
- switch(file_string(filename,str))
- {
- case 1:
- cout<<"打开失败"<<filename<<endl;
- return -1;
- case 2:
- cout<<"系统错误"<<endl;
- return -1;
- case 3:
- cout<<"读文件错误!"<<endl;
- return -1;
- }
- cout<<str<<endl;
- vector<node> vec;
- change(str,vec);
- for(vector<node>::size_type i=0;i!=vec.size();++i)
- cout<<vec[i].ch<<" "<<vec[i].weight<<endl;
- //______________________________________________________
- int n=vec.size();
- cout<<n<<endl;
- huffman ht;huffmancode hc;
- huffmantree(ht,hc,vec,n);
- for(int i=1;i<=n;i++)
- puts(hc[i]);
- //_______________________________________________
- string ss;
- cout<<"请输入编码:"<<endl;
- cin>>ss;
- string d;
- for(string::size_type mm=0;mm!=ss.size();)
- {
- int parent=2*n-1;
- while(ht[parent].left!=0)
- {
- if(ss[mm]=='0')
- parent=ht[parent].left;
- else
- parent=ht[parent].right;
- ++mm;
- }
- d=d+ht[parent].data.ch;
- }
- cout<<d<<endl;
- //_________________________________创建string.txt文件,向其中存入d的内容
- ofstream SaveFile("string.txt");
- SaveFile<<d;
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/310520133720.html
来源: http://www.codesnippet.cn/detail/310520133720.html