哈夫曼树课程设计报告

1、-. z.课程设计题目：哈夫曼编码器 院 系：专业班级： 学 号：学生*：指导教师： 2014年 1月 2日课程设计需求分析报告一、分析问题和确定解决方案1.分析问题利用哈夫曼编码进展通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进展译码复原。对于双工信道即可以双向传输信息的信道，每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。2.确定解决方案设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储构造存储所需要的数据，通过不同的函数

2、来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的t*t文件中，通过主函数调用来实现功能检测。3.输入的形式和输入值的*围手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。4.输出的形式在显示器界面上或者以文本的形式来实现程序调试的输出。5.程序所能到达的功能(1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmT

3、ree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode.(2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进展编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。(3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的代码码写入文件CodePrint中。(4)印哈夫曼树。将初始化的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。各个功能数据输出存储位置如表1所示表1：各个功能数据输出存储位置表功能字母二进制码初始

4、化WritehfmTree手动WritehfmCode手动ReadhfmTree文本读入ReadhfmCode文本读入hfmTree默认文本读入hfmCode默认文本读入编码WriteToBeTron手动WriteCodeFile手动ReadCodeFile文本读入印编码代码CodePrint印哈夫曼树TreePrint6.测试数据(1)正确的输入：1输入主菜单项中的英文字母I(i),E(e),D(d),P(p),Q(q)输出结果：进入所选的功能界面2输入子菜单项中的数字1，2，3，(4) 输出结果：执行所选的功能(2)含有错误的输入：1输入除了主菜单项中的英文字母I(i),E(e),D(d)

5、,P(p),Q(q) 输出结果： 2输入除了子菜单项中的数字1，2，3，(4) 输出结果：7.程序说明(1)程序中数据类型的定义：用到三组构造体，分别是哈夫曼树的动态数组存储构造*HuffmanTree，哈夫曼编码表的存储构造HuffmanCode，字符结点的动态数组存储构造wElem以及哈夫曼树类定义class Huffman。(2)主程序的流程图：用户从主菜单中选择所要进展的操作，如果输入选项错误则提示重新输入选项，否则进入选中的操作项(如图1所示)。 图1：主程序流程图(3)各程序模块之间的层次(调用)关系：主函数main调用初始化，编码，译码，打印二进制编码，打印哈夫曼树这五个子函数；

6、进入初始化功能后调用手动输入，文本读入，默认文本这三个函数；进入编码功能后调用手动编码，文本读入编码这两个函数；进入译码功能后调用手动译码，文本读入译码这两个函数(如图2所示)。 图2:：各程序模块之间的层次(调用)关系(4)默认的哈夫曼树：空格以及字母AZ频度分别为186，64，13，22，32，103，21，15，47，57，1，5，32，20，57，63，15，1，48，51，80，23，8，18，1，16，1建立一棵默认的哈夫曼树(如图3所示)。 图3：默认的哈夫曼树二、详细设计1、哈夫曼树存储及类的定义：#include #include #include #include #inc

7、lude typedef struct /哈夫曼树的存储构造int weight;/权值char HTch;/字符int parent,lchild,rchild;/双亲，左孩子，右孩子HTNode,*HuffmanTree; /动态数组存储哈夫曼树typedef struct /哈夫曼编码表的存储构造char ch; /字符char* hufCh; /二进制码HuffmanCode; /动态数组存储哈夫曼编码表typedef struct /字符结点char ch; /字符int wt; /字符权值wElem; /动态分配数组存储读入字符与权值class Huffmanpublic:Huff

8、man();/构造函数Huffman();/析构函数void Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n);/初始化，手动void Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v);/初始化，标准文件void Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int &n);/初始化，统计void EnCoding(HuffmanCode *HC,int hufnum); /手动编码voi

9、d EnCoding(HuffmanCode *HC,char*EnCodeFile); /文件读入编码void Print(char *);/打印二进制编码void Treeprinting( HTNode T,HuffmanTree HT,int n );/打印哈夫曼树;2、哈夫曼树的根本操作：/手动输入字符与权值并初始化void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n)/哈夫曼树对象，编码对象，字符数/从文件读入标准哈夫曼树并初始化void Huffman:Initialization(HuffmanTr

10、ee &HT,HuffmanCode *HC,int &n,int v)/哈夫曼树对象，编码对象，字符数,区分功能参数/从文件中统计字符与权值，构造哈弗曼树void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int &n)/哈夫曼树对象，编码对象，文件名，字符数/编码函数,对用户输入的文件的正文进展编码,然后将结果存入文件WriteCodeFile.t*t中void Huffman:EnCoding(HuffmanCode *HC,int hufnum)/编码数组对象，字符数/编码函数,从文件读取v

