问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。
1.基本要求
（1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
（2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；
（3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；
（4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；
2.重点，难点
重点：
（1）通过实验理解哈夫曼树的特征及其应用；
（2）哈夫曼树的构造算法设计；
（3）利用构造的哈夫曼树进行编码和译码。
难点：
（1）字符的哈夫曼树编码及存储；
（2）字符的译码与串的匹配算法。
3.源代码（纯C）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 |
#include <stdio.h> #include <stdlib.h> #include<string.h> #define MAXSIZE 50 /*©Copyright OmegaXYZ Xu Yi 2017*/ typedef struct//Huffman树的定义 { char name; unsigned int w;//权值 unsigned int pa;//父节点 unsigned int lch;//左子树 unsigned int rch;//右子树 }HTnode; typedef struct//Huffman编码 { int data; char name1; char *pre; }HCnode; int N,M; HCnode *HC; HTnode *HT; void Reverse(char *str)//字符串倒置，如此便不需要反向编码 { int i,j; char ch; for(i=0,j=strlen(str)-1;i<j;i++,j--){ ch=str[i]; str[i]=str[j]; str[j]=ch; } } int min_node(HTnode *HT,int n)//寻找Node中最小的节点 { int i,min; for(i=1;HT[i].pa;i++);//寻找根节点 min=i; for(i=1;i<n;i++) if(!HT[i].pa) if(HT[i].w<HT[min].w) min=i; HT[min].pa=1; return min; } void Output_HT(HTnode *HT)//输出Huffman树 { int i; printf(" 编号 名称 权值 父节点 左子树 右子树\n"); for(i=1;i<2*N;i++){ printf(" |%-5d %c %-5d %-5d %-6d %-4d|\n",i, HT[i].name,HT[i].w, HT[i].pa,HT[i].lch, HT[i].rch); } } /*©Copyright OmegaXYZ Xu Yi 2017*/ void PrintHC(HCnode *HC)//输出Huffman编码 { FILE *f1,*f2; int i=0,j=0,x=0,n=0,wpl=0;//wpl带权路径长度 char temp[50]; if((f1=fopen("ToBeTran.txt","r"))==NULL){//打开ToBeTran.txt printf("open failed!\n");exit(0); } if((f2=fopen("Code.txt","w"))==NULL){//打开Code.txt printf("open failed!\n");exit(0); } printf("输出Huffman编码\n"); for(i=1;i<=N;i++) { printf("%c-->%s",HC[i].name1,HC[i].pre); x=strlen(HC[i].pre); wpl+=(HC[i].data*x); printf("\n"); } i=0; while(!feof(f1)){//从ToBeTran中读取字符并写入Code temp[i]=fgetc(f1); for(j=1;j<=N;j++) if(temp[i]==HC[j].name1) { fprintf(f2,"%s",HC[j].pre); } i++; } fprintf(f2,"\b"); printf("\n带权路径长度(WPL) is %d\n",wpl); fclose(f1); fclose(f2); } /*©Copyright OmegaXYZ Xu Yi 2017*/ HTnode *Create()//构造Huffman树 { FILE *fp; int i,Si,Sj;//找出来的两个最小子树保存在Si和Sj里面 HTnode *HT; HT=(HTnode *)malloc((2*N)*sizeof(HTnode));//给HT分配2N-1这里分配2N个 printf("读取%d个叶节点的权值并生成Hufman Tree表格形式:\n",N); if((fp=fopen("DataFile.txt","rt"))==NULL){//读取DataFile的文件 //A,10a,2b,3c,10d,11e,20f,11g,10h,20i,14j,3k,7l,15m,9n,3o,25p,6q,2r,5s,20t,21u,9v,1w,5x,6y,8z,3 ,28!,8 printf("can not find file DataFile failed!\n");exit(0); } for(i=1;i<=N;i++) { fscanf(fp,"%c,%d",&HT[i].name,&HT[i].w);//将Data的名称和权值赋值给HT HT[i].lch=HT[i].rch=HT[i].pa=0;//初始化 } printf("\n"); for(;i<=M;i++) HT[i].lch=HT[i].rch=HT[i].pa=HT[i].w=0;//对其它多余的树进行初始化 for(i=N+1;i<=M;i++) { Si=min_node(HT,i);//寻找最小的节点 Sj=min_node(HT,i);//同上 HT[i].w=HT[Si].w+HT[Sj].w;//创建 HT[Si].pa=HT[Sj].pa=i; HT[i].lch=Si;HT[i].rch=Sj; } return HT; } /*©Copyright OmegaXYZ Xu Yi 2017*/ HCnode *Coding(HTnode *HT)//Huffman编码 { int i,j,c,f; HCnode *HC; char data[MAXSIZE]; HC=(HCnode *)malloc(N*sizeof(HCnode));//叶子节点的个数 for(i=1;i<=N;i++) { memset(data,'\0',MAXSIZE); HC[i].name1=HT[i].name;//将树的名称给HC HC[i].data=HT[i].w;//权值复制 for(c=i,j=0,f=HT[c].pa;f;c=f,f=HT[f].pa,j++)//根节点循环终止，HC[f]的父节点给f，反向Huffman编码 { if(HT[f].lch==c)data[j]='0';//左子树为0，右子树为1 else data[j]='1'; } HC[i].pre=(char *)malloc((strlen(data)+1)*sizeof(char)); Reverse(data);//逆置Huffman编码 for(j=0;j<strlen(data)+1;j++) HC[i].pre[j]=data[j]; HC[i].pre[j]='\0';//将Huffman编码给HC.pre[] } return HC; } void Decoding(HTnode *HT)//解码 { FILE *fp1,*fp2; char ch[50]; char cod[200]; int f,root,i=0,j=0; if((fp1=fopen("CodeFile.txt","r"))==NULL){ printf("open file failed");exit(0); } if((fp2=fopen("Textfile.txt","w"))==NULL){ printf("open file failed");exit(0); } while(!feof(fp1)){//将Codefile的文件给cod[] fscanf(fp1,"%c",&cod[i]); i++; } i=1; while(HT[i].pa){i++;}//寻找根节点 root=i; i=0; while(cod[i]!='\b')//结尾 { f=root; while(HT[f].lch!=NULL)//不为空 { if(cod[i]=='0') f=HT[f].lch; else f=HT[f].rch; i++; } ch[j++]=HT[f].name; } ch[j]='\0'; printf("\nCodeFile.txt解码为:%s\n",ch);i=0; fprintf(fp2,"%s\b",ch); fclose(fp1); fclose(fp2); } void Output() //输出Textfile.txt、ToBeTran.txt、Code.txt、CodeFile.txt、Textfile.txt { int c; char b; FILE *fp1,*fp2,*fp3,*fp4,*fp5; if((fp1=fopen("Datafile.txt","r"))==NULL){ printf("open file0 failed!\n");exit(0); } if((fp1=fopen("Datafile.txt","r"))==NULL){ printf("open file0 failed!\n");exit(0); } if((fp2=fopen("ToBeTran.txt","r"))==NULL){ printf("open file ToBeTran failed!\n");exit(0); } if((fp3=fopen("Code.txt","r"))==NULL){ printf("open file Code failed!\n");exit(0); } if((fp4=fopen("CodeFile.txt","r"))==NULL){ printf("open file CodeFile failed!\n");exit(0); } if((fp5=fopen("Textfile.txt","r"))==NULL){ printf("open file Textfile failed!\n");exit(0); } printf("\n输出DataFlie中的字符及其权值:\n"); while(!feof(fp1)){ fscanf(fp1,"%c,%d", &b,&c); printf("'%c'---%d\n",b,c); } printf("\n\n输出ToBeTran:\n"); while(!feof(fp2)){ fscanf(fp2,"%c",&b); printf("%c",b); } printf("\n\n输出Code.txt:\n"); while(!feof(fp3)){ fscanf(fp3,"%c",&b); printf("%c",b); } printf("\n\n输出CodeFile.txt:\n"); while(!feof(fp4)){ fscanf(fp4,"%c",&b); printf("%c",b); } printf("\n\n输出Textfile.txt:\n"); while(!feof(fp5)){ fscanf(fp5,"%c",&b); printf("%c",b); } printf("\n"); fclose(fp1);fclose(fp2);fclose(fp3);fclose(fp4);fclose(fp5); } void Output2(int n) //输出Textfile.txt、ToBeTran.txt、Code.txt、CodeFile.txt、Textfile.txt { int c; char b; FILE *fp1,*fp2,*fp3,*fp4,*fp5; switch(n) { case 1:printf("\n输出DataFlie中的字符及其权值:\n"); if((fp1=fopen("Datafile.txt","r"))==NULL){ printf("open file0 failed!\n");exit(0);} while(!feof(fp1)){fscanf(fp1,"%c,%d", &b,&c); printf("'%c'---%d\n",b,c);}fclose(fp1);break; case 2:printf("\n\n输出ToBeTran:\n"); if((fp2=fopen("ToBeTran.txt","r"))==NULL){ printf("open file ToBeTran failed!\n");exit(0);} while(!feof(fp2)){fscanf(fp2,"%c",&b); printf("%c",b);}fclose(fp2);break; case 3:printf("\n\n输出Code.txt:\n"); if((fp3=fopen("Code.txt","r"))==NULL){ printf("open file Code failed!\n");exit(0);} while(!feof(fp3)){fscanf(fp3,"%c",&b); printf("%c",b);}fclose(fp3);break; case 4:printf("\n\n输出CodeFile.txt:\n"); if((fp4=fopen("CodeFile.txt","r"))==NULL){ printf("open file CodeFile failed!\n");exit(0);} while(!feof(fp4)){fscanf(fp4,"%c",&b); printf("%c",b);}fclose(fp4);break; case 5:printf("\n\n输出Textfile.txt:\n"); if((fp5=fopen("Textfile.txt","r"))==NULL){ printf("open file Textfile failed!\n");exit(0);} while(!feof(fp5)){fscanf(fp5,"%c",&b); printf("%c",b);}fclose(fp5);break; default:printf("ERROR!"); } printf("\n"); } /*©Copyright OmegaXYZ Xu Yi 2017*/ int main() { int i; FILE *fp; char **code;//构建一个二维数组解码用 char ope; msgbox();//信息栏自己定义哦 printf("根据Data文件请输入叶节点个数（此文件输入>28）:"); while(scanf("%d",&N)) { if(N>0&&N<=500){ M=2*N-1; code=(char**)malloc(100*sizeof(char)); for(i=0;i<N;i++) code[i]=(char *)malloc(8*sizeof(char)); Output2(1); printf("读取DataFile中的字符及权值，建立Huffman树:\n"); HT=Create(); Output_HT(HT); printf("\n"); printf("对Huffman树进行编码:\n"); HC=Coding(HT); PrintHC(HC); printf("-------------------------------------------------------------------\n"); printf("将ToBeTran的内容改写成编码写入Code.txt\n"); Output2(2); Output2(3); printf("-------------------------------------------------------------------\n"); printf("对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中\n"); Decoding(HT); Output2(4); Output2(5); printf("-----------------------------总输出函数--------------------------------\n"); Output(); break; } else printf("请重新输入:\n"); } return 0; } |
4.结果演示
test