哈夫曼编码译码系统(共16页)

1、精选优质文档-倾情为你奉上 数据结构 课程设计赫夫曼编码/译码器设计指导教师：孙树森、周维达班级：09数媒（2）班学号：E姓名：曾焕凯专心-专注-专业 数据结构课程设计报告书1、 实验目的1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。2、熟悉掌握一门计算机语言，可以进行数据算法的设计。二、实验原理1、 哈夫曼树的定义： 假设有 n 个权值，试构造一颗有 n 个叶子节点的二叉树，每个叶子带 权值为 wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树； 2、 哈夫曼树的构造： weight 为输入的频率数组，把其中的值赋给依次建立的 HT Node 对象中的 data

2、 属性， 即每一个 HT Node 对应一个输入的频率。然后根据 data 属性按从小到大顺序排序，每次从 data 取出两个最小和此次小的 HT Node，将他们的 data 相加，构造出新的 HTNode 作为 他们的父节点，指针 parent，leftchild，rightchild 赋相应值。在把这个新的节点插入最小堆。 按此步骤可以构造构造出一棵哈夫曼树。 通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找 parent,直到 parent 为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记 录 1 或 0，这样，每个频率都会有一个 01 编码与

3、之唯一对应，并且任何编码没有前部分是 同其他完整编码一样的。3、 实验步骤先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码。然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文 件，并对其进行译码输出，最后存入另一个文件中。具体步骤：1. 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树； 2. 根据符号概率的大小按由大到小顺序对符号进行排序；3. 把概率最小的两个符号组成一个节点； 4. 重复步骤2. 3 ，直到概率和为 1；5. 从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”； 6. 从根节点开始，对

4、符号进行编码； 7. 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。四、实验结果与分析哈夫曼编码是动态变长编码，临时建立概率统计表和编码树。概率小的码比较长，概率 小的码比较长。概率大的码短，这样把一篇文件编码后，就会压缩许多。从树的角度看，哈夫曼编码方式是尽量把短码都利用上。首先，把一阶节点全都用上， 如果码字不够时， 然后， 再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据 建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最佳码。实验截图:五、实验心得本次实验结合了之前所学的赫夫曼算法，并利用其原理实现赫夫曼编码/译码系统

5、；实验难度较之前的几次实验有所增加，所以花了比较多的时间来编写，测试代码。期间参考了网上的一些程序，通过结合分析，了解其他人在实现这个算法时的思想，也借鉴了其中的一些东西，同时加入了自己的想法。最终完成饿了本次的作业。通过这次实验，我了解了一个算法到一个可以执行的程序之间还有很多工作需要做，深刻体会到实践出真知的到了，看似简单的算法在实现时却话费了这么多时间，但是这个过程中也让我学到了很多。六、主要代码Huffman_Tree.h：#ifndef Huffman_Tree_h#define Huffman_Tree_h#endif#include <stdio.h>typedef

6、struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode, * HuffmanTree; /存储赫夫曼树的结点类型typedef char * * HuffmanCode; /用于存储字符集中各个字符相应的赫夫曼编码void strcpy(char *S1,char *S2) /将字符串S2复制到S1 int i = 0; while( S2i != '0' ) S1i = S2i; i+; S1i = '0'/在HT1到HTt-1中找出权值最小的两个S1和S2-void Selec

7、t(HuffmanTree HT,int t,int &s1,int &s2) int i = 1; s1 = s2 = 0; HT0.weight = 50000; while( i <= t ) /遍历查找权值最小的结点S1 if( HTi.parent = 0 && HTi.weight < HTs1.weight ) s1 = i; i+; i = 1; while( i <= t ) /遍历查找除S1外权值最小的结点S2 if( i != s1 && HTi.parent = 0 && HTi.weig

8、ht < HTs2.weight ) s2 = i; i+; /根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中-int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int s1,s2,m,i,start; unsigned int c,f; HTNode * p; char *cd; if( n <= 1 ) return 0; m = 2 * n - 1; /赫夫曼树的总结点树为m HT = (HuffmanTree)malloc(m + 1) * sizeof(HT

9、Node); /申请存储赫夫曼树的空间 for(p = HT + 1, i = 1; i <= n; +i, +p, +w) /将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0 p->weight = *(w+1); p->parent = p->lchild = p->rchild = 0; for( ; i <= m; +i, +p ) /将各个非叶子结点的weight,parent,lchild,rchild均赋为0 p->weight = p->parent = p->lchild = p

