C++代码 赫夫曼编译

《C++代码 赫夫曼编译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、/*置以下数据于f:\临时\aa.txt：8529781423311ABCDEFGHAHDC*///------------------------赫夫曼编码-----------------------------#include#include#include#include#includeusingnamespacestd;//---------------------------------------------------------------typed

2、efstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼编码表classHuffman{private:HuffmanTreeHT;//储赫夫曼树HuffmanCodeHC;//赫夫曼编码表int*w;//频度stringstr;//字符串intn;//n个字符public:voidInitialization(ifstream&in);//初始化voidH

3、uffmanCoding();//赫夫曼编码voidSelect(inth,int&s1,int&s2,intl);//查找两个最小值voidEncoding(ifstream&in,ofstream&out);//编码voidDecoding();//译码voidPrintH();//输出编码};//---------------------------------------------------------------intmain(){ifstreamin("f:\临时\aa.txt");ofstreamout("f:\临时\bb.txt");

4、Huffmanhuffman;huffman.Initialization(in);huffman.HuffmanCoding();huffman.PrintH();huffman.Encoding(in,out);huffman.Decoding();return0;}//---------------------------------------------------------------voidHuffman::HuffmanCoding(){//w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。if(n<=1)ret

5、urn;intm=2*n-1,i,l=1,c,f,start;HuffmanTreep;//0号单元未用HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//*/HT=newHTNode[m+1];for(p=HT+1,i=1;i<=n;i++,p++,w++){p->weight=*w;p->lchild=0;p->rchild=0;p->parent=0;}for(;i<=m;i++,p++){p->weight=0;p->lchild=0;p->rchild=0;p->parent=0;}for(i=n+1;i<=m

6、;i++,l++){//建赫夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。ints1,s2;Select(i-1,s1,s2,l);//cout<

7、)malloc((n+1)*sizeof(char*));//*/HC=newchar*[n+1];//分配求编码的工作空间char*cd=(char*)malloc(n*sizeof(char));//*/char*cd=newchar[n];cd[n-1]='';//不是双引号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].lchild==c)cd[--start]='0

8、';elsecd[--s