#include<conio.h>
#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#define
MAXVALUE
10000
/*权值最大值*/
#define
MAXLEAF
30
/*叶子最多个数*/
#define
MAXNODE
MAXLEAF*2-1
/*
结点数的个数*/
#define
MAXBIT
50
/*编码的最大位数*/
typedef
struct
node
/*结点类型定义*/
{
char
letter
int
weight
int
parent
int
lchild
int
rchild
}HNodeType
typedef
struct
/*编码类型定义*/
{
char
letter
int
bit[MAXBIT]
int
start
}HCodeType
typedef
struct
/*输入符号的类型*/
{
char
s
int
num
}lable
void
HuffmanTree(HNodeType
HuffNode[],int
n,lable
a[])
{
int
i,j,m1,m2,x1,x2,temp1
char
temp2
for
(i=0i<2*n-1i++)
/*结点初始化*/
{
HuffNode[i].letter=0
HuffNode[i].weight=0
HuffNode[i].parent=-1
HuffNode[i].lchild=-1
HuffNode[i].rchild=-1
}
for
(i=0i<n-1i++)
for
(j=i+1j<n-1j++)
/*对输入字符按权值大小进行排序*/
if
(a[j].num>a[i].num)
{
temp1=a[i].num
a[i].num=a[j].num
a[j].num=temp1
temp2=a[i].s
a[i].s=a[j].s
a[j].s=temp2
}
for
(i=0i<ni++)
{
HuffNode[i].weight=a[i].num
HuffNode[i].letter=a[i].s
}
for
(i=0i<n-1i++)
/*构造huffman树*/
{
m1=m2=MAXVALUE
x1=x2=0
for
(j=0j<n+ij++)/*寻找权值最小与次小的结点*/
{
if
(HuffNode[j].parent==-1&&HuffNode[j].weight<m1)
{
m2=m1
x2=x1
m1=HuffNode[j].weight
x1=j
}
else
if
(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight
x2=j
}
}
HuffNode[x1].parent=n+i
HuffNode[x2].parent=n+i
/*权值最小与次小的结点进行组合*/
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight
HuffNode[n+i].lchild=x1
HuffNode[n+i].rchild=x2
}
}
void
HuffmanCode(int
n,lable
a[])
{
HNodeType
HuffNode[MAXNODE]
HCodeType
HuffCode[MAXLEAF],cd
int
i,j,c,p
HuffmanTree(HuffNode,n,a)
for
(i=0i<ni++)
/*按结点位置进行编码*/
{
cd.start=n-1
c=i
p=HuffNode[c].parent
while
(p!=-1)
{
if
(HuffNode[p].lchild==c)
cd.bit[cd.start]=0
else
cd.bit[cd.start]=1
cd.start--
c=p
p=HuffNode[c].parent
}
for
(j=cd.start+1j<nj++)
/*储存编码*/
HuffCode[i].bit[j]=cd.bit[j]
HuffCode[i].start=cd.start
}
for
(i=0i<ni++)
{
HuffCode[i].letter=HuffNode[i].letter
printf("
%c
",HuffCode[i].letter)
for
(j=HuffCode[i].start+1j<nj++)
printf("%d",HuffCode[i].bit[j])
printf("\n")
}
}
int
main()
{
lable
data[30]
char
s[100],*p
int
i,count=0
for
()
{
cout<<"
/
求哈夫曼编码,直到输入为end结束!
/"<<endl
printf("
Input
some
letters:")
scanf("%s",s)
if
(!strcmp(s,"end"))
exit(0)
for
(i=0i<30i++)
{
data[i].s=0
data[i].num=0
}
p=s
while
(*p)
/*计算字符个数与出现次数(即权值)*/
{
for
(i=0i<=count+1i++)
{
if
(data[i].s==0)
{
data[i].s=*p
data[i].num++
count++
break
}
else
if
(data[i].s==*p)
{
data[i].num++
break
}
}
p++
}
printf("\n")
printf("
different
letters:%d\n",count)
for
(i=0i<counti++)
{
printf("
%c
",data[i].s)
printf("weight:%d\n",data[i].num)
}
HuffmanCode(count,data)
count=0
}
getch()
}
这是我们的软件实习答案，希望对你有帮助!
由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n－1个结点，可以用一个大小为2n－1的一维数组存放哈夫曼树的各个结点。在哈夫曼树构造好后，为了求得哈夫曼编码需要走一条从根结点出发到叶子结点的路径，则对每个结点既要知道其双亲还要知道孩子结点的信息。所以一维数组的每个元素包括四个数据项：结点的权值、结点的双亲结点下标号、左右孩子结点下标号。数据类型的定义如下：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就可以了
