北邮信通院数据结构实验报告三哈夫曼编码器

北邮信通院数据结构实验报告三哈夫曼编码器北邮信通院数据结构实验报告三哈夫曼编码器20/20北邮信通院数据结构实验报告三哈夫曼编码器北京邮电大学电信工程学院数据结构实验报告实验名称：实验三树——哈夫曼编/解码器学生姓名：班级：班内序号：学号：日期：2014年12月11日1．实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的随意长度的字符串s进行统计，统计每个字符的频度，并成立赫夫曼树2、成立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：依据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行解析，谈论赫夫曼编码的压缩见效。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提示：1、用户界面能够设计为“菜单”方式：能够进行交互。2、依据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。1页-程序解析2.1存储结构Huffman树给定一组拥有确立权值的叶子结点，能够结构出不一样样样的二叉树，此中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。weightlchildrchildparent2-2-1-1-15-1-1-16-1-1-17-1-1-19-1-1-1weightlchildrchildparent2-1-155-1-156-1-167-1-169-1-1770173-13238165482967-12.2重点算法解析1）计算出现字符的权值利用ASCII码统计出现字符的次数，再将未出现的字符进行优选，将出现的字符及頻数存储在数组a[]中。voidHuffman::Init(){intnNum[256]={0};//记录每一个字符出现的次数intch=cin.get();inti=0;while((ch!='\r')&&(ch!='\n')){nNum[ch]++;//统计字符出现的次数str[i++]=ch;//记录原始字符串ch=cin.get();//读取下一个字符}str[i]='\0';n=0;4-for(i=0;i<256;i++){if(nNum[i]>0)//若nNum[i]==0，字符未出现{l[n]=(char)i;a[n]=nNum[i];n++;}}}时间复杂度为O（1）；2）创立哈夫曼树：算法过程：Huffman树采纳次序存储数组；数组的前n个结点存储叶子结点，今后是分支结点，最后是根结点；第一初始化叶子结点元素—循环实现；以循环结构，实现分支结点的合成，合成规则依据huffman树组成规则进行。重点点：选择最小和次小结点合成。voidHuffman::CreateHTree(){HTree=newHNode[2*n-1];//依据权重数组a[0..n-1]初始化Huffman树for(intj=0;j<n;j++)5-{HTree[j].weight=a[j];HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1;}intx,y;for(inti=n;i<2*n-1;i++)//开始建Huffman树{SelectMin(HTree,i,x,y);//从1~i中选出两个权值最小的结点HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;}}2时间复杂度为O(n)voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti;找一个比较值的初步值for(i=0;i<n;i++)//找i1{if(hTree[i].parent==-1)6-{i1=i;break;}}i++;for(;i<n;i++)//找i2{if(hTree[i].parent==-1){i2=i;break;}}if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的{intj=i2;i2=i1;i1=j;}开始找最小的两个i++;for(;i<n;i++){if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight){i2=i1;i1=i;}elseif(hTree[i].parent==-1hTree[i].weight<hTree[i2].weight){i2=i;}}}时间复杂度为O(n)创立编码表7-算法过程：从叶子到根自底向上第必然义码表存储空间；循环对n个叶子结点自底向上回溯到根，记下门路的左右关系，形成编码的逆序串；将各个叶子结点对应的逆序串反序即可。voidHuffman::CreateCodeTable(){HCodeTable=newHCode[n];//生成编码表for(inti=0;i<n;i++){HCodeTable[i].data=l[i];intchild=i;//孩子结点编号intparent=HTree[i].parent;//目前结点的父结点编号intk=0;while(parent!=-1){if(child==HTree[parent].LChild)//左孩子标‘0’HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';//右孩子标‘1’k++;child=parent;//迭代parent=HTree[child].parent;8-}HCodeTable[i].code[k]='\0';Reverse(HCodeTable[i].code);//将编码字符逆置}}时间复杂度为O(n)生成编码串将输入的字符串的每一个字符与编码表比较voidHuffman::Encode(char*d)//编码，d为编码后的字符串{char*s=str;while(*s!='\0'){for(inti=0;i<n;i++)if(*s==HCodeTable[i].data){strcat(d,HCodeTable[i].code);break;}s++;}9-}时间复杂度为O(n)（5）解码:算法过程：从根到叶子自顶向下鉴于huffman树存储数组，从根结点开始，依据输入待解码串s中码字0或1，分别向左或右追踪至叶子结点，叶子结点对应的字符（见码表），即为解码获得的字符；只需s串为结束，重复上述过程voidHuffman::Decode(char*s,char*d)//解码，s为编码串，d为解码后的字符串{while(*s!='\0'){intparent=2*n-2;//根结点在HTree中的下标while(HTree[parent].LChild!=-1)//假如不是叶子结点{if(*s=='0')parent=HTree[parent].LChild;elseparent=HTree[parent].RChild;s++;}*d=HCodeTable[parent].data;d++;10-}}时间复杂度为O（n）2.3其余（1）哈夫曼树的输出是以凹入表示法来实现的，详细算法以下：voidHuffman::Print(inti,intm){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';Print(HTree[i].LChild,m+1);Print(HTree[i].RChild,m+1);}}（2）统计字符頻数时，利用字符的ASCII码进行计数统计，调用了cin.get()函数程序运转程序框图：开始输入要编码的字符串统计字符頻数生成哈夫曼树11-创立编码表生成编码串解码结束程序源代码：#include<iostream>#include<iomanip>usingnamespacestd;structHNode{intweight;//结点权值intparent;//双亲指针intLChild;//左孩子指针intRChild;//右孩子指针};structHCode{chardata;charcode[100];};classHuffman{private:HNode*HTree;//Huffman树HCode*HCodeTable;//Huffman编码表charstr[1024];//输入的原始字符串charl[256];//叶子节点对应的字符inta[256];//记录每个出现的字符的个数public:intn;//叶子节点数12-voidInit();//初始化voidCreateHTree();//创立huffman树voidCreateCodeTable();//创立编码表voidPrintTable();voidEncode(char*d);//编码voidDecode(char*s,char*d);//解码voidPrint(inti,intm);//打印Huffman树voidSelectMin(HNode*hTree,intn,int&i1,int&i2);//找出最小的两个权值voidReverse(char*s);//逆序voidCompare(char*d);//比较压缩大小~Huffman();//析构};voidHuffman::Init(){intnNum[256]={0};//记录每一个字符出现的次数intch=cin.get();inti=0;while((ch!='\r')&&(ch!='\n')){nNum[ch]++;//统计字符出现的次数str[i++]=ch;//记录原始字符串ch=cin.get();//读取下一个字符}str[i]='\0';n=0;for(i=0;i<256;i++){if(nNum[i]>0)//若nNum[i]==0，字符未出现{l[n]=(char)i;a[n]=nNum[i];n++;}}}voidHuffman::CreateHTree(){HTree=newHNode[2*n-1];//依据权重数组a[0..n-1]初始化Huffman树for(intj=0;j<n;j++){13-HTree[j].weight=a[j];HTree[j].LChild=HTree[j].RChild=HTree[j].parent=-1;}intx,y;for(inti=n;i<2*n-1;i++)//开始建Huffman树{SelectMin(HTree,i,x,y);//从1~i中选出两个权值最小的结点HTree[x].parent=HTree[y].parent=i;HTree[i].weight=HTree[x].weight+HTree[y].weight;HTree[i].LChild=x;HTree[i].RChild=y;HTree[i].parent=-1;}}voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti;//找一个比较值的初步值for(i=0;i<n;i++)//找i1{if(hTree[i].parent==-1){i1=i;break;}}i++;for(;i<n;i++)//找i2{if(hTree[i].parent==-1){i2=i;break;}}if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的{intj=i2;i2=i1;i1=j;}//开始找最小的两个i++;for(;i<n;i++){if(hTree[i].parent==-1hTree[i].weight<hTree[i1].weight){i2=i1;i1=i;}elseif(hTree[i].parent==-1hTree[i].weight<hTree[i2].weight){i2=i;}}}voidHuffman::Print(inti,intm){if(HTree[i].LChild==-1)14-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';Print(HTree[i].LChild,m+1);Print(HTree[i].RChild,m+1);}}voidHuffman::CreateCodeTable(){HCodeTable=newHCode[n];//生成编码表for(inti=0;i<n;i++){HCodeTable[i].data=l[i];intchild=i;//孩子结点编号intparent=HTree[i].parent;//目前结点的父结点编号intk=0;while(parent!=-1){if(child==HTree[parent].LChild)//左孩子标‘0’HCodeTable[i].code[k]='0';elseHCodeTable[i].code[k]='1';//右孩子标‘1’k++;child=parent;//迭代parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';Reverse(HCodeTable[i].code);//将编码字符逆置}}voidHuffman::PrintTable(){for(inti=0;i<n;i++)cout<<HCodeTable[i].data<<'\t'<<HCodeTable[i].code<<endl;}voidHuffman::Encode(char*d)//编码，d为编码后的字符串{char*s=str;while(*s!='\0'){for(inti=0;i<n;i++)15-if(*s==HCodeTable[i].data){strcat(d,HCodeTable[i].code);break;}s++;}}voidHuffman::Decode(char*s,char*d)//解码，s为编码串，d为解码后的字符串{while(*s!='\0'){intparent=2*n-2;//根结点在HTree中的下标while(HTree[parent].LChild!=-1)//假如不是叶子结点{if(*s=='0')parent=HTree[parent].LChild;elseparent=HTree[parent].RChild;s++;}*d=HCodeTable[parent].data;d++;}}voidHuffman::Reverse(char*s)//换序{charch;intlen=strlen(s);for(inti=0;i<len/2;i++){ch=s[i];s[i]=s[len-i-1];s[len-i-1]=ch;}}voidHuffman::Compare(char*d)//比较压缩大小{cout<<"编码前："<<strlen(str)*8<<"bit"<<endl;cout<<"编码后："<<strlen(d)<<"bit"<<endl;16-}Huffman::~Huffman()//析构函数{delete[]HTree;delete[]HCodeTable;}voidmain(){HuffmanHFCode;chard[1024]={0};chars[1024]={0};cout<<"请输入要编码的字符串：";HFCode.Init();HFCode.CreateHTree();HFCode.CreateCodeTable();HFCode.Encode(d);HFCode.Decode(d,s);intm;cout<<