10、->rchild = 0; for( i = n + 1; i <= m; +i ) /构造赫夫曼树，给各个非叶子结点赋值 Select(HT, i - 1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /根据已建立的赫夫曼树对需要编码的字符进行编码- HC = (HuffmanCode)malloc(n + 1) * sizeof(char *); /用于存储指向存储各个字符相应赫夫曼编码的字

11、符数组的指针 cd = (char *)malloc(n * sizeof(char); /分配工作所需空间 cdn - 1 = '0' /编码结束符 for( i = 1; i <= n; +i) /逐个字符求赫夫曼编码 start = n -1; /编码在数组cd中的最前位置 /从叶子到根逆向求编码，初始值；停止条件；一次循环后对上一个节点做循环 for(c = i,f = HTi.parent; f != 0; c = f, f = HTf.parent) if(HTf.lchild = c) cd -start = '0' else cd -sta

12、rt = '1' HCi = (char *)malloc(n - start)*sizeof(char); /为第i个字符编码分配空间 strcpy(HCi, &cdstart); /将cd数组的start位置到n-1位置复制给HCi free(cd); /释放空间 return 1;Test.cpp:#include <stdio.h>#include <stdlib.h>#include "Huffman_Tree.h"#define Yes 1 /当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从ht

13、fTree文件读取过，则将Init_Mode置为Yes，否则为No#define No 0void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch,int &n ) /初始化赫夫曼数，要求用户输入字符和相应权值 int i = 1,w100,temp,j; char a20; /数字转字符时，用于储存赫夫曼编码 FILE *save; printf("请输入编码字符集的大小:"); scanf("%d",&n); /获取用户输入的字符集个数 while( i &l

14、t;= n ) /获取用户输入的字符和相应权值，分别存储在ch和w数组中 printf("请输入第%d个字符和该字符的权值:",i); fflush(stdin); /刷新标准输入缓冲区，把输入缓冲区里的东西丢弃 scanf("%c%d",&chi,&wi); i+; chi = '0' /哈夫曼树保存- HuffmanCoding(HT,HC,w,n); /根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中 if( save = fopen("hfmTree.TXT",&q

15、uot;w") = NULL ) /打开用于存储赫夫曼树的文件 printf("Open file fail.n"); exit(0); temp = n; /将字符集大小转换成字符形式写入到文件hfmTree.TXT中 j = 0; while( temp != 0 )/计算数字位数 temp = temp / 10; j+; temp = n; /数字转字符 aj = '0' while( temp != 0 ) aj - 1 = (char)(temp % 10 + 48); temp = temp / 10; j-; fputs(a,sav

16、e); printf("%dn",n); /向屏幕输出字符集大小n fputc('n',save); /换行 for( i = 1; i <= n; i+ ) /分别向文件和屏幕输出各个字符和相应的赫夫曼编码 fputc(chi,save); printf("%ct",chi); /字符 fputc('t',save); fputs(HCi,save); printf("%sn",HCi); /编码 fputc('n',save); for(i = 1; i <= 2 * n

17、 - 1; i+ ) /将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中 temp = HTi.parent; /将i结点的parent转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,save); fputc(' ',save); else j = 0; /计算HTi.parent数字位数 while( temp != 0 ) temp = temp / 10; j+; temp = HTi.parent; /数字转字符 aj = '0' while( temp != 0 ) aj - 1 = (c

18、har)(temp % 10 + 48); temp = temp / 10; j-; fputs(a,save); fputc(' ',save); temp = HTi.lchild; /将i结点的lchild转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,save); fputc(' ',save); else j = 0; /计算HTi.lchild数字位数 while( temp != 0 ) temp = temp / 10; j+; temp = HTi.lchild; /数字转字符 aj = '0

19、9; while( temp != 0 ) aj - 1 = (char)(temp % 10 + 48); temp = temp / 10; j-; fputs(a,save); fputc(' ',save); temp = HTi.rchild; /将i结点的rchild转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,save); fputc('n',save); else j = 0; /计算HTi.lchild数字位数 while( temp != 0 ) temp = temp / 10; j+; temp =

