哈夫曼编码译码器课程设计

1、fw）屛矗久多it耳迦WANG JNSTITUIIl Ul- 11UDWX课程设计说明书课程名称：数据结构与算法设计题目：哈夫曼编译码器院 系：计算机科学与信息工程学院学生姓名：刘文杰学 号： 16031210229专业班级： 软件工程16-2指导教师：孙高飞2017年12月11日设计题目哈夫曼编译码器限定人数3问题描述米用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符 串的长度不小于5000字节。读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对 编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较， 恢复文件和原文件必须完全一致。设字符集及频度如下表：字符空

2、格 ABCDEFGHI JKLM频度1866413223210321154757153220字符 NOPQRSTUVWXYZ 频度5763151485180238181161基本要求 与说明1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码2、读取文本文件，并对文件内容编码，生成编码文件3、对编码文件进行译码，获得恢复文件4、比较恢复文件和原文件是否相同。课程设计任务书设计题目哈夫曼编译码器学生姓名计算机和L学与刘文杰所在院系 计算机科学与专业、年级、班 软件工程16-2信息工程学院设计要求：1. 根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码。2. 读取文本文件，并对文件内容

3、编码，生成编码文件。3. 对编码文件进行译码，获得恢复文件。4. 比较恢复文件和原文件是否相冋。学生应完成的工作：1. 学生应认真学习参考程序，理解每个文件、每个函数以及各个变量的作用和意义。在此基础上 进一步改进程序，最后正确地运行程序。2. 对程序进行测试，设计详细的测试计划，然后根据测试计划设计测试用例，对程序进行测试。 测试时应注意对各种边缘情况进行测试。3. 完成课程设计报告。参考文献阅读：1.严蔚敏数据结构（C语言版）清华大学出版社，20112谭浩强.C程序设计（第四版）清华大学出版，20103.蒋立翔.C+程序设计技能百练M.中国铁道出版社，2004工作计划：1. 小组审题，查阅

4、资料，进行设计前的必要资料准备（3天）。2. 把程序完整运行出来（4天）。3. 增加改进程序（3天）。4. 写课程设计报告（3天）。5. 提交课程设计报告及答辩（1天）任务下达日期：2017年12月01日任务完成日期：2017年12月19 日指导教师（签名）：学生（签名）：哈夫曼编 译码器摘 要： 采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长 度不小于 5000 字节。读取要编码的文本文件， 将文件的内容进行编码， 生成新的文件 对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件 和原文件必须完全一致。关键词： 构建哈夫曼树 哈弗曼编码 哈夫曼译

5、码 字符串编码 打印编码函数目录1. 设计背景 . 11.1 哈夫曼树的介绍 11.2 设计的作用、目的 11.3 设计任务及要求 22. 设计方案 . 22.1 实验内容 22.2 操作思路 22.3 基本操作 33. 方案实施 . 43.1 C 语言编程 43.2 程序介绍 123.3 程序流程图以及说明 13图 3 主程序流程图 134. 结果与结论 . 144.1 程序运行结果 144.2 总结 165. 收获与致谢 . 176. 参考文献 . 171. 设计背景1.1 哈夫曼树的介绍Huffman Tree ，中文名是哈夫曼树或霍夫曼树或者赫夫曼树，它是最优二叉树。 定义：给定 n

6、个权值作为 n 个叶子结点，构造一棵二叉树，若树的带权路径长度达到最 小，则这棵树被称为哈夫曼树。(01) 路径和路径长度 定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路， 称为路径。 通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点 的路径长度为 L-1 。(02) 结点的权及带权路径长度 定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点 的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。(03) 树的带权路径长度定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL1.2 设

7、计的作用、目的 通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编 码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能 力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步 熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资 料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。通过课程设计各环节的实践，应达到如下要求：1 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2 根据哈夫曼编码算法，考虑一个有多种可能符号(各种符号发生的概率不同) 的信源，得到哈夫曼编码和码树；

8、3 掌握哈夫曼编码的优缺点；4 通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源 编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维 能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐 步熟悉开展科学实践的程序和方法。1.3 设计任务及要求1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法；2. 掌握哈夫曼编码 / 费诺编码方法的基本步骤及优缺点；3. 深刻理解信道编码的基本思想与目的， 理解线性分组码的基本原理与编码过程；2. 设计方案2.1 实验内容假设有n个权值，则构造出的哈夫曼树有 n个叶子结点。n个

