数据结构课程设计》赫夫曼编码实验报告.doc

数据结构课程设计实验报告 赫夫曼编码实验课程名称 数据结构课程设计 专 业 班 级 11级计科（2）班 学 生 姓 名 王琦 学 号 114090102036 指 导 教 师 冯 韵 实 验 时 间 ： 2013 年 9 月 24 日 2013至 2014学年第 1 学期第 1 至 9 周目 录一、概述1二、系统分析1三、概要设计2四、详细设计44.1 赫夫曼树的建立44.1.1 选择选择parent 为0 且权值最小的两个根结点的算法54.1.2 统计字符串中字符的种类以及各类字符的个数74.1.3构造赫夫曼树84.2赫夫曼编码104.2.1赫夫曼编码算法104.2.2建立正文的编码文件11五、运行与测试12六、总结与心得13- 2 -一、概述 本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出 电文字符串。 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时 间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。二、系统分析 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示 “1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式 的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。 假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为W i L i 。 若将此对应到二叉树上，W i 为叶节点的权 ，L i 为根节点到叶节点的路径长度。那么，W i L i 恰好为二叉 树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树， 此构造过程成为赫夫曼编码。 根据设计要求和分析，要实现设计，必须实现以下方面的功能： （1） 赫夫曼树的建立； （2） 赫夫曼编码的生成； （3） 编码文件的译码；三、概要设计 void main()void HufffmanEncoding(HuffmanTree HT,HuffmanCode HC)/编码部分char *decode(HuffmanCode Hc)/译码void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) /生成Huffman树void select(HufmanTree HT,int k,int &s1,int &s2) /找寻parent为0,权最小的两个节点其流程图如下：进行相应的操作输出结果结束构造赫夫曼树程序结束退出对编码串译码对字符串编码开始进行相应的操作四、详细设计 4.1 赫夫曼树的建立 由赫夫曼算法的定义可知，初始森林中共有 n 棵只含根节点的二叉树。算法的第二步是：将当前森林 中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新 节点。显然要进行 n-1 次合并，所以共产生 n-1 个新节点，它们都是具有两个孩子分支结点。由此可 知，最新求得的赫夫曼树中一共有2n-1 个结点，其中n 个结点是初始森林的n 个孤立结点。并且赫夫 曼树中没有度数为1 的分支结点。我们可用一个大小为2n-1 的一维数组来存储赫夫曼树中的结点。因 此，赫夫曼树的存储结构描述为： #define n 100 #define m 2*n-1 typedef struct int weight; int lchild,rchild,parent; HTNode; T typedef HTNode HuffmanTreem+1; 开始结束第i个结点权值i=num?创建赫夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法 void select(HuffmanTree T,int k,int *s1,int *s2)/在HT1k中选择parent为0且权值最小的两个根结点，其序号分别为S1和S2 int i,j; int min1=100; for(i=1;i=k;i+)/查找s1 if(Ti.weightmin1 & Ti.parent=0) j=i;min1=Ti.weight; *s1=j; min1=32767; for(i=1;i=k;i+)/查找s2,不和s1相同 if(Ti.weightmin1 & Ti.parent=0 & i!=(*s1) j=i; min1=Ti.weight; *s2=j;4.1.2 统计字符串中字符的种类以及各类字符的个数假设电子文件字符串全是大写字母，那么该算法的实现思想是：先定义一个含有26个元素的临时整型数组，用来存储各种字母出现的次数。应为大写字母的ASCII码与整数126个元素之间相差64，因此在算法中使用字母减去64作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；另外，要求出电文字符串中有多少种字符，并保存这些字符以供编码时使用。统计和保存都比较容易，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组元素中。具体实现如下：int jsq(char *s,int cnt,char str) /统计各字符串中各种字母的个数以及字符的种类 char *p; int i,j,k; int temp27; for(i=1;i=A & *p=Z) k=*p-64; tempk+; j=0; for(i=1,j=0;i=26;i+)/统计有多少种字符 if(tempi!=0) j+; strj=i+64;/将对应的数组送到数组中 cntj=tempi;/存入对应数组的权值 return j;4.1.3构造赫夫曼树void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str)/构造赫夫曼树HT int i,s1,s2; for(i=1;i=2*num-1;i+)/初始化HT，左右孩子，双亲，权值都为0 HTi.lchild=0; HTi.rchild=0; HTi.parent=0; HTi.weight=0; for(i=1;i=num;i+)/输入num个叶节点的权值 HTi.weight=cnti; for(i=num+1;i=2*num-1;i+)/从numd后面开始新建结点存放新生成的父节点 select(HT,i-1,&s1,&s2);/在HT1i-1中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2 HTs1.parent=i;HTs2.parent=i;/将s1和s2的parent赋值 HTi.lchild=s1; HTi.rchild=s2;/新结点的左右孩子 HTi.weight=HTs1.weight+ HTs2.weight;/新结点的权值 for(i=0;i=num;i+)/输入字符集中的字符 HCi.ch=stri; i=1; while(i=num) printf(字符 %c,次数为: %dn,HCi.ch,cnti+);4.2赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedef struct char ch; char bitsn+1; int start ; CodeNode; typedef CodeNode HuffmanCoden; 4.2.1赫夫曼编码算法 void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC) /根据赫夫曼树HT 求赫夫曼编码表 int c,p,i; char cdn; int start; cdnum=0; for(i=1;i0)/直至上诉到htc是树根为止 /若HTc是HTp的孩子，则生成0；否则生成代码1 cd-start=(HTp.lchild= =c)? 0:1 :c=p; /end of while strcpy(HCi.bits,&cdstart); HCi.len=num-start; 4.2.2建立正文的编码文件 建立编码文件的基本思想是：将要编码的字符串中的字符逐一与预先生成赫夫曼树时保保存的 字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完毕为止。 具体算法如下： viod coding(huffmanCode HC,char *str) int i,j; FILE *fp; fp =fopen(“codefile.tex”,”w”); while(*str)/对电文中字符逐一生成编码并写入文件 for(i=1;i=num;i+) if(HCi.ch= =*str) for(j=0;j=HCi.len;j+) fputc (HCi.bitsj,fp); break; str+