哈夫曼编码译码器课程设计word精品文档19页.doc

《哈夫曼编码译码器课程设计word精品文档19页.doc》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器课程设计word精品文档19页.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流哈夫曼编码译码器课程设计【精品文档】第 14 页课 程 设 计 说 明 书课程名称： 数据结构与算法 设计题目： 哈夫曼编译码器 院 系： 计算机科学与信息工程学院 学生姓名： 刘文杰 学 号： 16031210229 专业班级： 软件工程16-2 指导教师： 孙高飞 2017年 12 月 11日设计题目哈夫曼编译码器限定人数3问题描述采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于5000字节。读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件

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

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

4、计划：1. 小组审题，查阅资料，进行设计前的必要资料准备（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个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小

6、，则这棵树被称为哈夫曼树。 (01) 路径和路径长度定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 (02) 结点的权及带权路径长度定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 (03) 树的带权路径长度定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。1.2设计的作用、目的 通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码

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

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

9、个结点)； 2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 3. 从森林中删除选取的两棵树，并将新树加入森林； 4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。2.2操作思路以5,6,7,8,15为例，来构造一棵哈夫曼树。第1步：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。 第2步：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树的权值是左右孩子的权值之和。

10、即，新树的权值是11。 然后，将树5和树6从森林中删除，并将新的树(树11)添加到森林中。 第3步：在森林中，选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。 然后，将树7和树8从森林中删除，并将新的树(树15)添加到森林中。 第4步：在森林中，选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。 然后，将树11和树15从森林中删除，并将新的树(树26)添加到森林中。 第5步：在森林中，选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。 然后，将树15和树26从森林中删除，并将新的树(树41)添加到森林中。 此时，森林中

11、只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！3. 方案实施3.1 C语言编程 #include #include #include #define MAX 99999#define N 27/定义最多节点个数#define M 2*N - 1/中间节点个数typedef struct int weight;int parent;int LChild;int RChild;HTNode,HuffmanTreeM+1;/因为零号单元不使用typedef char * HuffmanCodeN+1;HuffmanCode co;/创建全局变量用于储存HuffmanCodechar CHN;i

12、nt 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+)CHi = A+i;for(i=0;i27;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.

13、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 = 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.LChi

14、ld = 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(&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);v

15、oid 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+)start = N-1;c = i;p = hti.parent;while(p)-start;if(htp.LChild = c)cdstart = 0;elsecdstart = 1;c = p;p = htp.parent;coi = (char*)malloc(N-start)*sizeof(char);strcpy(coi,&cdstart);p

