哈夫曼编码与解码(C语言实现)
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>#define MAXNUM 60typedef struct{char ch;int weight; //权值，这个字符出现的频率int parent;int left;int right;}HuffNode;typedef struct{char code;int start;}HuffCode;HuffNode ht; //存放哈夫曼树HuffCode hcd;//存放ht数组中对应的字符的编码int n; //字符的个数//初始化哈夫曼树htvoid initHt(){FILE * fp;char ch;int i=0;//从文件document/character.txt中读出要编码的字符和权值if((fp=fopen("document/character.txt","r"))==NULL){printf("can not open the file character.txt");exit(0);}ht.left=ht.right=ht.parent=-1;while((ch=fgetc(fp))!=EOF){if(ch=='\n'){i++;ht.left=ht.right=ht.parent=-1;}else if((ch>='a' && ch<='z')||(ch>='A' && ch<='Z'))ht.ch=ch;else if(ch>='0'&&ch<='9')ht.weight=ht.weight*10+ch-'0';}n=i+1;if(fclose(fp)){printf("can not close the file character.txt");exit(0);}}//构造哈夫曼树,看成有n棵树，选择权值最小的两棵树合并void createHuffTree(){int i=0,k;int minI,minJ;int f=0;minI=minJ=-1; //minI<minJfor(k=n;k<2*n-1;k++){//寻找ht中权值最小且无父结点的两个结点i=0;f=0; while(ht.ch!='\0'){ if(ht.parent==-1){ if(f==0){ minI=i; f++;}else if(f==1){if(ht.weight<ht.weight){minJ=minI;minI=i;}else minJ=i;f++;}else{ if(ht.weight<ht.weight){ minJ=minI; minI=i;}else if(ht.weight<ht.weight)minJ=i;}} i++;}//合并两个结点ht.ch='#';ht.left=minI;ht.right=minJ;ht.weight=ht.weight+ht.weight;ht.parent=-1;ht.parent=ht.parent=k;}}//将一个字符串反转void reverse(char *str){int i,j;char ch;for(i=0,j=strlen(str)-1;i<j;i++,j--){ch=str;str=str;str=ch;}}//哈夫曼编码，通过父节点从下往上找void createHuffCode(){ int i,j,length;FILE * fp;for(i=0;i<n;i++){length=0;j=i;//给每个字符进行编码while(ht.parent!=-1){ if(ht.parent].left==j){ hcd.code=0+'0';}else hcd.code=1+'0';j=ht.parent;}hcd.start=hcd.code-'0';hcd.code='\0';reverse(hcd.code);}//把hcd字符编码写入文件document/code.txt中if((fp=fopen("document/code.txt","w"))==NULL){printf("can not open the file character.txt");exit(0);} for(i=0;i<n;i++){fputc(ht.ch,fp);fputs(" ",fp);fputs(hcd.code,fp);fputc('\n',fp);}if(fclose(fp)){printf("can not close the file character.txt");exit(0);}}//哈夫曼解码，每次都从根节点开始搜索int releaseHuffCode(char *str,char* code){int root=2*n-2;int length=0,i=0;while(code){if(code=='0'+0)root=ht.left;else if(code=='0'+1)root=ht.right;elsereturn 0;if(ht.left==-1 && ht.right==-1){ str=ht.ch;root=2*n-2;}i++;}str='\0';if(root==2*n-2)return 1;return 0;}//用户输入编码字符void encode(){int i=0,j,f=1;char str;char code={'\0'};printf("\n请输入要编码的字符串(length<50)\n");scanf("%s",str);while(str){if((str>='a'&&str<='z')||(str>='A'&&str<='Z')){ for(j=0;j<n;j++) if(str==ht.ch){ strcat(code,hcd.code); break;} i++;}else{f=0;break;}}if(f) puts(code);elseprintf("你输入的字符串错误！\n");printf("按任意键后重新选择！\n");getch();}//用户输入解码字串voiddecode(){char str;char code;printf("\n请输入要解码的字串(用0和1表示)\n");scanf("%s",code);if(releaseHuffCode(str,code))puts(str);elseprintf("你输入的字串错误！\n");printf("按任意键后重新选择！\n");getch();}//主函数void main(){int choice=1; initHt(); createHuffTree(); createHuffCode(); while(choice){ system("cls"); printf("/****************哈夫曼编码与解码*********************/\n"); printf(" 在document/character.txt 文件中存放着各个字母的权值\n"); printf(" 程序从中读出各个字母的权值构造哈夫曼树并进行编码\n"); printf(" 各个字符的编码存在document/code.txt文件中\n"); printf("/*****************************************************/\n"); printf("\n请输入你的选择：1 ---- 编码2 ---- 解码0 ---- 退出\n"); scanf("%d",&choice); switch(choice){ case 1: encode(); break; case 2: decode(); break; case 0: printf("谢谢使用！\n"); break; default: choice=1; printf("你的输入错误！按任意键后重新输入！\n"); getch(); break; } }}
页:
[1]