#include<stdio.h> #include<iostream.h> #define n 5 #define m 2*n-1 #define MAX 998 typedef struct { float weight; char c; int lchild,rchild,parent; }hufmtree;//建立哈夫曼树结构
typedef struct { char bits[n]; int start; char ch; }codetype;//建立编码结构 hufmtree tree[m+1];//零下标不用 codetype code[n+1];
//输入字符、编码及构建哈夫曼树函数 void HuffManTree(hufmtree tree[]) { int i,j,p1,p2; char c; float small1,small2,f; for(i=1;i<=m;i++) { tree[i].parent=0; tree[i].lchild=0; tree[i].rchild=0; tree[i].weight=0.0; tree[i].c='\0'; } printf("请输入要编码的字符:"); for(i=1;i<=n;i++) { c=getchar(); tree[i].c=c; } cout<<"请输入相应字符的权值:"; for(i=1;i<=n;i++) { cin>>f; tree[i].weight=f; } for(i=n+1;i<=m;i++) { p1=0; p2=0; small1=MAX; small2=MAX; for(j=1;j<=i-1;j++) if(tree[j].parent==0) if(tree[j].weight<small1) { small2=small1; small1=tree[j].weight; p2=p1; p1=j; } else if(tree[j].weight<small2) { small2=tree[j].weight; p2=j; } tree[p1].parent=i; tree[p2].parent=i; tree[i].lchild=p1; tree[i].rchild=p2; tree[i].weight=tree[p1].weight+tree[p2].weight; } } //为字符编码函数 void HuffManCode(hufmtree tree[],codetype code[]) { int i,j,c,p; codetype cd; for(i=1;i<=n;i++) { cd.start=n; c=i; cd.ch=tree[i].c; p=tree[i].parent; for(j=0;j<n;j++) cd.bits[j]=' '; while(p!=0) { cd.start--; if(tree[p].lchild==c) cd.bits[cd.start]='0'; else cd.bits[cd.start]='1'; c=p; p=tree[p].parent; } code[i]=cd; } } //编码输出函数 void PutoutCode(codetype code[]) { int i,j; for(i=1;i<=n;i++) { cout<<code[i].ch<<" "; for(j=0;j<n;j++) cout<<code[i].bits[j]; cout<<endl; } } void main() { HuffManTree(tree); HuffManCode(tree,code); cout<<"字符编码结果为:"<<endl; PutoutCode(code); }