#include <stdio.h>#include <conio.h>#include <string.h>#include <malloc.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; clrscr(); printf("/n/n********************Initial*********************/n"); printf("The 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') { clrscr(); printf("/n/n/n*************************************/n/n"); printf("a. Encoding:/n/n"); printf("b. Decoding:/n/n"); printf("c. Print all codes:/n/n"); printf("d. Rebuild the huffmantree:/n/n"); printf("q. Quit.../n/n"); printf("/n************************************/n/n"); printf("Please enter your choice: "); scanf("%s",&choice); switch(choice) { case 'a': clrscr(); Encoding(Hfm); printf("/n/n*******Please enter anykey to continue*******/n"); getch(); break; case 'b': clrscr(); Decoding(Hfm); printf("/n/n*******Please enter anykey to continue********/n"); getch(); break; case 'c': clrscr(); Output(Hfm); printf("/n/n*******Please enter anykey to continue********/n"); getch(); break; case 'd': clrscr(); 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;}
使用方法：
1． 选择a，输入句子，例如THIS-PROGRAM-IS-MY-FAVORITE，空格用“-”代替。
2． 选择b，程序将从CodeFile文件中读取代码，译为字符输出并保存到TextFile文件。
3． 选择c，输出赫夫曼树的所有字符，权值和赫夫曼代码。
4． 选择d，重建赫夫曼树。
5． 选择q，退出系统。
由于是在TC下弄的，所以没有注释，凑合着看吧，呵呵
