哈夫曼编码问题

哈夫曼编码问题

A 7
B 27
C 3
D 5
E 11

原理：取权重之和最小的两个节点（根节点）组成二叉树，如此循环，直到没有一个剩下。

第一步：
8
/ \
3 5
C D

第二步：
15
/ \
7 8
A / \
3 5
C D

第三步：
26
/ \
11 15
E / \
7 8
A / \
3 5
C D

第四步：
53
/ \
26 27
/ \ B
11 15
E / \
7 8
A / \
3 5
C D

最后一步——编码：
左分支为0，右分支为1，则结果为：
A: 010
B: 1
C: 0110
D: 0111
E: 00

呵呵，分数太少了啊。代码贴给你了，测试没问题

#include "stdafx.h" // huffman.cpp : 定义控制台应用程序的入口点。 // #include <stdio.h> #include <string.h> #define n 50 #define m 2*n-1

typedef struct { char data[5]; int weight; int parent; int lchild; int rchild; } htnode;

typedef struct { char cd[n]; int start; } hcode;

void createht(htnode ht[],int n) { int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i++) ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for (i=n;i<2*n-1;i++) { min1=min2=32767; lnode=rnode=-1; for (k=0;k<=i-1;k++) if (ht[k].parent==-1) { if (ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } else if (ht[k].weight<min2) { min2=ht[k].weight;rnode=k; } } ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; } }

void createhcode(htnode ht[],hcode hcd[],int n) { int i,f,c; hcode hc; for (i=0;i<n;i++) { hc.start=n;c=i; f=ht[i].parent; while (f!=-1) { if (ht[f].lchild==c) hc.cd[hc.start--]='0'; else hc.cd[hc.start--]='1'; c=f;f=ht[f].parent; } hc.start++; hcd[i]=hc; } }

void disphcode(htnode ht[],hcode hcd[],int n) { int i,k; int sum=0,m=0,j; printf(" 输出哈夫曼编码:\n"); for (i=0;i<n;i++) { j=0; printf(" %s:\t",ht[i].data); for (k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; } m+=ht[i].weight; sum+=ht[i].weight*j; printf("\n"); } printf("\n 平均长度=%g\n",1.0*sum/m); } void main() { int i, n=4; char *str[]={"a","b","c","d"}; int fnum[]={1,3,4,7};

htnode ht[m]; hcode hcd[n]; for (i=0; i<n; i++) { strcpy(ht[i].data, str[i]); ht[i].weight=fnum[i]; } printf("\n"); createht(ht,n); createhcode(ht,hcd,n); disphcode(ht,hcd,n); printf("\n"); system("pause"); }