哈夫曼编码译码系统.doc

上传人:豆**** 文档编号:24089410 上传时间:2022-07-03 格式:DOC 页数:18 大小:302KB
返回 下载 相关 举报
哈夫曼编码译码系统.doc_第1页
第1页 / 共18页
哈夫曼编码译码系统.doc_第2页
第2页 / 共18页
点击查看更多>>
资源描述

《哈夫曼编码译码系统.doc》由会员分享,可在线阅读,更多相关《哈夫曼编码译码系统.doc(18页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date哈夫曼编码译码系统程序设计基础课程设计 数据结构 课程设计赫夫曼编码/译码器设计指导教师:孙树森、周维达班级:09数媒(2)班学号:E09700227姓名:曾焕凯- 数据结构课程设计报告书一、 实验目的1、提高分析问题、解决问题的能力,进一步巩固数据结构各种原理与方法。2、熟悉掌握一门计算机语言,可以进行数据算法的设计。二、实验原理1、 哈夫曼树的定义: 假设有 n

2、个权值,试构造一颗有 n 个叶子节点的二叉树,每个叶子带 权值为 wi,其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树; 2、 哈夫曼树的构造: weight 为输入的频率数组,把其中的值赋给依次建立的 HT Node 对象中的 data 属性, 即每一个 HT Node 对应一个输入的频率。然后根据 data 属性按从小到大顺序排序,每次从 data 取出两个最小和此次小的 HT Node,将他们的 data 相加,构造出新的 HTNode 作为 他们的父节点,指针 parent,leftchild,rightchild 赋相应值。在把这个新的节点插入最小堆。 按此步骤可以构造构造出一

3、棵哈夫曼树。 通过已经构造出的哈夫曼树,自底向上,由频率节点开始向上寻找 parent,直到 parent 为树的顶点为止。这样,根据每次向上搜索后,原节点为父节点的左孩子还是右孩子,来记 录 1 或 0,这样,每个频率都会有一个 01 编码与之唯一对应,并且任何编码没有前部分是 同其他完整编码一样的。三、 实验步骤先统计要压缩编码的文件中的字符字母出现的次数,按字符字母和空格出现的概率对其进行哈夫曼编码。然后读入要编码的文件,编码后存入另一个文件;接着再调出编码后的文 件,并对其进行译码输出,最后存入另一个文件中。具体步骤:1. 初始化,统计文本文件中各字符的个数作为权值,生成哈夫曼树; 2

4、. 根据符号概率的大小按由大到小顺序对符号进行排序;3. 把概率最小的两个符号组成一个节点; 4. 重复步骤2. 3 ,直到概率和为 1;5. 从根节点开始到相应于每个符号的“树叶”,概率大的标“0”,概率小的标“1”; 6. 从根节点开始,对符号进行编码; 7. 译码时流程逆向进行,从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。四、实验结果与分析哈夫曼编码是动态变长编码,临时建立概率统计表和编码树。概率小的码比较长,概率 小的码比较长。概率大的码短,这样把一篇文件编码后,就会压缩许多。从树的角度看,哈夫曼编码方式是尽量把短码都利用上。首先,把一阶节点全都用上, 如果码字不够时, 然后,

5、 再从某个节点伸出若干枝,引出二阶节点作为码字,以此类推,显然所得码长最短,再根据 建立的概率统计表合理分布和放置,使其平均码长最短就可以得到最佳码。实验截图:五、实验心得本次实验结合了之前所学的赫夫曼算法,并利用其原理实现赫夫曼编码/译码系统;实验难度较之前的几次实验有所增加,所以花了比较多的时间来编写,测试代码。期间参考了网上的一些程序,通过结合分析,了解其他人在实现这个算法时的思想,也借鉴了其中的一些东西,同时加入了自己的想法。最终完成饿了本次的作业。通过这次实验,我了解了一个算法到一个可以执行的程序之间还有很多工作需要做,深刻体会到实践出真知的到了,看似简单的算法在实现时却话费了这么多

6、时间,但是这个过程中也让我学到了很多。六、主要代码Huffman_Tree.h:#ifndef Huffman_Tree_h#define Huffman_Tree_h#endif#include typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode, * HuffmanTree; /存储赫夫曼树的结点类型typedef char * * HuffmanCode; /用于存储字符集中各个字符相应的赫夫曼编码void strcpy(char *S1,char *S2) /将字符串S2复制到S1 i

7、nt i = 0; while( S2i != 0 ) S1i = S2i; i+; S1i = 0;/在HT1到HTt-1中找出权值最小的两个S1和S2-void Select(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

8、 if( i != s1 & HTi.parent = 0 & HTi.weight 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)ma

9、lloc(m + 1) * sizeof(HTNode); /申请存储赫夫曼树的空间 for(p = HT + 1, i = 1; i weight = *(w+1); p-parent = p-lchild = p-rchild = 0; for( ; i weight = p-parent = p-lchild = p-rchild = 0; for( i = n + 1; i = m; +i ) /构造赫夫曼树,给各个非叶子结点赋值 Select(HT, i - 1, s1, s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1;

10、HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /根据已建立的赫夫曼树对需要编码的字符进行编码- HC = (HuffmanCode)malloc(n + 1) * sizeof(char *); /用于存储指向存储各个字符相应赫夫曼编码的字符数组的指针 cd = (char *)malloc(n * sizeof(char); /分配工作所需空间 cdn - 1 = 0; /编码结束符 for( i = 1; i = n; +i) /逐个字符求赫夫曼编码 start = n -1; /编码在数组cd中的最前位置 /从叶子到根逆

11、向求编码,初始值;停止条件;一次循环后对上一个节点做循环 for(c = i,f = HTi.parent; f != 0; c = f, f = HTf.parent) if(HTf.lchild = c) cd -start = 0; else cd -start = 1; HCi = (char *)malloc(n - start)*sizeof(char); /为第i个字符编码分配空间 strcpy(HCi, &cdstart); /将cd数组的start位置到n-1位置复制给HCi free(cd); /释放空间 return 1;Test.cpp:#include #includ

12、e #include Huffman_Tree.h#define Yes 1 /当程序已经调用过初始化赫夫曼树的InitHuff_T()函数,或已从htfTree文件读取过,则将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(请输入编码字符集的大小:); sca

13、nf(%d,&n); /获取用户输入的字符集个数 while( i = 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,w) = NULL ) /打开用于存储赫夫曼树

14、的文件 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,save); printf(%dn,n); /向屏幕输出字符集大小n fputc(n,save); /换行 for

15、( 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 - 1; i+ ) /将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中 temp = HTi.parent; /将i结点的parent转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,save

16、); fputc( ,save); else j = 0; /计算HTi.parent数字位数 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,save); fputc( ,save); temp = HTi.lchild; /将i结点的lchild转换成字符并写入到文件中 if(temp = 0) fputc(temp + 48,

17、save); fputc( ,save); 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,save); fputc( ,save); temp = HTi.rchild; /将i结点的rchild转换成字符并写入到文件中 if(temp = 0) fputc(temp +

18、 48,save); fputc(n,save); else j = 0; /计算HTi.lchild数字位数 while( temp != 0 ) temp = temp / 10; j+; temp = 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, Huffm

19、anCode &HC, char ch) FILE *ToBeTran,*CodeFile; int i; char c; if( ToBeTran = 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 =

20、1; while( 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); fclose(ToBeTran); fclose(CodeFile);/译码,翻译成相应的字符表示,并存储到文件-

21、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 fail.n); exit(0); if( TextFile = fopen(TextFile.TXT,w) = NULL ) printf(Open file fail.n); exit(0

22、); c = fgetc(CodeFile); while( c != EOF ) /从文件读取字符,存储在code数组中 codei = c; i+; c = fgetc(CodeFile); codei = 0; i = 1; while ( codei != 0 & p != 0 ) /对数组code中的赫夫曼编码进行译码,p储存节点号 if ( codei = 0 ) p=HTp.lchild; /进入左分支 else p = HTp.rchild; /进入右分支 if (!HTp.lchild& !HTp.rchild) /不再有叶子节点时(进入叶子结点) fputc(chp,Tex

23、tFile); /将相应的字符写入到文件中 printf(%c,chp); /将相应的字符输出到屏幕 p = 2 * n - 1; /重新从树根出发进行译码 i+; printf(n);/从文件读取赫夫曼树-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); ex

