爱华网
The function of this program is to encode English text(Othercharacters are ignored) using Huffmancoding.Because of the limitation of my ability,these isnoguaranteeto be perfect.Do nothesitate tomessage if you have any suggestions.Any feedback isappreciated.The program reads the in.txt (this file must be in the samedirectory with the program) and give a Huffman coding for everycharacters in code.txt.Note that,Huffman coding is not alwaysunique.Fallowing are codes in node.h defining the node of the Huffmantree:#ifndef _NODE_H#define _NODE_Hstruct node{char ch;long cnt;struct node *left;struct node *right;};#endifFallowing are codes of the main program:#include#include#include "node.h"int main(){void coding(struct node *root,char prefix[],FILE *fp);void test(struct node *root);struct node nodes[52];int i,j;char ch;//Initializationfor(i=0;i<52;i++){if(i<26){nodes[i].ch=i+97;}else{nodes[i].ch=i+39;}nodes[i].left=NULL;nodes[i].right=NULL;nodes[i].cnt=0;}FILE *infp;//open in.txtif((infp=fopen("in.txt","r"))==NULL){printf("cannot open filen");return 0;}//count the number of occurence of each characterwhile((ch=fgetc(infp))!=EOF){if(ch>='a'&&ch<='z'){nodes[ch-97].cnt+=1;}if(ch>='A'&&ch<='Z'){nodes[ch-39].cnt+=1;}}fclose(infp);//Ascending sort using Bubble sortfor(i=51;i>0;i--)for(j=0;j{if(nodes[j].cnt>nodes[j+1].cnt){long tempcnt=nodes[j].cnt;char tempch=nodes[j].ch;nodes[j].cnt=nodes[j+1].cnt;nodes[j].ch=nodes[j+1].ch;nodes[j+1].cnt=tempcnt;nodes[j+1].ch=tempch;}}//Construct Huffman treefor(i=0;i<51;i++){struct node *p1,*p2,*p3;p1=(struct node *)malloc(sizeof(struct node));p2=(struct node *)malloc(sizeof(struct node));p3=(struct node *)malloc(sizeof(struct node));if(nodes[i].left==NULL)p1->ch=nodes[i].ch;p1->cnt=nodes[i].cnt;p1->left=nodes[i].left;p1->right=nodes[i].right;if(nodes[i+1].left==NULL)p2->ch=nodes[i+1].ch;p2->cnt=nodes[i+1].cnt;p2->left=nodes[i+1].left;p2->right=nodes[i+1].right;p3->cnt=p1->cnt+p2->cnt;p3->left=p1;p3->right=p2;for(j=i+2;j<=52;j++){if(j==52){nodes[51].cnt=p3->cnt;nodes[51].left=p3->left;nodes[51].right=p3->right;break;}if(nodes[j].cntcnt){nodes[j-1].ch=nodes[j].ch;nodes[j-1].cnt=nodes[j].cnt;nodes[j-1].left=nodes[j].left;nodes[j-1].right=nodes[j].right;}else{nodes[j-1].cnt=p3->cnt;nodes[j-1].left=p3->left;nodes[j-1].right=p3->right;break;}}}FILE *codefp;//store results in code.txtif((codefp=fopen("code.txt","w"))==NULL){printf("cannot open code.txtn");return 0;}coding(&nodes[51],"",codefp);fclose(codefp);return 0;}
void coding(struct node *root,char prefix[],FILE *fp){char temp[52]="";char temp2[52]="";if(root->left==NULL){fprintf(fp,"%ct%sn",root->ch,prefix);}else{sprintf(temp,"%s%s",prefix,"0");coding(root->left,temp,fp);sprintf(temp2,"%s%s",prefix,"1");coding(root->right,temp2,fp);}}
Source code file is availablehere
