/*<<<---------------------------------------------------------------------------------------------->>>*/
/*<<<
**<<< Programme Name : Huffman Tree Print
**<<< IDE : TC2.0
**<<< Author : Cifry
**<<< Create Date : 2007.08.23
**<<< New Amend : 2007.08.25
**<<< QQ : 442044866
**<<< Email :[email protected]
**<<< Say :
**<<< 请在当前目录下建立一个名为“read.txt”的文本文件，该文件为数据读入
**<<< 文件。在“read.txt”中输入数据，格式为[节点标识][权]为一个节点(其中不
**<<< 不含空格，各节点间用空格分开(空格可任意多少) ，请在文件最后输入
**<<< “#”作为数据读取的结束标志。如:
**<<< a10 b2 c7 d3 e9 f40 j5 h123 i77 j6 k19 l22 m47 n24 o4 p11 #
**<<< 程序运行后将读取“read.txt”中数据，并将处理结果输出到创建在当前目
**<<< 录的“Print.txt”文件中。输出结果使用树型结构打印，形象易懂。
**<<<
**<<< Copyright(c)Cifry
<<<*/
/*<<<---------------------------------------------------------------------------------------------->>>*/
#include<stdio.h>
struct HufNode
{
char ID;
unsigned weight;
struct HufNode *lchild;
struct HufNode *rchild;
struct HufNode *parent;
};/*霍夫曼树节点*/
struct Volume_Bintree
{
struct HufNode *Tree;
struct Volume_Bintree *Next;
};/*二叉树集合节点(森林)*/
FILE *rfp,*wfp;
/*将文件中的数据做成二叉树集合*/
struct Volume_Bintree *ReadBintree()
{
struct Volume_Bintree *Forest =NULL;
struct Volume_Bintree *FCreater =NULL;
struct HufNode *HCreater =NULL;
Forest=(struct Volume_Bintree *)malloc(sizeof(struct Volume_Bintree));
Forest->Next=NULL;
FCreater=Forest;
while(1)
{
char ID;
while((ID=getc(rfp))==' '); /*寻找下一个二叉树数据的起始位置*/
if(ID=='#')break;/* # 为文件的结束标志*/
HCreater=(struct HufNode *)malloc(sizeof(struct HufNode));
HCreater->parent=NULL;
HCreater->lchild=NULL;
HCreater->rchild=NULL;
FCreater->Next=(struct Volume_Bintree *)malloc(sizeof(struct Volume_Bintree));
FCreater->Tree=HCreater;/*将读入的二叉树存入森林*/
HCreater->ID=ID;
fscanf(rfp,"%u",&HCreater->weight);
FCreater=FCreater->Next;
FCreater->Next=NULL;
}
FCreater=Forest; /*清除最后一个无用元素*/
while(FCreater->Next->Next!=NULL){FCreater=FCreater->Next;}
free(FCreater->Next->Next);
FCreater->Next=NULL;
return Forest;
}
/*构造霍夫曼树*/
struct HufNode *CreateHuf(struct Volume_Bintree *Forest)
{
struct Volume_Bintree *Comp =NULL;
struct Volume_Bintree *Min1 =NULL;
struct Volume_Bintree *Min2 =NULL;
struct HufNode *Tree1 =NULL;
struct HufNode *Tree2 =NULL;
while(1)
{
{/*获得二叉树集合中的最小权值的节点并在集合中清除该节点*/
Min1=Forest;/*二叉树集合的第一个二叉树给Min1*/
Comp=Forest;
while(Comp->Next!=NULL)/*查找权值最小的二叉树的前缀二叉树*/
{
if(Min1->Tree->weight > Comp->Next->Tree->weight)
Min1=Comp->Next;
Comp=Comp->Next;
}
if(Min1!=Forest)
{
Comp=Forest;
while(Comp->Next!=Min1){Comp=Comp->Next;}
}
Tree1=Min1->Tree;
if(Min1==Forest)/*第一个二叉树是二叉树集合的最小权值的二叉树*/
{
Forest=Min1->Next;
Tree1=Min1->Tree;
}
else if(Min1->Next==NULL)/*最后一个二叉树是二叉树集合的最小权值的二叉树*/
{
Comp->Next=Min1->Next;
}
else
{
Comp->Next=Min1->Next;
}
free(Min1);
}
/*继续从二叉树集合中获得最小权值的二叉树*/
{
Min2=Forest;
Comp=Forest->Next;
while(Comp!=NULL)/*查找权值最小的二叉树*/
{
if(Min2->Tree->weight > Comp->Tree->weight)
Min2=Comp;
Comp=Comp->Next;
}
Tree2=Min2->Tree;
}
Min2->Tree=(struct HufNode *)malloc(sizeof(struct HufNode));
Min2->Tree->lchild=Tree1;/*构造左子树*/
Tree1->parent=Min2->Tree;
Min2->Tree->rchild=Tree2;/*构造右子树*/
Tree2->parent=Min2->Tree;
Min2->Tree->ID='+';
Min2->Tree->weight=Tree1->weight+Tree2->weight;
if(Forest->Next==NULL) break;
}
return (struct HufNode *)Forest->Tree;
}
/*打印树*/
/*该函数稍加修改可以打印任何形式的树*/
/*flag 为节点标识 flag=0 根 flag=1左子树 flag=2 右子树*/
/*因为限于文件格式只能先打印"右"子树，所以flag的用法将是反过来的*/
char HufCod[100]={'/0'};/*用于存储霍夫曼编码*/
struct HufNode *Tree_prin(struct HufNode * HufNode,int flag)
{
int offset;
int sh=0;
{/*记录霍夫曼编码*/
offset=strlen(HufCod);
if(flag==1)
HufCod[offset]='0';
if(flag==2)
HufCod[offset]='1';
}
while(sh<offset)/*格式打印*/
{
if(HufCod[sh]=='1')
fprintf(wfp,"│ ");
if(HufCod[sh]=='0')
fprintf(wfp," ");
sh++;
}
if(flag==0) /*打印根节点*/
{
fprintf(wfp,"[%c]%-5u/n",HufNode->ID,HufNode->weight);
}
else if(flag==1)/*左叶子打印格式*/
{
fprintf(wfp,"└─[%c]%-5u",HufNode->ID,HufNode->weight);
}
else
{ /*打印右节点*/
fprintf(wfp,"├─[%c]%-5u",HufNode->ID,HufNode->weight);
}
if(flag!=0)/*节点打印霍夫曼编码*/
{
if(HufNode->ID!='+')
fprintf(wfp,"-->%s/n",HufCod);
else fprintf(wfp,"/n");
}
if(HufNode->rchild!=NULL)
Tree_prin(HufNode->lchild,2); /*先打印右节点*/
if(HufNode->lchild!=NULL)
Tree_prin(HufNode->rchild,1); /*后打印左节点*/
HufCod[offset]='/0';/*撤销该节点编码*/
}
int main()
{
struct HufNode *NonceNode =NULL;
if((rfp=fopen("read.txt","r"))==NULL)
{
printf("/n/n/t/tError:not find read.txt!!/n");
getch();exit(1);
}
if((wfp=fopen("Print.txt","w"))==NULL)
{
printf("/n/n/t/tError:not create write.txt!!/n");
getch();exit(1);
}
fprintf(wfp," Huffman Tree Print/n");
fprintf(wfp,"******************************************************/n/n");
NonceNode=CreateHuf(ReadBintree());/*构造霍夫曼树*/
Tree_prin(NonceNode,0);/*打印霍夫曼树*/
fclose(rfp);
fclose(wfp);
printf("/n/n/n/t/t/t******************************/n");
printf("/n/t/t/tFrom read.txt readin ....OK/n");
printf("/t/t/tResult to Print.txt ....OK/n");
printf("/n/t/t/t*********** finish ***********");
getch();
return 0;
}
![处理PCX文件[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)