2023年数据结构实验报告哈夫曼树

数据结构实验报告实验题目：Huffman编码与解码姓名:学号:

院系：。｝0k=1;while(s2==-l||s2==sl){oif(HT[k].parent==0)。s2=k;。k++;if(HT[s2].weight<HT[si],weight)。{。t=s2;s2=s1；sl=t;。)for(k=1;k<i;k++)if(HT[k].parent==O)八if(HT[k].weight<HT[sl].weight&&k!=sl&&k!=s2)00{°。os2=sl;。sl=k;°}o。e1seif(HT[k].weight<HT[s2].weight&&HT[k].weight>=HT[si].weight&&k!=sl&&k!=s2)s2=k：voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn)(oSqStackS；。InitStack(S);。HC=(char**)maIIoc((n+l)*sizeof(char*));Coding(HT,HC,2*n-l,S);)voidCoding(HuffmanTreeHT,char**HCJntroot,SqStack&S)(if(root!=0)。{。oif(HT[root].1c==0)(ooPush(S/\0')；。oHC[root]=(char*)ma1loc((StackLength(S)))；strcpy(HC[root],S.elem)；。«Pop(S/\0');00}。Push(S/O');。Coding(HT,HC,HT[root].1c,S);oPop(S/\0');oPush(S/1');。Coding(HT出C,HT[root].rc,S)：。Pop(S,'\0');voidInitStack(SqStack&S){0S,e1em=(char*)malloc(size*sizeof(char));S.stacksize=size；S.top=-l;)voidPush(SqStack&S,chare)(。S.elem[++S.top]=e;)voidPop(SqStack&S,chare)(if(S.top==-l)return;e=S.elem[S.top-]；。return；)intStackLength(SqStackS)(。if(S.top==-l)return(0);ereturn(S.top);)intFind(chara,chars[],intnum)for(i=l;i<=num;i++)oif(a==s[i])returni;。return0;)intRecover(HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn)(inti=0,j=0,kzm=0,t=0,h=0；ochars[size];°k=2*n—1；whi1e(string[i]){ooif(!HT[k].lc&&!HT[k].rc)(。。if(string[i]=='0'){s[j]='\O'；k=2*n-l;t=1；j=0;}if(string[i]=='l,)000I。。s[j]='\O';o®k=2*n—1；。。t=1;。J=0;°}。for(h=l;h<=n；h++)®if(!strcmp(HC[h],s))b[m++]=a[h];e1se。«if(string0]=='O'){k=HT[k]Jc；s[j++]='0'；}。if(string[i]==z1')°{。k=HT[k].rc;s[j]=zr；。j++；0}0。t=O；°}00if(!t)。i++;}oif(!HT[k].lc&&!HT[k].rc)°{oooif(string[i-l]=='0，){s[j]='\O,;k=2*n-l;j=0;}。if(string[i-1]=='1')000I。s[j]=f\O';»®k=2*n-l；。。t=1;。J=0;°}ofor(h=l;h<=n；h++)。if(1strcmp(HC[h],s))b[m++]=a[h];°}b[m]=>\O';if(k==2*n-1)return1;。elsereturn0;)实验名称：Huffman编码与解码实验问题描述：本实验需要以菜单形式完毕以下功能：.输入电文串.记录电文串中各个字符及其出现的次数.构造哈弗曼树.进行哈弗曼编码.将电文翻译成比特流并打印出来.将比特流还原成电文数据结构的描述：逻辑结构：本实验可用二叉树实现,其逻辑结构为一对二的形式，即一个结点相应两个结点。在实验过程中我们也应用到了栈的概念。存储结构：使用结构体来对数据进行存储：typedefstruct{intweight;ntparent,1c,rc;}HTNode,*HuffmanTree;typedefstructLNodebchar*elem;。intstacksize；。inttop;}SqStack;在main函数里面定义一个哈弗曼树并实现上述各种功能。程序结构的描述：本次实验一共构造了10个函数：.voidHuffTree(HuffmanTree&HT,intn[],intmun);此函数根据给定的mun个权值构建哈弗曼树，n0用于存放num个权值。.voidSelect(HuffmanTree&HT,intnjnti,int&sljnt&s2);此函数用于在中选择parent为0且weight为最小的两个结点,其下标分别为slzs2..voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn);此函数从哈弗.曼树HT上求得n个叶子结点的哈弗夏编码并存入数组HC中。.voidCoding(HuffmanTreeHT,char**HC,introot,SqStack&S)；此函数用于哈弗曼编码，先序遍历哈弗曼树HT,求得每个叶子结点的编码字符串，存入数组HC,S为一个顺序栈，用来记录遍历途径，root是哈弗曼数组HT中根结点的位置下标。.voidInitStack(SqStack&S)；此函数用于初始化一个栈。.voidPop(SqStack&Szchare)；此函数为出栈操作。.voidPush(SqStack&Szchare)；

