实验51 赫夫曼编译

1、界面输入字符串并进行编码进行译码对附件统计字符频率并编码字符出现频率最少，编码为:0011001011011,0011001011010,0011001100101,0011001100101和001100101100.字符空格,e,t,a,i,s是出现频率最高，编码为:(好像出错了L)编译后的文件大小为：909kb，比原文件小了一半多。源代码：#include stdafx.h#ifndef HUFFMAMCODE_H #define HUFFMAMCODE_H#include#includeusing namespace std;struct HuffmanNode /定义哈夫曼树各结点i

2、nt weight;int parent;int lchild, rchild;int flag;class HuffmanCode1 /哈夫曼编码类public:char Info100;int Start;char Leaf;class HuffmanTree1 /建立哈夫曼树类private:HuffmanNode *Node;public:int f;HuffmanCode1 *hf;HuffmanTree1();HuffmanTree1();void TranslatedCode();void CodeHuf(HuffmanNode a, HuffmanCode1 b, int n)

3、;void CreateHfmTree(char Str, int m, int n);void TransCode(HuffmanCode1 b, int n);void TranslateArtcle(HuffmanCode1 b, int n);#endif /HUFFMAMCODE_HHuffmanCode.cpp#include iostream#include#include math.h#include stdlib.h#includeusing namespace std;#define MAXDATA 100000 /最长字符串#define MAXSIZE 1500 /最多

4、子叶数/读取文件部分功能实现的代码$HuffmanTree1:HuffmanTree1()Node = NULL; /将树结点初始化为HuffmanTree1:HuffmanTree1()delete Node; /释放结点空间 void HuffmanTree1:CreateHfmTree(char Str, int m, int n)/建立哈夫曼树int i, j, m1, m2, x1, x2;HuffmanNode *HfmNode = new HuffmanNode2 * n - 1;HuffmanCode1 *HfmCode = new HuffmanCode1n;for (i =

5、 0; i2 * n - 1; i+)HfmNodei.weight = 0;HfmNodei.parent = 0;HfmNodei.flag = 0;HfmNodei.lchild = -1;HfmNodei.rchild = -1;for (i = 0; in; i+)HfmNodei.weight = mi;HfmCodei.Leaf = Stri;for (i = 0; in - 1; i+)m1 = m2 = 32767;x1 = x2 = 0;for (j = 0; jn + i; j+)if (HfmNodej.weight = m1&HfmNodej.flag = 0)m2

6、= m1;x2 = x1;m1 = HfmNodej.weight;x1 = j;else if (HfmNodej.weight = m2&HfmNodej.flag = 0)m2 = HfmNodej.weight;x2 = j;HfmNodex1.parent = n + i;HfmNodex2.parent = n + i;HfmNodex1.flag = 1;HfmNodex2.flag = 1;HfmNoden + i.weight = HfmNodex1.weight + HfmNodex2.weight;HfmNoden + i.lchild = x1;HfmNoden + i

