C++代码 赫夫曼编译.doc

/*置以下数据于f:临时aa.txt：8529781423311ABCDEFGHAHDC*/-赫夫曼编码-#include#include#include#include#includeusing namespace std;/-typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表class Huffmanprivate: HuffmanTree HT; /储赫夫曼树 HuffmanCode HC; /赫夫曼编码表 int *w; /频度 string str; /字符串 int n; /n个字符public: void Initialization(ifstream &in); /初始化 void HuffmanCoding(); /赫夫曼编码 void Select(int h,int &s1,int &s2,int l); /查找两个最小值 void Encoding(ifstream &in,ofstream &out);/编码 void Decoding(); /译码 void PrintH(); /输出编码;/-int main()ifstream in(f:临时aa.txt);ofstream out(f:临时bb.txt);Huffman huffman;huffman.Initialization(in);huffman.HuffmanCoding();huffman.PrintH();huffman.Encoding(in,out);huffman.Decoding();return 0;/-void Huffman:HuffmanCoding()/w存放n个字符的权值(均0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。if(n = 1) return;int m = 2 * n - 1,i,l = 1,c,f,start;HuffmanTree p;/0号单元未用HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode); /*/HT = new HTNodem+1;for(p = HT + 1,i = 1;i weight = *w;p-lchild = 0;p-rchild = 0;p-parent = 0;for(;i weight = 0;p-lchild = 0;p-rchild = 0;p-parent = 0;for(i = n + 1;i = m;i+,l+)/建赫夫曼树/在HT1.i-1选择parent为0且weight最小的两个结点，其序号分别为s1和s2。int s1,s2;Select(i - 1,s1,s2,l);/couts1 s2endl;HTs1.parent = i;HTs2.parent = i;HTi.lchild = s1;HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;/- - - 从叶子到根逆向求每个字符的赫夫曼编码 - - -/分配n个字符编码的头指针向量HC = (HuffmanCode)malloc(n+1)*sizeof(char*);/*/HC = new char*n+1;/分配求编码的工作空间char *cd = (char *)malloc(n*sizeof(char);/*/char *cd = new charn;cdn-1 = 0;/不是双引号for(i = 1;i = n;i+) /逐个字符求赫夫曼编码start = n - 1; /编码结束符位置for(c = i,f = HTi.parent;f != 0;c = f,f = HTf.parent) /从叶子到根逆向求编码if(HTf.lchild = c) cd-start = 0;elsecd-start = 1;/为第i个字符编码分配空间HCi = (char *)malloc(n - start)*sizeof(char); /*/HCi = new charn-start;strcpy(HCi,&cdstart); /从cd复制编码(串)到HCdelete cd;/释放工作空间/HuffmanCoding/-void Huffman:Select(int h,int &s1,int &s2,int l) /在HT1.n选择parent为0且weight最小的两个结点，返回其序号分别为s1和s2。int x = 0,y = 0,z;for(int i = 1;i = h;i+) if(HTi.parent != 0)continue;/parent不为0，则跳到下一次循环 int k = 0; for(int j = 1;j = h;j+) if(HTi.weight = h-2*l+2) /找到最小值s1 s1 = i; if(y = 0) z = i;/标记第一个最小值，解决两个最小值相等的问题 x+; y+; /if if(k = h-2*l+1) /找到最小值s2 s2 = i; x+; /if if(y = 2) /两个最小值相等 s1 = z; s2 = i; /if if(x = 2) if(s2 n)/使s2成为右孩子 int t = s2; s2 = s1; s1 = t; break;/找到两个最小值 /if/for/-void Huffman:Initialization(ifstream &in) /初始化inn;w = new intn;for(int i = 0;i wi;instr;/-void Huffman:PrintH() /输出编码cout-赫夫曼编码-endl;coutweight parent lchild rchild endl;coutstring(30,-)endl;for(int i = 1;i = 2*n -1;i+)coutsetw(5)setfill( )HTi.weightsetw(8)setfill( )HTi.parentsetw(7)setfill( )HTi.lchildsetw(7)setfill( )HTi.rchildendl;coutstring(30,=)endl;coutInfo weight HCendl;coutstring(22,-)endl;for(i = 1;i = n;i+)coutsetw(2)setfill( )stri-1setw(7)setfill( )HTi.weightsetw(8)setfill( ) HCiendl;coutstring(22,=)s;cout需要编码的文字：sendl;for(i = 0;i s.size();i+)for(j = 0;j n;j+)if(si = strj)t += HCj+1;k = 1;/ifif(k = 0)cout输入的文字有误！n;cout编成的代码：tendlendl;outtendl;couts;cout需要编译的代码：sendl;int i,j,k = 0,l,m;for(i = 1;k s.size();i+)for(j = 0,l = k;/*j sizeof(HC)/sizeof(*HCi)*/HCij != 0;j+,k+)m =