9、权值分别设为w1、 w2、wn,哈夫曼树的构造规则为：1. 将w1、w2、，wn看成是有n棵树的森林（每棵树仅有一个结点）；2. 在森林中选出根结点的权值最小的两棵树进行合并， 作为一棵新树的左、 右子树， 且新树的根结点权值为其左、右子树根结点权值之和；3. 从森林中删除选取的两棵树，并将新树加入森林；4. 重复（02） 、（03） 步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。2.2 操作思路以5,6,7,8,15 为例，来构造一棵哈夫曼树。第 1 步：创建森林，森林包括 5 棵树，这 5 棵树的权值分别是 5,6,7,8,15 。第2步：在森林中，选择根节点权值最小的两棵树 （

10、5 和6）来进行合并，将它们作为一 颗新树的左右孩子 （谁左谁右无关紧要，这里，我们选择较小的作为左孩子 ），并且新树 的权值是左右孩子的权值之和。即，新树的权值是 11。 然后，将树 5和树6从森林 中删除，并将新的树 （树 11）添加到森林中。第 3 步：在森林中，选择根节点权值最小的两棵树 （7 和 8） 来进行合并。得到的新树的 权值是 15。然后，将树7和树 8从森林中删除，并将新的树（树15）添加到森林中。第 4 步：在森林中，选择根节点权值最小的两棵树 （11 和 15） 来进行合并。得到的新树 的权值是 26。 然后，将树 11和树15从森林中删除，并将新的树 （树 26）添加

11、到森 林中。第 5 步：在森林中，选择根节点权值最小的两棵树 （15 和 26） 来进行合并。得到的新树 的权值是 41。 然后，将树 15和树26从森林中删除，并将新的树 （树 41）添加到森 林中。此时，森林中只有一棵树 （树 41） 。这棵树就是我们需要的哈夫曼树！3. 方案实施3.1 C 语言编程#include #include #include #define MAX 99999#define N 27 /定义最多节点个数#define M 2*N - 1 /中间节点个数 typedef structint weight;int parent;int LChild;int RChi

12、ld; HTNode,HuffmanTreeM+1; / 因为零号单元不使用typedef char * HuffmanCodeN+1;HuffmanCode co;/创建全局变量用于储存HuffmanCodechar CHN;int weightN = 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 HuffmanTree ht;char word30; /全局变量用于储存键入的内容 void Init_CH()int i;CH26 = ;CH0 = A; for(i=1;i26;i+) CH

