哈夫曼树课程设计报告

《哈夫曼树课程设计报告》由会员分享，可在线阅读，更多相关《哈夫曼树课程设计报告（20页珍藏版）》请在装配图网上搜索。

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

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

3、tehfmCode; 从文本中读 入字 符,建立 哈夫曼树存 于 ReadhfmTree, 输出哈夫 曼树及各 字符对应的 编 码存于 ReadhfmCode.(2) 编码。手动输入一串大写英文字符,该字符存于 WriteToBeTron 中,对字符进行编码并 将它存于 WriteCodeFile 中；从文件中读取字符编码并存于 ReadCodeFile 中。印代码文件。将文件 ReadCodeFile 以紧凑格式显示在终端上,每行 50 个代码。同时将此字符形式的代码码写入文件CodePrint中。(3) 印哈夫曼树。将初始化的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入

4、文件 TreePri nt 中。各个功能数据输出存储位置(如表1所示)表1:各个功能数据输出存储位置表功能字母二进制码初始化WritehfmTree （手动）WritehfmCode （手动）ReadhfmTree (文本读入)ReadhfmCode (文本读入)hfmTree (默认文本读入)hfmCode (默认文本读入)编码WriteToBeTro n （手动）WriteCodeFile（手动）ReadCodeFile （文本读入）印编码代码CodePri nt印哈夫曼树TreePri nt6. 测试数据(1) 正确的输入：1输入主菜单项中的英文字母l(i),E(e),D(d),P(p)

5、,Q(q)输出结果：进入所选的功能界面2输入子菜单项中的数字1，2，3，(4)输出结果：执行所选的功能 含有错误的输入：1输入除了主菜单项中的英文字母I(i),E(e),D(d),P(p),Q(q)输出结果： 2输入除了子菜单项中的数字1，2，3，(4)输出结果： 7. 程序说明(1)程序中数据类型的定义：用到三组结构体，分别是哈夫曼树的动态数组存储结构*HuffmanTree，哈夫曼编码表的存储结构HuffmanCode,字符结点的动态数组存储结构wElem以及哈夫曼树类定义 class Huffman主程序的流程图：_L是、否正_L否选择菜单项主臺单清重新输入选项数（如图2所示）。图2:各

6、程序模块之间的层次（调用）关系用户从主菜单中选择所要进行的操作，如果输入选项错误则提示重新输入选项，否则进入选中的操作项（如图1 所示）。I-初姑化 ”上 11UOUO 丄 HunffinooD lunnDimi lnrunLoua inKDoioii叵IOOOOl图3 :默认的哈夫曼树、详细设计1、哈夫曼树存储及类的定义:#in elude #in elude #i nclude #i nclude #in elude typedef struct /int weight;char HTch;int pare nt,lchild,rchild;哈夫曼树的存储结构/权值/字符/双亲，左孩子，右

7、孩子HTNode,*Huffma nTree; typedef struct /动态数组存储哈夫曼树哈夫曼编码表的存储结构char ch;/ 字符char* hufCh;/ 二进制码Huffma nCode;/动态数组存储哈夫曼编码表typedef struct / char ch; /int wt; / wElem; / class Huffman字符结点字符字符权值动态分配数组存储读入字符与权值public:Huffman();/ 构造函数初始化，手动Huffman();/ 析构函数void Initialization(HuffmanTree &HT,HuffmanCode *HC,in

8、t &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); / void EnCoding(HuffmanCode *HC,char*EnCodeFile); / void Print(char *);/ 打印二进制编码 void Tree

9、printing( HTNode T,HuffmanTree HT,int n );/手动编码文件读入编码打印哈夫曼树;2、哈夫曼树的基本操作：/手动输入字符与权值并初始化 void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n)/哈夫曼树对象，编码对象，字符数 /从文件读入标准哈夫曼树并初始化 void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,int &n,int v)/ 哈夫曼树对 象，编码对象， 字符 数,区分功能参数 /从文件中统计字符与权

10、值，构造哈弗曼树 void Huffman:Initialization(HuffmanTree &HT,HuffmanCode *HC,char*InitFile,int &n)/哈夫曼树对象，编码对 象，文件名， 字符数 /编码函数 ,对用户输入的文件的正文进行编码 ,然后将结果存入文件 WriteCodeFile.txt 中 void Huffman:EnCoding(HuffmanCode *HC,int hufnum)/ 编码数组对象，字符数 /编码函数 ,从文件读取 void Huffman:EnCoding(HuffmanCode *HC,char*EnCodeFile)/ 编码

11、数组对象，文件名 /译码函数，对文件 CodeFile 中的代码进行译码 ,结果存入文件 ReadTextFile.txt 中 void Huffman:DeCoding(HuffmanTree HT,HuffmanCode *HC,char*DeCodeFile,int n)/哈夫曼树对象，编码对象， 文件名，字符数 /译码函数，手动输入 void Huffman:DeCoding(HuffmanTree HT,HuffmanCode *HC,int n)/ 哈夫曼树对象，编码对 象，字符数/打印函数，将文件 CodePrint.txt 中的内容以每行个代码显示在屏幕上void Huffma

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

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

