构建哈夫曼树及输出哈夫曼代码及算法思想

哈夫曼树描述文档

一、 思路

通过一个argv[]数组存储从test文件中读取字母，然后利用ascal码循环计算每个字母的权值，利用weight[]是否为零，确定叶子节点，节点个数为count，传入到构建哈夫曼树的子程序中，然后利用cd[]数组存储每一个叶子节点的哈夫曼代码.输出代码时，通过与argv[]数组的比对，扫描ht数组，进而读出所有的数据。

二、 截图

三、 代码

#include

#include

#include

typedef struct

{

char data;

int weight;

int parent;

int lchild;

int rchild;

}HTNode;

typedef struct

{

char cd[50];

int start;

}HCode;

using namespace std;

int enter(char argv[])//进行读入操作

{

fstream in;

ofstream out;

char c;

int number=0;//字母个数置为0

in.open(\"test.txt\ //打开文件test.txt

out.open (\"code.txt\打开文件code.txt，如果不存在就新建一个，如果存在就清空

if(!in.eof()) in>>c; //从test.txt中读取一个字符存入c

printf(\"原文本是:\\n\");

while(! in.eof()){ //文件不为空，循环读取一个字符

cout<argv[number]=c;//存储c的值到数组

number++;

out<in>>c; //从test.txt中读取一个字符存入c

}

argv[number]='\\0';

printf(\"\\n\");

in.close; out.close; //使用完关闭文件

return(number);//返回叶子节点数目

}

void CreateHT(HTNode ht[],int n)

{

int i,j,k,lnode,rnode;

double min1,min2;

for(i=0;i<2*n-1;i++)

ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//置初值

for(i=n;i<2*n-1;i++)

{

min1=min2=32167;

lnode=rnode=-1;

for(k=0;k<=i-1;k++)

if(ht[k].parent==-1)

{

if(ht[k].weight{

min2=min1;

rnode=lnode;

min1=ht[k].weight;

lnode=k;

}

else if(ht[k].weight{

min2=ht[k].weight;rnode=k;

}

}

ht[i].weight=ht[lnode].weight+ht[rnode].weight;

ht[i].lchild=lnode;ht[i].rchild=rnode;//双亲

ht[lnode].parent=i;ht[rnode].parent=i;

}

}

void CreateHcode(HTNode ht[],HCode hcd[],int n)

{

int i,f,c;

HCode hc;

for(i=0;i{

hc.start=n;c=i;

f=ht[i].parent;

while(f!=-1)

{

if(ht[f].lchild==c)

hc.cd[hc.start--]='0';

else

hc.cd[hc.start--]='1';

c=f;f=ht[f].parent;

}

hc.start++;

hcd[i]=hc;

}

}

int main()

{

int enter(char argv[]);

void CreateHT(HTNode ht[],int n);//创建哈夫曼树

void CreateHcode(HTNode ht[],HCode hcd[],int n);//哈夫曼编码

char argv[500];

int n,i,j,k;

char zimu='A';

n=enter(argv);

HTNode ht[100];//创建结点

HCode hcd[200];

int weicount[58];//频度计数

int count;

for(i=0;i<58;i++)//对58个字母求频度

{

count=0;

for(j=0;j{

if(zimu==argv[j])

count++;

}

zimu++;//跳到第二个字母

weicount[i]=count;

}

zimu='A';

for(i=0;i<58;i++)

{

printf(\"The %c 's weight is: %d\\n\

zimu++;

}

zimu='A';

count=0;//计算叶子个数

for(i=0;i<56;i++)

{

if(weicount[i]!=0)

{

ht[count].data=zimu;

ht[count].weight=weicount[i];

count++;

}

zimu++;

}

CreateHT(ht,count);

CreateHcode(ht,hcd,count);

printf(\"\\n\");

printf(\"哈夫曼编码是：\\n\");

for(i=0;ifor(j=0;j{

if(argv[i]==ht[j].data)

{

printf(\"%c :\j].data);

for (k=hcd[j].start;k<=count;k++)

printf(\"%c\j].cd[k]);

printf(\"\\n\");

}

}

i=getchar();

return 0;

}