typedef struct Node
{
int weight
int parent, LChild,RChild
} HTNode, * HTree
typedef char *HuffmanCode
创建哈夫曼树并求哈夫曼编码的算法如下：
viod CreatHTree(HTree ht , HuffmanCode hc,int * w, int n)
{ /*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码hc */
int start
m=2*n-1
ht=(HTree)malloc((m+1)*sizeof(HTNode))
for(i=1i<=ni++)
ht[i] ={ w[i],0,0,0}
for(i=n+1i<=mi++)(* ht)[i] ={0,0,0,0}/* 初始化*/
for(i=n+1i<=mi++)
{
select(ht,i-1,&s1,&s2)
/* 在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回，select函数要求在上机调试使补充定义*/
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
} /*哈夫曼树建立完毕*/
/*以下程序是从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码的过程*/
hc=(HuffmanCode)malloc((n+1)*sizeof(char *))
cd=(char * )malloc(n * sizeof(char))
cd[n-1]＝’\0’；
for(i=1i<=ni++)
{
start=n-1
for(c=i,p=ht[i].parentp!=0c=p,p=ht[p].parent)
if(ht[p].LChild==c) cd[--start]=‘0’
else cd[--start]=‘1’
hc[i]=(char *)malloc((n-start)*sizeof(char))
strcpy(hc[i],&cd[start])
}
free(cd)
}
数组ht的前n个单元存放叶子结点的信息，最后一个单元存放的是根结点。
自己写个主程序，把八个字符的频率读入，调用CreatHTree就可以了
以前写的，证明最优子结构，随便一本算法书上就有.#include<stdio.h>
#include<stdlib.h>
#define
NIL
-2
#define
Size_Max_bm
30
#define
left(i)
(2*(i)+1)
#define
right(i)
(2*(i)+2)
#define
swap(a,b)
{cjys
tt=(a)(a)=(b)(b)=t}
#define
parent(i)
((i)%2?((i)-1)/2:((i)-2)/2)typedef
struct
cjys
{
char
sj
int
pl
struct
cjys
*left
struct
cjys
*right
}cjystypedef
struct
cjdl
{
int
size
int
leapsize
cjys
*p
}cjdl
cjys
*fpnn(void)
void
input(cjdl
*p)
cjys
*fpnn(void)
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
void
rd(cjdl
*p,
cjys
tp)
cjys
cd(cjdl
*p)
void
hbs(cjdl
*p)
cjys
*cjs(cjdl
*p)
void
bls(cjys
*p,int
*jl,
int
i)
void
disp(char
*tp,
cjys
*p)int
main()
{
cjdl
p
char
x[255]
cjys
*re=NULL
int
jl[Size_Max_bm]
input(&p)
re=cjs(&p)
printf("对照编码图为:\n")
bls(re,jl,0)
freopen("CON","r",stdin)
printf("输入Huffman码(VLC):")
scanf("%s",x)
disp(x,re)
system("pause")
}
void
input(cjdl
*p)
{
int
i
cjys
*tp
tp=fpnn()
printf("输入字母个数:")
scanf("%d",
&p->size)
p->p=malloc(sizeof(cjys)*p->size)
p->leapsize=0
for(i
=
0
i
<
p->sizei++)
{
printf("输入第%d字母:",i+1),scanf("
%c",&tp->sj)
printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl)
rd(p,*tp)
}
free(tp)
}
cjys
*fpnn(void)
{
cjys
*p=NULL
p=malloc(sizeof(cjys))
p->left=NULL
p->right=NULL
return
p
}
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
{
int
l=left(i),
r=right(i),
mini=i
if(l<leapsize
&&
p[l].pl<p[mini].pl)
mini=l
if(r<leapsize
&&
p[r].pl<p[mini].pl)
mini=r
if(mini
!=
i)
{
swap(p[i],p[mini])
zxdwh(p,mini,leapsize)
}
}
void
rd(cjdl
*p,
cjys
tp)
{
if(p->leapsize
==
p->size)
{
printf("队列已满!")
exit(0)
}
p->p[p->leapsize]=tp
int
j=p->leapsize,k=parent(j)
while(k>=0
&&
p->p[j].pl
<
p->p[k].pl)
{
swap(p->p[j],p->p[k])
j=k
k=parent(j)
}
p->leapsize++
}
cjys
cd(cjdl
*p)
{
if(p->leapsize
==
0)
{
printf("队列已空!")
exit(0)
}
cjys
tp=p->p[0]
p->leapsize--
p->p[0]=p->p[p->leapsize]
zxdwh(p->p,0,p->leapsize)
return
tp
}
void
hbs(cjdl
*p)
{
cjys
*p1=NULL,
*p2=NULL
cjys
tp
p1=fpnn()
p2=fpnn()
*p1=cd(p)
*p2=cd(p)
tp.left=p1
tp.right=p2
tp.pl=p1->pl+p2->pl
tp.sj=NIL
rd(p,tp)
}cjys
*cjs(cjdl
*p)
{
int
i,
n=p->leapsize
cjys
*tp=NULL
tp=fpnn()
for(i
=
0
i
<
n-1
i++)
hbs(p)
*tp=p->p[0]
return
tp
}
void
bls(cjys
*p,
int
*jl,
int
i)
{
if(p
==
NULL)
return
if(p->sj!=NIL)
{
int
i2
printf("%c:",p->sj)
for(i2
=
0
i2
<
i
i2++)
printf("%d",jl[i2])
printf("\n")
}
jl[i]=0
bls(p->left,jl,i+1)
jl[i]=1
bls(p->right,jl,i+1)
}
void
disp(char
*tp,
cjys
*p)
{
cjys
*ttp=NULL
int
pd=0
while(1)
{
ttp=p
while(1)
{
if(ttp->sj
!=
NIL)
{
printf("%c",ttp->sj)
break
}
if(*tp
==
'\0')
{
pd=1
break
}
if(*tp++
==
'0'
)
ttp=ttp->left
else
ttp=ttp->right
}
if(pd)
break
}
}
#include<stdio.h>#include<stdlib.h>
#define MAXSIZE 20
typedef struct TreeNode *HuffmanTree
typedef HuffmanTree ElemType
typedef struct code Code
struct TreeNode{
char c
int Weight
HuffmanTree Left,Right
}
typedef struct Heap{
ElemType Data[MAXSIZE]
int Size
int Capacity
}*MinHeap
struct code{
char c
char code[10]
}
struct TNode{
int Data
struct TNode* lchild
struct TNode* rchild
}
MinHeap BuildHeap()
{
MinHeap tmpH
tmpH=(MinHeap)malloc(sizeof(struct Heap))
ElemType Min=(ElemType)malloc(sizeof(ElemType))
Min->Weight=-1,Min->Left=Min->Right=NULL
tmpH->Size=0
tmpH->Capacity=MAXSIZE
tmpH->Data[0]=Min
return tmpH
}
int isFull(MinHeap H)
{
return H->Size>=H->Capacity
}
int isEmpty(MinHeap H)
{
return H->Size==0
}
void Insert(MinHeap H,ElemType T)
{
int i
if(isFull(H)){
printf("MinHeap is Full")
return
}
i=++H->Size
for(H->Data[i/2]->Weight>T->Weighti/=2)
H->Data[i]=H->Data[i/2]
H->Data[i]=T
}
ElemType DeleteMin(MinHeap H){
int Parent,child
ElemType min,tmp
if(isEmpty(H)){
printf("The Heap is Empty")
return NULL
}
min=H->Data[1]
tmp=H->Data[H->Size--]
for(Parent=1Parent*2<H->SizeParent=child)
{
child=Parent*2
if(child!=H->Size-1&&H->Data[child]->Weight>H->Data[child+1]->Weight)
child++
if(tmp->Weight>H->Data[child]->Weight)
{
H->Data[Parent]=H->Data[child]
}else break
}
H->Data[Parent]=tmp
return min
}
void InitHeap(MinHeap H,int n)
{
ElemType tmp
for(int i=0i<ni++)
{ getchar()
tmp=(ElemType)malloc(sizeof(ElemType))
scanf("%c,%d",&tmp->c,&tmp->Weight)
tmp->Left=tmp->Right=NULL
Insert(H,tmp)
}
}
HuffmanTree Huffman(MinHeap H)
{
int i
HuffmanTree T
for(i=1i<H->Sizei++)
{
T=(HuffmanTree)malloc(sizeof(HuffmanTree))
T->Left=DeleteMin(H)
T->Right=DeleteMin(H)
T->Weight=T->Left->Weight+T->Right->Weight
Insert(H,T)
}
T=DeleteMin(H)
return T
}
int main()
{
int n
scanf("%d",&n)
Code ans[n]
MinHeap H=BuildHeap()
HuffmanTree T
InitHeap(H,n)
T=Huffman(H)
return 0
}
哈夫曼树的构造，编码有01左右子树之分，稍微复杂
