1 #include "stdio.h" 2 const int maxlen = 1000; 3 #define infinity 65535 4 5 struct encode{ 6 char Data[maxlen];//存储编码(字符类型) 7 int count;//编码的位数 8 }; 9 struct bnode 10 { 11 int data;//数据 12 char ch;//字符 13 bnode *lchild,*rchild;//左孩子，右孩子结点 14 encode code;//存储编码信息 15 bool flags;//使用标志 16 }; 17 18 struct FileChar{ 19 char ch;//字符 20 int count;//字符在文章出现的次数 21 }; 22 23 bnode *tree[maxlen]; 24 FileChar CharNum[maxlen];//存放字符以及字符出现的次数 25 int num_char= 0;//不同字符的总数 26 27 /* 28 * int A[]:存放字符的频度 29 *int N:字符的个 30 *bnode *tree[maxlen]//树 31 */ 32 void initialization(int N,bnode *tree[maxlen])//初始化 33 { 34 int i; 35 for(i=0;i<N;i++) 36 { 37 tree[i] = new bnode; 38 tree[i]->data = CharNum[i].count;//结点的值 39 tree[i]->ch = CharNum[i].ch;//结点的字符 40 tree[i]->flags = true;//标识未使用 41 tree[i]->code.count = 0;//编码位数为0 42 tree[i]->lchild = NULL;//左子树为空 43 tree[i]->rchild = NULL;//右子树为空 44 } 45 } 46 47 void merge(int &n,bnode *tree[maxlen])//寻找当前根结点值最小的两个子树将其合并 48 { 49 int i,num1,num2,min1,min2; 50 min1 = infinity; 51 min2 = infinity; 52 for(i=0;i<n;i++)//寻找当前值最小的根节点 53 { 54 if((tree[i]->data<min1)&&tree[i]->flags) 55 { 56 min1 = tree[i]->data; 57 num1 = i; 58 } 59 } 60 tree[num1]->flags = false;//设置标识已使用过 61 62 for(i=0;i<n;i++)//寻找当前值最小的根节点 63 { 64 if((tree[i]->data<min2)&&tree[i]->flags) 65 { 66 min2 = tree[i]->data; 67 num2 = i; 68 } 69 } 70 tree[num2]->flags = false;//设置标识已使用过 71 //将两个子树合并 72 tree[n] = new bnode; 73 tree[n]->data = tree[num1]->data + tree[num2]->data; 74 tree[n]->flags = true; 75 tree[n]->code.count = 0;//编码位数为0 76 tree[n]->lchild = tree[num1]; 77 tree[n]->rchild = tree[num2]; 78 n++; 79 } 80 81 void Huffmantree(int &n,bnode *tree[maxlen])//构造哈夫曼树 82 { 83 int i,num; 84 bool flags = true;//标识 85 while(flags) 86 { 87 num = 0;//计数 88 for(i=0;i<n;i++)//统计未使用结点数 89 { 90 if(tree[i]->flags) 91 { 92 num++; 93 } 94 } 95 if(num>=2) 96 { 97 merge(n,tree);//合并当前根结点值最小的两棵子树 98 }else{ 99 flags = false;//哈夫曼树构造完成标识 100 } 101 } 102 } 103 104 void HFTree(bnode *Tree)//中序输出哈夫曼树 105 { 106 if(Tree) 107 { 108 HFTree(Tree->lchild); 109 printf(" %d",Tree->data); 110 HFTree(Tree->rchild); 111 } 112 } 113 114 void Encode(bnode *Tree)//每个结点进行编码 115 { 116 int i,count; 117 if(Tree) 118 { 119 if(Tree->lchild)//左子树根结点添加0 120 { 121 count = Tree->code.count; 122 for(i=0;i<count;i++)//父节点的编码添加到自己身上 123 { 124 Tree->lchild->code.Data[i] = Tree->code.Data[i]; 125 Tree->lchild->code.count++; 126 } 127 128 Tree->lchild->code.Data[count] = '0';//再添加0 129 Tree->lchild->code.count++; 130 } 131 if(Tree->rchild)//右子树根结点添加1 132 { 133 count = Tree->code.count; 134 for(i=0;i<count;i++)//父节点的编码添加到自己身上 135 { 136 Tree->rchild->code.Data[i] = Tree->code.Data[i]; 137 Tree->rchild->code.count++; 138 } 139 Tree->rchild->code.Data[count] = '1';//再添加1 140 Tree->rchild->code.count++; 141 } 142 Encode(Tree->lchild);//左子树继续 143 Encode(Tree->rchild);//右子树继续 144 } 145 146 } 147 148 //进行统计各个字符出现的次数 149 void analyse(FILE *fp) 150 { 151 int i; 152 bool flags;//标志，是否为新的字符 153 char ch;//字符 154 155 while((ch = fgetc(fp))!=EOF)//从文件内读取字符 156 { 157 flags = true; 158 for(i=0;i<num_char;i++)//字符进行处理 159 { 160 if(ch==CharNum[i].ch)//字符已经存在，次数+1 161 { 162 CharNum[i].count++; //字符出现次数+1 163 flags = false; 164 break; 165 } 166 } 167 if(flags)//此字符目前还不存在 168 { 169 CharNum[num_char].count = 1;//字符出现次数+为 170 CharNum[num_char].ch = ch;//新字符保存 171 num_char++;//不同字符总次数+! 172 } 173 } 174 } 175 176 177 void Save_Code()//保存编码 178 { 179 int i,j,k; 180 FILE *fp; 181 if((fp=fopen("D:/code.txt","w+"))==NULL) 182 { 183 printf("文件不存在 "); 184 185 }else{ 186 fprintf(fp,"%s","字符 编码 "); 187 printf("[编码结果显示] 字符 编码 "); 188 //每个字符及其编码包存到文件中 189 for(i=0;i<num_char;i++) 190 { 191 for(j=0;j<num_char;j++) 192 { 193 if(CharNum[i].ch==tree[j]->ch)//找到字符 194 { 195 fprintf(fp,"%c ",CharNum[i].ch);//字符存入文件 196 printf("%c ",CharNum[i].ch); 197 for(k=0;k<tree[j]->code.count;k++) 198 { 199 fprintf(fp,"%c",tree[j]->code.Data[k]);//字符编码存入文件 200 printf("%c",tree[j]->code.Data[k]); 201 } 202 fprintf(fp,"%c",' ');//换行符添加到文件中 203 printf(" "); 204 } 205 } 206 } 207 fclose(fp); 208 } 209 } 210 211 void translate(char file[])//译码 212 { 213 FILE *fp,*fout; 214 char ch; 215 int i,k; 216 int Line =0;//标识 217 if((fp=fopen(file,"r+"))==NULL) 218 { 219 printf("文件操作出错! "); 220 221 }else{ 222 if((fout=fopen("D:/decode.txt","w+"))==NULL) 223 { 224 printf("文件不存在 "); 225 226 }else{ 227 printf("[译码结果显示] "); 228 while((ch = fgetc(fp))!=EOF)//从文件内读取字符 229 { 230 Line++;//字符数+1 231 for(i=0;i<num_char;i++) 232 { 233 if(ch==tree[i]->ch)//找到tree中对应的字符 234 { 235 for(k=0;k<tree[i]->code.count;k++) 236 { 237 fprintf(fout,"%c",tree[i]->code.Data[k]);//字符编码存入文件 238 printf("%c",tree[i]->code.Data[k]); 239 } 240 fprintf(fout,"%c",' ');//换行符添加到文件中 241 printf(" "); 242 } 243 } 244 if(Line%10==0) 245 { 246 fprintf(fout,"%c",' ');//每个10个换行 247 printf(" "); 248 } 249 } 250 } 251 printf(" "); 252 fclose(fout); 253 } 254 } 255 256 int main() 257 { 258 int n; 259 FILE *fp; 260 printf("输入文件路径:"); 261 char file[30]; 262 scanf("%s",&file);//输入文件路径 263 if((fp=fopen(file,"r+"))==NULL) 264 { 265 printf("文件操作出错! "); 266 267 }else{ 268 analyse(fp); 269 } 270 271 n = num_char; 272 initialization(n,tree);//左右子树初始化 273 Huffmantree(n,tree);//构造哈夫曼树 274 printf("[哈夫曼树中序输出:"); 275 HFTree(tree[n-1]); 276 printf(" "); 277 278 Encode(tree[n-1]); 279 Save_Code(); 280 printf("[编码已经保存!] "); 281 translate(file); 282 printf("[译码已经保存!] "); 283 return 0; 284 }