24、it(0); fgets(c,10,hfmTree); /获取赫夫曼树叶子结点个数(字符串) 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 = fg

25、etc(hfmTree); /读取字符集中的一个字符 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 ) /读取赫夫曼树的各个结点的parent

26、,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 - 0; ch1 = fgetc(hfmTree); /读取lchild的

27、字符串形式,并将其转换成整数形式,赋给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); /读取rchild的字符串形式,并将其转换成整数形式,赋给HTi.rchild j = 0; while( ch1 != n ) /换行前将读取的字符

28、都保存在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; char c; int prin200; int k=0; if( CodeFile = fopen(CodeFile.TXT,r) = NULL ) printf(Open file f

29、ail.n); exit(0); if( CodePrin = fopen(CodePrin.TXT,w) = NULL ) printf(Open file fail.n); exit(0); c = fgetc(CodeFile); /从文件读取一个字符 while( c != EOF ) /对文件中的各个字符进行编码,直至文件结尾 if(c=1) prink=1; else prink=0; fputc(c,CodePrin); /将c相应的赫夫曼编码写入到文件中 printf(%d,prink); /将c相应的赫夫曼编码输出到屏幕 c = fgetc(CodeFile); /读入文件中

30、的下一个字符 k+; if(k%50=0) /50个字符时,换行 printf(n); fputc(n,CodePrin); printf(n); fclose(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);

