《《数据结构 哈夫曼编码的报告》》由会员分享，可在线阅读，更多相关《《数据结构 哈夫曼编码的报告》（10页珍藏版）》请在金锄头文库上搜索。
1、一、设计思想首先规定构建哈夫曼树，再去进行哈夫曼的译码，接着设计函数进行字符 串的编码过程，最后进行哈夫曼编码的译码。定义一个结构体，用于存放构建哈夫曼树所需要的所有变量，开辟一块地 址空间，用于存放数组，数组中每个元素为之前定义的结构体。输入 n 个字符 及其权值。构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为：1、初始化。将htO. m-1中2n-1个结点里的三个指针均置为空，权值 置为 0。2、 输入。读入n个叶子的权值存于向量的前n个分量中。它们是初始森 林中 n 个孤立的根结点上的权值。3、合并。对森林中的树共进行n-1次合并，所产生的新结点依次放入向量 ht的第i个分量
2、中。每次合并分两步： 在当前森林ht0. i-1的所有结点中，选取权最小和次小的两个根结点 s1和s2作为合并对象，这里0S1, s2i-10 将根为hts1和hts2的两棵树作为左右子树合并为一棵新的树，新树的 根是新结点hti。具体操作：将 hts1和 hts2的 parent 置为 i，将hti的lchild和rchild分别置为s1和s2新结点hti的权值置为hts1和hts2的权值之和。哈夫曼的编码：约定左子为0，右子为 1，则可以从根结点到叶子结点的路 径上的字符组成的字符串作为该叶子结点的编码0当用户输入字母时0就在已经找好编码的编码结构体中去查找该字母0查 到该字母就打印所存的
3、哈夫曼编码0接着就是完成用户输入0、 1 代码时把代码 转成字母的功能0这是从树的头结点向下查找，如果当前用户输入的0、 1 串中 是 0 则就走向该结点的左子0如果是 1 这就走向该结点的右结点，重复上面步 骤0直到发现该结点属于输入了字母的结构体则打印该结构体的字母0重复上 面步骤0直到找完用户输入0、 1 串为止0则就完成了程序所有的译码过程0二、算法流程图(1) 建立哈夫曼树的算法：定义各结点类型其中应包含两类数据一是权重域weight； 一是应该包括指 向左右孩子和指向双亲的指针这里分别用lchild、rchild和parent来表示，因此 可用静态三叉链表来实现0在实际构造中由于是
4、叶子结点来构造新的根结点其 构造过程中仅与叶子结点的权重有关而与其数据域无关，所以构造过程中不用 考虑其数值域，并且在链表中从叶子开始存放，然后不断的将两个最小权值的 子树合并为一个权值为其和的较大的子树，逐步生成各自内部结点直到树根0j=0结点的j=0Yjn输入字符和权值选出权值最小和次小两个结点 ml,m2.mlm2.ml为左子m2为 右子父结点为m1+m2对结构体进行 初始化，开始L_j=j+1哈夫曼树建成图1构建哈夫曼树图(2) 编码的算法 将建立的哈夫曼树从每个叶子结点开始沿着双亲回到根结点，每走一步进 行编码得到的一个编码值，由于每个叶子结点的哈夫曼编码是从根结点到相应 的叶子的路
5、径的各个分支的代码组成的 0 和 1 序列，所以先得到了低位编码后 得到高位编码因此可用一维数组从后向前来存放各位编码值，并用 start 来记 录编码的起始位置。图2哈夫曼编码图(3) 哈夫曼编码。 当我们输入一些字符串，进行哈夫曼编码，然后输出0、1 代码。图 3 哈夫曼编码四、哈夫曼译码当我们输入哈夫曼01 代码时进行译码过程，输出字符串。三、源代码#include #include /数组头文件#include#define MAX 999/宏定义typedef struct/定义哈夫曼编码的结构数组char data;int weight;/定义权值int parent;int lc
6、hild;int rchild;huffmannode;typedef struct/定义保存哈夫曼结构体char bits50;int start;huffmancode ;void main()huffmannode ht100;/定义储存权值的空间huffmancode cd100;char string100;/定义数组存储空间char hcd100;int i,j,x,y,s1,s2,m1,m2,n,c,f,k;printf(please input the n=);/输入字符的个数scanf(%d,&n);printf(n=n); for(i=0;in;i+)getchar();/
7、获得输入的字符printf(please input the value :);scanf(%c,&hti.data);/输入字符函数printf(please input the weight:);scanf(%d,&hti.weight); printf(n=n); for(i=0;i2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1; /初始化父结点，左右子结点 for (i=n;i2*n-1;i+)s1=s2=0;/初始化变量m1=m2=MAX;for (j=0;ji;j+) if (htj.weightm1 &htj.parent=-1) /寻找
8、无父结点的最小值 m2=m1;s2=s1;m1=htj.weight;s1=j;/寻找当前最小值else if(htj.weightm2 &htj.parent=-1) /寻找无父结点的次小值m2=htj.weight;s2=j;/ 寻找次小值/s1 的父结点为 i/ 最小值的权值相加为 i 的权值/i 的左子为 s1/i 的右子为 s2hts1.parent=i;hts2.parent=i; hti.weight=m1+m2; hti.lchild=s1;hti.rchild=s2;for(i=0;in;i+)cdi.start=n; x=i;y=htx.parent;/记录父结点while
9、 (y!=-1)if (hty.lchild=x) cdi.bitscdi.start=0;/给字符赋0 值elsecdi.bitscdi.start=1;/给字符赋1 值cdi.start-;x=y;y=hty.parent;printf(nout the huffmancode:n);for (i=0;in;i+)printf(%c:,hti.data);/输出字符for(j=cdi.start;j=n;j+)printf(%c,cdi.bitsj);/输出字符的01 代码printf(n); printf(n=n); printf(nPlease input the message:n)
10、;scanf(%s,string);/输入字符串for(i=0;stringi!=0;i+)for(c=0;c=n;c+) if(stringi=htc.data) /寻找与输入字符相匹配的字母 for(j=cdc.start;j=n;j+) printf(%c,cdc.bitsj);/输出字母代码break; printf(n=n); printf(Please input the HuffmanCode:n);scanf(%s,hcd);/输入 0、1 代码f=2*n-2;for(i=0;hcdi!=0;i+) if(hcdi=0)/判断输入为 0，寻找左子f=htf.lchild;els
11、e if(hcdi=1)f=htf.rchild;/判断输入为 1，寻找右子if(fn)printf(%c,htf.data); /输出字符串 f=2*n-2;printf(n);getch();四、运行结果步，第一步，运行程序，首先规定结点个数n=8回车，其次我们输入每个结点 的字符及每个结点对应的权值，得如图2。跻 C:U5ersXDe5ktopluanbi3n.exeplease input the n=8thethethethethethethethethethethethethethe 工 图5字符与权值的输入运行结果图步,单击回车得到每个叶子结点的编码，如图3。please ple
12、ase please please please please please please please please please please please please pleaseinput input input input input input input input input input input input input input inputualue weight value weight value weight value weight ualue weight value weight value weights12d33f58z8799c120第二扇 C:U5e rsXD esktopl dd n bia n .exeplease please please please please please pleaseinput input input input input input inputthe weight:87 the value ;x the weight；:99 the value ic the weight:120 the value :q the weight:4560 0 01_0 0 _0 _0 0 TI 1111001 00000001 tu oasdfzxcQthe huffmancode:图6 叶子结点编码
