hfm.zip_霍夫曼树_霍夫曼编码

#include"stdio.h" #include"malloc.h" #include"string.h" #define char_num 27 typedef struct{ char ch ; int w;} DFileNode ;// 定义数据文件的元素类型 void creatDataFile( )//创建数据文件 { FILE *f; char c; DFileNode s; int i,a[27]; //数组a用来存放从a--z每个字符出现的次数;0号单元不用 for(i=1;i<=26;i++) a[i]=0; printf("创建数据文件DataFile.dat\n"); printf("请输入一段仅包含小写字母a--z的一段文字以#结束\n"); c=getchar(); while(c!='#') { a[c-96]++; //使字符c出现的次数+1; c=getchar(); } f=fopen("DataFile.dat","wb");//写文件 for(i=1;i<=26;i++) { s.ch=i+96; s.w=a[i]; fwrite(&s,1,sizeof(DFileNode),f); } fclose(f); f=fopen("DataFile.dat","rb"); printf("字符及每个字符出现的次数(字符，出现次数)\n"); while(fread(&s,1,sizeof(DFileNode),f)) { printf("(%c ,%d) , ",s.ch,s.w); } fclose(f); } void creatToBeTran( )//创建原文文件 { FILE *f; char s; printf("创建原文文件:请输入一段仅包含小写字母a--z的一段文字作为原文以#结束\n"); f=fopen("ToBeTran.dat","w"); s= getchar(); while(s!='#') { fwrite(&s,1,sizeof(char),f); s=getchar(); } fclose(f); } void creatCodeFile( )//创建报文文件 { FILE *f; int s; printf("创建报文文件:请输入一段仅包含0和1的一段文字作为原文以2作为结束标志.\n"); f=fopen("CodeFile.dat","wb"); printf("输入报文0或1(输入的数字间用空格隔开)\n"); scanf("%d",&s); while(s<2) { fwrite(&s,1,sizeof(int),f); scanf("%d",&s); } fclose(f); f=fopen("CodeFile.dat","r"); while(fread(&s,1,sizeof(int),f)) { printf("%d ",s); } fclose(f); } typedef struct //赫夫曼树和赫夫曼编码的存储表示 { char ch; int weight; int parent,lchild,rchild; char *next; // 指向该字符的编码 }HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树 HuffmanTree HT; int min(HuffmanTree t,int i) { // 函数void select()调用 int j,flag; int k=10000; // 字符出现的总次数据不超过10000次 for(j=1;j<=i;j++) if(t[j].parent==0&&t[j].weight<k) k=t[j].weight,flag=j; t[flag].parent=1; return flag; } void select(HuffmanTree t,int i,int &s1,int &s2) { // s1为最小的两个值中序号小的那个 int j; s1=min(t,i); s2=min(t,i); if(s1>s2) { j=s1; s1=s2; s2=j; } } void print_huff_tree(HuffmanTree HT ,int n)//输出哈夫曼树，在必要时调用以验证算法的正确性 { HuffmanTree p; int i; printf("字符 权值 双亲 左孩子 右孩子 指向编码的指针\n"); for(p=HT+1,i=1;i<=n;++i,++p) printf("%-7c%-8d%-10d%-10d%-10d->%s\n",p->ch,p->weight,p->parent,p->lchild,p->rchild,p->next); } void creatHuffmanTree( HuffmanTree &HT, int n) {//创建含n个叶子结点的哈夫曼树,字符及权值在文件DataFile.dat中,即初始化Initialzation FILE *f1; int m,i,s1,s2; HuffmanTree p; DFileNode s; //从文件中读数据时用； m=2*n-1; f1=fopen("DataFile.dat","rb"); HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用 for(p=HT+1,i=1;i<=n;++i,++p) { fread(&s,1,sizeof(DFileNode),f1); //从文件中读一个数给s,构造叶子 (*p).ch=s.ch; (*p).weight=s.w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; (*p).next=NULL; } fclose(f1); printf("\n"); for(;i<=m;++i,++p) { (*p).ch=' ';(*p).parent=0;(*p).lchild=0;(*p).rchild=0;(*p).next=NULL;} for(i=n+1;i<=m;++i)//建n-1个分支结点 { // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2); HT[s1].parent=HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } } void HuffmanCoding(HuffmanTree &HT,int n) //对有n个叶子结点的哈夫曼树上的叶子结点进行编码 { char *cd; int i,start,c,f; 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'; HT[i].next=(char*)malloc((n-start)*sizeof(char)); // 为第i个字符编码分配空间 strcpy(HT[i].next,&cd[start]); // 从cd复制编码(串)到HC } free(cd); // 释放工作空间 } void EnCoding()//编码:对文件ToBeTran.dat中的文本进行编码，放在文件Code.txt中 { FILE *f1, *f2; char s; int i; f2=fopen("Code.txt","w");//打开文件Code.txt为了写 f1=fopen("ToBeTran.dat","r");//打开文件ToBeTran.dat为了读 fgetc(f1); while(fread(&s,1,sizeof(char),f1)) { i=1; while(HT[i].ch!=s) i++; fputs(HT[i].next,f2); } fclose(f1); fclose(f2); } void Decoding( )//译码:对文件CodeFile.dat中的报文进行译码，放在文件Textfile.txt中 { FILE *f1, *f2; char c; int s,p; f1=fopen("CodeFile.dat","rb"); f2=fopen("Textfile.txt","w"); p=2*char_num-1; //P指向哈夫曼树的根 while(fread(&s,1,sizeof(int),f1)) { // printf("%d",s); if(s==0) p=HT[p].lchild; else p=HT[p].rchild; if(HT[p].lchild==0) { c=HT[p].ch; fputc(c,f2); p=2*char_num-1; //让P重新指向哈夫曼树的根 } } fclose(f1); fclose(f2); } void output_1( )//输出原文和对应的译文； { FILE *f1, *f2; char c; int s; f1=fopen("ToBeTran.dat","r");//打开文件ToBeTran.dat为了读 printf("原文："); while(fread(&c,1,sizeof(char),f1)) printf("%c",c); fclose(f1); f2=fopen("Code.txt","r"); printf("\n译文："); while(fread(&c,1,sizeof(char),f2)) putchar(c); printf("\n"); fclose(f2); } void output_2( )//输出报文和对应的原文； { FILE *f1, *f2; char c; int s; f1=fopen("CodeFile.dat","rb"); printf("报文:"); while(fread(&s,1,sizeof(int),f1)) printf("%d",s); printf("\n"); fclose(f1); f2=fopen("Textfile.txt","r"); printf("原文:"); while(fread(&c,1,sizeof(char),f2)) putchar(c); printf("\n"); fclose(f2); } void main() { int i,j; creatDataFile( );//创建数据文件 creatHuffmanTree(HT, char_num);//建哈夫曼树即初始化Initialzation printf("初始的哈夫曼树:\n"); print_huff_tree( HT, 2*char_num-1);//验证所建初始的哈夫曼树 HuffmanCoding(HT, char_num);//编码 printf("编码后的哈夫曼树:\n"); print_huff_tree( HT, 2*char_num-1);//验证编码后的哈夫曼树及编码 for(i=1;i<=8;i++) { printf("字符%c的编码为:%-10s " ,HT[i].ch,HT[i].next); if(i%3==0) printf("\n"); } printf("\n"); creatToBeTran( );//创建原文文件 EnCoding();//编码 output_1( );//输出 creatCodeFile( );//创建报文文件 printf("\n"); Decoding();//译码 output_2( );//输出 }