20、HTi.rchild; /数字转字符 aj = '0' while( temp != 0 ) aj - 1 = (char)(temp % 10 + 48); temp = temp / 10; j-; fputs(a,save); fputc('n',save); fclose(save);/编码,并将所得编码存储到文件-void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch) FILE *ToBeTran,*CodeFile; int i; char c; if( ToBeTran =

21、fopen("ToBeTran.TXT","r") = NULL ) printf("Open file fail.n"); exit(0); if( CodeFile = fopen("CodeFile.TXT","w") = NULL ) printf("Open file fail.n"); exit(0); c = fgetc(ToBeTran); /从文件读取一个字符 while( c != EOF ) /对文件中的各个字符进行编码，直至文件结尾 i = 1; wh

22、ile( c != chi && chi != '0' ) /在ch数组中查找从文件读取的字符 i+; if(chi = '0') /未找到，c不在ch数组中，c无法被识别，退出 printf("字符%c无法识别n",c); exit(0); fputs(HCi,CodeFile); /若找到，则将c相应的赫夫曼编码写入到文件中 printf("%s",HCi); /将c相应的赫夫曼编码输出到屏幕 c = fgetc(ToBeTran); /读入文件中的下一个字符 printf("n")

23、; fclose(ToBeTran); fclose(CodeFile);/译码，翻译成相应的字符表示，并存储到文件- int p,i = 1;void Decoding(HuffmanTree &HT, char ch , int n) char code1000,c; p = 2 * n - 1; /n为叶子数量，2*n-1即为根节点的节点号 FILE *CodeFile,*TextFile; if( CodeFile = fopen("CodeFile.TXT","r") = NULL ) printf("Open file fa

24、il.n"); exit(0); if( TextFile = fopen("TextFile.TXT","w") = NULL ) printf("Open file fail.n"); exit(0); c = fgetc(CodeFile); while( c != EOF ) /从文件读取字符，存储在code数组中 codei = c; i+; c = fgetc(CodeFile); codei = '0' i = 1; while ( codei != '0' &&

25、 p != 0 ) /对数组code中的赫夫曼编码进行译码,p储存节点号 if ( codei = '0' ) p=HTp.lchild; /进入左分支 else p = HTp.rchild; /进入右分支 if (!HTp.lchild&& !HTp.rchild) /不再有叶子节点时（进入叶子结点） fputc(chp,TextFile); /将相应的字符写入到文件中 printf("%c",chp); /将相应的字符输出到屏幕 p = 2 * n - 1; /重新从树根出发进行译码 i+; printf("n");

26、/从文件读取赫夫曼树-void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch, int &n) FILE *hfmTree; char c100,ch1; int i,j,t; if( hfmTree = fopen("hfmTree.TXT","r") = NULL ) /打开存有赫夫曼树信息的文件 printf("Open file fail.n"); exit(0); fgets(c,10,hfmTree); /获取赫夫曼树叶子结点个数（字符串

27、） i = 0; /将字符串形式转换成整数形式 while( ci != 'n' ) i+; n = 0; for( j = 0; j < i; j+ ) n = 10 * n + cj - '0' /求出叶子结点数n HC = (HuffmanCode)malloc(n + 1) * sizeof(char *); /申请HC空间 HT = (HuffmanTree)malloc(2 * n) * sizeof(HTNode); /申请赫夫曼树存储空间 i = 1; while( i <= n ) chi = fgetc(hfmTree); /读取

28、字符集中的一个字符 HCi = (char *)malloc(10)*sizeof(char); /申请用于存储读取到的字符集中的字符的赫夫曼编码的空间 fgetc(hfmTree); /将t读取并输出 ch1 = fgetc(hfmTree); /读取赫夫曼编码，存储在相应的HCi数组里 int j = 0; while( ch1 != 'n' ) HCij = ch1; j+; ch1 = fgetc(hfmTree); HCij = '0' i+; chi = '0' i = 0; while( i < 2 * n - 1 ) /读取

