哈夫曼树课程设计报告

1、闽江学院课程设计说明书题目： 哈夫曼编译码器 院 系： 计算机科学系 专业班级： 10软件工程 学 号： 学生姓名： 指导教师： 2011年 12 月 30 日 课程设计需求分析报告一、分析问题和确定解决方案1.分析问题利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。2.确定解决方案设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调

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

3、mcode;从文本中读入字符，建立哈夫曼树存于readhfmtree, 输出哈夫曼树及各字符对应的编码存于readhfmcode.(2)编码。手动输入一串大写英文字符，该字符存于writetobetron中，对字符进行编码并将它存于writecodefile中；从文件中读取字符编码并存于readcodefile中。(3)译码。先初始化默认哈夫曼树，手动输入二进制代码进行译码存于writetextfile中；从文件中读取二进制代码进行译码存于readtextfile中。(4)印代码文件。将文件readcodefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的代码码写入文件code

4、print中。(5)印哈夫曼树。将初始化的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。各个功能数据输出存储位置（如表1所示）表1：各个功能数据输出存储位置表功能字母二进制码初始化writehfmtree（手动）writehfmcode（手动）readhfmtree（文本读入）readhfmcode（文本读入）hfmtree（默认文本读入）hfmcode（默认文本读入）编码writetobetron（手动）writecodefile（手动）readcodefile（文本读入）译码writetextfile（手动）writecodefile（手动）re

5、adtextfile（文本读入）印编码代码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),p(p),q(q) 输出结果： 2输入除了子菜单项中的数字1，2，3，(4) 输出结果：7.程序说明(1)程序中数据类型的定义：用到三组结构体，分别是哈夫曼树的动态数组存储结构*huffmantree，哈夫曼编码表的存储结构huff

6、mancode，字符结点的动态数组存储结构welem以及哈夫曼树类定义class huffman。(2)主程序的流程图：用户从主菜单中选择所要进行的操作，如果输入选项错误则提示重新输入选项，否则进入选中的操作项(如图1所示)。 图1：主程序流程图(3)各程序模块之间的层次(调用)关系：主函数main（）调用初始化，编码，译码，打印二进制编码，打印哈夫曼树这五个子函数；进入初始化功能后调用手动输入，文本读入，默认文本这三个函数；进入编码功能后调用手动编码，文本读入编码这两个函数；进入译码功能后调用手动译码，文本读入译码这两个函数(如图2所示)。 图2:：各程序模块之间的层次(调用)关系(4)默认

7、的哈夫曼树：空格以及字母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 #include typedef struct /哈夫曼树的存储结构int weight;/权值char htch;/字符int parent,lchild,rchild;/双亲，左孩子，右孩子htnode,*huffmantree; /

8、动态数组存储哈夫曼树typedef struct /哈夫曼编码表的存储结构char ch; /字符char* hufch; /二进制码huffmancode; /动态数组存储哈夫曼编码表typedef struct /字符结点char ch; /字符int wt; /字符权值welem; /动态分配数组存储读入字符与权值class huffmanpublic:huffman();/构造函数huffman();/析构函数void initialization(huffmantree &ht,huffmancode *hc,int &n);/初始化，手动void initialization(hu

9、ffmantree &ht,huffmancode *hc,int &n,int v);/初始化，标准文件void initialization(huffmantree &ht,huffmancode *hc,char*initfile,int &n);/初始化，统计void encoding(huffmancode *hc,int hufnum); /手动编码void encoding(huffmancode *hc,char*encodefile); /文件读入编码void decoding(huffmantree ht,huffmancode *hc,int n);/手动译码void d

10、ecoding(huffmantree ht,huffmancode *hc,char*decodefile,int n);/文件读入译码void print(char *);/打印二进制编码void treeprinting( htnode t,huffmantree ht,int n );/打印哈夫曼树;2、哈夫曼树的基本操作：/手动输入字符与权值并初始化void huffman:initialization(huffmantree &ht,huffmancode *hc,int &n)/哈夫曼树对象，编码对象，字符数/从文件读入标准哈夫曼树并初始化void huffman:initial

11、ization(huffmantree &ht,huffmancode *hc,int &n,int v)/哈夫曼树对象，编码对象，字符数,区分功能参数/从文件中统计字符与权值，构造哈弗曼树void huffman:initialization(huffmantree &ht,huffmancode *hc,char*initfile,int &n)/哈夫曼树对象，编码对象，文件名，字符数/编码函数,对用户输入的文件的正文进行编码,然后将结果存入文件writecodefile.txt中void huffman:encoding(huffmancode *hc,int hufnum)/编码数组对

12、象，字符数/编码函数,从文件读取void huffman:encoding(huffmancode *hc,char*encodefile)/编码数组对象，文件名/译码函数，对文件codefile中的代码进行译码,结果存入文件readtextfile.txt中void huffman:decoding(huffmantree ht,huffmancode *hc,char*decodefile,int n)/哈夫曼树对象，编码对象，文件名，字符数/译码函数，手动输入void huffman:decoding(huffmantree ht,huffmancode *hc,int n)/哈夫曼树对

