算法设计与分析实验

《算法设计与分析实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验名称:哈夫曼编码的实现;实验目的:利用贪心算法的思想实现哈夫曼编码算法程序;实验原理:前缀码是任一字符的代码都不是其他字符代码的前缀。使平均码长达到最小的前缀码编码方案称为最优前缀码。表示最优前缀码的二叉树是一棵完全二叉树，即树中任一结点都有两个儿子结点。哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T。算法以

2、C

3、个叶结点开始，执行

4、C

5、-1次的“合并”运算后产生最终所要求的树T。实验环境:VC++6.0实验过程:程序代码如下：////******Huffman编码*******////////#include"iostream.h"#include"stdlib

6、.h"constintN=100;////////////////////////classBintree{public:Bintree(){}Bintree(chara){data=a;code=0;sign='l';flag='N';leftch=NULL;rightch=NULL;}voidMakeBintree(chara,Bintree*left,Bintree*right){data=a;sign='l';flag='N';leftch=left;rightch=right;}voidsetdata(chara){data=a;}chargetdata(){ret

7、urndata;}8voidsetcode(intc){code=c;}intgetcode(){returncode;}voidsetsign(chara){sign=a;}chargetsign(){returnsign;}voidsetflag(chara){flag=a;}chargetflag(){returnflag;}classBintree*leftch;classBintree*rightch;private:chardata;intcode;charsign,flag;};/////////////////////////classHuffman{publ

8、ic:voidHuffman12(Bintree*tt,floatw){tree=tt;weight=w;next=NULL;}Bintree*gettree()8{returntree;}floatgetweight(){returnweight;}Huffman*next;private:Bintree*tree;floatweight;};/////////////////////classMinHeap{public:voidInitialize(Huffman*h,intn);Huffman*RemoveMin();voidPut(Huffman*h);Huffma

9、n*gethm(){returnhm;}private:Huffman*hm;};///////////voidMinHeap::Initialize(Huffman*h,intn){Huffman*first,*second,*temp;inti,j;temp=newHuffman;for(i=0;inext;for(j=0;jnext!=NULL&&second->getweight()>8second->next->getweight()){temp=second->n

10、ext;second->next=temp->next;temp->next=second;first->next=temp;first=first->next;}else{first=first->next;second=second->next;}}}hm=h;};/////////Huffman*MinHeap::RemoveMin(){Huffman*p;if(!hm)return0;else{p=hm->next;hm=hm->next;returnp;}}////voidMinHeap::Put(Huffman*p){Huffman*head;head=hm;if

11、(!head->next){head->next=p;p->next=NULL;}elsewhile(head->next!=NULL&&(head->next->getweight()getweight())){8head=head->next;}if(head->next!=NULL){p->next=head->next;head->next=p;}else{head->next=p;p->next=NULL;}};/////////////Huffman*HuffmanTree(char