13、i = A+i;for (i =0;i 27;i+) printf( %c ,CHi);void select(int * sr,int * sl,int n)int i,point; point = MAX; for(i=0;in;i+) if (hti+1 .weightpoint & hti+1.parent=0) *sr = i+1;/*sr 是最小的 point = ht * sr .weight;ht * sr.parent = 1; point = MAX; for(i=0;in;i+) if (hti+1 .weightpoint & hti+1.parent=0) *sl =

14、 i+1;/*sl 是第二小point = ht*sl.weight;ht * sl.parent = 1; void InitHuffmanCode()int i,sr,sl; for(i=1;i=N;i+) hti.weight = weighti-1; hti .parent = 0; hti.LChild = 0;hti .RChild = 0;for(i=N+1;i=M;i+)hti .weight = 0;hti .parent = 0;hti .LChild = 0;hti .RChild = 0;printf( 初始化完成 n );for(i=N+1;i=M;i+)select

15、(&sr,&sl,i-1);hti .weight = htsr .weight + htsl .weight; htsr .parent = i; htsl .parent = i;hti .LChild = sr;hti .RChild = sl;for(i=1;i=M;i+)printf( %d %dn,hti .parent,i);void CreateHuffmanCode()FILE * trans;int i,start,p,c;char * cd;cd = (char * )malloc(N * sizeof(char); cdN-1 = 0;for(i=1;i=N;i+)st

16、art = N-1;c = i;p = hti .parent;while (p)-start;if (htp .LChild = c) cdstart =0;else cdstart =1;c = p;p = htp .parent;coi = (char* )malloc(N -start)* sizeof(char); strcpy(coi, & cdstart); printf( %s %dn,coi,i);if (trans=fopen(C:trans.txt,w )=NULL)printf( cannot open trans.txt!); exit(0);fputs( 哈夫曼编码

17、表初始化如下 n ,trans);for (i =0;i N;i +) fputc(CHi,trans); fputs( : ,trans); fputs(coi+1,trans); fputs(n ,trans); fclose(trans);void InputHuffmanWord()FILE *fp;if (fp = fopen(C:storeWord.txt ,w ) = NULL)printf( cannot open storeWord.txt!); exit(0);printf( 请输入以 #结束的大写字母字符串 :n ); while (strcmp(word,# )!= 0

18、) fputs(word,fp); gets(word);fclose(fp);/选择原码输入类型void SelectInputType()system(cls );int point;while (1)printf( 0:从键盘键入编码内容 n);printf( 1:从文件中读取编码内容 n);printf( 2:退出 n);scanf(%d,&point); system(cls ) ;switch(point) case0:InputHuffmanWord();break;case1:printf(将编码内容保存在storeWord.txt文件即可。n); pri ntf( 请进行下一

19、步操作！ n);break;case2:pri ntf(已经退出输入编码内容。n);return ; default:printf(Input error!n);break;/编码void Huffman_Encod()int p = M,i,flag;FILE *Input,*Output;char ch;if(Output = fopen(C:storeWord.txt,r) = NULL)printf(cannot open store.txt!); exit(0);if(Input = fopen(C:storeCode.txt,w ) = NULL)printf(cannot ope

20、n storeCode.txt!); exit(0);while (!feof(Output) /遇到输入文件的结束标识flag = 0;ch = fgetc(Output); /putchar(ch); for(i=0;iN;i+) if(CHi = ch) fputs(coi+1,Input); flag = 1;if (flag = 0) fputc(* ,Input); fclose(Output); fclose(Input);/译码void Huffman_Decod()FILE * fp,* Input;int p = M,i =0; char ch;if (fp = fopen

21、(C:storeCode.txt,r ) = NULL) printf( cannot open storeCode.txt!); exit(0);if (Input = fopen(C:storeWord_1.txt ,w ) = NULL) printf( cannot open storeWord_1.txt!); exit(0);ch = fgetc(fp); while ( !feof(fp)if(ch = 0) p = htp .LChild;elseif (ch = 1)p = htp .RChild;elseif (ch = *) fputs(* ,Input); putcha

22、r(ch);else printf( Input error! );if (htp .LChild = 0 & htp .RChild = 0) fputc(CHp-1,Input); putchar(CHp-1);p = M; ch = fgetc(fp); fclose(fp); fclose(Input); printf( n ); /译码与原码比较 void Compare_word()char ch_1,ch_2;int flag = 1;FILE * origin, * decod;if (origin = fopen(C:storeWord.txt ,r ) = NULL) pr

23、intf( cannot open storeCode.txt!); exit(0);if (decod = fopen(C:storeWord_1.txt ,r ) = NULL) printf( cannot open storeWord_1.txt!); exit(0);while ( !feof(decod)ch_1 = getc(decod); ch_2 = getc(origin); if (ch_1 != *) if (ch_1 != ch_2)flag = 0; fclose(decod); fclose(origin); if (flag = 0) printf( 原码与译码

24、不相符！ n);elseprintf( 原码与译码相符！ n);void main()int point;Init_CH();InitHuffmanCode();CreateHuffmanCode();while (1)printf( *哈夫曼编译器 *n );printf( n 0:初始化哈夫曼表 n);printf( 1:输入编码内容 n);printf( 2:开始编码 n);printf( 3:开始译码 n);printf( 4:与译码与原码比较 n);printf( 5:退出哈夫曼编译器 n); scanf(%d ,& point); system(cls);switch(point)

25、case0:printf(哈夫曼表初始化完成！n请进行下一步操作！ n);break;case1:SelectInputType(); break;case2:Huffman_Encod();printf(编码结束！请进行下一步操作！n);break;case3: Huffman_Decod();printf(译码结束！已将译码内容存放 storeWord_1.txt!n); printf(请进行下一步操作！n);break;case4:Compare_word(); break;case5:printf(已经退出编译器。n); return ;default:printf(Input err

26、or!n);break;3.2 程序介绍本程序的编码和运行都是在 Visual C+ 6.0 中实现的，在 Visual Stdio 中也能实 现， 整个程序虽然看似庞大， 但编写过程清晰， 采用模块化编写， 各个问题逐个击破， 也方便对程序的管理和运行。整个程序的编写分为五大部分 , 五大部分紧密相连，环环 相扣，共同实现程序的编码。在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree):(1) 初始化将T0 m-1中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。(2) 输入读入 n 个叶子的权值存于向量的前 n 个分量(即 T0n-1) 中。它们

27、是初始森林 中 n 个孤立的根结点上的权值。(3) 合并对森林中的树共进行n-1次合并，所产生的新结点依次放人向量 T的第i个分量中 (n i 结束数组a 一维，存放输入概率数组b，二维存放编码过程概率数组c,三维，存放编码每个位置即时编码；数组d，一维存放码长i为整型变量计数 编码次数m为整型n， x为控制循环整型变量，y为检错控 制整型变量，K为存放平均码长浮点型变 量，H为存放信源熵浮点型变量，三重循环初始化，使其所有值为2显示请输入消息个数”响蜂鸣器调用获取概率函数，将返回值给y丫=0存在错误，结束程序调用获取概率函数，将返回值给y图3主程序流程图4. 结果与结论4.1程序运行结果52

28、 4952 5053 5153 520 531110 1110000 2WOO 311110 4100 5boon 6110X1 73101 81010 90000010111 100XQO1L 1111111 1Z00010 131011 141101 15110010 10000001000 170110 ISDill 19001 20plOOl 2100000 2200001 230X001001 24110011 25000001010 260000010110 27软件工程16-2刘文杰1涣口加2芻哈夭曼编译器J05 :初始化哈夫曼表5 r ；输入编码內容尸；幵始编码s幵始谭码43

29、:与谨码与原码比技55 ；退岀哈夫晏编译器为了最大化优化程序，尽可能美观，设计了五个输入选择步骤，可多次进行选择输 入输出操作，输入时可从键盘键入或者从文件指定路径获取。printf（*哈夫曼编译器 *n）；printf（n 0:初始化哈夫曼表n）;printf（” 1:输入编码内容n）;printf（ 2:开始编码 n）;printf（ 3:开始译码 n）;printf（ 4:与译码与原码比较n）;printf（” 5:退出哈夫曼编译器n）;；初始化哈夫晏表1“ ；输入编玛内容2 ;开始编码3s :开始译阳，；与译码与原码比较 F :退出哈夭昼编译器printf(请输入以#结束的大写字母字符

30、串:n);while(strcmp(word,#)!=0)fputs(word,fp);gets(word);fclose(fp);根据编写的程序，通过while循环，在输入#时程序输入结束，即可进行译码，并将 译码内容，通过程序存放在 C盘中DHRKDSKJDSP*棒码结策！已将译码內容有恥tgtWW七十! 情进行下一垢揉作！软件工程i2刘文杰1G031210229杓棊岭哈夭昙编译需0：初始化哈夫曼表1J输入编禹内容了 ：开始编码X：开始译码% ：与译职与原码比较用：退出哈夭曼编译器译码内容存放在指定位置，找到打开即可见。iF(Fp FapenCTzstareUDrd.txtV1) HULL

31、)_J storeWord_l.txt -记事本 | 文件旧糯(E)體式Q)窗V 薯旳(H)KJDSHFJKJKJSDGKJGI最后可审核源码译码是否相符，退出哈夫曼编译器皐码与译码相符！炭件工程1吕-2刘文杰16031210229 卄片哈天曼编译器卄*乜：初始化哈夫昼表f ：谕入编码內容辽；开始编码述；开抬译玛与译码三原码比较窗：退出哈夫晏编译器已经退出编译器、 Press any key to continue4.2总结本次课程设计，让我对哈夫曼编码以及 C语言有了更深的理解和操作能力。开始针 对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计 流程及思路。再通过

32、查阅相关资料，使自己的知识也更加丰富了，明白了哈夫曼编码的 原理以及仿真的实现。首先对给题目进行了计算，进行哈夫曼编码，求出平均码长，编码效率，开始时不 是很顺利，以前学的很多书本上的东西记得不太清楚了，经过复习课本的内容，掌握原 理后顺利求出结果。然后是利用 C语言编写程序，由于我现在正在公司实习，接触到编 程的东西比较多，所以对C语言编程还是比较熟悉的，所以我选择使用 C语言来实现仿 真，仔细研究后得到程序的算法，还有我也参考了一部分网上的算法，但是在运行时还 是出错了，之后又经过几次的修改，终于得出了结果，可是和自己计算的码却是相反的， 而其它结果却是相同，让我疑惑了，我又仔细想了想了，原因应该出现在编码的时候， 在编码过程中如果0和1赋值相反的话，就会出现这种情况，但是两种的码字应该都是 正确的。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不 断领悟，不断获取最终的检测调试环节，本身就是在践行过而能改，善莫大焉的知行观。 这次课程设计终于顺利完成了，在设计