[此贴子已经被作者于2005-4-21 18:24:24编辑过]

本人现在编好了这个程序. 不足的地方希望高手们纠正啊

#include<iostream> using std::cout; using std::endl; using std::cin; #include<cstdlib> #include<iomanip> typedef struct { int weight; int parent,lchild,rchild; }HFNode; typedef struct { char cd[4];//串中只有4个不同字符 int start; }Code; void CreatHuffman(HFNode [],int[] ,int,int);//生成哈夫曼树 void HuffmanCode(HFNode [],Code [],int);//对哈夫曼树编码 void printcode(char [],char [],Code []);//输出编码 static int s1,s2;

int main() { char ch[]="abcd"; char string[]="abaabcbdabcbabac"; int wei[]={6,6,3,1};//各个字符在串中出现的频率.叶子结点

int m=7;//为形成哈夫曼树的总结点数. HFNode HT[7]; Code hcd[7]; CreatHuffman(HT,wei,4,7); HuffmanCode(HT,hcd,4); printcode(string,ch,hcd); return 0; } void CreatHuffman(HFNode HT[],int wei[],int n,int m)//生成哈夫曼树 { int min1,min2; if(n<1) cout<<"参数不合理!!"<<endl; for(int i=0;i<n;++i) { HT[i].weight=wei[i]; HT[i].parent=-1; HT[i].lchild=-1; HT[i].rchild=-1; } for(i=n;i<m;++i) { HT[i].weight=0; HT[i].parent=-1; HT[i].lchild=-1; HT[i].rchild=-1; } for(i=n;i<m;++i) { min1=min2=1000;//随便设立一个数,但一定要比顺序表中的数都大. s1=s2=-1;//S1是左结点,S2是右结点. for(int k=0;k<=i-1;k++) if(HT[k].parent==-1)//在未访问的结点中查找. { if(HT[k].weight<min1) { min2=min1; s2=s1; min1=HT[k].weight; s1=k; } else if(HT[k].weight<min2) { min2=HT[k].weight; s2=k; } }

HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } i=i-1; HT[i].parent=0;//根结点的父亲为0. } void HuffmanCode(HFNode HT[],Code hcd[],int sum)//对哈夫曼树编码 { int f,c; Code hc; for(int i=0;i<sum;i++) { hc.start=0; c=i; f=HT[i].parent; while(f!=0) { if(HT[f].lchild==c) hc.cd[hc.start++]='0';//左结点的编码是0 else hc.cd[hc.start++]='1';//右结点的编码是1. c=f; f=HT[f].parent; } hc.cd[hc.start]='\0';//这个是从叶子结点到根的编码. for(int j=hc.start-1,k=0;j>=0;j--,k++)//转为从根到叶子的编码. hcd[i].cd[k]=hc.cd[j]; hcd[i].cd[k]='\0'; } } void printcode(char string[],char ch[],Code hcd[]) { int len=strlen(string); cout<<"编码后,各字符对应的编码:"<<endl; for(int k=0;k<4;k++) cout<<ch[k]<<'\t'<<hcd[k].cd<<endl; cout<<"待编码的字符:"<<string<<endl; cout<<"编码为:"<<endl; for(int i=0;i<len;i++) for(int j=0;j<4;j++) if(string[i]==ch[j]) cout<<hcd[j].cd; cout<<endl; }