2024年实验三哈夫曼树实验报告

数据构造试验汇报试验名称：试验三树學生姓名：班级：班内序号：學号：曰期：12月7号试验规定运用二叉树构造实現赫夫曼编/解码器。基本规定：初始化(Init)：可以對输入的任意長度的字符串s進行记录，记录每個字符的频度，并建立赫夫曼树建立编码表(CreateTable)：运用已經建好的赫夫曼树進行编码，并将每個字符的编码输出。编码(Encoding)：根据编码表對输入的字符串進行编码，并将编码後的字符串输出。译码(Decoding)：运用已經建好的赫夫曼树對编码後的字符串進行译码，并输出译码成果。打印(Print)：以直观的方式打印赫夫曼树（选作）计算输入的字符串编码前和编码後的長度，并進行分析，讨论赫夫曼编码的压缩效果。测试数据：IlovedataStructure,IloveComputer。IwilltrymybesttostudydataStructure.提醒：1、顾客界面可以设计為“菜單”方式：可以進行交互。2、根据输入的字符串中每個字符出現的次数记录频度，對没有出現的 字符一律不用编码。2、程序分析2.1存储构造（1）二叉树template<classT>classBiTree{public:BiTree(); //构造函数，其前序序列由键盘输入~BiTree(void); //析构函数 BiNode<T>*Getroot(); //获得指向根結點的指针protected:BiNode<T>*root; //指向根結點的頭指针};//申明类BiTree及定义构造BiNodeData：二叉树是由一种根結點和两棵互不相交的左右子树构成。二叉树中的結點具有相似数据类型及层次关系。示意图：rootlchildparentrchild（2）静态三叉链表structHNode//哈夫曼树的静态三叉链表{unsignedintweight;//結點权值unsignedintparent;//双亲指针unsignedintLchild;//左孩子指针unsignedintRchild;//右孩子指针};示意图：parentRchildLchilddataparentRchildLchilddata(3)编码表的节點构造structHCode//字符及其编码构造{chardata;charcode[100];};示意图：charcode[100]chardatacharcode[100]chardata2.2关键算法分析一：关键算法(一)初始化函数voidHuffman::Init(inta[],intn)（1）算法自然語言创立一种長度為2*n-1的三叉链表将存储字符及其权值的链表中的字符逐一写入三叉链表的前n個結點的data域，并将對应結點的孩子域和双亲域赋為空從三叉链表的第n個結點開始，i=n從存储字符及其权值的链表中取出两個权值最小的結點x,y，记录其下標x,y。将下標為x和y的哈夫曼树的結點的双亲设置為第i個結點将下標為x的結點设置為i結點的左孩子，将下標為y的結點设置為i結點的右孩子，i結點的权值為x結點的权值加上y結點的权值，i結點的双亲设置為空4.根据哈夫曼树创立编码表（2）源代码voidHuffman::Init(inta[],intn)//创立哈夫曼树{//二叉树只有度為和度為的結點時，總結點数為（n-1）個HTree=newHNode[2*n-1];//根据权重数组a[1—>n]初始化哈夫曼树inti,x,y;for(i=0;i<n;i++)//n個叶子結點{HTree[i].weight=a[i];HTree[i].Lchild=-1;HTree[i].Rchild=-1;HTree[i].parent=-1;}for(inti=n;i<2*n-1;i++)//開始建哈夫曼树，從底层向顶层搭建{SelectMin(HTree,i,x,y);//從--(i-1)中选出两個权值最小的結點HTree[x].parent=i;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;}}(3)時间复杂度在选用两個权值最小的結點的函数中要遍历链表，時间复杂度為O(n),故该函数的時间复杂度為O（n^2）（二）记录字符出現频度的代码（1）算法自然語言=1\*GB3①用cin.getline（）函数获取一段字符串。同步设置一种权值数组weight，以及临時记录和寄存权值的数组s。=2\*GB3②用strlen（）函数获取未编码時的字符串長度。=3\*GB3③從字符串的起始位置進行权值记录，即获得str[i]每個字符的ASⅡ编码，并在s[(int)str[i]]数组中進行+1记录，為字符出現一次。=4\*GB3④i進行自加，记录下面字符出現的频度，在對应的数组元素中進行+1记录。=5\*GB3⑤继续循环，直到字符串結束。（2）源代码（在main（）函数中实現）inti,j=0,v;ints[200]={0};intweight[M];//权值数组cout<<"請输入一段字符串，按回車键結束："<<endl;cin.getline(str,1000,'\n');//由顾客输入一段字符串cout<<endl;Len1=strlen(str);//得到未编码時的字符串長度for(i=0;str[i]!='\0';i++)//记录每個字符的权值s[(int)str[i]]++;//(int)str[i]為每個字符的ASⅡ编码for(i=0;i<200;i++)if(s[i]!=0)//假如权值不為{c[j]=i;//ASⅡ编码為i的字符写入字符数组cweight[j]=s[i];//权值s数组赋給权值weight数组j++;}n=j;//叶子結點個数for(v=0;v<n;v++)//循环输出字符权值cout<<c[v]<<"的权值為："<<weight[v]<<endl;(3)時间复杂度：若输入的字符串長度為n，则時间复杂度為O(n)（三）选择两個最小权值的函数（1）算法自然語言=1\*GB3①先临時将前两個叶子結點作為权值最小的两個結點i1，i2=2\*GB3②從第三個叶子結點開始，每一种結點的权值与i1，i2進行比较，假如此結點权值比i1权值要小，则将i1結點赋給i2，此結點赋給i1。=3\*GB3③假如此結點权值比i2要小，此結點赋給i2。=4\*GB3④每進行一次循环，總結點個数－1.（两個結點進行权值合并）=5\*GB3⑤继续执行循环，直到循环到根結點，循环結束。（2）源代码voidHuffman::SelectMin(HNode*hTree,intn,int&i1,int&i2){inti,j;//找一种比较的起始值for(i=0;i<n;i++)//找i1{if(hTree[i].parent==-1){ i1=i; break;}}i++;for(;i<n;i++)//找i2{//先让前两個叶子結點分别為i1，i2if(hTree[i].parent==-1){ i2=i; break;}}if(hTree[i1].weight>hTree[i2].weight)//i1指向最小的{ j=i2; i2=i1; i1=j;}i++;for(;i<n;i++)//開始找最小的两個{if(hTree[i].parent==-1&&hTree[i].weight<hTree[i1].weight){//假如之後的叶子結點权值不不小于前两個，那么進行互换 i2=i1;//把i1赋給i2 i1=i;}elseif(hTree[i].parent==-1&&hTree[i].weight<hTree[i2].weight){ i2=i;//一直保证i2权值不小于i1}}}（3）時间复杂度若输入的字符串長度為n，则時间复杂度為O(n)（四）创立编码表（1）算法自然語言1.生成一种编码表2.從终端結點開始，假如此結點是其父結點的左孩子，则標“0”；假如是其父結點的右孩子，则標“1”。3.将父結點赋給孩子結點，并将新的孩子結點的父結點作為目前父結點，反复2操作。4.继续循环，直到根結點，即不满足循环条件時，将编码表的最终一位置0.5.将编码字符逆置。将编码串的最终一位置换成新编码串的第一位，倒数第二位置换成新编码串的第二位，直到置换完毕。6.将新的编码串重新赋給编码表。7.输出字符的哈夫曼编码。8.循环将字符编码後的長度赋給Len3数组。（2）源代码voidHuffman::CreateTable(chardata[],intn){HCodeTable=newHCode[n];//生成编码表for(inti=0;i<n;i++){HCodeTable[i].data=data[i];intchild=i;intparent=HTree[i].parent;intk=0;//從终端結點開始编码，代表每個编码串的長度while(parent!=-1){if(child==HTree[parent].Lchild)HCodeTable[i].code[k]='0';//左孩子標“0”elseHCodeTable[i].code[k]='1';//右孩子標“1”k++;child=parent;//向上追溯parent=HTree[child].parent;}HCodeTable[i].code[k]='\0';//當编码到根結點時循环結束，编码串最终一位置表結束{//将编码字符逆置 charcode[M]; intu;for(u=0;u<k;u++) code[u]=HCodeTable[i].code[k-u-1];//上述编码串的最终一位变成新的编码表中编码串的第一位for(u=0;u<k;u++) HCodeTable[i].code[u]=code[u];//将新的编码串重新赋給编码表cout<<c[i]<<"的哈夫曼编码為：";cout<<HCodeTable[i].code<<endl;Len3[i]=k;//每個字符编码後的長度}}}（3）時间复杂度若输入的字符串長度為n，则時间复杂度為O(n)。（五）编码算法（1）算法自然語言1.從字符串的起始位置開始，将每個字符与编码表中的字符進行比對。2.當两字符相等時，输出编码表中字符對应的编码。3.将此字符编码的長度加到Len2中，循环結束後，Len2的数值為字符串编码後的總長度。（2）源代码voidHuffman::Encoding(intn)//编码{cout<<endl<<"输入的字符串转化為哈夫曼编码為:"<<endl;for(inti=0;str[i]!='\0';i++)//只要字符串不結束就执行循环{for(intj=0;j<n;j++)if(str[i]==HCodeTable[j].data)//假如字符串中的字符与编码表中的字符相等{cout<<HCodeTable[j].code;//输出编码表中字符對应的编码Len2+=Len3[j];//求编码後的字符總的编码長度，為了求压缩比}}cout<<endl;}（3）時间复杂度设待编码字符串長度為n，编码表中字符個数為m，则复杂度為O（n*m）。（六）解码算法（1）算法自然語言1.從根节點開始，假如编码串為0，则下溯到此結點的左孩子結點；假如编码串為1，则下溯到此結點的右孩子結點。2.执行循环，直到不满足while循环条件，即追溯到叶子結點。输出叶子結點的字符。（2）源代码voidHuffman::Decoding(char*p)//p為编码串{cout<<"解码後的字符串為:"<<endl;char*q=0;while(*p!='\0'){intparent=2*n-1-1;//根結點在哈夫曼树中的下標while(HTree[parent].Lchild!=-1)//假如不是叶子結點就执行循环{if(*p=='0')parent=HTree[parent].Lchild;elseif(*p=='1')parent=HTree[parent].Rchild;p++;}cout<<HCodeTable[parent].data;//输出叶子結點的字符}cout<<endl<<endl;}（3）時间复杂度若输入的字符串長度為n，则時间复杂度為O(n)。（七）计算压缩比函数（1）算法自然語言获得编码前字符串的長度，即其占用的字节数（float类型）。获得编码後的字符串的長度，将其除以8，得到其占用的字节数（float类型）。压缩比将两個相除。（2）源代码voidHuffman::Calculate(intx,inty)//编码前後的压缩比{cout<<"编码前字符串長度為："<<x<<"Byte"<<endl;//编码前以字节存储cout<<"编码後字符串的大小為:"<<y<<"bit"<<endl;//编码後以位存储cout<<"压缩比為："<<(((float)(y/8))/((float)x))*100<<"%"<<endl;}//计算压缩比（3）時间复杂度時间复杂度為O(1)。2.3其他1.由于題目规定能输入任意長的字符串，因此本程序采用了string变量来记录输入的字符串，并采用string类的类组员函数来完毕各项任务2.记录权值代码和将编码串逆置的代码都没有單独定义函数。其中记录权值代码放到了主程序中，将编码串逆置代码放到了CreateTable（）函数中。3.未能将哈夫曼树直观打印出来。3、程序运行成果（1）程序流程图開始開始调用主函数调用主函数等待顾客输入字符串等待顾客输入字符串运用顾客输入的字符串创立哈夫曼树和编码表运用顾客输入的字符串创立哈夫曼树和编码表打印权值表和编码表打印权值表和编码表计算编码前後的压缩比计算编码前後的压缩比重新输入二進制编码重新输