/敬竖弊/哈夫曼树的构造哈夫曼树,哈夫曼编码 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#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
=
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
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）