哈弗曼编码程序.doc

#include #include #include #define N 8#define M 2*N-1typedef struct float weight;int lchild,rchild,parent;codenode;typedef codenode huffmantreeM;typedef struct char ch;int start;char bitsN+1;code;typedef code huffmancodeN;void select(huffmantree HT,int k,int *p1,int *p2)int i;float small1=10000,small2=10000;for (i=0;i=k;i+)if (HTi.parent=-1)if (HTi.weightsmall1)small2=small1;small1=HTi.weight;*p2=*p1;*p1=i;elseif (HTi.weightsmall2)small2=HTi.weight;*p2=i;void creathfcode(huffmantree HT)int i;for (i=0;iM;i+)HTi.weight=0;HTi.parent=-1;HTi.lchild=-1;HTi.rchild=-1;printf(请输入%d个字符的权重n,N);float k;for (i=0;iN;i+)scanf(%f,&k);HTi.weight=k;int p1,p2;for (i=N;iM;i+)select(HT,i-1,&p1,&p2);HTp1.parent=HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight;void huffmancoding(huffmantree HT,huffmancode HC)/编码int i,c,p;for (i=0;i=0)HCi.start-;if(HTp.lchild=c)HCi.bitsHCi.start=0;elseHCi.bitsHCi.start=1;c=p;p=HTp.parent;void huffmandecoding(huffmantree HT,huffmancode HC)int j=0,p;char s100;unsigned int i=0;scanf(%s,&s);char chN+1;while (istrlen(s)p=M-1;while (HTp.lchild!=-1)if (si=0)p=HTp.lchild;i+;elsep=HTp.rchild;i+;chj=HCp.ch;j+;i+;chj=0;puts(ch);int main()int i,j,k=0;char ch=A,B,C,D,E,F,G,H;huffmantree HT;huffmancode HC;printf(已知%d个字符为n,N);for(i=0;i=N;i+)printf(%c ,chi);HCi.ch=chi;printf(n);creathfcode(HT);huffmancoding(HT,HC);printf(字符哈夫曼编码为：n);for(i=0;iN;i+)printf(n%c:,HCi.ch);for(j=HCi.start;jN;j+)printf(%c,HCi.bitsj);print