2022年哈弗曼编码与译码.docx

《2022年哈弗曼编码与译码.docx》由会员分享，可在线阅读，更多相关《2022年哈弗曼编码与译码.docx（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源一个完整的系统应具有以下功能：(1) I ：初始化 Initialization ；从终端读入字符集大小n，以及 n 个字符和 n 个权值，建立赫夫曼树，并将它存于文件hfmTree 中；(2) E：编码Encoding ；利用已建好的赫夫曼树如不在内存，就从文件hfmTree 中读入， 对文件 ToBeTran 中的正文进行编码，然后将结果存入文件CodeFile 中；(3) D ：译码 Decoding ；利用已建好的赫夫曼树将文件CodeFile 中的代码进行译码，结果存入文件 Textfile 中；以下为选做：(4) P：印代码文件 Print ；将文件 CodeFile

2、以紧凑格式显示在终端上，每行50 个代码；同时将此字符形式的编码文件写入文件CodePrin 中；(5) T ：印赫夫曼树 Treeprinting ；将已在内存中的赫夫曼树以直观的方式比方树显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中；2. 测试要求(1) 已知某系统在通信联络中只可能显现八种字符，其频率分别为，试设计赫夫曼编码；(2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“ THIS PROGRAMEISMYFAVORITE ”；字符ABCDEFGHIJKLM频度1866413223210321154757153220字

3、符NOPQRSTUVWXYZ频度57631514851802381811613. 实现提示(1) 编码结果以文本方式储备在文件Codefile 中；(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit；请用户键入一个挑选功能符；此功能执行完毕后再显示此菜单，直至某次用户挑选了“Q”为止；(3) 在程序的一次执行过程中，第一次执行I， D 或 C 命令之后，赫夫曼树已经在内存了， 不必再读入；每次执行中不肯定执行I 命令，由于文件 hfmTree 可能早已建好；#include #include #include #include typedef stru

4、ct char letter; floatwt;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;/ 动态安排

5、数组储备Huffman 编码表/*初始化 Huffman 树* void selectHuffmanTree HT,int lint a,b,c,j; s1=s2=1; a=b=1000;forj=1;j=l;j+ ifHTj.code=0c=HTj.weight; ifcab=a;a=c;s2=s1;s1=j;else ifc0，构造 Huffman 树 HT,并求出 n 个字符的 Huffman 编码 HC. unsigned int i,f,start,c,m;char*cd;if n=1 return; m =2*n-1;HT=HuffmanTreemallocm+1*sizeofHT

6、Node; fori=1;i=m;+iHTi.weight=HTi.parent=HTi.lchild=HTi.rchild=HTi.code=0;fori=1;i=n;+iHTi.weight=HLi.wt; for i=n+1;i=m;+iselectHT,i-1; HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;欢迎下载精品学习资源HC=HuffmanCodemallocn+1*sizeofchar*; cd=char*mallocn*sizeofch

7、ar;cdn-1=0; fori=1;i=A&pi=Z|pi= forj=1;j=n;j+ifpi=HLj.letter fort=0;HCjt.=0;t+codingk+=HCjt;/for codingk=0;/encoding/*打印操作 * void PrintFILE *fp1,FILE *fp2/将文件 fp1 中的代码以紧凑格式显示在终端上，每行50 个代码/同时将此字符形式的编码文件写入文件fp2 中char c200; int i;fgetsc,200,fp1; fori=0;ci=0|ci=1;i+ printf%c,ci;fprintffp2,%c,ci;ifi+1/50

8、*50=i+1printfn;fprintffp2,n;/for printfn;/Printvoid PreOrderTraverseHuffmanTree HT,int k,FILE *fp欢迎下载精品学习资源/先序遍历并打印树，结果存放于fp 中,k 为根结点的下标int i;fori=1;i=DEPTH-1;i+fprintffp, ; for;i=DEPTH;i+fprintffp,|;fprintffp,%dn,HTk.weight;ifHTk.lchild.=0 DEPTH+;PreOrderTraverseHT,HTk.lchild,fp;DEPTH-;ifHTk.rchild

9、.=0 DEPTH+;PreOrderTraverseHT,HTk.rchild,fp; DEPTH-;ifHTk.lchild=0&HTk.rchild=0return; return; /PreOrderTraversevoid TreePrintingHuffmanTree HT,int n,FILE *fp/打印树 HT ，结果存于文件 fp 中， n 为树的叶子结点数int i,k;fori=1;i=2*n;i+ifHTi.parent=0k=i;break;/查找根结点PreOrderTraverseHT,k,fp; return;/TreePrinting/*主函数 * int

10、mainFILE *fp1,*fp2,*fp3,*fp4,*fp5; HuffmanTree HT; HuffmanCode HC;hfmlist HL;unsigned int i,n;char*b,c100,cha,ch;b=char *malloc100*sizeofchar; printf 请挑选操作： n;printfi: 初始化 Initializationne: 编码 Encodingnd: 译码 Decodingn;printfp: 印 代 码 文 件 Printnt: 印 哈 夫 曼 树 Treeprintingnq: 退 出 Quitn;b=char*malloc100*s

11、izeofchar;HL=hfmlistmalloc30*sizeofhfm;/储备字符与权值，线性表长30printfn;欢迎下载精品学习资源printf 挑选操作 i,e,d,p,t,q:; ch=getchar;getchar; printfn; doswitchchcase i:printf 正在进行初始化 n; printf 输入字符长度： ;scanf%d,&n; getchar; printfn;HC=HuffmanCodemallocn+1*sizeofchar; HT=HuffmanTreemalloc2*n*sizeofHTNode; fori=1;iletter, &HL

12、+i-wt; getchar;/foriffp5=fopenhfmTree.txt,w=NULL printfcannot open file.n;exit0;/if fori=1;iletter,HL+i-wt;/for fclosefp5;HuffmanCodingHT,HC,HL,n;printfn已经将 Huffman 树存入文件 hfmTree.txt 中nn; printf 初始化完毕，请挑选操作：n;printfi: 重新初始化 Initializationne: 编码 Encodingnd: 译码 Decodingn; printfp:印 代 码 文 件 Printnt: 印

13、哈 夫 曼 树 Treeprintingnq: 退 出Quitnn; break; case e:printf 请输入编码 ,以#结尾： ;iffp2=fopenToBeTran.txt,w=NULL printfcannot open filen;exit0;欢迎下载精品学习资源/ifcha=getchar;whilecha.=#fputccha,fp2; cha=getchar;欢迎下载精品学习资源/while getchar;fclosefp2;printf 已经把编码存入文件ToBeTran.txt 中nn; EncodingHC,HL,b,n;printf 文本的哈夫曼编码是 :;p

14、rintf%sn,b;printf 下面进行储存 :; saveb;printf 编码完毕，请挑选操作：n;printfi: 重新初始化 Initializationne: 编码 Encodingnd: 译码 Decodingn; printfp:印 代 码 文 件 Printnt: 印 哈 夫 曼 树 Treeprintingnq: 退 出Quitn; break; case d:DecodingHT,HL,c,n; printf 输入要译码的编码： ; printf 正在进行译码n; printf%sn,c;savec;printf 已经将结果存入文件 %s 中n,a;printf 译码完

15、毕，请挑选操作：n;printfi: 重新初始化 Initializationne: 编码 Encodingnd: 译码 Decodingn; printfp:印 代 码 文 件 Printnt: 印 哈 夫 曼 树 Treeprintingnq: 退 出Quitn;break; case p:fori=1;i=n;i+printf 字符 :%cttt 译码 :%sn,HLi.letter,HCi; iffp1=fopenCodeFile.txt,w=NULLprintfcannot open the file.n; exit0;/ififfp4=fopenCodeFile.txt,r=NUL

16、L printfcannot open the file.n;exit0;/ifPrintfp4,fp1;printf 该代码文件已经存在并命名为CodePrin.txtn; fclosefp4;fclosefp1; break;欢迎下载精品学习资源case t:printf 打印树存在于文件TreePrin 中n; iffp3=fopenTreePrin.txt,w=NULLprintfcannot open filen;exit0; TreePrintingHT,n,fp3;fclosefp3;break;case q:exit0;break; default :exit0;break;/switchprintfn请挑选操作 i,e,d,p,t,q:; ch=getchar;getchar;whilech.=q;/do return 0 ;/main欢迎下载