此函数为进栈操作。8.intStackLength(SqStackS)；此函数用于求栈长，返回一个int型的值。9.intFind(chara,chars[],intnum);此函数用于查找字符a在电文串中的位置。10.intRecover(HuffmanTreeHl；char**HC,charstring口,chara[],charb[],intn);此函数用于将比特流还原成电文。调试分析：输入任意一个字符串，如输入welcometoustc:运营结果如下：又堂工XXXHHXX子：电et±口口出口口口口申树Aom文文文文文文文文文曼*M1221211cwelcomtus又堂工XXXHHXX子：电et±口口出口口口口申树Aom文文文文文文文文文曼*M1221211cwelcomtus数数数数数数数次次次次次次次次次现现现现现现现现现出出出出出出出出出哈弗曼编码：w：11108：0111：1111C：100D：101n:000t：110u：001s：010该电文的哈弗曼编码为：请输入哈弗曼编码：按照提醒输入任意•个或多个哈弗曼编码，如输入:请输入哈弗曼编码:Iwo结果对的。若输入一个11111:请输入哈弗曼编码:11111代码有误?.—.结果对的。实验完毕！实验体会和收获：本次实验提高了对哈弗曼树的结识，同时加深了对二叉树的理解.，在栈的运用上更加纯熟,对数组的应用也有了提高。源代码：#inc1ude<stdio.h>#inc1ude<std1ib,h>#inc1ude<ma11oc.h>#include<string.h>weight;intparent,1c,rc；}HTNode,*HuffmanTree;typedefstruetLNode(char*elem;intstacksize;。inttop;}SqStack;#definesize20voidHuffTree(HuffmanTree&HTjntn[]Jntmun)；voidSelect(HuffmanTree&HT,intnjntiJnt&sl,int&s2)；voidHuffmanCoding(HuffmanTreeHT,char**&HC,intn)；voidCoding(HuffmanTreeHT,char**HCJntroot,SqStack&S);voidInitStack(SqStack&S);voidPop(SqStack&S,chare)；voidPush(SqStack&S,chare);intStackLength(SqStackS)；intFind(chara,chars[],intnum);intRecover(HuffmanTreeHT,char**HC,charstringO^hara[],charb[],intn);intmain()«>inti=0,n[size]={0},j=O,k=l,num=0;»charstring[size]={0},m[size]={0},a[size]={0},b[size]={0};char**HC;oHuffmanTreeHT；printf(”请输入电文串:\n")；scanf("%s",string)；strcpy(m,string);whi1e(string[j])(。if(string[j]!='#')a[k]=string[j];i=j；。whi1e(string[i])。(。。if(string[i]==a[k])00I。string=。。n[k]++;°}°i++；°}。if(n[k]!=0)001printf("该电文中字符％c出现次数为％d\n",a[k],n[k])；。0num++；k++：。｝printf("哈弗曼树:\n“)；HuffTree(HT,n,num);for(i=l;i<=2*num-1；i++)printf("%d\t%d\t%d\t%d\n",HT[i].weightzHT[i].parentzHT[i].lc出T[i].rc)；printf(“哈弗曼编码:\n)3HuffmanCoding(HT,HC,num);for(i=1;i<=num;i++){，printf("%c:%s\nu,a[i]ZHC[i])；0)sprintf("\n该电文的哈弗曼编码为:\n")；。i=0;owhi1e(string[i])printf("%s"ZHC[Find(m[i++]zaznum)]);Printf("\n请输入哈弗曼编码:\n")；scanf("%sH,string)；if(Recover(H7；HCzstring,a,b,num))printf("％s\n"，b);ee1sepr