欢迎来到天天文库
浏览记录
ID:32657981
大小:96.29 KB
页数:8页
时间:2019-02-14
《huffman编码课程设计样本》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、Huffman编/解码实验目的:熟悉二叉树的使用,学会用哈夫曼编码进行编码和译码。问题描述:利用Huffman编码进行通信可以大大提高信道的利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据进行预先编码,在接收端进行解码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/解码系统。基本要求一个完整的系统应该具有以下功能:1.I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立Huffman树,并将它存入hfmTree中。2.E:编码
2、(Encoding)。利用已经建好的Huffman树(如果不在内存,则应从文件hfmTree屮读取),对文件ToBeTranH-1的正文进行编码,然后将结果存入文件CodeFile屮。3.D:解码(Decoding)。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码,结果存入TextFile中。4.P:打印代码文件(Print)o将文件CodeFile以紧凑的格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。5.T:打印Huffman树(TreePrinting)。
3、将已经在内存中的Huffman树以直观的形式(树或者凹入的形式)显示在终端上,同时将此字符形式的Huffman树写入文件TreePrint中。实现提示1.编码结果以文本的方式存储在文件CodeFile中。2.用户界面可以设计为“菜单”方式:显示上述功能符号,再加上“Q”,表示退出(quit)。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单,直至某次用户选择了Q为止。1.在程序的一次执行过程中,第一次执行T,D,C命令后,HuffoNw树已经存在在内存中了,不必在读入。每次执行中不一定执行了I命令,因为文件hfmTree
4、可能己经早己建好。算法思想:用HuffmanTree构造一个最优二叉树,其中运用到select函数选择两个权值最小的节点。在哈夫曼构造过程中,需要访问频繁节点的双亲,故采用三叉链表的结构。编码和解码的结果均存在txt格式的文件中方便查看。实际程序中未使用课本提供的使用栈的思想编写HuffmanCoding和Coding,也可以运行。程序代码:#include#inc1ude#includeusingnamespacestd;#definemaxcode50typedef
5、struct{charcode[maxcode];charch;intweight,parent,IChild,rChild;}HTNode,*HuffmanTree;voidselect(HuffmanTreeHT,int&minl,int&min2,intn)//在HT中选择parent为零且weight为最小的两个节点,其下标分别为mini和min2//{inti=l,tem;while(HT[i].parent!=0)i++;tem=HT[i].weight;mini二i;for(i=l;i6、i].weight7、8、i==minl)i++;tem=HT[i].weight;min2=i;for(i=l;i〈n;i++){if(HT[i].weight9、)//{inti,m=2*nT;for(i=l;i<=m;i++){if(i>n)HT[i].weight=0;HT[i].IChild=HT[i].rChild=HT[i].parcnt=0;}intmini,min2;for(i=n+l;i<=m;i++){select(HT,mini,min2,i);HT[i].IChild=minl;HT[i].rCh订d=min2;HT[i]・weight二HT[mini].weight+HT[min2].weight;HT[mini].parcnt=HT[min2].parent二10、i;voidIlcodingdluffmanTree&HT,intn){inti,j,k,p;chartern[100];for(i=l;i<=n;i++){k二i;p二0;while(HT[k].parent!=0)j=HT[k].parent;//48表示字符0的ASC码
6、i].weight7、8、i==minl)i++;tem=HT[i].weight;min2=i;for(i=l;i〈n;i++){if(HT[i].weight9、)//{inti,m=2*nT;for(i=l;i<=m;i++){if(i>n)HT[i].weight=0;HT[i].IChild=HT[i].rChild=HT[i].parcnt=0;}intmini,min2;for(i=n+l;i<=m;i++){select(HT,mini,min2,i);HT[i].IChild=minl;HT[i].rCh订d=min2;HT[i]・weight二HT[mini].weight+HT[min2].weight;HT[mini].parcnt=HT[min2].parent二10、i;voidIlcodingdluffmanTree&HT,intn){inti,j,k,p;chartern[100];for(i=l;i<=n;i++){k二i;p二0;while(HT[k].parent!=0)j=HT[k].parent;//48表示字符0的ASC码
7、
8、i==minl)i++;tem=HT[i].weight;min2=i;for(i=l;i〈n;i++){if(HT[i].weight9、)//{inti,m=2*nT;for(i=l;i<=m;i++){if(i>n)HT[i].weight=0;HT[i].IChild=HT[i].rChild=HT[i].parcnt=0;}intmini,min2;for(i=n+l;i<=m;i++){select(HT,mini,min2,i);HT[i].IChild=minl;HT[i].rCh订d=min2;HT[i]・weight二HT[mini].weight+HT[min2].weight;HT[mini].parcnt=HT[min2].parent二10、i;voidIlcodingdluffmanTree&HT,intn){inti,j,k,p;chartern[100];for(i=l;i<=n;i++){k二i;p二0;while(HT[k].parent!=0)j=HT[k].parent;//48表示字符0的ASC码
9、)//{inti,m=2*nT;for(i=l;i<=m;i++){if(i>n)HT[i].weight=0;HT[i].IChild=HT[i].rChild=HT[i].parcnt=0;}intmini,min2;for(i=n+l;i<=m;i++){select(HT,mini,min2,i);HT[i].IChild=minl;HT[i].rCh订d=min2;HT[i]・weight二HT[mini].weight+HT[min2].weight;HT[mini].parcnt=HT[min2].parent二
10、i;voidIlcodingdluffmanTree&HT,intn){inti,j,k,p;chartern[100];for(i=l;i<=n;i++){k二i;p二0;while(HT[k].parent!=0)j=HT[k].parent;//48表示字符0的ASC码
此文档下载收益归作者所有