实验四-赫夫曼.doc

目 录1.概述 11.1问题描述 12.现状分析 13.系统分析 14.1系统功能模块图 25.1赫夫曼树的存储构造定义 35.2赫夫曼算法及其实现 35.3记录字符串中字符的种类以及各类字符的个数 35.4赫夫曼编译码系统功能模块 36.重要代码构造 46.1定义赫夫曼编码类型如下 46.2赫夫曼编码算法 46.3建立正文的编码文献 57.重要代码段分析 67.1赫夫曼编码的构造定义 67.2赫夫曼编码算法 68.运营与测试 78.1 测试数据及成果 79.总结和心得 8参照文献 810.附：源代码 91.概述1.1问题描述 运用赫夫曼编码进行通信可以大大提高信道运用率，缩短信息传播时间，减少传播成本这规定在发送端通过一种编码系统看待传播数据预先编码，对于双工信道（即可以双向传播信息的信道），每端都需要一种完整的编码系统2.现状分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文献的存储空间和计算机网络的传送时间已越来越引起人们的注重，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术赫夫曼编码是一种编码方式，以赫夫曼树—即最优二叉树，带权途径长度最小的二叉树，常常应用于数据压缩。

赫夫曼编码使用一张特殊的编码表将源字符（例如某文献中的一种符号）进行编码赫夫曼编码的应用很广泛，运用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码树中从根到每个叶子均有一条途径，对途径上的各分支商定：指向左子树的分支表达“0”码，指向右子树的分支表达“1”码，取每条途径上的“0”或“1”的序列作为和各个叶子相应的字符的编码，这就是赫夫曼编码赫夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串. 赫夫曼编码是已被证明的一种有效的熵编码方式, 在诸如文本、图像、视频压缩及通信、密码等信息压缩编码原则中被广泛使用目前广泛应用的许多其她高效数据压缩算法3.系统分析运用二叉树构造实现赫夫曼编/解码器 基本规定： 1、 初始化：可以对输入的任意长度的字符串进行记录，记录每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：运用已经建好的赫夫曼树进行编码，并将每个字符的编码输出 3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出 4、 译码(Decoding)：运用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码成果。

4.概要设计4.1系统功能模块图赫夫曼编\译码器的重要功能是先建立赫夫曼树，然后运用建好的赫夫曼树生成赫夫曼编码后进行译码 在数据通信中，常常需要将传送的文字转换成由二进制字符0、1构成的二进制串，称之为编码构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所通过的途径分支构成的0和1的序列便为该节点相应字符的编码，称之为赫夫曼编码 最简朴的二进制编码方式是等长编码若采用不等长编码，让浮现频率高的字符具有较短的编码，让浮现频率低的字符具有较长的编码，这样也许缩短传送电文的总长度赫夫曼树课用于构造使电文的编码总长最短的编码方案赫夫曼编码 /译码器类型及有关变量的定义建立赫夫曼树生成赫夫曼文献赫夫曼译码4.1系统功能模块图5.具体设计5.1赫夫曼树的存储构造定义#define n 100//叶子结点数#define m 2*n-1//赫夫曼树中结点总数typedef struct{ int weight;//权值 int lchild,rchild,parent;//左右孩子及双亲指针}HTNode;//树中结点类型typedef HTNode HuffmanTree[m+1];//零号单元不用5.2赫夫曼算法及其实现①根据给定的n 个权值{w1, w2 ,···wn }, 构成n 棵二叉树的集F={T1,T2 ,···Tn }, 其中每棵二叉树Ti 中只有一种带权为wi 的根结点,其左右子树均空。

②在F 中选用两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树, 且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和③在F 中删除这两棵树, 同步将新得到的二叉树加入F 中④反复②和③, 直到F 只含一棵树为止, 这棵树便是赫夫曼树 5.3记录字符串中字符的种类以及各类字符的个数该算法的重要实现思想是：先定义一种具有26个元素的临时整型数组，用来存储多种字母浮现的次数由于大写字母与小写字母相差64位，因此在算法中我们可以使用字母减去64作为记录数组的下标对号入座在记录和保存过程中，我们用一种循环来判断先前记录的各类字符与否为零，若不为零，则将其存入一种数组相应得元素中，同步将其相应的字符也存入另一种数组元素中5.4赫夫曼编译码系统功能模块( 1)赫夫曼建树模块 : 根据输入的字符和频率, 完毕赫夫曼树的构造, 并根据赫夫曼树求赫夫曼编码 2)编码模块: 读取文本文献进行编码, 编码成果存入到新文献 3)译码模块: 读取编码文献并解码, 打开存储编码的文献, 根据所读取的编码文献中的每字符,运用赫夫曼树进行解码 4)输出模块: 将解码后的每个字母写入到一种新的文献中6.重要代码构造6.1定义赫夫曼编码类型如下typedef struct{char ch;//寄存编码的字符char bits[n+1];//寄存编码的位置int start;//编码起始位置}CodeNode;typedef CodeNode HuffmanCode[n];6.2赫夫曼编码算法void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC){ int c,p,i; char cd[n]; int start; cd[num]='\0'; for(i=1;i<=num;i++) { start=num; c=i; while((p=HT[c].parent)>0) { cd[--start]=(HT[p].lchild==c) ?'0':'1'; c=p; } strcpy(HC[i].bits,&cd[start]); HC[i].len=num-start; }}6.3建立正文的编码文献建立正文的编码文献的基本思想是：将要编码的字符串中的字符逐个与预先生成赫夫曼树是保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文献，直至所有的字符解决完为止。

具体实现算法如下：void coding(HuffmanCode HC,char*str){ int i,j; FILE *fp; fp=fopen("codefile.txt","w"); while(*str){ for(i=1;i<=num;i++) if(HC[i].ch==*str){ for(j=0;j0)//直至上溯到HT[c]是树根为止 {//若HT[c]是HT[p]的左孩子，则生成0；否则生成代码1 cd[--start]=(HT[p].lchild==c) ?'0':'1'; c=p; } strcpy(HC[i].bits,&cd[start]); HC[i].len=num-start; }}8.运营与测试8.1 测试数据及成果输入：NO MAN CAN DO TWO THINGS AT ONCE,得出成果：9.总结和心得通过这次课程设计，我们学习了诸多在上课没懂的知识，并对求赫夫曼树及赫夫曼编码/译码的算法有了更加深刻的理解。

更巩固了课堂中学习有有关赫夫曼编码的知识.参照文献[1] 《数据构造课程设计》-----苏仕华 等编著[2] 《数据构造（C语言版）》-----严蔚敏 吴伟民编著[3] 《C程序设计（第三版）》------谭浩强 著10.附：源代码#include #include /*(1)类型及有关变量的定义*/#define n 100// 叶子结点数#define m 2*n-1//赫夫曼树中的结点总数typedef struct { char ch; char bits[9];//寄存编码位串 int len;//编码长度}CodeNode;typedef CodeNode HuffmanCode[n+1];typedef struct { int weight;//权值 int lchild,rchild,parent;//左右孩子及双亲指针}HTNode;//树中的结点类型typedef HTNode HuffmanTree[m+1];//0号单元不可用int num;//字母类型的个数/*(2)建立赫夫曼树的三个函数*/void select(HuffmanTree T,int k,int *s1,int *s2){//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分别为S1和S2 int i,j; int min1=100; for(i=1;i<=k;i++)//查找s1 if(T[i].weight