7、.rchild = x2;CodeHuf(HfmNode, HfmCode, n);TransCode(HfmCode, n);/TranslateArtcle(HfmCode,n); hf = HfmCode; f = n;void HuffmanTree1:CodeHuf(HuffmanNode a, HuffmanCode1 b, int n) /对哈夫曼树进行编码HuffmanCode1 Hfd;int c, p;for (int i = 0; in; i+)Hfd.Start = n - 1;c = i;p = ac.parent;while (p != 0)if (ap.lchil

8、d = c)Hfd.InfoHfd.Start = 0;elseHfd.InfoHfd.Start = 1;Hfd.Start-;c = p;p = ac.parent;printf(%c :, bi.Leaf);for (int j = Hfd.Start + 1; jn; j+)bi.Infoj = Hfd.Infoj;printf(%c, Hfd.Infoj);printf(n);bi.Start = Hfd.Start;void HuffmanTree1:TransCode(HuffmanCode1 b, int n) /对文章进行翻译并保存ifstream ifs(RFCdoc.tx

9、t);ofstream ofs(WCode.txt);char s3200000;int t = 0;char ch;cout * endl;while (ifs.get(ch)if (ch != n)st = ch;for (int i = 0; in; i+)if (st = bi.Leaf)for (int j = bi.Start + 1; jn; j+)ofs bi.Infoj;t+;/printf(n);/printf(报文的编码已经保存在WCode.txt中n);/cout * endl;void HuffmanTree1:TranslateArtcle(HuffmanCode1

10、 b, int n) /将所译的码翻译成文章并保存int t = 0;ifstream ifs(WCode.txt);ofstream ofs(TransWData.txt);string s;getline(ifs, s);for (t = 0; st != 0; t+);int l = 0;int j = 0;printf(报文的译码结果为：n);while (lt)while (jn)int hu = bj.Start + 1;int k = 0;while (hun)if (sl = bj.Infohu)l+;hu+;k+;elsebreak;if (hu = n)printf(%c,

11、 bj.Leaf);ofs bj.Leaf;j = 0; break;elsel = l - k; j+;continue;printf(n);printf(译码的结果已经保存到TransWData.txt中n);cout * endl;void HuffmanTree1:TranslatedCode()ifstream ifs(RFCdoc.txt);char str3200000;char Str3200000;int i = 0, j, m100, h, k = 0;int n = 0;cout * endl;/printf(文件中提取的文章字符串是：n);char ch;while (

12、ifs.get(ch)/printf(%c, ch);if (ch != n)strn+ = ch;printf(n);printf(字符串中共含有字符%d个n, n);for (i = 0; in; i+)j = 0; h = 0;while (stri != strj)j+;if (j = i)Strk = stri;printf(字符%c出现, Strk);elsecontinue;for (j = i; jn; j+)if (stri = strj)h+;printf(%d次n, h);mk = h;k+;cout * endl;printf(字符串中字符种类有%d种n, k);cou

13、t * endl;printf(每个字符对应的哈夫曼编码是：n);CreateHfmTree(Str, m, k);cin.get();/printf(n);/手动输入功能实现的代码$typedef struct /哈弗曼树节点的结构体char info; /关联字符信息unsigned int weight; /每个节点的权职unsigned int parent, lchild, rchild;HTNode, *HuffmanTree;typedef char *HuffmanCode; /存储哈弗曼编码void Select(HuffmanTree HT, int j, int &s1,

14、 int &s2) /选择双亲节点为0，并且最小的两个子叶节点int i = 1, m;while (HTi.parent != 0)i+; /找第一个双亲节点为0的子叶结点for (s2 = s1 = i; ij; i+)/ 保证s1中的权值最小，s2次小if (HTi.parent = 0 & HTi.weight= HTs1.weight & HTi.weight = HTs2.weight)s2 = i;while (HTi.parent = 0 & s1 = s2)m = i;m+;while (HTm.parent != 0)m+;s2 = m;void HuffmanCoding

15、(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info) /哈弗曼编码int i, m;HuffmanTree p;if (n1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m + 1)*sizeof(HTNode);for (p = HT + 1, i = 1; i info = *info;p-weight = *w;p-parent = 0;p-lchild = 0;p-rchild = 0;/forfor (; i weight = 0;p-parent = 0;p-lc

16、hild = 0;p-rchild = 0;/forfor (i = n + 1; i = m; +i) /建立哈弗曼树int s1, s2;Select(HT, i - 1, s1, s2);HTs1.parent = i;HTs2.parent = i;HTi.lchild = s2;HTi.rchild = s1;HTi.weight = HTs1.weight + HTs2.weight;/for/哈弗曼编码HC = (HuffmanCode)malloc(n + 1)*sizeof(char *);char* cd = (char*)malloc(n*sizeof(char);cdn

17、 - 1 = 0;for (i = 1; i = n; +i)int f;unsigned int c;int start = n - 1;for (c = i, f = HTi.parent; f != 0; c = f, f = HTf.parent)if (HTf.lchild = c)cd-start = 0;else cd-start = 1;HCi = (char*)malloc(n - start)*sizeof(char);strcpy(HCi, &cdstart);/forfree(cd);/HuffmanCoding/输出并保存字符串的二进制编码void CheckCodi

18、ng(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m, int k)ofstream ofs(BCode.txt); /查询哈弗曼编码信息int p;int j;for (int i = 0; im; i+)for ( j = 1; HT != strchecki; j+);cout HCj; /输出并保存字符串的二进制编码ofs HCj;cout endl;cout 字符串的二进制编码已经保存在“BCode.txt”中 endl;/cout译码翻译得到的文章已保存在“Data.txt”中endl;cout * endl;

19、cout 各字符对应的编码为: endl; /输出各字符对应的哈夫曼编码for (p = 1; p = k; p+)cout HT : HCp endl;/CheckCodingss/译码过程、对BCode.txt的编码进行译码void HuffmanTranslateCoding2(HuffmanTree HT, int n)ifstream ifs(BCode.txt);ofstream ofs(TransBData2.txt);string c;int m = 2 * n - 1;int i, j = 0;getline(ifs, c);cout 译码翻译得到的文章已保存在“

20、TransBData2.txt”中 endl;cout 译码翻译得到的文章为:;while (cj != 0)i = m;while (HTi.lchild & HTi.rchild)if (cj = 0)i = HTi.lchild;else if (cj = 1)i = HTi.rchild;j+;cout HT; /翻译成字符串并输出和保存ofs HT;void Menushow()cout |*| endl;cout |请输入： | endl;cout | 1 .对您输入的字符串进行编码 | endl;cout | 2 .从文件提取字符串，然后对提取的字符串进行

21、编码 | endl;cout | 3 .对“RFCdoc.txt”生成的二进制编码进行译码 | endl;cout | 4 .退出本系统 | endl;cout |*| endl;cout |温馨提示： | endl;cout | 在执行1操作时务必在您输入的字符串后加上“#” | endl;cout | 译码操作2应在编码操作1后才能进行 | endl;cout |*| endl;int _tmain(int argc, _TCHAR* argv)int n = 0, i = 0, k = 0, j, h, *w;FILE *fp;char ch2, strMAXDATA, choose,

22、name = BData.txt;w = new intMAXSIZE;char *info;char *strcheck = str;info = new charMAXSIZE;char *ch = new charMAXSIZE;HuffmanTree HT = new HTNodeMAXSIZE;HuffmanCode HC = NULL;HuffmanTree1 HuffmanNode;Menushow();while (1)cout endl 请输入您要进行的操作（1/2/3/4)： choose;cout * endl;switch (choose)case 3:HuffmanNode.TranslatedCode();break;case 2:HuffmanTranslateCoding2(HT, n);break;case 4:/退出