14、ght=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个结点中选择pare nt为且权值weight最小的两个结点，其序号分别为S1和S2;HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2

15、;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 个字符编码分配空间 s

16、trcpy(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;break;3、主函数：

17、#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

18、) caseI: / 进入初始化选择界面/ 选择初始化方式后，进入子菜单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);/ 标准初始化 ca

19、se 4: break;break;caseE: / 进入编码选择界面/ 选择字符序列读入方式后进入子菜单switch(c)case 1:hf.EnCoding(HC,hufnum);break; / 手动编码 case 2:/ 输入需要的文件名 ( 需包含后缀名 .txt) 进行编码hf.EnCoding(HC,buf); break; / 文件读入编码case 3:break;break;caseP:/ 进入打印二进制编码界面 hf.Print(ReadCodeFile.txt); break; caseT:/ 进入打印哈夫曼树界面 hf.Treeprinting(HT2*current_

20、n-1,HT,current_n);break; caseQ:exit(-1); / 退出 default:exit(-1);三、系统调试与测试1、调试过程中遇到的问题及解决办法 :(1) 逐个手动输入字符和权值进行编码，若数据太大效率太低。 解决办法：后来增加一个新的功能从文本中读入数据，这样可大大提高效率。(2) 初始化文本读入时，若数据过大，会结束进程，无法进行操作。 解决办法：增加动态数组的最大上限，当超过上限，会提示“文本数据过大” ，而且可以显 示范围内的数据。(3) 只能读取固定的文件进行编码。 解决办法：可以手动输入想要读取的文件名。(4) 只能打印默认的哈夫曼树 解决办法：通

21、过增加两种初始化方式(手动初始化和文本读入初始化) ，打印用户当前初始 化的哈夫曼树。(5) 进入子菜单后，输入的选项必须为数字，否则会出现死循环。 解决办法：把输入的数据类型由整型改为字符型。2、测试数据及其输出结果：(1) 进入主菜单界面，用户可以选择所要执行的操作，比如：初始化建立哈夫曼树 ，编码，译码，打印二进制编码代码，打印哈夫曼树。在执行编码、译码操作前，请先初始化默认的 哈夫曼树 (如图 4 所示) 。哈化用始码码用務 便初编译S - 一 - 二-二 - - _一 - 二一 一 _一 _ 一一X I E D p T Q码树 代曼 码夫 编哈二二器tt译夫二 二 二 二 二 二 二

22、请按顺序选择要实现的功:图4 :主菜单界面（2）进入初始化界面，用户可以选择执行手动初始化（如图5所示），初始化结果存入WritehfmCode.txt ，WritehfmTree.txt;文本读入初始化（如图6 所示），初始化结果存入ReadhfmCode.txt ， ReadhfmTree.txt ;默认文本初始化（如图 7 所示），初始化结果存入hfmCode.txt ， hfmTree.txt 。标til合夫晏树3个字樓E 箜始回 手从裂 -择入段tAiAtAiAiAiAiA人符字 主nL月士戶t冃士戶十ZL-Hluk主II-HIUE士尸土片士冃茶竟键返回主菜图5:手动初始化哈夫曼树祐

23、 丰辜導不马后”輪石马 證咅弋书马1. Id kJ IdHL.VPP丄也也丄 JLJ1L直直 ni. mt FtJLBJL jLX ZL 0101XX0JLX 匕3ZL亘0 i mt乃卫 0BBeJL0XX0JL JL文f_L X 0 0000 1 J o j fimFm l Ffe x im HRcm-i m fi =L=L 0X0000X JL JL 七爭九灵冋土奈屮图6 :文本读入初始化哈夫曼树请选揑初始化方 将字卷需码后編前希马ill iiu f员鈕航航融 00000 1H110010 110011 180001 UQJM1 0110 11Q8801000 丄 10111 11BB10

24、 0111 1U011100S610010010 0011 11H1按任愛键返回主菜单6S001 11UUU00 110001 1100081010 1Q301丄 1100031011图7 :默认文本初始化进入编码界面，用户可以选择执行手动编码（如图8所示），编码结果存入WriteCodeFile.txt ;文本读入编码（如图9所示），编码结果存入 ReadCodeFile.txt 。亍育选拝:字 符序歹IJ i贡入方 式是否査看编石孕后的二进制代可呂?丈是否=n图&手动编码手动请选择字符序列谏入方式乂 2请输入文件掘 ：321 - txt+ 対文件进行编码井槁编码存于文件ReadCo de

