哈夫曼编译码器课程教学设计报告

1、学号15082015-2016 学年 第 1 学期数据结构课程设计报告题目：哈夫曼编 / 译码器专业：计算机科学与技术（对口）班 级 ：13 （3）姓名：陈霞指导教师：彭飞成绩：,.计算机学院2015 年11 月12 日目录1设计内容及要求 .31.1内容 .31.2要求 .42概要设计 .52.1抽象数据类型定义 .52.2模块划分 .73设计过程及代码 .73.1设计过程 .73.2代码 .11,.4设计结果与分析175参考文献201 设计内容及要求1.1 内容,.利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数

2、据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工信道 （即可以双向传输信息的信道），每端都需要一个完整的编/ 译码系统。 试为这样的信息收发站写一个哈夫曼编/ 译码系统。1.2 要求一个完整的系统应具有以下功能：（ 1 ） I：初始化（ Initialization）。从终端读入字符集大小n ，以及 n 个字符和n 个权值，建立哈夫曼树，并将它存于文件hfmTree中。（ 2 ） E：编码（ Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（ 3 ） D ：译码（ D

3、ecoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（ 4 ）P：印代码文件（ Print ）。将文件 CodeFile以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码写入文件CodePrint中。（ 5 ）T：印哈夫曼树（ Tree Printing ）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 测试数据 （ 1 ）数据一：已知某系统在通信联络中只可能出现8 种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23

4、,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序,.进行调试。（ 2 ）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“ THIS PROGRAM IS MY FAVORITE ”。字符频度ABCDEFGHIJKLM1864132232102115475715322063字符频度NOPQRSTUVWXYZ57631514851802381811612 概要设计2.1抽象数据类型定义ADT Stack数据对象： D=ai|ai ElemSet,i=1,2,.,n, n0数据关系：若 D 为空集，则称为空树。若 D 仅为一个数据元素，则 R 为空集，否则

5、 R=H ， H 是如下的二元关系：（ 1）再 D 中存在唯一的称为根的数据元素root ，它在关系 H 下无前驱。（ 2）若 D-root空集，则存在一个划分D1 ， D2 ，Dm，（ m0 ）。（ 3 ）对应于 D-root的划分， H-root ，X1 ， 有唯一的一个划分H1 ，H2 ，Hm，（ m0 ）。,.基本操作：InitTree(&T)操作结果：构造空树T。DestroyTree(&T)初始条件：树T 已存在。操作结果：树T 被销毁。ClearTree(&T)初始条件：树T 已存在。操作结果：将树T 清为空栈。TreeEmpty(T)初始条件：树T 已存在。操作结果：若树T 为

6、空，则返回TRUE ，否则 FALSE。TreeDepth(T)初始条件 :树 T 已存在。操作结果：返回T 的深度。Root （ T）初始条件：树T 已存在。操作结果：返回树T 的根。,.2.2模块划分本程序包括三个模块：(1) 主程序模块void main()初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；（ 2 ）哈夫曼模块实现哈夫曼树的抽象数据类型（ 3 ）求哈夫曼编码模块实现求哈夫曼编码算法的数据类型3 设计过程及代码3.1设计过程1 、 数据类型的定义（1 ）哈夫曼树类型typedef struct/构造树char data;/结点权值int weight;/权重,.int p

7、arent;/双亲结点int lchild;/左孩子int rchild;/右孩子HTNode;HTNode ht30;（2 ）求哈夫曼编码类型typedef structchar cd30;/存放当前结点的哈弗曼编码int start;/cdstartcdn存放哈弗曼码HCode;HCode hcd30;,.2 、主要模块的算法描述,.开始Int I,f,c;Int I;I=0inInScanf( “%d”,&htt.weHc.start=n;c=ii+F!=-1结束multiplex主函数流程图图 3.1.1Hc.start+;I+哈弗曼编码算法流程图图 3.1.2,.3.2代码#incl

8、ude#define n 27 /叶子数目#define m (2*n-1)/结点总数#define maxval 10000.0#define maxsize 100/哈夫曼编码的最大位数typedef structchar ch;float weight;int lchild,rchild,parent;hufmtree;typedef structchar bitsn;/位串int start;/编码在位串中的起始位置char ch;/字符codetype;void huffman(hufmtree tree);/建立哈夫曼树,.void huffmancode(codetype cod

9、e,hufmtree tree);/根据哈夫曼树求出哈夫曼编码void decode(hufmtree tree);/依次读入字符，根据哈夫曼树译码intmain()printf(哈夫曼编码n);printf(总共有 %d 个字符 n,n);hufmtree treem;codetype coden;int i,j;/循环变量huffman(tree);/建立哈夫曼树huffmancode(code,tree);/根据哈夫曼树求出哈夫曼编码printf(【输出每个字符的哈夫曼编码】n);for(i=0;in;i+)printf(%c: ,codei.ch);for(j=codei.start;

10、jn;j+)printf(%c ,codei.bitsj);printf(n);printf(【读入字符，并进行译码】n);decode(tree);/依次读入电文，根据哈夫曼树译码void huffman(hufmtree tree)/建立哈夫曼树,.int i,j,p1,p2;/p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标float small1,small2,f;char c;for(i=0;im;i+)/初始化treei.parent=0;treei.lchild=-1;treei.rchild=-1;treei.weight=0.0;printf(【依次读入前%d 个

11、结点的字符及权值(中间用空格隔开)】 n,n);for(i=0;in;i+) /读入前n 个结点的字符及权值printf(输入第 %d 个字符为和权值,i+1);scanf(%c %f,&c,&f);getchar();treei.ch=c;treei.weight=f;for(i=n;im;i+)/进行 n-1次合并，产生n-1个新结点p1=0;,.p2=0;small1=maxval;small2=maxval;/maxval是 float类型的最大值for(j=0;ji;j+)/选出两个权值最小的根结点if(treej.parent=0)if(treej.weightsmall1)sma

12、ll2=small1; /改变最小权、次小权及对应的位置small1=treej.weight;p2=p1;p1=j;elseif(treej.weightsmall2)small2=treej.weight; /改变次小权及位置p2=j;treep1.parent=i;treep2.parent=i;treei.lchild=p1; /最小权根结点是新结点的左孩子treei.rchild=p2; /次小权根结点是新结点的右孩子,.treei.weight=treep1.weight+treep2.weight;/huffmanvoid huffmancode(codetype code,hu

13、fmtree tree)/根据哈夫曼树求出哈夫曼编码/codetype code为求出的哈夫曼编码/hufmtree tree为已知的哈夫曼树int i,c,p;codetype cd;/缓冲变量for(i=0;in;i+)cd.start=n;cd.ch=treei.ch;c=i;/从叶结点出发向上回溯p=treei.parent;/treep是 treei 的双亲while(p!=0)cd.start-;if(treep.lchild=c)cd.bitscd.start=0;/treei是左子树，生成代码0elsecd.bitscd.start=1;/treei是右子树，生成代码1,.c=

14、p;p=treep.parent;codei=cd;/第 i+1 个字符的编码存入codei/huffmancodevoid decode(hufmtree tree)/依次读入字符，根据哈夫曼树译码int i,j=0;char bmaxsize;char endflag=2;/电文结束标志取2i=m-1;/从根结点开始往下搜索printf(输入发送的编码(以 2 为结束标志)： );gets(b);printf(译码后的字符为);while(bj!=2)if(bj=0)i=treei.lchild;/走向左孩子elsei=treei.rchild;/走向右孩子if(treei.lchild=-1)/treei是叶结点,.printf(%c,treei.ch);