赫夫曼樹列印(TC2.0)

/*<<<---------------------------------------------------------------------------------------------->>>*/

/*<<<

**<<< 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;

}