13、象，编码对象，字符数/打印函数，将文件codeprint.txt中的内容以每行个代码显示在屏幕上void huffman:print(char* cfilename) /文件名/打印哈夫曼树void coprint(huffmantree start,huffmantree ht) /哈夫曼树对象，哈夫曼树对象其中部分操作的伪代码如下：(1)从文件读入标准哈夫曼树并初始化void huffman:initialization(huffmantree &ht,huffmancode *hc,int &n,int v)/哈夫曼树对象，编码对象，字符数,区分功能参数定义一个动态数组存放空格和26个英

14、文字母，把字符串 abcdefghijklmnopqrstuvwxyz读入文件charfile.txtwhile(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

15、;ht0.lchild=-1;ht0.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.p

16、arent=i;hti.lchild=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)*si

17、zeof(char);/为第i个字符编码分配空间strcpy(hci.hufch,&cdstart);/从cd复制编码(串)到hc/向屏幕输出哈夫曼编码,并把编码保存在文件hfmcode.txt中;(2)编码函数,从文件读取void huffman:encoding(huffmancode *hc,char*encodefile)/编码数组对象，文件名对文件进行编码,并将编码存于文件readcodefile.txt中while(ufileread.get(charinbuf)for(int k=1;k=27;k+)if(charinbuf=hck.ch)codewritehck.hufch;b

18、reak; 3、主函数：#include 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:/进

19、入初始化选择界面/选择初始化方式后，进入子菜单switch(c)case 1:hf.initialization(ht,hc,current_n);break; /手动初始化case 2:/输入需要初始化的文件名(需包含后缀名.txt)建立哈夫曼树;/建立哈夫曼树,并把哈夫曼树存放在readhfmtree.txt中 hf.initialization(ht,hc,buf,current_n); break;/从文件读入数据初始化case 3:hf.initialization(ht,hc,current_n,0);/标准初始化 case 4:break;break;casee:/进入编码选择界

20、面/选择字符序列读入方式后进入子菜单switch(c)case 1:hf.encoding(hc,hufnum);break;/手动编码 case 2:/输入需要的文件名(需包含后缀名.txt) 进行编码hf.encoding(hc,buf); break;/文件读入编码 case 3:break;break;cased:/进入译码选择界面/选择译码方式后进入子菜单switch(c)case 1:hf.decoding(ht,hc,hufnum); break;/手动译码 case 2:/输入需要的文件名(需包含后缀名.txt) 进行译码 hf.decoding(ht,hc,buf,hufnu

21、m);break;/文件译码case 3:break;/返回break;casep:/进入打印二进制编码界面 hf.print(readcodefile.txt);break;caset:/进入打印哈夫曼树界面 hf.treeprinting(ht2*current_n-1,ht,current_n);break;caseq:exit(-1);/退出default:exit(-1);三、系统调试与测试1、调试过程中遇到的问题及解决办法:(1)逐个手动输入字符和权值进行编码，若数据太大效率太低。解决办法：后来增加一个新的功能从文本中读入数据，这样可大大提高效率。(2)初始化文本读入时，若数据过大

22、，会结束进程，无法进行操作。解决办法：增加动态数组的最大上限，当超过上限，会提示“文本数据过大”，而且可以显示范围内的数据。(3)只能读取固定的文件进行编码。解决办法：可以手动输入想要读取的文件名。(4)只能打印默认的哈夫曼树解决办法：通过增加两种初始化方式（手动初始化和文本读入初始化），打印用户当前初始化的哈夫曼树。(5)进入子菜单后，输入的选项必须为数字，否则会出现死循环。解决办法：把输入的数据类型由整型改为字符型。2、测试数据及其输出结果：(1)进入主菜单界面，用户可以选择所要执行的操作，比如：初始化，编码，译码，打印二进制编码代码，打印哈夫曼树。在执行编码、译码操作前，请先初始化默认的

23、哈夫曼树(如图4所示) 。 图4：主菜单界面(2)进入初始化界面，用户可以选择执行手动初始化(如图5所示)，初始化结果存入writehfmcode.txt，writehfmtree.txt；文本读入初始化(如图6所示)，初始化结果存入readhfmcode.txt，readhfmtree.txt；默认文本初始化(如图7所示)，初始化结果存入hfmcode.txt，hfmtree.txt。 图5：手动初始化哈夫曼树 图6：文本读入初始化哈夫曼树 图7：默认文本初始化(3)进入编码界面，用户可以选择执行手动编码(如图8所示)，编码结果存入writecodefile.txt；文本读入编码(如图9所示

24、)，编码结果存入readcodefile.txt。 图8：手动编码 图9：文本读入编码(4)进入译码界面，用户可以选择执行手动译码(如图10所示)，译码结果存入writetextfile.txt；文本读入译码(如图11所示)，译码结果存入readtextfile.txt。 图10：手动译码 图11：文本译码(5)进入打印编码代码界面(如图12所示)，打印结果存入codeprint.txt。 图12：打印编码代码(6)进入打印哈夫曼树，打印结果存入treeprint.txt。打印默认哈夫曼树(如图13所示)，打印频度差距大的哈夫曼树(如图14所示)，打印频度差距小的哈夫曼树(如图15所示) 图1

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

26、initializationo(n*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、经验和体会一周的课程设计结束了，在这次的课程设计中不仅检验了我们所学习的知识，也培养了我们如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，与组员分工设计，相互探讨，相互学习，相互监督，学会了合作，学会了运筹帷幄，学