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

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

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

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

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

5、曼树的介绍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个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。 (01) 路径和路径长度定义：在一棵树中，从一个结点往下可以

6、达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为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 棵树的森林(每棵树仅有一个结点)； 2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树

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

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

11、quot;和"树26"从森林中删除，并将新的树(树41)添加到森林中。 此时，森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！3. 方案实施3.1 C语言编程 #include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 99999#define N 27/定义最多节点个数#define M 2*N - 1/中间节点个数typedef struct int weight;int parent;int LChild;int RChild;HTNode,Huf

12、fmanTreeM+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;i<26;i+)

13、CHi = '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;i<n;i+)if(hti+1.weight<point && hti+1.parent=0)*sr = i+1;/*sr是最小的point = ht*sr.weight;ht*sr.parent = 1;point = MAX;for(i=0;i<n;i+)if(hti+1.weight<p

14、oint && 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.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(&quo

15、t;-初始化完成-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);void CreateHuffmanCode()FILE * trans;int i,start,p,c;char *cd;cd = (cha

16、r *)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);printf("%s %dn",coi,i);if(

17、trans=fopen("C:trans.txt","w")=NULL)printf("cannot open trans.txt!");exit(0);fputs("-哈夫曼编码表初始化如下-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 *f

18、p;if(fp = fopen("C:storeWord.txt","w") = NULL)printf("cannot open storeWord.txt!");exit(0);printf("请输入以'#'结束的大写字母字符串:n");while(strcmp(word,"#")!=0)fputs(word,fp);gets(word);fclose(fp);/选择原码输入类型void SelectInputType()system("cls");int

19、 point;while(1)printf(" '0':从键盘键入编码内容n");printf(" '1':从文件中读取编码内容n");printf(" '2':退出n");scanf("%d",&point);system("cls");switch(point)case 0:InputHuffmanWord();break;case 1:printf("将编码内容保存在storeWord.txt文件即可。n");pr

20、intf("请进行下一步操作！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.tx

21、t!");exit(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;i<N;i+)if(CHi = ch)fputs(coi+1,Input);flag = 1;if(flag = 0)fputc('*',

22、Input);fclose(Output);fclose(Input);/译码void Huffman_Decod()FILE *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("ca

23、nnot 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(ch = '*')fputs("*",Input);putchar(ch);elseprintf("Input error!");if(htp.LChild = 0 && htp.RChild = 0)fputc(CH

24、p-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)printf("cannot open storeCode.txt!");exit(0);if(decod

25、 = 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");elsep

26、rintf("原码与译码相符！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");

27、printf(" '4':与译码与原码比较n");printf(" '5':退出哈夫曼编译器n");scanf("%d",&point);system("cls");switch(point)case 0:printf("哈夫曼表初始化完成！n请进行下一步操作！n");break;case 1:SelectInputType();break;case 2:Huffman_Encod();printf("编码结束！请进行下一步操作！n")

28、;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程序介绍本程序的编码和运行都是在Visual C+ 6.0中实现的，在Visual Stdio中也能实现， 整个程

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

30、结点中，选取权最小和次小的两个根结点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程序流程图以及说明说明图3 主程序流程图4. 结果与结论4.1程序运行结果为了最大化优化程序，尽可能美观，设计了五个输入选择步骤，可多次进行选择输入输出操作

31、，输入时可从键盘键入或者从文件指定路径获取。printf("* 哈夫曼编译器 *n");printf("n '0':初始化哈夫曼表n");printf(" '1':输入编码内容n");printf(" '2':开始编码n");printf(" '3':开始译码n");printf(" '4':与译码与原码比较n");printf(" '5':退出哈夫曼编译器n"

32、);printf("请输入以'#'结束的大写字母字符串:n");while(strcmp(word,"#")!=0)fputs(word,fp);gets(word);fclose(fp);根据编写的程序，通过while循环，在输入#时程序输入结束，即可进行译码，并将译码内容，通过程序存放在C盘中。译码内容存放在指定位置，找到打开即可见。最后可审核源码译码是否相符，退出哈夫曼编译器。4.2总结本次课程设计，让我对哈夫曼编码以及C语言有了更深的理解和操作能力。开始针对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计

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