霍夫曼编码译码器

《霍夫曼编码译码器》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

数据结构课程设计（哈夫曼编/译码器）院系信息科学与工程学院专业班级学生姓名学号课程设计日期：2011年6月26日至2011年7月7日35 目录一、问题描述.................................................3二、需求分析1、基本要求2、测试数据..................................................3三、概要设计.................................................4四、详细设计.................................................7五、测试分析...............................................17六、课程设计总结.......................................26七、附录（源代码）.........................................2735 一、问题描述利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。二、需求分析1、基本要求一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。35 （5）T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。2、测试数据（1）数据一：已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，以此设计哈夫曼编码。利用此数据对程序进行调试。（2）用下表给出的字符集和频度实现统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVOURITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161二、概要设计一个完整的系统应具有以下功能：nI：初始化(Initialization)。从终端读入字符集大小n35 ，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。①对赫夫曼树初始化。②根据书本算法，对树进行从叶子到根的逆向求每个字符的赫夫曼编码。③更新赫夫曼树，并存到hfmTree.txt中。流程图如下：开始传入参数：结点个数nI<=n?NY动态分配内存，声明哈夫曼树HT，并对其值进行初始化建哈夫曼树，依次在HT[1..i-1]中Selectparent为0且weight最小的两个结点分配n个字符编码的头指针向量和求编码的工作区间从叶子到根逆向逐个字符求哈夫曼编码35 释放工作空间结束图1算法流程图nE：编码(Encoding)。利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。①将终端输入须要编码的语句逐字在已建好的赫夫曼树中查找。②当在树中找到相匹配字符时，将该字符对应的赫夫曼编码用strcat()统一存到code[]数组。③最后将code[]数组中的编码在终端输出并存储到CodeFile.txt中。nD：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。①从CodeFile.txt中获取须要译码的编码组。②将编码逐一读入，并在赫夫曼中根据左‘0’右‘1’去查找字符。③将译好的语句在终端输出，并存至Textfile.txt中。nP：打印表(TreePrint35 )。将已建立好的赫夫曼树的存储情况在终端以表格的形式罗列出来，使树的调用看起来更直观。nT：打印图(TreePrint)。将已建好的赫夫曼树以直观的图形在终端输出。①根据树的先序遍历算法，依次访问各个结点。②根据P打印出来的表，分析其所在的层次。③根据层次的大小，在终端输出相应长度的长条，来完成凹入表的输出。四、详细设计#include#include#includetypedefstruct{charelem;intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;//动态分配数组存储赫夫曼树编码表voidInitialization();voidEncoding();voidDecoding();voidHuffmanCoding(int);voidSelect(int,int*,int*);voidPrintHufmFigue();voidputout(int,int);voidTurn(int,void(*Visit)(int,int));voidTreePrint();35 //-------------------全局函数-----------------------intipt=1,n,q,p=0,code_num=0,TempLen=0,diamonds,lay;intw1=100000,w2=100000,w3=100000;HuffmanCodeHC=NULL;HuffmanTreeHT;intmain(){charkey;system("colorFC");printf("╔━━━━━━━━━━━━━━━━━━━━━╗ ");printf("┃赫夫曼编/译码器┃ ");printf("┃┃ ");printf("╚━━━━━━━━━━━━━━━━━━━━━╝ ");do{printf(" ");printf("╔━━━━━━━━━━━━━━━━━━━━━╗ ");printf("┃操作菜单┃ ");printf("┃┃ ");printf("┃I:初始化(Initialization)┃ ");printf("┃E:编码(Encoding)┃ ");printf("┃D:译码(Decoding)┃ ");printf("┃P:打印表(PrintHufmFigue)┃ ");printf("┃T:打印图(TreePrint)┃ ");printf("┃Q:退出(Initialization)┃ ");printf("┃┃ ");printf("╚━━━━━━━━━━━━━━━━━━━━━╝ ");printf(" ");printf("PleaseEnterakeyoftheoperation:");scanf("%c",&key);getchar();switch(key){case'i':case'I':Initialization();break;case'e':case'E':Encoding();break;35 case'd':case'D':Decoding();break;case'p':case'P':PrintHufmFigue();break;case't':case'T':TreePrint();}}while(key!='q'&&key!='Q');return1;}/*函数功能：建立赫夫曼树并对其进行初始化。函数参数：FILE*FhfmTreeP，将赫夫曼树的相关信息保存于此hfmTree.TXT中。函数实现：实现了字符集和频度的实际统计，并可将信息保存到hfmTree.TXT中。函数返回值：无*/voidInitialization(){inti,m;charstyle[]={'',''};printf("PleaseinputthenumberofNode:");scanf("%d",&n);getchar();m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用for(i=1;i<=n;i++){printf("Inputcharactersandweight(justlikea30Enter):");scanf("%c%d",&HT[i].elem,&HT[i].weight);getchar();HT[i].parent=HT[i].lchild=HT[i].rchild=0;}HuffmanCoding(n);35 FILE*FhfmTreeP=NULL;if(NULL==(FhfmTreeP=fopen("E:\hfmTree.txt","w")))printf("OpenhfmTree.txtfailed! ");else{for(i=1;i<=n;i++){fprintf(FhfmTreeP,"%c",HT[i].elem);fputs(HC[i],FhfmTreeP);fputs(style,FhfmTreeP);}}fclose(FhfmTreeP);printf("EverycharactorhasbeencodedandputedintoE:\hfmTree.txt! ");return;}voidHuffmanCoding(intn){inti,m,s1,s2,start,c,f;/*weight存放n个字符的权值（均char*cd;>0），构造赫夫曼树HT，并求出m=2*n-1;n个字符的赫夫曼编码HC。*/for(i=n+1;i<=m;++i){HT[i].elem='0';HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;}for(i=n+1;i<=m;++i){//建赫夫曼树Select(i-1,&s1,&s2);/*在HT[1...i-1]选择parent为0HT[s1].parent=i;HT[s2].parent=i;且weight最小的两个结点，其.HT[i].lchild=s1;HT[i].rchild=s2;序号分别为s1,s2*/HT[i].weight=HT[s1].weight+HT[s2].weight;}//-----------------从叶子到根逆向求每个字符的赫夫曼编码--------------------------35 HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间cd[n-1]='';//编码结束符for(i=1;i<=n;++i){//逐个字符求赫夫曼编码start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码{if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]);//从cd复制编码（串）到HC}free(cd);//释放工作空间return;}//HuffanCoding/*函数功能：选出当前字符集中，两个最小值s1,s2.函数参数：*s1,*s2,用于存储选出的两个最小值。函数返回值：无*/voidSelect(intn,int*s1,int*s2){inti;(*s1)=(*s2)=0;for(i=1;i<=n;i++){if(HT[i].weight(*s2)){i=(*s1);(*s1)=(*s2);(*s2)=i;}return;}/*函数功能：将终端输入的字符串编译成用0/1表示的编码，并将相应信息存入TXT文档。函数参数：temp[1000],用于临时存储终端输入的字符串。Code[1000],用于存储0/1编码。ToBeTran.txt,用于存储终端输入的字符串。CodeFile.txt，用于存储编译后的0/1编码。函数返回值：无*/voidEncoding(){inti,j,all;chartemp[1000],code[10000];printf("PleaseputinthesentenceyouwanttoEncoding:");35 //scanf("%s",temp);getchar();gets(temp);code[0]='';FILE*FToBeTranP=NULL;if(NULL==(FToBeTranP=fopen("E:\ToBeTran.txt","w")))printf("OpenToBeTran.txtfailed! ");elsefputs(temp,FToBeTranP);fclose(FToBeTranP);TempLen=strlen(temp);for(i=0;iMaxCode){MaxCode=strlen(HC[i]);MaxI=i;}}Floor=MaxCode+1;diamonds=Floor+10;lay=diamonds;Turn(numb,putout);return;}voidTurn(intw,void(*Visit)(int,int)){p++;w3=w2;w2=w1;w1=w;if(w3=1;count--){printf("█");}if(HT[lr].lchild!=0)printf("%d ",HT[lr].weight);elseprintf("%c ",HT[lr].elem);printf(" ");return;}五、测试分析I：初始化（Initialization）：35 E：编码（Encoding）35 D：译码（Decoding）P：打印表（TreePrint）35 35 35 T：打印图（Initialization）35 35 35 分别打开htmTree.txt,CodeFile.txt，TxtFile.txt，ToBeTran.txt文件（如下图从上到下的顺序）查看内部存储信息均符合预期结果。35 六、课程设计总结：这次数据结构课程设计持续了两周，在这两周中付出了很多，同样也得到了很多。这次课程设计巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。在本次课程设计中，不得不提的还有合作。虽说课题不是太难，但有时自己想不明白，通过大家的讨论可以更快和更有效率的解决问题，而且印象还很深刻。所以以后要多多和同学讨论，毕竟自己的不可能想得很全。通过这次课程设计，让我学到了很多，让我知道了认真上好专业实验课的重要性，以后多在实践中锻炼自己，毕竟说和做还是有很大差距的，而且35 写程序的过程中要考虑周到，严密。在做设计的时候要有信心，有耐心，切勿浮躁。认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。六、附录（程序源代码):#include#include#includetypedefstruct{charelem;intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidInitialization();voidEncoding();voidDecoding();voidHuffmanCoding(int);voidSelect(int,int*,int*);voidPrintHufmFigue();voidputout(int,int);voidTurn(int,void(*Visit)(int,int));voidTreePrint();intipt=1,n,q,p=0,code_num=0,TempLen=0,diamonds,lay;intw1=100000,w2=100000,w3=100000;HuffmanCodeHC=NULL;HuffmanTreeHT,T=NULL;intmain(){charkey;system("colorFC");printf("╔━━━━━━━━━━━━━━━━━━━━━╗ ");printf("┃赫夫曼编/译码器┃ ");printf("┃┃ ");printf("╚━━━━━━━━━━━━━━━━━━━━━╝ ");do{printf(" ");35 printf("╔━━━━━━━━━━━━━━━━━━━━━╗ ");printf("┃操作菜单┃ ");printf("┃┃ ");printf("┃I:初始化(Initialization)┃ ");printf("┃E:编码(Encoding)┃ ");printf("┃D:译码(Decoding)┃ ");printf("┃P:打印表(TreePrint)┃ ");printf("┃T:打印图(Initialization)┃ ");printf("┃Q:退出(Initialization)┃ ");printf("┃┃ ");printf("╚━━━━━━━━━━━━━━━━━━━━━╝ ");printf(" ");printf("请输入要执行的功能:");scanf("%c",&key);getchar();switch(key){case'i':case'I':Initialization();break;case'e':case'E':Encoding();break;case'd':case'D':Decoding();break;case'p':case'P':PrintHufmFigue();break;case't':case'T':TreePrint();}}while(key!='q'&&key!='Q');return1;35 }voidInitialization(){inti,m;charstyle[]={'',''};printf("请输入节点的数目:");scanf("%d",&n);getchar();m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));T=HT+m;for(i=1;i<=n;i++){printf("输入字符以及权重:");scanf("%c%d",&HT[i].elem,&HT[i].weight);getchar();HT[i].parent=HT[i].lchild=HT[i].rchild=0;}HuffmanCoding(n);FILE*FhfmTreeP=NULL;if(NULL==(FhfmTreeP=fopen("E:\hfmTree.txt","w")))printf("打开hfmTree.txt失败! ");else{for(i=1;i<=n;i++){fprintf(FhfmTreeP,"%c",HT[i].elem);fputs(HC[i],FhfmTreeP);fputs(style,FhfmTreeP);}}fclose(FhfmTreeP);printf("编码完成并已存入E:\hfmTree.txt! ");return;}voidHuffmanCoding(intn){inti,m,s1,s2,start,c,f;char*cd;m=2*n-1;for(i=n+1;i<=m;++i)35 {HT[i].elem='0';HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;}for(i=n+1;i<=m;++i){Select(i-1,&s1,&s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='';for(i=1;i<=n;++i){start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));//}free(cd);return;}//HuffanCodingvoidSelect(intn,int*s1,int*s2){inti;(*s1)=(*s2)=0;for(i=1;i<=n;i++){if(HT[i].weight(*s2)){i=(*s1);(*s1)=(*s2);(*s2)=i;}return;}voidEncoding(){inti,j,all;chartemp[1000],code[10000];printf("请输入你要编译的句子:");//scanf("%s",temp);getchar();gets(temp);code[0]='';FILE*FToBeTranP=NULL;if(NULL==(FToBeTranP=fopen("E:\ToBeTran.txt","w")))printf("打开ToBeTran.txt失败! ");elsefputs(temp,FToBeTranP);fclose(FToBeTranP);35 TempLen=strlen(temp);for(i=0;iMaxCode){MaxCode=strlen(HC[i]);MaxI=i;}}Floor=MaxCode+1;diamonds=Floor+10;lay=diamonds;Turn(numb,putout);return;}voidTurn(intw,void(*Visit)(int,int)){p++;w3=w2;w2=w1;35 w1=w;if(w3=1;count--){printf("█");}if(HT[lr].lchild!=0)printf("%d ",HT[lr].weight);elseprintf("%c ",HT[lr].elem);printf(" ");return;}35