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

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

2、I 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、码函数11. 设计背景哈夫曼树的介绍 设计的作用、目的设计任务及要求22. 设计方案22.1 实验内容22.2 操作思路32.3 基本操作43. 方案实施43.1 C 语言编程123.2 程序介绍 程序流程图以及说明 13图 3 主程序流程图144. 结果与结论 程序运行结果164.2 总结175. 收获与致谢176. 参考文献目录. 11.1. 11.2. 21.3. 133.3. 144.11. 设计背景1.1 哈夫曼树的介绍Huffman Tree ，中文名是哈夫曼树或霍夫曼树或者赫夫曼树，它是最优二叉树。 定义：给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若树的带权路径长度达

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

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

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

9、1、w2、，wn看成是有n棵树的森林（每棵树仅有一个结点）；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。 然后，将"树 1

11、1"和"树15"从森林中删除，并将新的树 （树 26）添加到森 林中。第 5 步：在森林中，选择根节点权值最小的两棵树 （15 和 26） 来进行合并。得到的新树 的权值是 41。 然后，将"树 15"和"树26"从森林中删除，并将新的树 （树 41）添加到森 林中。此时，森林中只有一棵树 （树 41） 。这棵树就是我们需要的哈夫曼树！3. 方案实施3.1 C 语言编程#include <stdio.h>#include <stdlib.h>#include <string.h>#defi

12、ne MAX 99999#define N 27 /定义最多节点个数#define M 2*N - 1 /中间节点个数 typedef structint weight;int parent;int LChild;int RChild; 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

13、,23,8,18,1,16,;1 HuffmanTree ht;char word30; /全局变量用于储存键入的内容 void Init_CH()int i;CH26 = ' 'CH0 = 'A' for(i=1;i<26;i+) 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 .

14、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<point && 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<

15、;=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(&sr,&sl,i-1);hti .weight = htsr .weight + htsl .weight; htsr .parent

16、= 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+)start = N-1;c = i;p = hti .parent;while (p)

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

18、"); 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 *fp;if (fp = fopen("C:storeWord.txt" ,"w" ) = NULL)printf( &

19、quot;cannot 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");