25、File ”七xt：中+退否査看编码后的二进制代码？ 是汰亠否=N=y编码后的二进制码为.011031111110110100111000110131111111101000131011100 RW101 01101 01l 130101 Q11110101Q1100111001,1.丄 1111 按任童撻返回主菜单图9:文本读入编码进入打印编码代码界面（如图12所示），打印结果存入 CodePrint.txt。请按顺序选择芸实现的功龍i漏码后的二进制码为=3100111010000000011110X0S010X0X1X0S3SQ91e0100091B0100101B00916llllie0

26、00091B100m & 1001 0好士 1 m 按任意琏返回主菜单亠图12：打印编码代码进入打印哈夫曼树，打印结果存入TreePrint.txt。打印默认哈夫曼树（如图13所示），打印频度差距大的哈夫曼树（如图14所示），打印频度差距小的哈夫曼树（如图15所示）-4 1(图13:打印默认哈夫曼树图15:打印频度差距小的哈夫曼树四、结果分析1、算法的时空分析和改进设想(选取主要函数)(1) 程序算法分析：经过对程序中哈夫曼树的基本操作函数及其他相关算法的时空间复杂度的分析可知本程序中哈夫曼树的基本操作函数及相关算法的空间复杂度良好，但哈夫曼树的Initialization以及DeCoding

27、操作函数的时间复杂度比较复杂，不过从总体的算法效率看，哈夫曼树的 基本操作函数及其他相关算法时间及空间复杂度良好，总体效率良好。(2) 主要函数时空分析(n代表字符种类数)(如表2所示):表2:主要函数时空分析表基本操作时间复杂度分析空间复杂度分析In itializatio nO(n*n)S(n)En Cod ing0(n)S(n)O(n)S(n)DeCodi ngO(n*n)S(n)O(n*n)S(n)PrintO(n)S(n)Treepri nti ngO(n)S(n)改进设想：1当前使用的是一维动态数组存储，当哈夫曼函数添加增加、删除、修改这些功能时， 可选用链式存储哈夫曼树，效率会更

28、高。2、当前程序只能识别大写英文字母和空格，可改进为输入小写字母时也可识别。3、当前程序是在先序遍历哈夫曼树时，采用递归算法，可以设计一个非递归算法遍历哈夫曼树，这样可以降低时间复杂度，提高程序运行速率。2、经验和体会一周的课程设计结束了， 在这次的课程设计中不仅检验了我们所学习的知识，也培养了我们如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，与组员分工设计，相互探讨，相互学习，相互监督，学会了合作，学会了运筹帷幄，学会了宽容， 学会了理解，也学会了做人与处世。完成这次的课程设计任务，我们要做好以下准备：(1) 首先要熟练掌握二叉树的性质、先序遍历二叉树、最优二叉树的

29、构建、字符串匹配等， 然后在此基础上掌握理解 huffman树和编码和译码。(2) 完成哈夫曼编译器，我们要考虑如何把文件当中的英文字母编成二进制代码，如何将二 进制代码翻译成英文字母以及如何构建一棵哈夫曼树。在这次的课程设计任务中，我们遇到的问题和困难：(1) 起初功能太简单，经过讨论，我们增加了一些必要的选择功能，比如：读入方式分为文 本读入和手动读入。(2) 逐个手动输入字符和权值进行编码，若数据太大效率太低。后来增加一个新的功能从文 本中读入数据，这样可大大提高效率。(3) 初始化文本读入时，若数据过大，会结束进程，无法进行操作。后来增加动态数组的最 大上限，当超过上限，会提示“文本数

30、据过大” ，而且可以显示范围内的数据。每次出现问题我们都一起讨论， 研究解决和改进的方法。 这次课程设计的成功， 可以说 是我们五个人一起努力的成果。我们小组由五个人组成，每个人都有自己在小组中的作用， 黄志发：编写代码，设计界面 ，调试程序 / 施鸿俊、赖玉丹：测试数据 / 邱琳娜、胡明 丽：文档编写和整理。我们总是在不断地调试程序和改进程序的功能， 皇天不负有心人， 我们终于在自己的努 力和老师的辛勤指导下顺利完成了课程设计。五、参考文献1数据结构(C+语言描述)，殷人昆主编，清华大学出版社2数据结构题集 ，严蔚敏编著，清华大学出版社六、附录1、源程序文件：Huffman.h ：包含哈夫曼树结构体、哈夫曼编码结构体、结点结构体，哈夫曼树的类定义 Huffman.Cpp ：哈夫曼树类的成员函数实现main.Cpp ：程序的入口，包含主界面和各个功能函数的调用2、输入数据文本：News.txt ：存储了一篇较大规模的大写英文文章，用于文件读入编码和文件读入初始化 123.txt ：存储了较小规模的大写英文文章，用于文件读入编码和文件读入初始化321.txt: 存储了较小规模的 0,1 代码，用于文件读入进行译码3、小组成员及分工表 （如表 3所示）：