Unsigned int weight; unsigned int parent,lchild,rchild




Yüklə 22.4 Kb.
tarix27.02.2016
ölçüsü22.4 Kb.
#include

#include


typedef struct Huffman

{

char ch;



unsigned int weight;

unsigned int parent,lchild,rchild;

}HuffmanTree;
typedef struct

{

unsigned int data;



int No;

}SortArray;


HuffmanTree* Initialization(int n);

char** HuffmanCoding(HuffmanTree *HT, int n);

int* SeleteWeight(HuffmanTree* HT, int n);

void HuffmanDecoding(HuffmanTree *HT,char** HC, int n);

void PrintCode(void);

void Menu(void);

void Process(void);
void main()

{

Process();



}

//Functions

void Process(void)

{

int op;



int num;

HuffmanTree* tree;

char ch;

char** hc;

Menu();

scanf("%d",&op);



while(op!=6)

{

switch(op)



{

case 1:printf("Please input the number of character:");

scanf("%d",&num);

ch=getchar();

putchar(ch);

tree=Initialization(num);

break;

case 2:hc=HuffmanCoding(tree, num);break;



case 3:HuffmanDecoding(tree, hc, num);break;

case 4:PrintCode();break;

//case 5:

default:printf("ERROR!\n");

break;

}

Menu();



}

}

void Menu(void)



{

printf("=======================MENU=========================\n");

printf("\t\t1.Initialization Huffman Tree.\n");

printf("\t\t2.Cording the Huffman Tree.\n");

printf("\t\t3.Decording the Huffman Tree.\n");

printf("\t\t4.Output the codefile.dat.\n");

printf("\t\t5.Output the Huffman Tree.\n");

printf("\t\t6.Exit.\n");

printf("====================================================\n");

printf("Your option:");

}

HuffmanTree* Initialization(int n)



//n为字符个数

{

HuffmanTree *HT;



FILE* F_hfm;

int i;


int m;

char ch;


char latter;

unsigned int w;


m=2*n-1;

HT=(HuffmanTree *)malloc((m+1)*sizeof(HuffmanTree));

for (i=1;i<=n;i++)

{

printf("Please input the LATTER:");



//HT[i].ch=getchar();

scanf("%c",&HT[i].ch);

ch=getchar();

putchar(ch);

}
for (i=1;i<=n;i++)

//输入n个权值


{

printf("Please input the WEIGHT:");

scanf("%d",&w);

HT[i].weight=w;

HT[i].parent=HT[i].lchild=HT[i].rchild=0;

}

for (;i<=m;i++)



HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;
F_hfm=fopen("hfmtree.dat","wb");

for (i=1;i<=m;i++)

//输出到文件

fwrite(&HT[i],sizeof(HuffmanTree),1,F_hfm);



fclose(F_hfm);

return HT;

}
char** HuffmanCoding(HuffmanTree *HT, int n)

//Huffman编码

{

FILE* F_code;



FILE* ftemp;

int i,j;


int m;

unsigned int min1,min2;

int *seleted;

char **HC;

char *cd;

int start,c,f;


if (HT==NULL)

{

ftemp=fopen("hfmtree.dat","rb");



for (j=1;j<=m;j++)

fread(&HT[j],sizeof(HuffmanTree),1,ftemp);

}

fclose(ftemp);


m=2*n-1;

seleted=(int *)malloc(2*sizeof(int));


for (i=n+1;i<=m;i++)

//编码


{

seleted=SeleteWeight(HT, i-1);

min1=seleted[0]; min2=seleted[1];

HT[min1].parent=i;

HT[min2].parent=i;

HT[i].lchild=min1;

HT[i].rchild=min2;

HT[i].weight=HT[min1].weight+HT[min2].weight;

}
HC=(char **)malloc((n+1)*sizeof(char *));

cd=(char *)malloc(n*sizeof(char));

cd[n-1]='\0';
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';

HC[i]=(char *)malloc((n-start)*sizeof(char));

strcpy(HC[i],&cd[start]);

}

free(cd);


F_code=fopen("codefile.dat","wb");

for (j=1;j<=n;j++)

fwrite(HC[j],sizeof(strlen(HC[j])),1,F_code);

//将编码表里的数据一一存到文件中

fclose(F_code);

return HC;

}
int* SeleteWeight(HuffmanTree* HT, int n)

//对权值进行排序,选出其中最小两个

{

SortArray* array;



int i,j,m,k,h;

int *resu;

int temp;
array=(SortArray *)malloc((n+1)*sizeof(SortArray));

resu=(int *)malloc(2*sizeof(int));


h=1;

for (i=1;i<=n;i++)

{

if (HT[i].parent==0)



{

array[h].data=HT[i].weight;

array[h].No=i;

h++;


}

}
for (i=1;i<=h-1;i++)

//用选择排序法将权值排序

{

k=i;



//array[0].data=array[i].data;

//array[0].No=array[i].No;


for (j=i+1;j<=h-1;j++)

{

if (array[j].data<=array[k].data)



k=j;

}

if (k!=i)



{

temp=array[i].data;

array[i].data=array[k].data;

array[k].data=temp;


temp=array[i].No;

array[i].No=array[k].No;

array[k].No=temp;

}

}


resu[0]=array[1].No;

resu[1]=array[2].No;


return resu;

}
void HuffmanDecoding(HuffmanTree *HT,char** HC, int n)

{

int i;


int j,m;

int k=0;


char *ch;

FILE* ftext;


ch=(char *)malloc((n+1)*sizeof(char));

//存放译码后的字符串


for (i=1;i<=m;i++)

//查找根结点


if (HT[i].parent==0)

break;


for (j=1;j<=n;j++)

// HC中前缀码的个数

{

while (HT[i].lchild!=0 && HT[i].rchild!=0)



{

if (HC[i][k]=='0')

i=HT[i].lchild;

else


i=HT[i].rchild;

k++;


}

ch[j]=HT[i].ch;

//strcpy(&ch[j],HT[i].ch);

}

ftext=fopen("textfile.dat","wb");



for (i=1;i<=n;i++)

{

fwrite(&ch[1],sizeof(char),1,ftext);



}

fclose(ftext);

}
void PrintCode(void)

{

int m=1;



char ch;

FILE* fprint;


fprint=fopen("codefile.dat","rb");

while ( feof(fprint)==0 )

{

ch=fgetc(fprint);



printf("%c",ch);

m++;


if (m%50==0)

printf("\n");



}

fclose(fprint);



}


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azrefs.org 2016
rəhbərliyinə müraciət

    Ana səhifə