数据结构严蔚敏版 Huffman编码.docx
《数据结构严蔚敏版 Huffman编码.docx》由会员分享，可在线阅读，更多相关《数据结构严蔚敏版 Huffman编码.docx（8页珍藏版）》请在冰点文库上搜索。
数据结构严蔚敏版Huffman编码
#include
#include
#include
#include
#include
#defineMAX10000
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
HuffmanTreeHT;
HuffmanCodeHC;
unsignedint*w;
char*source_code;
voidHuffmanCoding（HuffmanTree&HT,HuffmanCode&HC,unsignedint*w,intn）;
voidSelect（HuffmanTreeHT,intt,int&s1,int&s2）;
voidmain（）
{
intn,i;//n是赫夫曼树叶子节点数
charchoose='y';//用于选择程序是否退出
//程序解说
printf（"本程序将演示构造哈夫曼树.\n"）;
printf（"首先输入叶子结点数目.\n例如:
2\n"）;
printf（"然后输入原始码以及权值.\n"）;
printf（"第1个原始码及其权值:
"）;
printf（"a5\n"）;
printf（"第2个原始码及其权值:
"）;
printf（"b3\n"）;
printf（"程序会构造一棵哈夫曼树并显示哈夫曼编码.\n"）;
cout<<"权值"<<""<<"原始码"<<""<<"哈夫曼编码"<printf（"5a1\n"）;
printf（"3b0\n"）;
putchar（'\n'）;
putchar（'\n'）;
while（choose!
='N'&&choose!
='n'）
{
printf（"请输入叶子结点数目:
"）;
scanf（"%d",&n）;//输入叶子结点数
if（n<=1）
{printf（"该数不合理!
\n"）;continue;}
w=（unsignedint*）malloc（n*sizeof（unsignedint））;//开辟空间存放权值
source_code=（char*）malloc（n*sizeof（char））;//开辟空间存放原始码
printf（"请输入各原始码以及权值:
\n"）;
for（i=0;i{
printf（"第%d个原始码及其权值:
",i+1）;
cin>>source_code[i];//输入原始码
cin>>w[i];//输入各叶子结点权值
}
HuffmanCoding（HT,HC,w,n）;
putchar（'\n'）;
printf（"哈夫曼树构造完毕，还要继续吗?
（Y/N）"）;
scanf（"%c",&choose）;
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
voidHuffmanCoding（HuffmanTree&HT,HuffmanCode&HC,unsignedint*w,intn）
{
//算法6.12
//w存放n个字符的权值（均>0），构造哈夫曼树HT，
//并求出n个字符的哈夫曼编码HC
inti,j,m,s1,s2,start;
char*cd;
unsignedintc,f;
if（n<=1）return;
m=2*n-1;
//HC=（char**）malloc（（n+1）*sizeof（char*））;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;//0号单元未用
for（i=1;i<=n;i++）{//初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for（i=n+1;i<=m;i++）
{//初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf（"\n哈夫曼树的构造过程如下所示：
\n"）;
printf（"HT初态:
\n结点weightparentlchildrchild"）;
for（i=1;i<=m;i++）
printf（"\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild,HT[i].rchild）;
printf（"按任意键，继续..."）;
getch（）;
for（i=n+1;i<=m;i++）
{//建哈夫曼树
//在HT[1..i-1]中选择parent为0且weight最小的两个结点，
//其序号分别为s1和s2。
Select（HT,i-1,s1,s2）;
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;
printf（"\nselect:
s1=%ds2=%d\n",s1,s2）;
printf（"结点weightparentlchildrchild"）;
for（j=1;j<=i;j++）
printf（"\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild,HT[j].rchild）;
printf（"按任意键，继续..."）;
getch（）;
}
//---从叶子到根逆向求每个字符的哈夫曼编码---
cd=（char*）malloc（n*sizeof（char））;//分配求编码的工作空间
cd[n-1]='\0';//编码结束符。
for（i=1;i<=n;++i）
{//逐个字符求哈夫曼编码
start=n-1;//编码结束符位置
for（c=i,f=HT[i].parent;f!
=0;c=f,f=HT[f].parent）
//从叶子到根逆向求编码
if（HT[f].lchild==c）cd[--start]='0';
elsecd[--start]='1';
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
//为第i个字符编码分配空间
strcpy（HC[i],&cd[start]）;//从cd复制编码（串）到HC
}
free（HT）;
free（HC[i]）;
free（source_code）;
free（w）;
free（cd）;//释放工作空间
}//HuffmanCoding
////////////////////////////////////////////////////////////////////////////////////////////////
voidSelect（HuffmanTreeHT,intt,int&s1,int&s2）
{
inti=0;
intj=0;
intk=0;
intleast=0;
intsecond=0;
for（i=1;i<=t;i++）
{
if（HT[i].parent==0）
break;
}
for（j=i+1;j<=t;j++）
{
if（HT[j].parent==0）
break;
}
if（HT[i].weight{
least=i;
second=j;
}
else
{
least=j;
second=i;
}
for（k=j+1;k<=t;k++）
{
if（HT[k].parent==0）
{
if（HT[k].weight{
second=least;
least=k;
}
elseif（HT[k].weight>=HT[least].weight&&HT[k].weightsecond=k;
}
}
s1=least;
s2=second;
}
升级会员 