哈夫曼树及哈夫曼编码 C++代码实现


/*哈夫曼编码*/

#include <iostream>

using namespace std;

//********************************
//构造哈夫曼树
//********************************

/*哈夫曼树顺序表的定义*/
typedef struct
{
intweight;
intparent,lchild,rchild;
}HTNode;

typedef HTNode * HuffmanTree;


/*初始化一个哈夫曼树*/
void InitHuffmanTree(HuffmanTree&HT,int m)
{
inti;
HT=newHTNode[m];
for(i=0;i<m;i++)
{
HT[i].weight=0;
HT[i].parent=-1;
HT[i].lchild=-1;
HT[i].rchild=-1;
}
}
//****************************************
//从n个结点中选取最小的两个结点
//****************************************
void SelectMin(HuffmanTree &HT,intn,int &min1,int &min2)
{
typedefstruct
{
intNewWeight;//存储权
intp;//存储该结点所在的位置
}TempNode,*TempTree;

TempTreeTT=new TempNode[n];

inti,j;

j=0;
for(i=0;i<n;i++)
{
if(HT[i].parent==-1&& HT[i].weight!=0)
{
TT[j].NewWeight=HT[i].weight;
TT[j].p=i;
j++;
}
}//将HT中没有双亲的结点存储到TT中

intm1,m2;
m1=m2=0;
for(i=0;i<j;i++)
{
if(TT[i].NewWeight<TT[m1].NewWeight)//此处不让取到相等,是因为结点中有相同权值的时候,m1取最前的
那个。
m1=i;
}
for(i=0;i<j;i++)
{
if(m1==m2)
m2++;//当m1在第一个位置的时候,m2向后移一位
if(TT[i].NewWeight<=TT[m2].NewWeight&& i!=m1)//此处取到相等,是让在结点中有相同的权值的时候,

//m2取最后的那个。
m2=i;
}

min1=TT[m1].p;
min2=TT[m2].p;

}

/*创建哈夫曼树*/
void CreateHaffmanTree(HuffmanTree&HT,int n)
{
inti;
intm;
intmin1,min2;
if(n<=1)
cout<<"ParameterError!";
m=2*n-1;//哈夫曼树中结点的个数

InitHuffmanTree(HT,m);

for(i=0;i<n;i++)
{
cin>>HT[i].weight;
}

for(i=n;i<m;i++)
{
SelectMin(HT,i,min1,min2);
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].lchild=min1;
HT[i].rchild=min2;
HT[i].weight=HT[min1].weight+HT[min2].weight;

cout<<min1<<""<<min2<<endl;
}
}

//***********************************
//构造哈夫曼编码
//***********************************

/*哈夫曼编码的定义*/
typedef struct
{
charch;
charbits[10];
}CodeNode;

typedef CodeNode * HuffmanCode;

/*哈夫曼编码的构造*/
void CreateHuffmanCode(HuffmanTree&HT,HuffmanCode &HC,int n)
{
inti;
intstart;
intc;
intp;
char*cd;
charq;
HC=newCodeNode[n];
cd=newchar[n];
cd[n-1]='/0';

for(i=0;i<n;i++)
{
cin>>q;
HC[i].ch=q;
start=n-1;

c=i;
while((p=HT[c].parent)>=0)
{
--start;
cd[start]=(HT[p].lchild==c)?'0':'1';
c=p;
}
strcpy(HC[i].bits,&cd[start]);
}

deletecd;
}

/*哈夫曼编码的输出*/
void OutputHuffmanCode(HuffmanCode&HC,int n)
{
inti;
for(i=0;i<n;i++)
{
cout<<HC[i].ch<<""<<HC[i].bits<<endl;
}
}

void main()
{
inti;
cout<<"输入字符个数:";
cin>>i;
HuffmanTreeHT;
HuffmanCodeHC;

CreateHaffmanTree(HT,i);
CreateHuffmanCode(HT,HC,i);
OutputHuffmanCode(HC,i);
}

唉,这个程序,用了我两天的时间,主要在一个地方,就是SelectMin()函数,其他的都简单,就是这里是一个瓶颈,突破它,就出来了。我参考了很多人写的这个函数,但是我测试了几组数据,都不符合,虽然是一个很简单的事情,可是用程序写出来,就不那么容易了。我自己写的我觉得比较繁杂,不是很简练,也许是算法不好,希望有谁有好的算法的,请指点一下!


PS:另外推荐一个让大家真正练手的网站:猪八戒威客网,在这里可以按自己的能力去接一些程序设计的任务。我觉得这是一种很不错的学习方法,当你接了别人的任务,无形中就给了自己压力和动力,然后就会主动的去查询资料,分析问题,可能会历经艰辛才能解决问题,但这中间的过程是很珍贵的,你会通过自己的努力学到很多课本上没有学到的东西,也能过一回需求分析的瘾,真实的体会到和客户进行交流的诸多“纠结”,最后,如果你的努力得到客户的认可,可以获得一笔小小的佣金,当做对自己的奖励,更重要的是,通过做任务,你能体会到自己存在的价值感和对自己能力的肯定!


智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告