initialition.cpp

用C++编写的哈弗曼树的源代码,方便C语言及C++初学者学习交流

#include"head.h"
void Initialition(Huffmantree &HT,int *m)
{
	int n=0,i=0,c=0,f=0;
	char g;
	int h=0,s1,s2,start=0;
	char *cd;
	Node *p0,*p1,*p2,*p3;
	*m=0;
	FILE *hfmTree,*pindu;
	hfmTree=fopen("hfmTree","wb+");
	pindu=fopen("pindu.txt","r");
	fscanf(pindu,"%d",&n);
	p0=(Node *)malloc(sizeof(Node));
	p0->next=NULL;
	p2=p0;
	p3=p0;
	for(i=0;i<=n-1;i++)
	{//将文件pindu.txt中的字符和权重读入内存
		fscanf(pindu,"%c%d",&g,&h);
		p1=(Node *)malloc(sizeof(Node));
		p1->a=g;
		p1->weight=h;
		p2->next=p1;
		p2=p1;
		p1->next=NULL;
	}
	*m=2*n-1;//总结点个数
	HT=(Huffmantree)malloc((*m+1)*sizeof(HTNode));//0号单元不用
	p0=p0->next;
	p3=p3->next;
	for(i=1;i<=n;i++)
	{
		HT[i].c=p0->a;
		HT[i].weight=p0->weight;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
		p0=p0->next;
	}
	for(;i<=*m;i++)
	{//赋初值为0
		HT[i].weight=0;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for(i=n+1;i<=*m;i++)
	{//建赫夫曼树，选择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;
	}
//从叶子到根逆向求每个字符的赫夫曼编码
	cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
	cd[n-1]='\0';//编码结束符
	printf("哈夫曼编码             字符    权重\n");
	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';
			else
				cd[--start]='1';
		}
		strcpy(HT[i].a,&cd[start]);
		strcpy(p3->c,&cd[start]);//从cd复制编码到存储编码文件
		fwrite(p3,sizeof(Node),1,hfmTree);//将编码读入文件
		printf("%20s    %1c   %5d\n",p3->c,p3->a,p3->weight);
		p3=p3->next;
		}
	fclose(hfmTree);
	fclose(pindu);
	return;
	}