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

华北科技学院计算机学院开放实验实验报告实验名称实验学期 2014 至 2015学年 第 一 学期学生所在系部计算机学院年级 2013 专业班级 软件工程B13-2班学生姓名 扈鹏程 学号 201307044213任课教师栾尚敏实验成绩计算机学院制开课实验室：基础(二)年 月 日实验题目I哈夫曼树编码的设计与实现一、实验目的设计哈夫曼树编码系统，锻炼学生的编程能力，巩固哈夫曼算法，熟悉遍历方法。二、设备与环境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(n>1)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.关闭文件P=P->NEXT新建链表建立哈夫曼树判断链表中有几个结点读取一个字符P->W+新建结点存储字符，并赋权值为1C=P->C是"I是否C=P->C | P=NU!仅有一个则退出，否则循环寻找链表中未标记元素中权值最小的结点移动到链表开头，重复一次，新建结点作为这两个节点的根，建立子树，并由这个结点代替原来两结点的位置，其权值为两个子结点的权值只和，然后回到开始的判断。 是否仅剩 '、一是A下1个结点是指针指向头p=head将q指向的结点移至开头建立哈夫曼树 修改初始字符从缓存区读取一个字符，判断是否为回车，是回车则退出，否则写入文件，再次读取一个字符回到判断处，进行循环。判断是否 打印哈夫曼树这是个前序遍历的递归处理方式，先处理根，有字符则输出字符，然后进入下一步，无字符直接进入下一步，存在左子树，有，则调用本函数进行处理左子树，同样进入下一步，无左子树同样进入下一步，再判断有无右子树，有，则调用本函数进行处理右子树，否则，结束。否 编码从缓存区读取一个字符判断是否为回车，是回车则退出，否则进入主要处理过程，利用遍历的方式寻找，直至找到字符位置或者遍历完整棵树，若未找到则输出原字符，找到则利用回溯法判断，是左子树，字符串存入0，右子树存入1，直至查找到根，逆序输出字符诸I的编码0 的字符是个虽符回到否断处，进行循环。指针指向根 译码从缓存区读取一个字符，令指针指向树根，判断是否为回车，是回车则退出，否则进入 主要操作部分，判断是否为0或1，都不是则为出错，输出该字符并重新读取一个字符，直 到为0或1后进入下一步，判断为0，指针指向左子树的根，为1，指针指向左子树的根， 判断当前结点是否存储字符，无字符，则再次读取一个字符回到开头判断处，有字符，输出这个字符，指针指向根，然后再次读取一个字符回到开头判断处。(4) C语言实现：在VC 6.0环境下，实现上述算法。/ 赫夫曼树.cpp : Defines the entry point for the console application./华北科技学院计算机学院综合性实验报告#include "stdafx.h"#include<stdio.h>#include<stdlib.h>#include<string.h>#include "conio.h"#include<graphics.h>#include<windows.h>#pragma comment(lib,"winmm.lib")#define N sizeof(struct HTNode)void prCode(struct HTNode *H,struct HTNode *Hh);struct HTNode char 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 |欢迎使用赫夫曼编码一译码系统1n");printf("t |1 n");printf("t |修改编码字符I n");printf("t 11 n");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->weight<=i)qc0=pc0;qc=pc;i=pc->weight; 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 && n>1)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 |欢迎使用赫夫曼编码一译码系统1 n");printf("t |1 n");printf("t |编码I n");printf("t 11 nn");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 |欢迎使用赫夫曼编码一译码系统1 n");printf("t |1 n");printf("t i查看字符编码i n");华北科技学院计算机学院综合性实验报告 printf("t 11 n");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 |欢迎使用赫夫曼编码一译码系统1 n"); printf("t |1 n");printf("t |译码I n"); printf("t 11 n");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 |欢迎使用赫夫曼编码一译码系统1 n"); printf("t |1 n");printf("t |初始化赫夫曼链表I n"); printf("t 11 n");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 |欢迎使用赫夫曼编码一译码系统1 n");printf("t |11 n");printf("t |按键|操 作 内 容I n");if(pd2=0)printf("t |11 n");printf("t |1. I初始化赫夫曼链表I n");if(pd2=1)printf("t |11 n");printf("t |1. I建立 赫夫曼 树I n");if(pd2<2)printf("t |11 n");printf("t I 2. I修改 编码 字符I n");elseprintf("t |11 n");printf("t I 1. I修改 编码 字符I n");if(pd2=2)printf("t |11 n") 华北科技学院计算机学院综合性实验报告printf("t |_2查#字#编 WI n");printf("t |11 n")； printf("t |3. |编码I n");printf("t |11 n")；printf("t |4. |译码I n");printf("t |11 n")；printf("t |5. |打印 赫夫曼 树| n");printf("t |11 n");printf("t |0. |退出| n");printf("t 111 n");printf("nnt请输入您的选择:“)；a=getche();if(pd2=0)if(a>'2') a='8'if(a='2') a+=1;if(pd2=1)if(a>'2') a='8'if(a!='0') a+=1;if(pd2=2)if(a>'5') a='8'if(a!='0') a+=2;return a;char Menu1(void)继续单char p;system("cls");printf("nt |欢迎使用赫夫曼编码一译码系统1 n");printf("t | n");printf("t |操作I n"); printf("t |11 n");printf("t |操作 内容I 操作选项I n");printf("t |11 n");printf("t |继续当 前操作|1I n");printf("t |11 n");printf("t |返回 上一级|2I n");printf("t |11 n");printf("t |退出|0| n")printf("t 111 nnn"); 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;elsesetfont(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,hlT0-ll,hr+30);circle(hlT5Tl,hr+35,7);H Tprint1(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);H Tprint1(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,”按任意键继续。")；getche();closegraph();void wait(void)int i;for(i=0;i<6;i+)printf(".");Sleep(500);void main(int argc, char* argv)system("title赫夫曼编码一译码系统");system("color 97”);struct HTNode *Hhead;char i,j;Hhead=(struct HTNode *)malloc(N);Hhead->lchild=Hhead->parent=Hhead->rchild=Hhead->next=NULL;while(1)M: system(”cls”)；i=Menu();MD:switch(i)case '1':init(Hhead);break;case '2':Creat_Htree(Hhead);goto M;case 3 :change();break;case '4':prCode1(Hhead->next,Hhead->next);break;case '5':code(Hhead);break;case '6':encode(Hhead->next);break;case 7 :HTprint(Hhead->next);break;case '0':goto END;default :printf("nntt警告:输入错误，稍后重新进入菜单进行选择!")； printf("nntt 请稍候，正在为您跳转”);wait();goto M;system("cls");if(pd2=2)M1:j=Menu1();switch(j)case '1':goto MD;case '2':goto M;case '0':goto END;default :printf("nntt警告:输入错误，稍后重新进入菜单进行选择!"); printf("nntt 请稍候，正在为您跳转");wait();goto M1;END:system("cls");printf("nnnnnnnntttt 谢 谢 使用！nnnnnnnnnnnnnnn");return;四、实验结果及分析（1）主程序模块（几个主要菜单）初始化菜单- n x I_孙睥1沽田甘土昌绵若丘福弟n,互妨_里lulffl :娜八笑与柄-P-I 1甲口 T K小按键操作 内容i.初始化赫夫曼链表2.修改编码字符0.退出请输入您的选择：.初始化哈夫曼链表-X欢迎使用赫夫曼编码一译码系统，20输入结果统计如下=a：l s：2d：4 f：8g：3 h：l4+ -U S士号TIL、j1 L- 初始化链表后的菜单n菅理员：跃编码一样码球欢迎使用赫夫曼编码一译码系统，按键操作 内容1.建立赫夫曼树2.修改编码字符0.退出请输入您的选择: 哈夫曼树建立后的菜单s凝员：祸夫取码滔晋敦欢迎使用赫夫曼编码一译码系统，按键操作 内容1.修改编码字符2.查看字符编码3.编码4.译码5.打印赫夫曼树0.退出请输入您的选择: 菜单输入错误警告:输入错误,稍后重新进入菜单进行选择， 请稍候，正在为您跳转(2)主要操作修改初始字符匚二二二二二二矣兰便里暨芝美算四二苴四圣逃二二二二二二暨通%壬变