16、rintf(%s %dn,coi,i);if(trans=fopen(C:trans.txt,w)=NULL)printf(cannot open trans.txt!);exit(0);fputs(-哈夫曼编码表初始化如下-n,trans);for(i=0;iN;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(cann

17、ot open storeWord.txt!);exit(0);printf(请输入以#结束的大写字母字符串:n);while(strcmp(word,#)!=0)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)case 0:InputHuffma

18、nWord();break;case 1:printf(将编码内容保存在storeWord.txt文件即可。n);printf(请进行下一步操作！n);break;case 2:printf(已经退出输入编码内容。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!);exi

19、t(0);if(Input = fopen(C:storeCode.txt,w) = NULL)printf(cannot open 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

20、 *fp,*Input;int p = M,i=0;char ch;if(fp = fopen(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;else if(ch = 1)p = htp.RChild;else if(

21、ch = *)fputs(*,Input);putchar(ch);elseprintf(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) = NU

22、LL)printf(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(原码与译码不相符！n);elseprint

23、f(原码与译码相符！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)case 0:printf(哈夫曼表初始化完成！n请进行下一步操

24、作！n);break;case 1:SelectInputType();break;case 2:Huffman_Encod();printf(编码结束！请进行下一步操作！n);break;case 3:Huffman_Decod();printf(译码结束！已将译码内容存放storeWord_1.txt!n);printf(请进行下一步操作！n);break;case 4:Compare_word();break;case 5:printf(已经退出编译器。n);return ;default:printf(Input error!n);break;3.2程序介绍本程序的编码和运行都是在Vi

25、sual C+ 6.0中实现的，在Visual Stdio中也能实现， 整个程序虽然看似庞大，但编写过程清晰，采用模块化编写，各个问题逐个击破，也方便对程序的管理和运行。整个程序的编写分为五大部分,五大部分紧密相连，环环相扣，共同实现程序的编码。 在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：(1)初始化将T0m-1中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。(2)输入 读入n个叶子的权值存于向量的前n个分量(即T0n-1)中。它们是初始森林中n个孤立的根结点上的权值。(3)合并 对森林中的树共进行n-1次合并，所产生的新结点依次放人向

26、量T的第i个分量中(nim-1)。每次合并分两步： 在当前森林T0i-1的所有结点中，选取权最小和次小的两个根结点p1和Tp2作为合并对象，这里0p1，p2i-1。 将根为Tp1和Tp2的两棵树作为左右子树合并为一棵新的树，新树的根是新结点Ti。具体操作：将Tp1和Tp2的parent置为i，将Ti的lchild和rchild分别置为p1和p2新结点Ti的权值置为Tp1和Tp2的权值之和。注意： 合并后Tpl和Tp2在当前森林中已不再是根，因为它们的双亲指针均已指向了Ti，所以下一次合并时不会被选中为合并对象。3.3程序流程图以及说明主程序N结束定义全局数组 a, b, c ,d 定义全局变量

27、定义变量 n, x, y, K,开始输出编码过程中产生的新概率输出码字输出平均码长、信源熵，编码效率，冗余度初始输出提示 获取y=xiaoxi()ordination(m,a);Y数组 a 一维，存放输入概率数组 b，二维存放编码过程概率 数组 c，三维，存放编码每个位置即时编码；数组 d，一维存放码长 i 为整型变量 计数编码次数 m 为整型n， x 为控制循环整型变量， y 为检错控制整型变量， K 为存放平均码长浮点型变量， H 为存放信源熵浮点型变量，三重循环初始化，使其所有值为 2显示“请输入消息个数”，响蜂鸣器调用获取概率函数，将返回值给 yY=0 存在错误，结束程序调用获取概率函

28、数，将返回值给 y说明图3 主程序流程图4. 结果与结论4.1程序运行结果为了最大化优化程序，尽可能美观，设计了五个输入选择步骤，可多次进行选择输入输出操作，输入时可从键盘键入或者从文件指定路径获取。printf(* 哈夫曼编译器 *n);printf(n 0:初始化哈夫曼表n);printf( 1:输入编码内容n);printf( 2:开始编码n);printf( 3:开始译码n);printf( 4:与译码与原码比较n);printf( 5:退出哈夫曼编译器n);printf(请输入以#结束的大写字母字符串:n);while(strcmp(word,#)!=0)fputs(word,fp)

29、;gets(word);fclose(fp);根据编写的程序，通过while循环，在输入#时程序输入结束，即可进行译码，并将译码内容，通过程序存放在C盘中。译码内容存放在指定位置，找到打开即可见。最后可审核源码译码是否相符，退出哈夫曼编译器。4.2总结本次课程设计，让我对哈夫曼编码以及C语言有了更深的理解和操作能力。开始针对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计流程及思路。再通过查阅相关资料，使自己的知识也更加丰富了，明白了哈夫曼编码的原理以及仿真的实现。首先对给题目进行了计算，进行哈夫曼编码，求出平均码长，编码效率，开始时不是很顺利，以前学的很多书本上的东

30、西记得不太清楚了，经过复习课本的内容，掌握原理后顺利求出结果。然后是利用C语言编写程序，由于我现在正在公司实习，接触到编程的东西比较多，所以对C语言编程还是比较熟悉的，所以我选择使用C语言来实现仿真，仔细研究后得到程序的算法，还有我也参考了一部分网上的算法，但是在运行时还是出错了，之后又经过几次的修改，终于得出了结果，可是和自己计算的码却是相反的，而其它结果却是相同，让我疑惑了，我又仔细想了想了，原因应该出现在编码的时候，在编码过程中如果0和1赋值相反的话，就会出现这种情况，但是两种的码字应该都是正确的。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取最终的

31、检测调试环节，本身就是在践行过而能改，善莫大焉的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在同事的指导下，终于迎刃而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可!最后通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，在设计过程中虽然遇到了一

32、些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，我掌握的知识不再是纸上谈兵，而且提高了自己的动手能力和独立思考的能力。在这过程中我收获颇丰，在此期间也得到了同学的热心帮助，在这里忠心的感谢。这个课程设计对以后的工作也很有帮助，我会在以后的工作中多将理论与实际结合，从根本上解决问题，逐步提高自己的能力。5. 收获与致谢通过这次实验让我更深刻的了解了获取输入内容，编码函数以及打印编码函数的过程。虽然在进行过程中遇到了很多问题，但在老师的帮助下和与小组成员的讨论下，都一一解决了。这次课程设计加强了我的分析

33、问题能力和解决问题能力，也提高了我的设计和程序编码的能力。在这过程中，让我们体会到了团队的力量。感谢我的队友的帮助和张老师这一学期来的教学。6. 参考文献1 严蔚敏 . 数据结构（C语言版）M . 北京：清华大学出版社，2011.2 耿国华 . 数据结构C语言描述M . 北京：高等教育出版社，2011.3 张铭 . 数据结构与算法 . 北京：高等教育出版社，2008.4 殷人昆 . 数据结构（C语言描述）M . 北京：清华大学出版社，2011.5 胡学钢 . 数据结构（C语言版）M . 北京：高等教育出版社，2008.指导教师评语：1、课程设计报告：a、内容： 不完整 完整 详细 b、方案设计： 较差 合理 非常合理c、实现： 未实现 部分实现 全部实现 d、文档格式： 不规范 基本规范 规范 2、出勤： 全勤 缺勤 次3、答辩： a、未能完全理解题目，答辩情况较差 b、部分理解题目，部分问题回答正确 c、理解题目较清楚，问题回答基本正确 d、理解题目透彻，问题回答流利 课程设计报告成绩： ，占总成绩比例： 50% 课程设计其它环节成绩：环节名称： 出勤 ，成绩： ，占总成绩比例： 20% 环节名称： 答辩 ，成绩： ，占总成绩比例： 30% 总 成 绩： 指导教师签字：年 月 日