29、赫夫曼树的各个结点的parent,lchild,rchild.并赋值到赫夫曼树HT中 ch1 = fgetc(hfmTree); /读取parent的字符串形式,存储在c中，并将其转换成整数形式，赋给HTi.parent j = 0; while( ch1 != ' ' ) /遇到空格前将读取的字符都保存在c中 cj = ch1; j+; ch1 = fgetc(hfmTree); HTi+1.parent = 0; /初始化 for( t = 0; t < j; t+ ) /字符转整型 HTi+1.parent = 10 * HTi+1.parent + ct - &#

30、39;0' ch1 = fgetc(hfmTree); /读取lchild的字符串形式，并将其转换成整数形式，赋给HTi.lchild j = 0; while( ch1 != ' ' ) /遇到空格前将读取的字符都保存在c中 cj = ch1; j+; ch1 = fgetc(hfmTree); HTi+1.lchild = 0; /初始化 for( t = 0; t < j; t+ ) /字符转整型 HTi+1.lchild = 10 * HTi+1.lchild + ct - '0' ch1 = fgetc(hfmTree); /读取rchi

31、ld的字符串形式，并将其转换成整数形式，赋给HTi.rchild j = 0; while( ch1 != 'n' ) /换行前将读取的字符都保存在c中 cj = ch1; j+; ch1 = fgetc(hfmTree); HTi+1.rchild = 0; /初始化 for( t = 0; t < j; t+ ) /字符转整型 HTi+1.rchild = 10 * HTi+1.rchild + ct - '0' i+; /显示规定格式编码,并将所得编码存储到文件-void CodePrin() FILE *CodePrin,*CodeFile; ch

32、ar c; int prin200; int k=0; if( CodeFile = fopen("CodeFile.TXT","r") = NULL ) printf("Open file fail.n"); exit(0); if( CodePrin = fopen("CodePrin.TXT","w") = NULL ) printf("Open file fail.n"); exit(0); c = fgetc(CodeFile); /从文件读取一个字符 while(

33、 c != EOF ) /对文件中的各个字符进行编码，直至文件结尾 if(c='1') prink=1; else prink=0; fputc(c,CodePrin); /将c相应的赫夫曼编码写入到文件中 printf("%d",prink); /将c相应的赫夫曼编码输出到屏幕 c = fgetc(CodeFile); /读入文件中的下一个字符 k+; if(k%50=0) /50个字符时，换行 printf("n"); fputc('n',CodePrin); printf("n"); fclose

34、(CodePrin); fclose(CodeFile);/显示并打印赫夫曼树-void TreePrint(HuffmanTree &HT, int n) FILE *TreePrint; char a20; int temp; int j; if( TreePrint = fopen("TreePrint.TXT","w") = NULL ) /打开用于存储赫夫曼树的文件 printf("Open file fail.n"); exit(0); for(i = 1; i <= 2 * n - 1; i+ ) /将赫夫

35、曼树各个结点的parent,lchild,rchild分别显示 printf("%d ",HTi.parent); printf("%d ",HTi.lchild); printf("%d",HTi.rchild); printf("n"); temp = HTi.parent; /将i结点的parent转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,TreePrint); fputc(' ',TreePrint); else j = 0; /计算HTi.pare

36、nt数字位数 while( temp != 0 ) temp = temp / 10; j+; temp = HTi.parent; /数字转字符 aj = '0' while( temp != 0 ) aj - 1 = (char)(temp % 10 + 48); temp = temp / 10; j-; fputs(a,TreePrint); fputc(' ',TreePrint); temp = HTi.lchild; /将i结点的lchild转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,TreePrint);

37、fputc(' ',TreePrint); else j = 0; /计算HTi.lchild数字位数 while( temp != 0 ) temp = temp / 10; j+; temp = HTi.lchild; /数字转字符 aj = '0' while( temp != 0 ) aj - 1 = (char)(temp % 10 + 48); temp = temp / 10; j-; fputs(a,TreePrint); fputc(' ',TreePrint); temp = HTi.rchild; /将i结点的rchild转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,TreePrint); fputc('n',TreePrint); else j = 0; /计算HTi.lchild数字位数 while( temp != 0 ) temp = temp / 10; j+; temp = HTi.rchild; /数字转字符 aj = '0' while( temp != 0 ) aj - 1 =