信息论课程设计（论文）-Huffman编码的编码与译码.doc

本科生课程论文题 目： Huffman编码的编码与译码 姓 名： 学 院： 理学与信息学院 专 业： 信息与计算科学专业 班 级： 学 号： 指导教师： 完成时间： 2011年6月29日 2011年6月29日第 28 页 共 28 页目 录摘要11.概念解释12.程序设计算法23.程序调试窗34.致谢5参考文献5附录6Huffman编码的编码与译码信息与计算科学 指导教师 摘要：在这个信息高速发展的时代，每时每刻都在进行着大量信息的传递，到处都离不开信息，它贯穿在人们日常的生活生产之中，对人们的影响日趋扩大,而利用哈夫曼编码进行通信则可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润，这也是信息时代发展的趋势所在。文字处理是现代计算机应用的重要领域。文本由字符组成，字符以某种编码形式存储在计算机中。每个字符的编码可以是相等长度的，也可以是不等长度的。ASCII编码是等长编码。为了提高存储和处理文本的效率，在一些计算机应用场合，如数据通信，常采用不等长的编码，对常用的字符用较少的码位，不常出现的字符用较多的码位编码，从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等长编码方法。关键词：Huffman编码 编码 译码 VC+ 程序代码 哈夫曼树一 概念解释：1、哈夫曼树哈夫曼树也称最优二叉树.给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为哈夫曼树.其中,叶子结点的权值(weight)是对叶子结点赋予的一个有意义的数值量.设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度(weighted path length),记为:WPL=,wk为第k个叶子结点的权值,lk为从根结点到第k个叶子结点的路径长度. 2、哈夫曼算法根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是:(1) 初始化:由预先给定的n个权值w1, w2, wn构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F= T1,T2,Tn;(2) 选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;二 设计方案：哈夫曼编码/译码程序主要由主函数、哈夫曼树类和各种功能函数组成，程序运行时首先进入主函数，对各种功能函数进行调用，从而实现了整个程序的运行。将各种不同的函数分别包含在各自的结构体中，使整个程序结构更加的清晰明了，各功能相互独立且紧密联系，有利于编程的实现，同时也体现了面向对象设计语言的封装性。在主菜单中运用了switch()函数和“case”语句，便于对整个程序操作和控制；对数据保存在文档中，则运用了文件I/O流和C语言的文件处理方式，进行文件与内存之间输入，输出数据。程序的主要功能：1、Huffman编码（void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n)）a)先将每个字符的出现概率存在数组HT1-n的weight中，并将每个数组元素的rchild，lchild，parent都置为0。b)每次对数组中的parent值为0的元素的weight值进行堆排序，取出两个最小的值相加加入HT中。新加入的元素的weight值为两个weight值相加，parent值为0，lchild,rchild为选出来的两个最小值的数组序号，两个选出来的最小值的parent值为新存入的元素的数组序号。重复操作，直至数组存满c)HC为char *类型，HCi里存放着第i个字符串的首地址。cd存放编码，最后一个元素存放字符串截止符0，采用倒序存储，从叶子节点往上寻找，若是lchild，则从后往前在cd内存入0。若是rchild，则从后往前在cd内存入1。直至找到根节点。将cd中存储的字符串拷贝到HCi指向的数组中。d)重复c)，直至所有字符都存入HCi指向的数组中，即编码成功。2、堆排序（函数1、void HeapAdjust(SqList &L, int s, int m)，函数2、void select(HuffmanTree t, int i, int &s1, int &s2)）a)函数2是在函数1的基础上实现的，函数1的功能是已知L.rs.m中记录的关键字除L.rs.key之外均满足堆的定义,调整L.rs的关键字，使L.rs.m成为一个小顶堆（对其中记录的关键字而言）。函数2的功能是在HuffmanTree中的前i个元素中找出parent值为0且weight值最小的两个元素的下标，将他们存入s1,s2中。b)函数2、void select(HuffmanTree t, int i, int &s1, int &s2)首先将HuffmanTree中的前i个元素（parent值为0）的weight值存入线性表L的数组r中，并将对应的在HuffmanTree中的位置存储在其otherinfo中。从非叶子节点开始堆排序，调用函数1，形成一个小顶堆。取堆顶元素将其otherinfo等于s1,将小顶堆的首尾元素对调，对除最后一个元素以外的其他所有元素进行堆排序，形成小顶堆。取堆顶元素将其otherinfo等于s2。3、解码（void decode()）从根节点（即parent值为0的HuffmanTree数组中的最后一个元素）往下，为0则往左枝继续，为1则往右枝继续，直至叶子节点（即rchild,lchild都为0的HuffmanTree数组中的元素），如果未到叶子节点01字符串就终止了，即输出提示信息。三 程序调试窗：图1图2图3图4图5图6四 致谢：在本次课程设计的整个过程中，要特别感谢给我提供帮助和指导的于加举老师，是他耐心的指导才使得本次设计得以顺得完成，也要感谢同学的帮助，在此还要特别感谢为我们提供良好上机环境的学校.如果没有以上老师，同学和学校的帮助和支持，本次设计实难完成.再次感谢老师的精心辅导和同学的帮助，使我顺利完成此次设计以及为学习以后的科目打下良好的基础.参考文献 【1】 C语言程序设计（第三版） 谭浩强 清华大学出版社 2009.10【2】 数据结构（C版）。杨剑主编 清华大学出版社 2011.11【3】信息论与编码技术 清华大学出版社 2010.2附录：程序代码：#include stdio.h#include stdlib.h #include string.h#include conio.h#include iostream.h#define MAXSIZE 60/*/*定义赫夫曼树结构体*/*typedef structfloat weight;unsigned int parent, lchild, rchild;HTNode, *HuffmanTree;typedef char *HuffmanCode ;/*/*定义堆结构体*/*typedef structfloat key; /关键字项int otherinfo; /其他数据项（此题目中用不到）RedType; typedef structRedType rMAXSIZE+1; /r0闲置用作哨兵int length; /顺序表长度SqList;/*/*全局变量*/*HuffmanTree HT; /赫夫曼树HuffmanCode HC; /码值FILE *fp, *fp1, *fp2;int a30 = 0;float b30;float *w; /权/*/*测试解码（可以输入一个不正确的二进制码串），显示在屏幕上*/*void testdecode() char str200; /存放自己输入的码字int p, p1, i; /解码的线索char ch;printf(n请根据以上各个字符的编码输入一串二进制码字(200个以内):n);gets(str);printf(解码后为:n);p = 59; /最初令p为树根整数，p由根顺着树枝一直到树叶 i = 0;ch = stri+; while (ch!=0) for ( ; ch!=0 & (HTp.lchild!=0|HTp.rchild!=0) ; ) /未到叶子节点即为得到相应源码 if (ch = 0) p = HTp.lchild; else if(ch = 1) p = HTp.rchild;else printf(n你输入了0,1之外的字符，无法正确译码，请检查 !n); return ; /直接结束ch = stri+; /下一个码字 不断的取下一个 if(p 30) printf(n以上正确译出了前面的字符，由于你输入的二进制码不完整，最后一位字符无法译出，请检查!n);/*/*下面是解码，写入文件中并在屏幕上显示*/* void decode() int p;char ch;printf(nn对编码解码后的如下:n);fp1 = fopen(bianma.txt,r);if(!fp1)printf(can not open this file!n);exit(0); p = 59; /最初令p为树根整数，p由根顺着树枝一直到树叶ch = fgetc(fp1); fp2 = fopen(jiema.txt,w); /将解码输入到文件jiema.txt中if (!fp2)printf(can not open this file!n);exit(0);while (ch!=EOF)for ( ; HTp.lchild!=0|HTp.rchild!=0 ; ) if (ch = 0) p = HTp.lchild; else p = HTp.rchild; ch = fgetc(fp1); /下一个码字 不断的取下一个 switch (p) case 27 : printf(,); fprintf(fp2,); break;case 28 : printf(.); fprintf(fp2, .); break; case 29 : printf( ); fprintf(fp2, ); break; case 30 : printf(n); fprintf(fp2, n); break; default : printf(%c, p+96); fprintf(fp2, %c, p+96); p = 59; /这里p要重置为59，因为经过上面的程序p已经变化了，不重置为1则HTp.lchild!=0|HTp.rchild!=0所以for语句无法进行! /while循环printf(n);fprintf(fp2, n);fclose(fp1);fclose(fp2);/*/*将编码存入文件中*/*void printcode() char ch;fp = fopen(Huffman.txt,r);if (!fp)printf(can not open this file!n);exit(0);fp1 = fopen(bianma.txt,w);if (!fp1)printf(can not open this file!n);exit(0); printf(n原英文文章经编码后如下:n); ch = fgetc(fp);while (ch!=EOF) if (ch 96 & ch 64 & ch 91) /大小字母 printf(%s, HCch-64); fputs(HCch-64, fp1); /输出到文件里面 ch = fgetc(fp);if (ch = ,)printf(%s, HC27);fputs(HC27, fp1);ch = fgetc(fp);if (ch = .)printf(%s, HC28);fputs(HC28, fp1);ch = fgetc(fp);if (ch = )printf(%s, HC29);fputs(HC29, fp1);ch = fgetc(fp);if (ch = n)printf(%s, HC30);fputs(HC30, fp1);ch = fgetc(fp); printf(nn); fclose(fp);fclose(fp1);/*/*程序主干部分*/*堆排序*/*/堆排序void HeapAdjust(SqList &L, int s, int m)/已知L.rs.m中记录的关键字除L.rs.key之外均满足堆的定义,本函数调整L.rs的关键字，使L.rs.m成为一个小顶堆（对其中记录的关键字而言）RedType rc;int j; rc = L.rs; /暂存根结点的记录for (j = 2 * s ; j = m ; j*=2) /沿关键字较小的孩子结点向下筛选 if (j L.rj+1.key) +j;if (rc.key = L.rj.key) break;L.rs = L.rj; / 将小关键字记录往上调s = j; L.rs = rc; / 回移筛选下来的记录/选出最小的两个元素void select(HuffmanTree t, int i, int &s1, int &s2) /此函数被调用一次则就用堆排序选择两个最小的赋给s1和s2SqList L;RedType rc;int j, k, n = 1;L.length = 0;for (j = 1 ; j 0 ; -k)HeapAdjust(L,k,L.length); /全部堆排序s1 = L.r1.otherinfo; /最小的选出来了！rc = L.r1;L.r1 = L.rL.length; /此次的select函数，进行堆排序的只有L.length 个（parent！=0的没有在里面），所以这里是L.length而不是iL.rL.length = rc;HeapAdjust(L,1,L.length-1); /将首尾调换后，在L.length-1个元素中仅第一个元素无序，所以将其堆排序s2 = L.r1.otherinfo; /次小的选出来了/*/*程序主干部分*/*赫夫曼编码*/* void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *w, int n) / 算法6.12 / w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC int m, i, s1, s2, start, k; unsigned c, f; HuffmanTree p; char *cd; if (n = 1) /单节点 return; m = 2 * n - 1; /一共m个节点 w = (float *)malloc(30*sizeof(float); /将每个字符出现的概率存入数组w中 for (i = 0 ; i 30 ; i+) *(w+i) = bi; HT = (HuffmanTree)malloc(m+1)*sizeof(HTNode); / 0号单元未用 for (p = HT + 1, i = 1 ; i weight = *w; p-parent = 0; p-lchild = 0; p-rchild = 0; for (i = n + 1 ; i parent=0; for (i = n + 1 ; i = m ; +i) / 建赫夫曼树 select(HT, i-1, s1, s2); / 在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 HTs1.parent = i; HTs2.parent = i; /最小的和次小的双亲已经不为0了，下次就不在它两中间找最小的和次小的了。 HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf(赫夫曼树如下表:n) ; printf(*n) ; printf(* number * name * weight * parent * lchild * rchild *n); for(k = 1 ; k = m ; k+) if (k 30) printf(* %2d * * %f * %2d * %2d * %2d *n,k,HTk.weight,HTk.parent,HTk.lchild,HTk.rchild); printf(*n) ; printf(n) ; HC = (HuffmanCode)malloc(n+1)*sizeof(char*); /HC为指向编码(串)的指针，HCi为指向第i个编码的指针 cd = (char*)malloc(n*sizeof(char); /每串编码最多有n个字符 cdn-1 = 0; for (i = 1 ; i = n ; i+) /开始编码 start = n-1; for (c = i, f = HTi.parent ; f!=0 ; c = f, f = HTf.parent)/f=HTi.parent f!=0是结束条件，所有的编码最后都要回到HTm,而只有HTm的parent是0! / 从叶子到根逆向求编码 if (HTf.lchild=c) /c是左孩子则码值是0 cd-start = 0; /这样逆着输，当我们正序输出的时候就恰好是想要的编码了! else cd-start = 1; HCi = (char*)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间HC0未用 strcpy(HCi,&cdstart); /从cd复制编码(串)到HC，这里的&cdstart是一个地址，编码串的首地址 free(cd); / 释放工作空间 printf(经赫夫曼编码后码值如下:n); for (i = 1 ; i %f-, i+64, i+96, HTi.weight); puts(HCi); printf( , -%f-%sn, HT27.weight, HC27); printf( . -%f-%sn, HT28.weight, HC28); printf(空格-%f-%sn, HT29.weight, HC29); printf(换行-%f-%sn, HT30.weight, HC30); /*/*输出各个字符的次数，概率*/* void showdetail() int i;printf(此英文文章中各个字母,个数，概率如下表:n); printf(*n);printf(* 字母 * 个数 * 概率 *n); for (i = 0 ; i = a & ch = A & ch = Z) ach-A+; count+=1; if (ch = ,) a26+; /逗号放在a26 if (ch = .) a27+; /句号放在a27 if (ch = ) a28+; /空格符放在a28 if (ch = n) a29+; /换行符放在a29 ch = fgetc(fp); printf(nn);for (i = 0 ; i 30 ; i+) bi = ai/count; /b存贮每个字符出现的概率fclose(fp); /文件用完就关闭/*/*主函数*/* void main() char c; char s300=1.查看原文.nn2.字符统计.nn3.赫夫曼编码并输出内容.nn4.输出整篇文章的编码.nn5.对码字进行解码.nn6.测试解码.nn7.退出.nn; printf(nnnnn); printf( *n); printf( * *n); printf( * 说明：本程序的赫夫曼编码对象： *n); printf( * 26个大小写字母（每个字母的大小写看作一个编码对象） *n); printf( * 逗号、句号、空格以及换行符。 *n); printf( * 步骤：把要编译的内容以Huffman.txtw命名并保存到平行目录下*n); printf( * 注意:必须按顺序先进行1，2，3项的操作,否则会有错误! *n); printf(