20、printf( " '1':从文件中读取编码内容 n");printf(" 2:退出 n");scanf("%d",&point); system("cls" ) ;switch(point) case0:InputHuffmanWord();break;case1:printf("将编码内容保存在storeWord.txt文件即可。n"); pri ntf( "请进行下一步操作！ n");break;case2:pri ntf("已经退出输

21、入编码内容。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&q

22、uot;,"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('*' ,Input); fclose(Output); fclose(Input);/译码void Hu

23、ffman_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( "cannot open storeWord_1.txt!"

24、); exit(0);ch = fgetc(fp); while ( !feof(fp)if(ch = '0') p = htp .LChild;elseif (ch = '1')p = htp .RChild;elseif (ch = '*') fputs("*" ,Input); putchar(ch);else printf( "Input error!" );if (htp .LChild = 0 && htp .RChild = 0) fputc(CHp-1,Input); put

25、char(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 (dec

26、od = 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( "原码与译码不相符

27、！ 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( &qu

28、ot; '3':开始译码 n");printf( " '4':与译码与原码比较 n");printf( " '5':退出哈夫曼编译器 n"); scanf("%d" ,& point);system("cls"); switch(point)case0:printf("哈夫曼表初始化完成！ n请进行下一步操作！n");break;case1: SelectInputType(); break;case2: Huffman_Enco

29、d();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 error!n");break;3.2 程序介绍本程序的编码和运行都

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

31、林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(n < i < m-1)。每次合并分两步： 在当前森林 T0i-1 的所有结点中，选取权最小和次小的两个根结点 p1 和 Tp2作为合并对象，这里0W pl, p2w i-1。 将根为 Tp1 和 Tp2 的两棵树作为左右子树合并为一棵新的树， 新树的根是新 结点 Ti 。具体操作：将 Tp1和 Tp2的 pare nt 置为 i ,将 Ti 的 lchild 和 rchild 分别置为 p1 和 p2新结点 Ti 的权值置为 Tp1 和 Tp2 的权值之和。合并后Tpl和Tp2在当前森林中已不再是根，因为它们

32、的双亲指针均已指向了Ti，所以下一次合并时不会被选中为合并对象。3.3程序流程图以及说明图3主程序流程图4. 结果与结论4.1程序运行结果52 4952 5053 5153 52j 53 1110 11W000 2OlOOO 311110 4100 5boon 6110001 7noi a1010 90X0010111 10OWOOll 11urn 12OOCIO 131011 141101 15110010 16pooooj no1000 17180111 19001 20 01001 21OOCOOO 220X01 23OWOOOl 24110011 25POOOOIOIO 26U 00X

33、10110 21软件工程刘文杰*哈夫矍编译器J05 :初始化哈夫曼表r ;输人骗阳內容?乎：幵始编玛它幵始译码'43 :与译码与原码比技'S5 ；退岀哈夫曼编译器为了最大化优化程序，尽可能美观，设计了五个输入选择步骤，可多次进行选择输 入输出操作，输入时可从键盘键入或者从文件指定路径获取。printf（"*哈夫曼编译器 *n"）；printf（"n '0':初始化哈夫曼表n"）;printf（” '1':输入编码内容n"）;printf（" '2':开始编码 n"

34、;）;printf(" 3:开始译码 n");printf（" '4':与译码与原码比较n"）;printf（” '5':退出哈夫曼编译器n"）;；初始化哈夫昙表 *13 :输入编码内苔 '23 ;开始编码 '35 ;开始译阳与译玛0原码比较' F :退出哈夭昼编谨器printf("请输入以#结束的大写字母字符串:n");while(strcmp(word,"#")!=0)fputs(word,fp);gets(word);fclose(fp);根据

35、编写的程序，通过while循环，在输入#时程序输入结束，即可进行译码，并将 译码内容，通过程序存放在C盘中。DHFKDSKJBSP+ 棒码结策！已将译码内 情进行下一步操作！ 软件工程迢-2刘文杰1G031210229 严|*袜哈夫昼编译H卄0"：初始化哈夫曼表 输入编碍内容了 ：开始编码开始译码4 ：与译职勻原码比较X：退出哈夫曼编译器译码内容存放在指定位置，找到打开即可见。1F( (Fp = FapenCCzstareWDrd.txt11,11) = NULL)sto re Wo rd_l rfcd -记事卞文禅（Ri隣任桔式（O）查看W m（H）KJDSHFJKSDKJSDGK

36、JG+I最后可审核源码译码是否相符，退出哈夫曼编译器原码与译码相符!软件工程饴刘文杰桂*哈天曼编译器卄*H'：初始化哈夫昼表'1* :输入编码內容迂；开始编码'于；开抬译玛P：与译玛与廉码比较筲：退出皓夫曇编译巻4.2总结本次课程设计，让我对哈夫曼编码以及 C语言有了更深的理解和操作能力。开始针 对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计 流程及思路。再通过查阅相关资料，使自己的知识也更加丰富了，明白了哈夫曼编码的 原理以及仿真的实现。首先对给题目进行了计算，进行哈夫曼编码，求出平均码长，编码效率，开始时不 是很顺利，以前学的很多书本上的东西记得不太清楚了，经过复习课本的内容，掌握原 理后顺利求出结果。然后是利用 C语言编写程序，由于我现在正在公司实习，接触到编 程的东西比较多，所以对C语言编程还是比较熟悉的，所以我选择使用 C语言来实现仿 真，仔细研究后得到程序的算法，还有我也参考了一部分网上的算法，但是在运行时还 是出错了，之后又经过几次的修改，终于得出了结果，可是和自己计算的码却是相反的， 而其它结果却是相同，让我疑惑了，我又仔细想了想了，原因应该出现在编