数据结构的问题,求一个构造哈夫曼树的算法

Question

如题, 请高手帮个忙

Answer 1

void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
/*建立叶结点个数为n，权值数组为weight[]的哈夫曼树*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼树hafftree[]初始化，n个叶结点共有2n-1个结点*/
for(i=0;i<2*n-1;i++)
{if(i<n) {hafftree[i].data=data[i];
hafftree[i].weight=weight[i]; /*叶结点*/
}
else {hafftree[i].weight=0; /*非叶结点*/
hafftree[i].data='\0';
}
hafftree[i].parent=0; /*初始化没有双亲结点*/
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++) /*构造哈夫曼树n-1个非叶结点*/
{m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{if(hafftree[j].weight<m1&&hafftree[j].flag==0)
{m2=m1;
x2=x1;
m1=hafftree[j].weight;
x1=j;
}
else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
{m2=hafftree[j].weight;
x2=j;
}
}
hafftree[x1].parent=n+i;
hafftree[x2].parent=n+i;
hafftree[x1].flag=1;
hafftree[x2].flag=1;
hafftree[n+i].weight=hafftree[x1].weight+hafftree[x2].weight;
hafftree[n+i].leftchild=x1;
hafftree[n+i].rightchild=x2;

}
}
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[])
{/*由n个结点的哈夫曼树hafftree[]构成的哈夫曼编码haffcode[]*/
int i,j,child,parent;
struct haffcode newcode;
struct haffcode *cd;
cd=&newcode;
for(i=0;i<n;i++) /*求n个结点的哈夫曼编码*/
{cd->start=MAXBIT-1; /*不等长编码的最后一位是n-1*/
cd->weight=hafftree[i].weight;
cd->data=hafftree[i].data; /*取得编码对应值的字符*/
child=i;
parent=hafftree[child].parent;
while(parent!=0)
{if(hafftree[parent].leftchild==child)
cd->bit[cd->start]=0; /*左孩子编码为0*/
else
cd->bit[cd->start]=1; /*右孩子编码为1*/
cd->start--;
child=parent;
parent=hafftree[child].parent;
}
for(j=cd->start+1;j<MAXBIT;j++) /*保存每个叶结点的编码和等长编码的起始位*/
haffcode[i].bit[j]=cd->bit[j];
haffcode[i].data=cd->data;
haffcode[i].start=cd->start;
haffcode[i].weight=cd->weight;
}
}

Answer 2

//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案
//by jirgal 2005.4.18
#include<iostream.h>
#include<iomanip.h>
#define NUM 26 //字母数
#define TNUM 51 //
#define LTH 15 //编码最大长度

class Node
{
public:
char data;
int weight;
int parent;
int lchild;
int rchild;
};

void main()
{
char ch[NUM]={'a','b','c','d','e','f','g','h','i','j','k','l',
'm','n','o','p','q','r','s','t','u','v','w','x','y','z'};//26个字母

int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42,
339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率

Node nodes[TNUM]; //用对象数组存储哈夫曼树

int i,j,one,two,a,b;
int hc[NUM][LTH]; //用于存储编码
int m,n;

//初始化数组
for(i=0;i<NUM;i++)
{
nodes[i].data=ch[i];
nodes[i].weight=weit[i];
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}
for(i=NUM;i<TNUM;i++)
{
nodes[i].data='@';
nodes[i].weight=-1;
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}

//建立哈夫曼树
for(i=NUM;i<TNUM;i++)
{
a=b=-1;
one=two=10000; //最大权数
for(j=0;j<i;j++)
{
if(nodes[j].parent==-1)
{
if(nodes[j].weight<=two)
{
one=two;
two=nodes[j].weight;
a=b;
b=j;
}
else if(nodes[j].weight>two&&nodes[j].weight<=one)
{
one=nodes[j].weight;
a=j;
}
}
}//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点
nodes[a].parent=i;
nodes[b].parent=i;
nodes[i].lchild=a;
nodes[i].rchild=b;
nodes[i].weight=nodes[a].weight+nodes[b].weight;
}

//初始化hc
for(i=0;i<LTH;i++)
{
for(j=0;j<NUM;j++)
{
hc[j][i]=7;
}
}

//编码
for(i=0;i<NUM;i++)
{
j=LTH-1;
for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent)
{
if(nodes[n].lchild==m)
{
hc[i][j]=0;
}
else
{
hc[i][j]=1;
}
j--;
}

}

//输出 nodes
cout<<"HuffmanTree:"<<endl;
cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6)
<<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl;
for(i=0;i<TNUM;i++)
{
cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6)
<<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl;
}

//输出编码
cout<<endl<<"Result:"<<endl;
cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n";
for(i=0;i<NUM;i++)
{
cout<<setw(6)<<ch[i]<<setw(8)<<weit[i];
cout<<" ";
for(j=0;j<LTH;j++)
{
if(hc[i][j]!=7)
{
cout<<hc[i][j];
}
}
cout<<endl;
}
cout<<"\nDone.\n"<<endl;
}

Answer 3

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>a
#include<graphics.h>
#define MAXVALUE 200 /*权值的最大值*/
#define MAXBIT 30 /*最大的编码位数*/
#define MAXNODE 30 /*初始的最大的结点数*/
struct haffnode
{char data;
int weight;
int flag;
int parent; /*双亲结点的下标*/
int leftchild; /*左孩子下标*/
int rightchild; /*右孩子下标*/
};
struct haffcode
{int bit[MAXNODE];
int start; /*编码的起始下标*/
char data;
int weight; /*字符权值*/
};

/*函数说明*/

void pprintf(struct haffcode haffcode[],int n);
/*输出函数*/
void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[]);
/*建立哈夫曼树*/
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[]);
/*求哈夫曼编码*/
void test(struct haffcode haffcode[],int n);
/*测试函数*/
void end();
/*结束界面函数*/