哈弗曼编码与译码.doc

一个完整的系统应具有以下功能：(1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。(2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。以下为选做：(4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。(5) T：印赫夫曼树（Tree printing）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。2. 测试要求(1) 已知某系统在通信联络中只可能出现八种字符，其频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811613. 实现提示(1) 编码结果以文本方式存储在文件Codefile中。(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。(3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。#include #include #include #include typedef struct char letter;float wt;hfm,*hfmlist;/*全局变量*unsigned int s1,s2,n;char choose;int DEPTH=0;char a20;/*Huffman树和Huffman编码的存储表示*typedef structunsigned int weight;unsigned int code;unsigned int parent,lchild,rchild;HTNode, *HuffmanTree; /动态分配数组存储Huffman树typedef char * *HuffmanCode; /动态分配数组存储Huffman编码表/*初始化Huffman树*void select(HuffmanTree HT,int l)int a,b,c,j;s1=s2=1;a=b=1000;for(j=1;j=l;j+)if(HTj.code=0) c=HTj.weight; if(ca)b=a;a=c;s2=s1;s1=j; else if(c0），构造Huffman树HT,并求出n个字符的Huffman编码HC.unsigned int i,f,start,c,m; char*cd;if (n=1) return;m =2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1;i=m;+i)HTi.weight=HTi.parent=HTi.lchild=HTi.rchild=HTi.code=0; for(i=1;i=n;+i)HTi.weight=HLi.wt;for (i=n+1;i=m;+i)select(HT,i-1);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*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=A&pi=Z)|pi= ) for(j=1;j=n;j+) if(pi=HLj.letter) for(t=0;HCjt!=0;t+)codingk+=HCjt; /forcodingk=0;/encoding/*打印操作*void Print(FILE *fp1,FILE *fp2)/将文件fp1中的代码以紧凑格式显示在终端上，每行50个代码/同时将此字符形式的编码文件写入文件fp2中char c200;int i;fgets(c,200,fp1);for(i=0;ci=0|ci=1;i+)printf(%c,ci);fprintf(fp2,%c,ci);if(i+1)/50*50=(i+1)printf(n);fprintf(fp2,n);/forprintf(n);/Printvoid PreOrderTraverse(HuffmanTree HT,int k,FILE *fp)/先序遍历并打印树，结果存放于fp中,k为根结点的下标int i;for(i=1;i=DEPTH-1;i+)fprintf(fp, );for(;i=DEPTH;i+)fprintf(fp,|-);fprintf(fp,%dn,HTk.weight);if(HTk.lchild!=0)DEPTH+;PreOrderTraverse(HT,HTk.lchild,fp);DEPTH-;if(HTk.rchild!=0)DEPTH+;PreOrderTraverse(HT,HTk.rchild,fp);DEPTH-;if(HTk.lchild=0&HTk.rchild=0)return;return; /PreOrderTraversevoid TreePrinting(HuffmanTree HT,int n,FILE *fp)/打印树HT，结果存于文件fp中，n为树的叶子结点数int i,k;for(i=1;i=2*n;i+)if(HTi.parent=0)k=i;break;/寻找根结点PreOrderTraverse(HT,k,fp);return;/TreePrinting/*主函数*int main()FILE *fp1,*fp2,*fp3,*fp4,*fp5;HuffmanTree HT;HuffmanCode HC;hfmlist HL;unsigned int i,n; char *b,c100,cha,ch; b=(char *)malloc(100*sizeof(char);printf(请选择操作：n);printf(i:初始化(Initialization)ne:编码(Encoding)nd:译码(Decoding)n); printf(p:印代码文件(Print)nt:印哈夫曼树(Tree printing)nq:退出(Quit)n);b=(char *)malloc(100*sizeof(char);HL=(hfmlist)malloc(30*sizeof(hfm);/存储字符与权值，线性表长30printf(n);printf(选择操作(i,e,d,p,t,q):);ch=getchar();getchar();printf(n);do switch(ch)case i:printf(正在进行初始化n); printf(输入字符长度：); scanf(%d,&n); getchar(); printf(n); HC=(HuffmanCode)malloc(n+1)*sizeof(char); HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); for(i=1;iletter, &(HL+i)-wt); getchar(); /for if(fp5=fopen(hfmTree.txt,w)=NULL) printf(cannot open file!n); exit(0); /if for(i=1;iletter,(HL+i)-wt); /for fclose(fp5); HuffmanCoding(HT,HC,HL,n); printf(n已经将Huffman树存入文件hfmTree.txt中nn); printf(初始化完毕，请选择操作：n); printf(i:重新初始化(Initialization)ne:编码(Encoding)nd:译码(Decoding)n); printf(p:印代码文件(Print)nt:印哈夫曼树(Tree printing)nq:退出(Quit)nn); break;case e: printf(请输入编码,以#结尾：); if(fp2=fopen(ToBeTran.txt,w)=NULL) printf(cannot open filen);exit(0); /if cha=getchar(); while(cha!=#) fputc(cha,fp2); cha=getchar(); /while getchar(); fclose(fp2); printf(已经把编码存入文件ToBeTran.txt中nn); Encoding(HC,HL,b,n); printf(文本的哈夫曼编码是:); printf(%sn,b); printf(下面进行保存:); save(b); printf(编码完毕，请选择操作：n); printf(i:重新初始化(Initialization)ne:编码(Encoding)nd:译码(Decoding)n); printf(p:印代码文件(Print)nt:印哈夫曼树(Tree printing)nq:退出(Quit)n); break;case d: Decoding(HT,HL,c,n); printf(输入要译码的编码：); printf(正在进行译码n); printf(%sn,c); save(c); printf(已经将结果存入文件%s中n,a); printf(译码完毕，请选择操作：n); printf(i:重新初始化(Initialization)ne:编码(Encoding)nd:译码(Decoding)n); printf(p:印代码文件(Print)nt:印哈夫曼树(Tree printing)nq:退出(Quit)n); break;case p: for(i=1;i=n;i+)printf(字符:%cttt译码:%sn,HLi.letter,HCi); if(fp1=fopen(CodeFile.txt,w)=NULL) printf(cannot open the file!n); exit(0); /if if(fp4=fopen(CodeFile.txt,r)=NULL) printf(cannot open the file!n); exit(0); /if Print(fp4,fp1); printf(该代码文件已经存在并命名为CodePrin.txtn); fclose(fp4); fclose(fp1); break;case t:printf(打印树存在于文件TreePrin中n);