风_吟_飞整理http://hi.baidu.com/风_吟/home用Huffman编码实现压缩程序摘要:本文是对Huffman算法进行的一次实践。根据ascii码文件中各ascii字符出现的频率情况创建Huffman树，再将各字符对应的哈夫曼编码写入文件中。同时，亦可根据对应的哈夫曼树，将哈夫曼编码文件解压成字符文件.关键词:Huffman算法,压缩，解压缩Abstract:Thisarticleisapracticeofhuffmanalgorithm.First,Icreatethehuffmantreebasedontheappearancefrequencyofeachasciicharacterinthefiles,thenIoutputeachasciicharacter’scorrespondinghuffmancodetothezippedfile.AndIalsomaketheprogramcouldunzipthehuffmanzippedfilesintotheasciifiles.KeyWords:HuffmanAlgorithm,Zip,unzip前言:Huffman算法是个简单而高效的贪心算法，主要用来创建最优二叉树.可以在通讯时，对于出现频率较高的字符，用较少的比特数便可以进行通讯.从而节省通讯线路的资源消耗。该算法在各类数据结构,算法,组合数学，离散数学，图论等主题的书籍中都有所涉及。故本文不再赘述，本文致力于用Huffman算法实现压缩与解压缩,采用的语言为C语言，编译环境VC++6.0.下面给出1中实现的Huffman树的结构及创建算法，有两点说明:1.这里的Huffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。2.由于对于最后生成的Huffman树，其所有叶子结点均为从一个内部树扩充出去的，所以，当外部叶子结点数为m个时，内部结点数为m-1.整个Huffman树的需要的结点数为2m-1./*Code1:HuffmanAlgorithm*/#defineMAXCHAR30000#defineMAXNODE300#defineMAXNUM150#defineInfoTypecharstructHtNode{EBTreeTypeww;charinfo;intparentIndex;风_吟_飞整理http://hi.baidu.com/风_吟/homeintllinkIndex;intrlinkIndex;};structHtTree{structHtNodeht[MAXNODE];introotIndex;};typedefstructHtTree*PHtTree;PHtTreehuffmanAlgorithm(intm,EBTreeType*w){PHtTreepht;inti,j;intfirstMinIndex,secondMinIndex;intfirstMinW,secondMinW;pht=(PHtTree)malloc(sizeof(structHtTree));assertF(pht!=NULL,"inhuffmanalgorithm,memapplyfailure\n");/*Initializethetreearray*/for(i=0;i<2*m-1;i++){pht->ht[i].llinkIndex=-1;pht->ht[i].rlinkIndex=-1;pht->ht[i].parentIndex=-1;if(i<m){pht->ht[i].ww=w[i];pht->ht[i].info=(char)i;}elsepht->ht[i].ww=-1;}for(i=0;i<m-1;i++)//newInnerNodeNum:m-1{firstMinW=MAXCHAR;firstMinIndex=-1;secondMinW=MAXCHAR;secondMinIndex=-1;for(j=0;j<m+i;j++){if(pht->ht[j].ww<firstMinW&&pht->ht[j].parentIndex==-1){//transminFirstinfotominSecondinfosecondMinIndex=firstMinIndex;secondMinW=firstMinW;风_吟_飞整理http://hi.baidu.com/风_吟/home//setnewfirstm