哈夫曼编码的设计与实现1.doc

华北科技学院计算机学院综合性实验报告华北科技学院计算机学院开放实验实 验 报 告实验名称 哈夫曼树编码的设计与实现 实验学期 2014 至 2015 学年 第 一 学期学生所在系部 计算机学院 年级 2013 专业班级 软件工程B13-2班 学生姓名 扈鹏程 学号 201307044213 任课教师 栾尚敏 实验成绩 计算机学院制12哈夫曼树编码的设计与实现开放实验报告开课实验室：基础（二） 年 月 日实验题目哈夫曼树编码的设计与实现一、实验目的 设计哈夫曼树编码系统，锻炼学生的编程能力，巩固哈夫曼算法，熟悉遍历方法。二、设备与环境Windows Xp，VC6.0三、实验内容(1)原理分析：编写此系统是为了实现一个利用哈夫曼算法的编码和译码系统。比如，在利用电报通讯时，需要将文字转换成有二进制的字符组成的字符串。比如需要传送的电文为“A B D C C D A”假设将A,B,C,D分别编码为00,10,10,11。则上述电文便为00011110101100，总长14位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的代码。但是这种编码必须遵循:任何一个字符的编码都不是另一个字符编码的前缀。哈夫曼编码恰好可以很好的解决前缀码这一问题。在使用哈夫曼编码时，它会根据结点权值进行，对于使用频率低的字符，会将其置于树层次比较高的地方；相反的是使用频率高的字符。这样做的结果就是使使用频率高的字符编码变得很短而使用频率低的字符编码长一些，而编码长度一般取决于使用频率高的字符，因此这样可以大大缩短字符编码长度，并且不易被别人获取编码规则。运用哈夫曼编码最重要的一点就是建立哈夫曼树，而对于树这种非线性结构，使用链式存储有着多种优势：节省内存空间，因为它不会存在多申请存储空间的情况；同时，指针可以清晰的指示各结点之间的关系，不像顺序存储那样需要进行复杂的逻辑设计；(2) 算法设计：采用逐步求精的方法，给出从自然语言描述的算法到类C语言描述的算法；初始化哈夫曼树1） 建立链表，若链表已存在，则销毁原链表，重新建立，用以存储符号及权值。由文件中逐个读取字符，并在链表中查找，找到则权值加1，否则为其新建结点，并赋其权值为1。类C描述：void new(Linklist *head) if(head!=NULL) destory(head); p=head-next; while(fp!=EOF) c=getc(fp);while(p!=NULL & i=0) if(c=p-c) p-w+;i+ p0=p;p=p-next;if(p=NULL) q=Linklist * malloc(space); q-c=c;q-w=1;p0-next=p;c=getc(fp); 2） 建立哈夫曼树。I 在1）建立的链表中，挑选出未标记且权值最小的结点，将其移动至第一个结点位置，并且进行标记，并且重复次操作一次；II 新建结点为这两个结点的父节点，并取代这两个结点在链表中的位置，其权值为两个子节点权值之和；III 回到步骤I，直至链表中除头外仅剩一个结点。类C描述：void init(Linklist *head) while(n1) search(head);search(head); q=Linklist * malloc(space); q-rchild=head-next-next; q-lchild=head-next; q-c=0; q-lchild-parent=q-rchild-parent=q; q-w=q-lchild-w+q-rlchild-w; q-next=q-rchild-next;head-next=q;n-; 哈夫曼树应用1） 打印哈夫曼树。I 输出根结点存储字符，若没有则不处理；如果此结点为叶结点，则结束；II 如果有左子树，画出需要的线条与圆圈，进入左子树处理过程；III 如果有右子树，画出需要的线条与圆圈，进入右子树处理过程；类C描述：void printHT(Linklist *head) if(head-c!=0) print(head-c);return; if(head-lchild!=NULL) line();sq();printHT(head-lchild); if(head-rchild!=NULL) line();sq();printHT(head-rchild);2） 编码I 获取一个需要编码的字符；II 利用前序遍历的方法找到该字符在哈夫曼树中的位置；III 逆序比较，若为左孩子，则向字符串中存入0，否则存入1，直到比较到根，逆序输出编码，同时存入相应文件中；类C描述：void code(Linklist *head) int i=0; c=getchar(); while(c!=n) p=ad(c); if(p-c!=c) return; while(p!=head) p0=p;p=p-parent; if(p-lchild=p0) ai+=0; if(p-rchild=p0) ai+=1; i-; for(;i=0;i-) printf(ai); 3） 译码I 指针指向树根；II 获取一个需要译码的字符；III 判断为0，则指针指向左孩子，否则指向右孩子；IIII 判断是否有字符存储，若有，输出该字符并返回I，否则返回II，直到所有的字符都获取完毕。类C描述：void encode(Linklist *head) Linklist *p; c=getchar(); while(c!=n) if(c=0 & p-lchild!=NULL) p=p-lchild; else if(c=1 & p-lchild!=NULL) p=p-rchild; else print(c);pd1+; if(p-c != 0) print(p-c);p=head; (3)系统描述：采用流程图的形式描述整个系统，并详细介绍各模块的功能实现。主程序模块程序开始运行时，可选择修改原字符或初始化，初始化即建立链表操作，选择修改原字符执行修改操作，然后重新选择；建立链表之后可选择建立哈夫曼树或修改原字符，修改同前文所述，建立完哈夫曼树之后有六项操作可以选择，包括退出、修改初始字符（在此处仅修改，不会改变本次运行的字符编码）、查看字符编码、编码、译码、打印哈夫曼树，之后进入重复寻则，可以继续当前操作、返回上层和退出，其中，除退出选项外，其余几个选项结束后会询问继续、返回上层或退出，选择继续则再次进行之前选择的项目处理，选择返回上层则回到项目选择处，两个退出选项均直接结束本次操作。 主程序模块建立链表打开文件，判断文件指针是否为结束标记，是则退出，不是，读取一个字符，并循环判断是否存在，存在，则权值加1，如果不存在，则新建结点储存该字符，并且权值赋值为1. 新建链表建立哈夫曼树判断链表中有几个结点，仅有一个则退出，否则循环寻找链表中未标记元素中权值最小的结点移动到链表开头，重复一次，新建结点作为这两个节点的根，建立子树，并由这个结点代替原来两个结点的位置，其权值为两个子结点的权值只和，然后回到开始的判断。建立哈夫曼树修改初始字符从缓存区读取一个字符，判断是否为回车，是回车则退出，否则写入文件，再次读取一个字符回到判断处，进行循环。 修改初始字符打印哈夫曼树这是个前序遍历的递归处理方式，先处理根，有字符则输出字符，然后进入下一步，无字符直接进入下一步，存在左子树，有，则调用本函数进行处理左子树，同样进入下一步，无左子树同样进入下一步，再判断有无右子树，有，则调用本函数进行处理右子树，否则，结束。 打 印 哈 夫 曼 树编码从缓存区读取一个字符，判断是否为回车，是回车则退出，否则进入主要处理过程，利用遍历的方式寻找，直至找到字符位置或者遍历完整棵树，若未找到则输出原字符，找到则利用回溯法判断，是左子树，字符串存入0，右子树存入1，直至查找到根，逆序输出字符串中存储的编码。再次读取一个字符回到判断处，进行循环。 编 码译码从缓存区读取一个字符，令指针指向树根，判断是否为回车，是回车则退出，否则进入主要操作部分，判断是否为0或1，都不是则为出错，输出该字符并重新读取一个字符，直到为0或1后进入下一步，判断为0，指针指向左子树的根，为1，指针指向左子树的根，判断当前结点是否存储字符，无字符，则再次读取一个字符回到开头判断处，有字符 ，输出这个字符，指针指向根，然后再次读取一个字符回到开头判断处。 译 码(4)C语言实现：在VC 6.0环境下，实现上述算法。/ 赫夫曼树.cpp : Defines the entry point for the console application./#include stdafx.h#include#include#include#include conio.h#include#include#pragma comment(lib,winmm.lib)#define N sizeof(struct HTNode)void prCode(struct HTNode *H,struct HTNode *Hh);struct HTNodechar c,note;int weight;struct HTNode *parent,*lchild,*rchild,*next;int n=0,pd=0,pd1=0,pd2=0;void change(void)FILE *fp;char c,c1;system(cls);printf(nt欢迎使用赫夫曼编码译码系统n);printf(tn);printf(t 修改 编码 字符 n);printf(tn);if(pd2=2) printf(nt由于已经执行完赫夫曼树建立操作，本次更改只在程序下次运行时生效!);else printf(nt提示:因文本变化，需要重新初始化赫夫曼链表,否则本程序将nt在下次运行生效!);pd2=0;printf(nnttt是否继续修改编码原字符?nntttt是Y,否N:); c1=getche();if(c1=y | c1=Y)if(fp=fopen(编码来源.txt,w)=NULL)printf(打开失败!);exit(0);printf(nnt请输入新的文本(以回车为结束):);c=getchar();while(c!=n)fputc(c,fp);c=getchar();printf(nntt 修改编码原字符成功!nntt );fclose(fp);else printf(nntt );system(pause);void count(struct HTNode *ch) /编码统计FILE *fp;int i=0;char a;struct HTNode *p,*q,*p0;if(fp=fopen(编码来源.txt,r)=NULL)printf(打开失败!);exit(0);a=fgetc(fp);while(!feof(fp)p=ch-next;i=0;p0=ch;while(p!=NULL) & (i=0)if(a=(p-c) p-weight+;i+;break;p0=p;p=p-next;if(p=NULL) q=(struct HTNode *)malloc(N);q-c=a;q-weight=1;p0-next=q;q-next=q-parent=q-lchild=q-rchild=NULL;n+;a=fgetc(fp);fclose(fp);void pr(struct HTNode *p)while(p)if(p-c = ) printf(空格:%dt,p-weight);p=p-next;continue;printf(%c:%d t,p-c,p-weight);p=p-next;void search(struct HTNode *C)struct HTNode *pc,*pc0,*qc,*qc0;int i=999;pc0=qc=C;pc=C-next;while(pc!=NULL)if(pc-note!=y & pc-weightweight;pc0=pc;pc=pc-next;qc-note=y;qc0-next=qc-next;qc-next=C-next;C-next=qc;void Creat_Htree(struct HTNode *H)/建立赫夫曼树system(cls);pd2+;struct HTNode *h;while(H-c & n1)search(H);search(H);h=(struct HTNode *)malloc(N);h-rchild=H-next-next;h-lchild=H-next;h-c=0;h-lchild-parent=h-rchild-parent=h;h-weight=h-rchild-weight+h-lchild-weight;h-next=h-rchild-next;H-next=h;n-;printf(nnnnnnnnnnntttt赫夫曼树建立成功!nnnnnnnnnnnnntt );system(pause);struct HTNode *code1(struct HTNode *H,char c)/查找目标字符在赫夫曼树中的位置if(H-c=c) pd=1; return H;if(!pd & H-lchild!=NULL) code1(H-lchild,c);if(!pd & H-rchild!=NULL) code1(H-rchild,c);void code2(struct HTNode *H,char c,FILE *fp)struct HTNode *p,*p0;char a50;int i=0;pd=0;p0=code1(H,c);if(p0-c!=c) printf(%c,c);pd1+;return;p=p0;while(p!=H)p0=p;p=p-parent;if(p-lchild=p0) ai+=0;if(p-rchild=p0) ai+=1;i-;for(;i=0;i-) printf(%c,ai);fprintf(fp,%c,ai);pd1+;if(pd1=55)printf(nt );pd1=0;void code(struct HTNode *H)/赫夫曼编码char c,fc;FILE *fp,*ff;if(fp=fopen(code.txt,w)=NULL)printf(打开失败!);exit(0);if(ff=fopen(codetxt.txt,r)=NULL)printf(打开失败!);exit(0);system(cls);pd1=0;printf(nt欢迎使用赫夫曼编码译码系统n);printf(tn);printf(t 编 码 n);printf(tnn);prCode(H-next,H-next);printf(nnt);printf(请注意:如果您输入的字符不存在,本系统将不予编码,并以原型表示!n);CO:printf(nt请选择字符获取方式nnt自行键入,请按:1nnt文本读入,请按:2nnt请输入您的选择:);fc=getche();if(fc=1)printf(nnt请输入您想编码的字符(以回车为结束标记!):);c=getchar();printf(nnt您输入文本的编码为:nnt );while(c!=n)code2(H-next,c,fp);c=getchar();else if(fc=2)c=fgetc(ff);printf(nnt文本的编码为:nnt );while(!feof(ff)code2(H-next,c,fp);c=fgetc(ff);elseprintf(选择错误!请重新选择!nn);goto CO;fclose(fp);fclose(ff);printf(nntt稍后如需查看可查看文本code.txtnntt );system(pause);return;void prCode(struct HTNode *H,struct HTNode *Hh)/字符编码集合if(H-c!=0) if(H-c = ) printf( 空格:);else printf( %c :,H-c);char a50;int i=0;struct HTNode *p,*p0;p=p0=H;while(p!=Hh)p0=p;p=p-parent;if(p-lchild=p0) ai+=0;if(p-rchild=p0) ai+=1;i-;for(;i=0;i-) printf(%c,ai);printf(t);if(H-lchild!=NULL) prCode(H-lchild,Hh); /递归输出字符编码if(H-rchild!=NULL) prCode(H-rchild,Hh);void prCode1(struct HTNode *H,struct HTNode *Hh)system(cls);printf(nt欢迎使用赫夫曼编码译码系统n);printf(tn);printf(t 查看 字符 编码 n);printf(tn);printf(t字符编码如下:nt);puts();prCode(H,Hh);printf(nntt );system(pause);void encode(struct HTNode *H)/译码FILE *fp,*ff;char c,fc;struct HTNode *p=H;pd1=0;system(cls);if(fp=fopen(encode.txt,w)=NULL)printf(打开失败!);exit(0);if(ff=fopen(entxt.txt,r)=NULL)printf(打开失败!);exit(0);printf(nt欢迎使用赫夫曼编码译码系统n); printf(tn); printf(t 译 码 n); printf(tn);EN: printf(nt请选择字符获取方式nnt自行键入,请按:1nnt文本读入,请按:2nnt请输入您的选择:); fc=getche(); if(fc=1) printf(nnt 请输入所需要翻译的密码文(注意:文本为由0、1组成，以回车结束)nntt密码文:);c=getchar();printf(nnt译文:);printf(ntt );while(c!=n) /逐步进行查找if(c=0 & p-lchild!=NULL) p=p-lchild;else if(c=1 & p-lchild!=NULL) p=p-rchild;else printf(%c,c);pd1+;if(p-c != 0) printf(%c,p-c);fprintf(fp,%c,p-c);p=H;pd1+;if(pd1=45) printf(ntt );pd1=0;c=getchar(); else if(fc=2) c=fgetc(ff);printf(nnt译文:);printf(ntt );while(!feof(ff) /逐步进行查找if(c=0 & p-lchild!=NULL) p=p-lchild;if(c=1 & p-lchild!=NULL) p=p-rchild;if(p-c != 0) printf(%c,p-c);fprintf(fp,%c,p-c);p=H;pd1+;if(pd1=45) printf(ntt );pd1=0;c=fgetc(ff); else goto EN;fclose(fp);fclose(ff);printf(nntt 译码成功!nntt结束后您还可以到文本encode.txt中查询nntt );system(pause);void init(struct HTNode *Hhead)/初始化赫夫曼链表pd2=1;struct HTNode *p0,*p;system(cls);printf(nt欢迎使用赫夫曼编码译码系统n); printf(tn); printf(t 初始化赫夫曼链表 n); printf(tn);while(Hhead-next !=NULL) p0=Hhead;p=p0-next; while(p-next!=NULL) p0=p;p=p0-next; p0-next=NULL;free(p);count(Hhead);printf(nt输入结果统计如下:nn);pr(Hhead-next);printf(nntt );printf(赫夫曼链表初始化成功!nntt );system(pause);return;char Menu(void)/分情况菜单char a;printf(nt欢迎使用赫夫曼编码译码系统n); printf(tn); printf(t按键 操 作 内 容 n); if(pd2=0) printf(tn);printf(t 1. 初始化赫夫曼链表 n); if(pd2=1) printf(tn);printf(t 1. 建立 赫夫曼 树 n); if(pd22) a=8; if(a=2)a+=1; if(pd2=1) if(a2) a=8; if(a!=0)a+=1; if(pd2=2) if(a5) a=8; if(a!=0)a+=2; return a;char Menu1(void)/继续单char p;system(cls);printf(nt欢迎使用赫夫曼编码译码系统n); printf(tn); printf(t 操 作 n); printf(tn); printf(t 操 作 内 容 操 作 选 项 n); printf(tn); printf(t 继续 当 前 操作 1 n); printf(tn); printf(t 返回 上 一 级 2 n); printf(tn); printf(t 退 出 0 n）printf(tnnn); printf(tt 请输入你的选择:);p=getche();return p;void HTprint1(struct HTNode *H,int hl,int hr,int ll)/按格式画出赫夫曼树if(H-c!=0) if(H-c = ) setfont(12,0,楷体);setcolor(RED);outtextxy(hl-6,hr-6,);hl=315;hr=20;else setfont(13,0,楷体);setcolor(RED);outtextxy(hl-3,hr-6,H-c);hl=315;hr=20;return;if(H-lchild!=NULL) setcolor(BLUE);line(hl-5,hr+5,hl-10-ll,hr+30);circle(hl-15-ll,hr+35,7);HTprint1(H-lchild,hl-15-ll,hr+35,ll/3); /递归输出字符编码if(H-rchild!=NULL) setcolor(BLUE);line(hl+5,hr+5,hl+10+ll,hr+30);circle(hl+15+ll,hr+35,7);HTprint1(H-rchild,hl+15+ll,hr+35,ll/3);void HTprint(struct HTNode *H) /640*480char a=b;int b=0;int hl=320,hr=120,ll=155;/int hl=315,hr=20,ll=130;int graph=VGA,mode;initgraph(&graph,&mode,);setbkcolor(WHITE);cleardevice();setcolor(RED);circle(hl,hr,7);HTprint1(H,hl,hr,ll);setfont(50,0,楷体);outtextxy(190,50, 赫夫曼树);outtextxy(100,350,按任意键继续