11、oid Huffman:EnCoding(HuffmanCode *HC,char*EnCodeFile)/编码数组对象，文件名/译码函数，对文件CodeFile中的代码进展译码,结果存入文件ReadTe*tFile.t*t中void Huffman:DeCoding(HuffmanTree HT,HuffmanCode *HC,char*DeCodeFile,int n)/哈夫曼树对象，编码对象，文件名，字符数/译码函数，手动输入void Huffman:DeCoding(HuffmanTree HT,HuffmanCode *HC,int n)/哈夫曼树对象，编码对象，字符数/打印函数，将

12、文件CodePrint.t*t中的内容以每行个代码显示在屏幕上void Huffman:Print(char* cfileName) /文件名/打印哈夫曼树void coprint(HuffmanTree start,HuffmanTree HT) /哈夫曼树对象，哈夫曼树对象其中局部操作的伪代码如下：(1)从文件读入标准哈夫曼树并初始化void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)/哈夫曼树对象，编码对象，字符数,区分功能参数定义一个动态数组存放空格和26个英文字母，把字符串 ABCDEFGH

13、IJKLMNOPQRSTUVW*YZ读入文件CharFile.t*twhile(charRead.get(inbuf)wj.ch=inbuf;wj.wt=cwj;j+;/w存放n字符及其权值(从0号单元开场),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC.int i,m,ww=0;/n:字符数 m:树结点数 int s1,s2;HuffmanTree p;/定义指针变量pif(n=1) return;/小于2个字符，完毕m=2*n-1;/n个叶子，2*n-1个结点HT=new HTNode(m+1)*sizeof(HTNode);HT0.parent=-1;HT0.lchild=-1;HT

14、0.rchild=-1;HT0.weight=0;for(p=HT+1,i=1;iweight=www.wt; p-HTch=www.ch;p-parent=p-lchild=p-rchild=0;/跳出循环时i=n+1;for(;iweight=0;p-HTch=#;p-parent=p-lchild=p-rchild=0; for(i=n+1;i=m;i+)/建立哈夫曼树Select(HT,i-1,s1,s2);/在HT数组的至i-1个结点中选择parent为且权值weight最小的两个结点,其序号分别为S1和S2;HTs1.parent=i;HTs2.parent=i;HTi.lchil

15、d=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;char *cd=new charn;/分配编码的存储空间cdn-1=0;/编码完毕符int c,f,start;for(i=1;i=n;i+)/逐个字符求哈夫曼编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi.ch=wi-1.ch;/复制字符HCi.hufCh=new char (n-start)*sizeof(char);/为第i个字

16、符编码分配空间strcpy(HCi.hufCh,&cdstart);/从cd复制编码(串)到HC/向屏幕输出哈夫曼编码,并把编码保存在文件hfmCode.t*t中;(2)编码函数,从文件读取void Huffman:EnCoding(HuffmanCode *HC,char*EnCodeFile)/编码数组对象，文件名对文件进展编码,并将编码存于文件ReadCodeFile.t*t中while(ufileRead.get(charInbuf)for(int k=1;k=27;k+)if(charInbuf=HCk.ch)codeWriteHCk.hufCh;break;3、主函数：#inclu

17、de Huffman.cpp/主函数void main() int current_n=27; /全局变量，字符数char c; /功能选择int hufnum=27; /默认字符数HuffmanTree HT; /哈夫曼树对象HuffmanCode *HC=new HuffmanCode(hufnum+1)*sizeof(HuffmanCode);/分配n 个 /字符编码的头指针向while(1)/主菜单cout请按顺序选择要实现的功能:;int k=1; Huffman hf;/类对象while(k)/将小写转化为大写switch(c)caseI:/进入初始化选择界面/选择初始化方式后，进

18、入子菜单switch(c)case 1:hf.Initialization(HT,HC,current_n);break; /手动初始化case 2:/输入需要初始化的文件名(需包含后缀名.t*t)建立哈夫曼树;/建立哈夫曼树,并把哈夫曼树存放在ReadhfmTree.t*t中 hf.Initialization(HT,HC,buf,current_n); break;/从文件读入数据初始化case 3:hf.Initialization(HT,HC,current_n,0);/标准初始化 case 4:break;break;caseE:/进入编码选择界面/选择字符序列读入方式后进入子菜单s

19、witch(c)case 1:hf.EnCoding(HC,hufnum);break;/手动编码 case 2:/输入需要的文件名(需包含后缀名.t*t)进展编码hf.EnCoding(HC,buf); break;/文件读入编码case 3:break;break;caseP:/进入打印二进制编码界面hf.Print(ReadCodeFile.t*t);break;caseT:/进入打印哈夫曼树界面 hf.Treeprinting(HT2*current_n-1,HT,current_n);break;caseQ:e*it(-1);/退出default:e*it(-1);三、系统调试与测试

20、1、调试过程中遇到的问题及解决方法:(1)逐个手动输入字符和权值进展编码，假设数据太大效率太低。解决方法：后来增加一个新的功能从文本中读入数据，这样可大大提高效率。(2)初始化文本读入时，假设数据过大，会完毕进程，无法进展操作。解决方法：增加动态数组的最大上限，当超过上限，会提示文本数据过大，而且可以显示*围内的数据。(3)只能读取固定的文件进展编码。解决方法：可以手动输入想要读取的文件名。(4)只能打印默认的哈夫曼树解决方法：通过增加两种初始化方式手动初始化和文本读入初始化，打印用户当前初始化的哈夫曼树。(5)进入子菜单后，输入的选项必须为数字，否则会出现死循环。解决方法：把输入的数据类型由

21、整型改为字符型。2、测试数据及其输出结果：(1)进入主菜单界面，用户可以选择所要执行的操作，比方：初始化，编码，译码，打印二进制编码代码，打印哈夫曼树。在执行编码、译码操作前，请先初始化默认的哈夫曼树(如图4所示) 。 图4：主菜单界面(2)进入初始化界面，用户可以选择执行手动初始化(如图5所示)，初始化结果存入WritehfmCode.t*t，WritehfmTree.t*t；文本读入初始化(如图6所示)，初始化结果存入ReadhfmCode.t*t，ReadhfmTree.t*t；默认文本初始化(如图7所示)，初始化结果存入hfmCode.t*t，hfmTree.t*t。 图5：手动初始化

22、哈夫曼树 图6：文本读入初始化哈夫曼树 图7：默认文本初始化(3)进入编码界面，用户可以选择执行手动编码(如图8所示)，编码结果存入WriteCodeFile.t*t；文本读入编码(如图9所示)，编码结果存入ReadCodeFile.t*t。 图8：手动编码 图9：文本读入编码(5)进入打印编码代码界面(如图12所示)，打印结果存入CodePrint.t*t。 图12：打印编码代码(6)进入打印哈夫曼树，打印结果存入TreePrint.t*t。打印默认哈夫曼树(如图13所示)，打印频度差距大的哈夫曼树(如图14所示)，打印频度差距小的哈夫曼树(如图15所示) 图13：打印默认哈夫曼树 图14：

23、打印频度差距大的哈夫曼树 图15：打印频度差距小的哈夫曼树 四、结果分析1、算法的时空分析和改良设想(选取主要函数)(1)程序算法分析：经过对程序中哈夫曼树的根本操作函数及其他相关算法的时空间复杂度的分析可知本程序中哈夫曼树的根本操作函数及相关算法的空间复杂度良好，但哈夫曼树的Initialization以及DeCoding操作函数的时间复杂度比拟复杂，不过从总体的算法效率看，哈夫曼树的根本操作函数及其他相关算法时间及空间复杂度良好，总体效率良好。(2)主要函数时空分析n代表字符种类数(如表2所示)：表2：主要函数时空分析表根本操作时间复杂度分析空间复杂度分析InitializationO(n

24、*n)S(n)EnCodingO(n)S(n)O(n)S(n)DeCodingO(n*n)S(n)O(n*n)S(n)PrintO(n)S(n)TreeprintingO(n)S(n)(3)改良设想：1当前使用的是一维动态数组存储，当哈夫曼函数添加增加、删除、修改这些功能时，可选用链式存储哈夫曼树，效率会更高。2、当前程序只能识别大写英文字母和空格，可改良为输入小写字母时也可识别。3、当前程序是在先序遍历哈夫曼树时，采用递归算法，可以设计一个非递归算法遍历哈夫曼树，这样可以降低时间复杂度，提高程序运行速率。2、经历和体会一周的课程设计完毕了，在这次的课程设计中不仅检验了我们所学习的知识，也培养了我们如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，与组员分工设计，相互探讨，相互学习，相互监视，学会了合作，学会了运筹帷幄，学会了宽容，学会了理解，也学会了做人与处世。完成这次的课程设计任务，我们要做好以下准备：(1)首先要熟练掌握二叉