数据结构哈弗曼编码实验

《数据结构哈弗曼编码实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、哈弗曼编码及译码代码#include"iostream.h"#include"math.h"#include"stdlib.h"#include#defineMAXSIZE100//最多子叶数#defineMAXCODE10000//编码最大长度typedefstruct{charinfo;//关联字符信息unsignedintweight;//每个节点的权职unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;//存储哈弗曼编码void

2、Select(HuffmanTreeHT,intj,int&s1,int&s2){//选择双亲节点为0，并且最小的两个子叶节点inti=1,m;while(HT[i].parent!=0)i++;//找第一个双亲节点为0的子叶结点for(s2=s1=i;i=HT[s1].weight&&HT[i].weight<=HT

3、[s2].weight)s2=i;while(HT[i].parent==0&&s1==s2){m=i;m++;while(HT[m].parent!=0)m++;s2=m;}}}voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn,char*info){//哈弗曼编码inti,m;HuffmanTreep;if(n<1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,

4、++w,++info){//初始化所有已存在的子叶信息p->info=*info;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}//forfor(;i<=m;++i,++p){//构造所需要的过度根节点p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}//forfor(i=n+1;i<=m;++i){//建立哈弗曼树ints1,s2;Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchi

5、ld=s2;HT[i].rchild=s1;HT[i].weight=HT[s1].weight+HT[s2].weight;}//for//哈弗曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));char*cd=(char*)malloc(n*sizeof(char));cd[n-1]='';for(i=1;i<=n;++i){intf;unsignedintc;intstart=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchil

6、d==c)cd[--start]='0';elsecd[--start]='1';}HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}//forfree(cd);}//HuffmanCodingvoidCheckCoding(HuffmanTreeHT,HuffmanCodeHC,char*strcheck,intm){//查询哈弗曼编码信息//char*strcopy=newchar[MAXCODE];for(inti=0;i

7、[j].info!=strcheck[i];j++);cout<

8、;}cout<