31、 for(i = 1; i = 2 * n - 1; i+ ) /将赫夫曼树各个结点的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.parent数字位数 while( temp !=

32、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); fputc( ,TreePrint); else j = 0; /计算HTi.lc

33、hild数字位数 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

34、); else j = 0; /计算HTi.lchild数字位数 while( temp != 0 ) temp = temp / 10; j+; temp = HTi.rchild; /数字转字符 aj = 0; while( temp != 0 ) aj - 1 = (char)(temp % 10 + 48); temp = temp / 10; j-; fputs(a,TreePrint); fputc(n,TreePrint); fclose(TreePrint); /主函数-int main() HuffmanTree HT; HuffmanCode HC; char ch100;

35、 /用于存储字符集 int n,Init_Mode = No; /n为字符集的大小,Init_Mode = No 表示内存中没有赫夫曼树的信息 char mode; /让用户选择不同的操作 printf(请输入你要选择的功能(命令需要大写)n); printf(I - 初始化 E - 编码n); printf(D - 译码 P - 显示并打印编码n); printf(T - 显示并打印赫夫曼树 Q - 退出程序n); scanf(%c,&mode); /获得用户选择的操作 while( mode != Q ) /当用户输入不为Q时,执行相应操作 switch(mode) case I : In

36、itHuff_T(HT,HC,ch,n); Init_Mode = Yes; break; case E : if( No = Init_Mode ) ReadHuff_T(HT,HC,ch,n); Encoding(HT,HC,ch); Init_Mode = Yes; break; case D : if( No = Init_Mode ) ReadHuff_T(HT,HC,ch,n); Decoding(HT,ch,n); Init_Mode = Yes; break; case P : CodePrin(); break; case T : if( No = Init_Mode ) ReadHuff_T(HT,HC,ch,n); TreePrint(HT,n); Init_Mode = Yes; break; default : printf(您的输入有错,请重新选择.n); printf(请输入你要选择的功能n); printf(I - 初始化 E - 编码n); printf(D - 译码 P - 显示并打印编码n); printf(T - 显示并打印赫夫曼树 Q - 退出程序n); fflush(stdin); scanf(

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 小学资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知得利文库网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号-8 |  经营许可证:黑B2-20190332号 |   黑公网安备:91230400333293403D

© 2020-2023 www.deliwenku.com 得利文库. All Rights Reserved 黑龙江转换宝科技有限公司 

黑龙江省互联网违法和不良信息举报
举报电话:0468-3380021 邮箱:hgswwxb@163.com