还剩2页未读,继续阅读
文本内容:
上机实验6哈夫曼编码【实验目的】1熟悉哈夫曼树的存储结构2掌握哈夫曼树构建的算法3掌握哈夫曼树的遍历方法4掌握哈夫曼编码算法【实验内容】实现哈夫曼编码算法根据给定的权值数组,构建带权路径长度最小的哈夫曼树,然后输出对应的哈夫曼编码【实验步骤】1在Microsoft VisualC++中创建应用程序L62在程序中定义哈夫曼树的存储结构tnodepointer3编写函数select,实现在给定的n个元素的结点数组中,找出权值最小的两个元素,返回其下标4编写huffmancoding,实现构建哈夫曼树,并返回哈夫曼编码5编写哈夫曼编码的输出函数output6编写主函数,初始化结点的权值数组,调用huffmancoding函数,输出哈夫曼编码7编译连接程序,执行并观察程序的运行效果【参考源代码】#include stdio.h#include stdlib.h#include string.h typedefstruct〃哈夫曼树结点的类型int weight,parent,lchild,rchild;}tnode,tnodepointer;void selecttnodepointer HT,int n,int sl,int s2{〃在数组HT的前n个parents的元素中,找出权最小的两个元素并将其下标分别赋给si、s2int i;sl=0;fori=0;inHT[i].parent!=0;i++〃略过已经加入树的结点si=i+1;fori=0;in;i++〃用s1保存权最小的元素的下标ifHT|i].weightHT[s1].weightHT[i].parent==O sl=i;s2=0;fori=0;ins2=sl||HT[i].parent!=0;i++s2=i+l;fori=0;in;i++〃用s2保存权次小的元素的下标ifHT[i].weightHT[s2].weightHT[i].parent==Os1!=i s2=i;char**huffmancodingint*w,int n{〃由长度为n的权值数组w,得到其对应的哈夫曼编码函数的返回值是n个字符编码的头指针组成的数组的首地址二级指针tnodepointerHT=tnodepointermalloc2*n-1*sizeoftnode;〃定义存放2n-l个结点的数组tnodepointer TEMP;forTEMP=HT;TEMPHT+n;TEMP++,w++〃将w中的权值移动到数组HT中{〃结构体变量赋值TEMP-weight=*w;TEMP-parent=0;TEMP-lchild=0;TEMP-rchild=0;forint m=2*n-1;TEMPHT+m;TEMP++〃初始化非叶子结点的parent项TEMP-parent=0;forint i=n;i2*n-l;i++〃设置各个结点的值,构建哈夫曼树int sl,s2;selectHT,i,sl,s2;〃在数组HT的前n个parent=0的元素中,找出权最小的两个元素并将其下标分别赋给si、s2HT[sl].parent=i;HT[s2].parent=i;HT[i].lchild=sl;HT[i].rchild=s2;HT[i].weight=HT[sl].weight+HT[s2|.weight;char*str=char*mallocn*sizeofchar;//str用于临时存放哈夫曼编码char**huffmancode=char**maHocn*sizeofchar*;forint i=0;in;i++〃构建哈夫曼编码int start=n-1;str[start]=\O;int c=i,temp=HT[c].parent;whiletemp!=0〃temp=0表示该结点为根结点ifHT[temp].lchild==c str[--start]=O;else str[-start]-T;c=temp;temp=HT[c].parent;huffmancode[i]=char*mallocn・start*sizeofchar;strcpyhuffmancode[i],str[start];free HT;freestr;return huffmancode;void outputchar**p,int n〃输出数组p中各元素指向的字符串forint i=0;in;i++printf u%s\p[i];printf n\n n;void main〃测试int w[]={5,29,7,8,14,23,3,11};char**p=huffmancodingw,8;printf与权值对应的huffman编码为\n n;outputp,8;【运行结果】参考源码中设置的权值为w={5,29,7,8,14,23,3,11},程序运行结果如附图7所示c、C:\¥I!OOTS\syst e・32\c・d.exe|与权值对应的huF Fman编科为:00011011101111110010000001请按任意键继续..•ZD附图7上机实验6运行结果【实验总结】该算法的关键之一是select函数的实现,即如何在给定的n个元素的结点数组中,找出权值最小的两个元素,返回其下标构建哈夫曼树时,利用了哈夫曼树的链接表来保存树的左右孩子信息和父结点信息在返回哈夫曼编码时,从树根遍历到树的叶子结点,这样逆向构建哈夫曼编码。