#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 10000
#define MAX 60
typedef int Status;
typedef char **HuffmanCode;
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef struct{
HuffmanTree HT;
char *c;
int longth;
HuffmanCode HC;
}Huffman;
void Select(HuffmanTree HT,int end,int *s1,int *s2)
{
int i;
int min1=MAX_NUM;
int min2;
for (i=1;i<=end;i++)
{
if (HT[i].parent==0 && HT[i].weight<min1)
{
*s1=i;
min1=HT[i].weight;
}
}
min2=MAX_NUM;
for(i=1;i<=end;i++)
{
if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight)
{
*s2=i;
min2=HT[i].weight;
}
}
}
Huffman HuffmanCoding(Huffman Hfm)
{
/*---------------------------------*/
int i,n,m,s1,s2,start;
int c,f;
char *cd;
n=Hfm.longth;
if(n<=1) return Hfm;
m=2*n-1;
for(i=n+1;i<=m;++i)
{
Select(Hfm.HT,i-1,&s1,&s2);
Hfm.HT[s1].parent=i;
Hfm.HT[s2].parent=i;
Hfm.HT[i].lchild=s1;
Hfm.HT[i].rchild=s2;
Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
}
/*------------------------------------------*/
Hfm.HC=(HuffmanCode)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=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
{
if(c==Hfm.HT[f].lchild) cd[--start]='0';
else cd[--start]='1';
}
Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(Hfm.HC[i],&cd[start]);
}
free(cd);
return Hfm;
}
Huffman InputHuffman(Huffman Hfm)
{
int i,n;
system("cls");
printf("\n\n\t\t********************Initial*********************\n");
printf("\tThe chars and weights will be saved in the file \"hfmTree\"\n");
printf("Please input the number of the chars: ");
scanf("%d",&n);
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
Hfm.c=(char *)malloc((n+1)*sizeof(char));
for(i=1;i<=n;i++)
{
printf("Please input the char: ");
scanf("%s",&Hfm.c[i]);
printf("Please input the weight of the char: ");
scanf("%d",&Hfm.HT[i].weight);
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.longth=n;
return Hfm;
}
Huffman InitHuffman(Huffman Hfm)
{
int n,i;
FILE *fp;
fp=fopen("hfmTree","rt");
if(fp==NULL)
{
Hfm=InputHuffman(Hfm);
fp=fopen("hfmTree","wt");
fprintf(fp,"%d\n",Hfm.longth);
for(i=1;i<=Hfm.longth;i++)
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
}
else
{
fscanf(fp,"%d\n",&n);
Hfm.c=(char *)malloc((n+1)*sizeof(char));
Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
for(i=1;i<=n;i++)
fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight);
for(i=1;i<=n;i++)
{
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
for(;i<=2*n-1;++i)
{
Hfm.HT[i].weight=0;
Hfm.HT[i].parent=0;
Hfm.HT[i].lchild=0;
Hfm.HT[i].rchild=0;
}
Hfm.longth=n;
}
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}
void Output(Huffman Hfm)
{
int i,n;
n=Hfm.longth;
printf("\n\n******************Output the code of the chars****************\n\n");
for(i=1;i<=n;i++)
{
printf("\n");
printf("Char: %c\t",Hfm.c[i]);
printf("Weight: %d\t",Hfm.HT[i].weight);
printf("Code: ");
puts(Hfm.HC[i]);
}
}
void Encoding(Huffman Hfm)
{
int i=0,j=0,n;
char ch[MAX];
FILE *fp,*ffp;
n=Hfm.longth;
printf("\n\n*******************Encoding**************************\n\n");
if((ffp=fopen("ToBeTran","rt"))==NULL)
{
printf("\nPlease input the sentence: ");
scanf("%s",&ch);
printf("\n");
fp=fopen("CodeFile","wt+");
}
else
{
fscanf(ffp,"%s",ch);
fclose(ffp);
}
while(ch[j])
{
for(i=1;i<=n;i++)
if(ch[j]==Hfm.c[i])
{
printf("%s",Hfm.HC[i]);
fprintf(fp,"%s",Hfm.HC[i]);
break;
}
j++;
}
rewind(fp);
fclose(fp);
}
void Decoding(Huffman Hfm)
{
HuffmanTree p;
int i,n;
int j=0;
char d[50];
FILE *fp;
n=Hfm.longth;
printf("\n\n******************Decoding************************\n\n");
if((fp=fopen("CodeFile","rt"))==NULL)
{
printf("Please input the code:");
scanf("%s",&d);
}
else
{
fscanf(fp,"%s",d);
fclose(fp);
}
printf("\nThe file is : ");
fp=fopen("TextFile","wt+");
while(d[j])
{
p=&Hfm.HT[2*n-1];
while(p->lchild||p->rchild)
{
if(d[j]=='0')
{ i=p->lchild; p=&Hfm.HT[i]; }
else
{ i=p->rchild; p=&Hfm.HT[i]; }
j++;
}
printf("%c",Hfm.c[i]);
fprintf(fp,"%c",Hfm.c[i]);
}
fclose(fp);
}
Huffman RebuildHuffman(Huffman Hfm)
{
int n,i;
FILE *fp;
fp=fopen("hfmTree","wt");
Hfm=InputHuffman(Hfm);
fprintf(fp,"%d\n",Hfm.longth);
for(i=1;i<=Hfm.longth;i++)
fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
rewind(fp);
fclose(fp);
Hfm=HuffmanCoding(Hfm);
return Hfm;
}
int main()
{
Huffman Hfm;
char choice='a';
Hfm=InitHuffman(Hfm);
while(choice!='q')
{
system("cls");
printf("\n\n\n\t\t*************************************\n\n");
printf("\t\t\ta. Encoding:\n\n");
printf("\t\t\tb. Decoding:\n\n");
printf("\t\t\tc. Print all codes:\n\n");
printf("\t\t\td. Rebuild the huffmantree:\n\n");
printf("\t\t\tq. Quit...\n\n");
printf("\n\t\t************************************\n\n");
printf("Please enter your choice: ");
scanf("%c",&choice);
switch(choice)
{
case 'a':
system("cls");
Encoding(Hfm);
printf("\n\n*******Please enter anykey to continue*******\n");
getch();
break;
case 'b':
system("cls");
Decoding(Hfm);
printf("\n\n*******Please enter anykey to continue********\n");
getch(); break;
case 'c':
system("cls");
Output(Hfm);
printf("\n\n*******Please enter anykey to continue********\n");
getch(); break;
case 'd':
system("cls");
Hfm=RebuildHuffman(Hfm);
printf("\n\n********************Initial*********************\n");
getch(); break;
case 'q':
break;
default:
printf(" Your choice is wrong!\n Please enter anykey to choice again!\n");
getch(); break;
}
}
return 0;
}
hefuman.rar （27个子文件） 
hefuman 
11.plg 736B 11.cpp 8KB hefuman.ncb 33KB hfmTree 0B TextFile 53B hefuman.dsw 522B Debug 11.ilk 234KB vc60.pdb 108KB
11.exe 208KB vc60.idb 73KB hefuman.ilk 230KB hfmTree 18B hefuman.pdb 449KB hefuman.pch 225KB 11.obj 21KB 11.pch 225KB hefuman.exe 208KB 11.pdb 1.13MB CodeFile 0B 11.dsw 512B 11.opt 48KB 11.dsp 3KB hefuman.opt 48KB 11.ncb 41KB CodeFile 0B hefuman.dsp 4KB hefuman.plg 692B
评论0
最新资源