北京邮电大学电信工程学院数据结构实验报告实验名称：实验三树 ----- 哈夫曼编/解码器学生姓名：班级：班内序号：学号：日期：2014年12月11日1. 实验要求利用二叉树结构实现赫夫曼编/解码器。
基本要求：1、初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。
3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、译码(Decoding)：禾U用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。
5、打印(Print):以直观的方式打印赫夫曼树(选作)6计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。
测试数据：I love data Structure, I love Computer。
I will try my best to study data Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。
2. 程序分析2.1存储结构Huffman 树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman 树，也叫做最优二叉树哈夫虽树示意图root孩子双亲表示法_____________________ JL________________weight Ichild rchild pare nt数存储在数组a[]中。
void Huffma n::l nit() {int nNu m[256]= {0}; //int ch = ci n.get(); int i=0;while((ch!='\r') && (ch!='\n')) {nNu m[ch]++; // str[i++] = ch; // ch = cin .get();// str[i]='\0';n = 0;2.2关键算法分析(1)计算出现字符的权值利用ASCII 码统计出现字符的次数,再将未出现的字符进行筛选,将出现的字符及頻记录每一个字符出现的次数统计字符出现的次数记录原始字符串读取下一个字符for ( i=0;i<256;i++){if (nNum[i]>0) // 若nNum[i]==0，字符未出现{l[n] = (char)i;a[n] = nNu m[i];n++;}}}时间复杂度为0( 1);(2 )创建哈夫曼树：算法过程：Huffman树采用顺序存储---数组；数组的前n个结点存储叶子结点，然后是分支结点，最后是根结点；首先初始化叶子结点元素一循环实现；以循环结构，实现分支结点的合成，合成规则按照huffman树构成规则进行。
关键点：选择最小和次小结点合成。
void Huffma n::CreateHTree(){HTree = new HNode [2*n-1]; // 根据权重数组a[0..n-1] 初始化Huffman 树for (i nt j = 0; j < n; j++)HTree[j].weight = a[j];HTree[j].LChild = HTree[j].RChild = HTree[j].pare nt = -1;}int x,y;for (int i = n; i < 2*n-1; i++) // 开始建Huffman 树{SelectMin( HTree, i, x, y); //从1~i中选出两个权值最小的结点HTree[x].pare nt = HTree[y].pare nt = i;HTree[i].weight = HTree[x].weight+ HTree[y].weight;HTree[i].LChild = x;HTree[i].RChild = y;HTree[i].pare nt = -1;}}2时间复杂度为0(n )void Huffman::SelectMin( HNode *hTree,int n, int & 1, int &i2 ) {int i;// 找一个比较值的起始值for(i=0; i<n; i++) // 找i1{ if(hTree[i].pare nt==_1 ){ i1=i; break;}i++；for( ; i<n; i++) // 找i2{ if(hTree[i].pare nt==_1 ){ i2=i; break; }}指向最小的if(hTree[i1].weight>hTree[i2].weight) 〃i1{ int j=i2; i2=i1; i1 = j; }// 开始找最小的两个i++;for( ; i<n; i++){ if(hTree[i].pare nt==-1&& hTree[i].weight < hTree[i1].weight ) { i2=i1; i1 = i; } else if( hTree[i].pare nt==-1&& hTree[i].weight < hTree[i2].weight){ i2=i; }}}时间复杂度为0(n)(3)创建编码表child = pare nt; //迭代首先定义码表存储空间；循环对n 个叶子结点自底向上回溯到根，记下途径的左右关系, 将各个叶子结点对应的逆序串反序即可。
void Huffma n::CreateCodeTable() {HCodeTable = new HCode[ n]; // 生成编码表for (int i=0;i< n;i++)HCodeTable[i].data = l[i];int child = i;int pare nt = HTree[i].pare nt; ////孩子结点编号当前结点的父结点编号int k=0;while(pare nt!=-1)if (child==HTree[pare nt]. LChild) HCodeTable[i].code[k] = 'O'; elseHCodeTable[i].code[k] = '1 k++;算法过程：从叶子到根 自底向上形成编码的逆序串;//左孩子标//右孩子标‘ 1'pare nt = HTree[child].pare nt;child = pare nt; //迭代HCodeTable[i].code[k] = '\0：Reverse(HCodeTable[i].code);//将编码字符逆置}}时间复杂度为0(n)(4)生成编码串将输入的字符串的每一个字符与编码表比较void Huffman::Encode(char *d)〃编码，d为编码后的字符串{char *s = str;while(*s!='\0'){for (in t i=0;i< n;i++)if (*s == HCodeTable[i].data ){strcat(d, HCodeTable[i].code);break;}s++;}*d = HCodeTable[pare nt].data;时间复杂度为0(n)(5) 解码：算法过程： 从根到叶子---自顶向下基于huffman 树存储数组，从根结点开始，依据输入待解码串 s 中码字0或1，分别向左或只要s 串为结束，重复上述过程{while(*s!='\0') {{if (*s=='0')pare nt = HTree[pare nt].LChild; elsepare nt = HTree[pare nt].RChild; s++; } d++;右跟踪至叶子结点，叶子结点对应的字符(见码表)，即为解码得到的字符;void Huffma n::Decode(char* s, char *d)//解码，s 为编码串，d 为解码后的字符串int pare nt = 2*n-2;while (HTree[pare nt]. LChild!=-1) II //根结点在HTree 中的下标如果不是叶子结点}时间复杂度为0(n)2.3其他(1)哈夫曼树的输出是以凹入表示法来实现的，具体算法如下：void Huffma n::Pri nt( in t i, i nt m){if (HTree[i].LChild == -1)cout<<setfill(' ')<<setw(m+1)<<l[i]<<setfill('-')<<setw(10-m)<<'\n：else{cout<<setfill(' ')<<setw(m+1)<<HTree[i].weight<<setfill('-')<<setw(10-m)<<'\n：Prin t(HTree[i].LChild,m+1);Prin t(HTree[i].RChild,m+1);}}(2)统计字符頻数时，利用字符的ASCII码进行计数统计，调用了cin.get()函数3.程序运行程序框图：开始输入要编码的字符串*d = HCodeTable[pare nt].data;结束#in elude <iostream> #i nclude <ioma nip> using n amespace std; struct HNode {int weight; 〃结点权值int parent; //双亲指针int LChild; //左孩子指针 int RChild ; //右孩子指针};struct HCode {char data; char code[100]; };class Huffma n {private:HNode* HTree; HCode* HCodeTable; char str[1024]; char l[256]; int a[256]; public:int n;程序源代码://Huffman 树 //Huffman 编码表 //输入的原始字符串〃叶子节点对应的字符//记录每个出现的字符的个数〃叶子节点数void Ini t();void CreateHTree();void CreateCodeTable(); void Prin tTable();void En code(char *d); void Decode(char *s, char *d); void Prin t( int i,i nt m);//初始化//创建huffman树//创建编码表//编码//解码//打印Huffman树void SelectMi n( HNode *hTree, int n, int & 1, i nt & 2);// 找出最小的两个权值void Reverse(char* s); void Compare(char*d);~ Huffma n(); }; //逆序//比较压缩大小〃析构void Huffma n::l nit() {int nNum[256]= {0};int ch = cin .get();int i=0;while((ch!='\r') && (ch!='\n')) {nNu m[ch]++;str[i++] = ch;ch = cin .get(); }str[i]='\0'; //记录每一个字符出现的次数//统计字符出现的次数//记录原始字符串//读取下一个字符n = 0;for ( i=0;i<256;i++) {if (nN um[i]>0){l[n] = (char)i;a[n] = nNu m[i];n++;}}}void Huffman::CreateHTree(){HTree = new HNode [2* n-1]; 树〃若nNum[i]==0，字符未出现//根据权重数组a[0..n-1]初始化Huffmanfor (i nt j = 0; j < n; j++){HTree[j].weight = a[j];HTree[j].LChild = HTree[j].RChild = HTree[j].pare nt = -1;}int x,y;for (int i = n; i < 2*n-1; i++) 〃开始建Huffman 树{SelectMin( HTree, i, x, y); //从1~i中选出两个权值最小的结点HTree[x].pare nt = HTree[y].pare nt = i;HTree[i].weight = HTree[x].weight+ HTree[y].weight;HTree[i].LChild = x;HTree[i].RChild = y;HTree[i].pare nt = -1;}void Huffman::SelectMin( HNode *hTree,int n, {int & 1, int &i2 ) int i;//找一个比较值的起始值for(i=0; i<n; i++) // 找i1{ if(hTree[i].pare nt==_1 ){ i1=i; break; }}i++;for( ; i<n; i++) // 找i2{ if(hTree[i].pare nt==_1 ){ i2=i; break; }}if(hTree[i1].weight>hTree[i2].weight) 〃i1 指向最小的{ int j=i2; i2=i1; i1 = j; }〃开始找最小的两个i++;for( ; i<n; i++){ if(hTree[i].pare nt==_1&& hTree[i].weight < hTree[i1].weight ){ i2=i1; i1 = i; }else if( hTree[i].pare nt==-1&& hTree[i].weight < hTree[i2].weight){ i2=i; }}}void Huffma n::Pri nt( in t i, i nt m){if (HTree[i].LChild == -1)cout<<setfill(' ')<<setw(m+1)<<l[i]<<setfill('-')<<setw(10-m)<<'\n： else{cout<<setfill(' ')<<setw(m+1)<<HTree[i].weight<<setfill('-')<<setw(10-m)<<'\n：Prin t(HTree[i].LChild,m+1);Prin t(HTree[i].RChild,m+1);}}void Huffma n::CreateCodeTable(){HCodeTable = new HCode[n]; // 生成编码表for (i nt i=0;i <n ;i++){HCodeTable[i].data = l[i];int child = i; //孩子结点编号in t pare nt = HTree[i].pare nt; //当前结点的父结点编号int k=0;while(pare nt!=-1){if (child==HTree[parent].LChild) //左孩子标’O'HCodeTable[i].code[k] = '0';elseHCodeTable[i].code[k] = '1' ; // 右孩子标’1k++;child = pare nt; // 迭代pare nt = HTree[child].pare nt;}HCodeTable[i].code[k] = '\0';Reverse(HCodeTable[i].code); // 将编码字符逆置}}void Huffma n::Pri ntTable(){for (i nt i=0;i <n ;i++) cout<<HCodeTable[i].data<<'\t'<<HCodeTable[i].code<<e ndl;}void Huffman::Encode(char *d)〃编码，d为编码后的字符串{char *s = str;while(*s!='\0'){for (int i=0;i< n;i++)if (*s ==HCodeTable[i].data ){strcat(d, HCodeTable[i].code);break;}s++;}}void Huffman::Decode(char* s, char *d) 〃解码，s 为编码串，d 为解码后的字符串{while(*s!='\0'){in t pare nt = 2*n-2; 〃根结点在HTree中的下标while (HTree[pare nt]. LChild!=-1) 〃如果不是叶子结点{if (*s=='0')pare nt = HTree[pare nt].LChild;elsepare nt = HTree[pare nt].RChild;s++;}*d = HCodeTable[pare nt].data;d++;}}void Huffman::Reverse(char* s)// 换序{char ch;int len = strle n( s);for (int i=0;i<len/2;i++) {ch = s[i];s[i] = s[le n-i-1];s[le n-i-1] = ch;}}void Huffman::Compare(char*d)〃比较压缩大小{cout<<"编码前："<<strle n(str)*8<<"bit"<<e ndl;cout<<"编码后："<<strle n(d)<<"bit"<<e ndl;}Huffman::~ Huffman()// 析构函数{delete []HTree;delete []HCodeTable;}void mai n(){Huffma n HFCode;char d[1024]={0};char s[1024]={0};cout<<"请输入要编码的字符串：";HFCode.I nit();HFCode.CreateHTree();HFCode.CreateCodeTable();HFCode.E ncode(d);HFCode.Decode(d,s);int m;cout<<"欢迎使用\n"<<"1.打印哈夫曼树\n"<<"2.打印哈夫曼编码表打印编码\n"<<"3. \n"<<"4.打印解码\n"<<"5.压缩比"<<endl;while(1){cin»m;switch(m){case 1:{HFCode.Pri nt(2*HFCode. n-2,1);break;}case 2:{HFCode.Pri ntTable();break;}case 3:{cout<<"编码结果："<<d<<e ndl; break;} case 4:{cout<<"解码结果："<<s<<endl; break; } case 5:{pare(d); } } } }运行结果:*E ：\vc-b - \Microsoft Visual Stu□ i o\F/lyPrcy ects x h af u m\Debug\nafnj.e>：eI uiLl ti'y my best tLoue cl 且 I ：丑 S true cure I loue Computer^:叱* ?■片3 的st 黏 码t a 員> 编站翁筮 要y 用吟匸毎M 比」瓦LnJn r D r DI D I 5H 丿欢迎下载 214.总结在编程时，最开始在字符统计时出现了空格无法统计的问题，后来用ci n.get()函数进 行统计。
