求用c语言实现霍夫曼编码的程序，最好能带讲解的程序。感谢！

//* * * * * * * * * * * * * * * * * * * * * * * *

/敬竖弊/哈夫曼树的构造哈夫曼树,哈夫曼编码 *

//* * * * * * * * * * * * * * * * * * * * * * * *

#include <dos.h>

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct

{unsigned int weight //结点权值

unsigned int parent,lchild,rchild//结点的父指针，左右孩子指针

}HTNode,*HuffmanTree //动态分配数组存储哈夫曼树

typedef char **HuffmanCode//动态分配数组亮族存储哈夫曼编码表

void CreateHuffmanTree(HuffmanTree &,unsigned int*,int )//生成一棵哈夫曼树

void HuffmanCoding(HuffmanTree,HuffmanCode &,int ) //对哈夫曼树进行编码

void PrintHuffmanCode(HuffmanCode,unsigned int*,int)//显示哈夫曼编码

void Select(HuffmanTree,int,int&,int&)//在数组中寻找权值最小的两个结点

void main()

{HuffmanTree HT //哈夫曼树HT

HuffmanCode HC //哈夫曼编码表HC

int n,i//n是哈夫曼树叶子结点数

unsigned int *w//w存放叶子结点权值

char j='y'

textbackground(3) //设定屏幕颜色纤羡

textcolor(15)

clrscr()

//程序解说

printf("本程序将演示构造哈夫曼树.\n")

printf("首先输入叶子结点数目.\n例如:8\n")

printf("然后输入每个叶子结点的权值.\n")

printf("例如:5 29 7 8 14 23 3 11\n")

printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n")

printf(" 5---0110\n 29---10\n 7---1110\n 8---1111\n 14---110\n")

printf(" 23---00\n 3---0111\n 11---010\n")

while(j!='N'&&j!='n')

{printf("请输入叶子结点数目:")

scanf("%d",&n) //输入叶子结点数

if(n<=1) {printf("该数不合理!\n")continue}

w=(unsigned int*)malloc(n*sizeof(unsigned int))//开辟空间存放权值

printf("请输入各叶子结点的权值:\n")

for(i=0i<ni++) scanf("%d",&w[i]) //输入各叶子结点权值

CreateHuffmanTree(HT,w,n) //生成哈夫曼树

HuffmanCoding(HT,HC,n) //进行哈夫曼编码

PrintHuffmanCode(HC,w,n) //显示哈夫曼编码

printf("哈夫曼树构造完毕，还要继续吗?(Y/N)")

scanf(" %c",&j)

}

}

void CreateHuffmanTree(HuffmanTree &HT,unsigned int *w,int n)

{//w存放n个结点的权值，将构造一棵哈夫曼树HT

int i,m

int s1,s2

HuffmanTree p

if(n<=1) return

m=2*n-1 //n个叶子结点的哈夫曼树，有2*n-1个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))//开辟2*n各结点空间，0号单元不用

for(p=HT+1,i=1i<=n++i,++p,++w) //进行初始化

{p->weight=*w

p->parent=0

p->lchild=0

p->rchild=0

}

for(i<=m++i,++p)

{p->weight=0

p->parent=0

p->lchild=0

p->rchild=0

}

for(i=n+1i<=m++i) //建哈夫曼树

{Select(HT,i-1,s1,s2)

//从HT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2

HT[s1].parent=iHT[s2].parent=i//修改s1和s2结点的父指针parent

HT[i].lchild=s1HT[i].rchild=s2//修改i结点的左右孩子指针

HT[i].weight=HT[s1].weight+HT[s2].weight//修改权值

}

}

void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)

{//将有n个叶子结点的哈夫曼树HT进行编码， 所编的码存放在HC中

//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码

int i,c,f,start

char *cd

HC=(HuffmanCode)malloc((n+1)*sizeof(char *))//分配n个编码的头指针向量

cd=(char *)malloc(n*sizeof(char)) //开辟一个求编码的工作空间

cd[n-1]='\0' //编码结束符

for(i=1i<=n++i) //逐个地求哈夫曼编码

{start=n-1 //编码结束位置

for(c=i,f=HT[i].parentf!=0c=f,f=HT[f].parent) //从叶子到根逆向求编码

if(HT[f].lchild==c) cd[--start]='0' //若是左孩子编为'0'

else cd[--start]='1' //若是右孩子编为'1'

HC[i]=(char *)malloc((n-start)*sizeof(char)) //为第i个编码分配空间

strcpy(HC[i],&cd[start])//将编码从cd复制到HC中

}

free(cd)//释放工作空间

}

void PrintHuffmanCode(HuffmanCode HC,unsigned int *w,int n)

{//显示有n个叶子结点的哈夫曼树的编码表

int i

printf("HuffmanCode is :\n")

for(i=1i<=ni++)

{printf(" %3d---",w[i-1])

puts(HC[i])

}

printf("\n")

}

void Select(HuffmanTree HT,int t,int&s1,int&s2)

{//在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2

int i,m,n

m=n=10000

for(i=1i<=ti++)

{if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n))

if(m<n)

{n=HT[i].weights2=i}

else {m=HT[i].weights1=i}

}

if(s1>s2) //s1放较小的序号

{i=s1s1=s2s2=i}

}

以前写的埋早，证明最优子结构，随便一本算法书上就有雀丛. #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 = 0i <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 = 0i <n-1i++)

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 = 0i2 <ii2++)

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

}

}

---