哈夫曼编码-数据结构实验
拖延了一个多月，终于交上了
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 ////////////////////////////////////////////////////////////////////////////// 5 /*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/ 6 typedef struct{ 7 int weight;//权值 8 char ch; //增加一个域用于存放该节点的字符 9 int parent, lchild, rchild; 10 }HTNode, *HuffmanTree; 11 typedef char **HuffmanCode; //指向赫夫曼编码的指针 12 ////////////////////////////////////////////////////////////////////////////// 13 /*本程序用到的函数原型*/ 14 void welcome(); //打印操作选择界面 15 void HuffmanCoding(HuffmanTree &, char *, int *, int);//建立赫夫曼树的算法 16 void select(HuffmanTree HT, int j, int *s1, int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点 17 void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树 18 void Coding(); //编码 19 void Decoding(); //译码 20 void Print_code(); //打印译码好的代码文件 21 void Print_tree(); //以凹凸表形式打印哈夫曼树 22 int Read_tree(HuffmanTree &HT); //从文件中读入赫夫曼树 23 void find(HuffmanTree &HT, char *code, char *text, int i, int m);//译码时根据01字符串寻找相应叶子节点的递归算法 24 void Convert_tree(unsigned char T[100][100], int s, int *i, int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树 25 HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间 26 int n = 0; //全局变量，存放赫夫曼树叶子结点的数目 27 int main() 28 { 29 char select; 30 while (1) 31 { 32 welcome(); 33 scanf("%c", &select); 34 switch (select) 35 { 36 case \'i\': 37 case \'I\':Init(); break; 38 case \'c\': 39 case \'C\':Coding(); break; 40 case \'d\': 41 case \'D\':Decoding(); break; 42 case \'p\': 43 case \'P\':Print_code(); break; 44 case \'t\': 45 case \'T\':Print_tree(); break; 46 case \'e\': 47 case \'E\':exit(1); 48 default:printf("Input error!\n"); 49 } 50 getchar(); 51 } 52 return 0; 53 } 54 void welcome() //打印操作选择界面 55 { 56 printf("*-----------------------------------------------------*\n"); 57 printf("| What do you want to do? |\n"); 58 printf("|-----------------------------------------------------|\n"); 59 printf("| |\n"); 60 printf("| I--------------------------Init the Huffman tree. |\n"); 61 printf("| C--------------------------Code your file. |\n"); 62 printf("| D--------------------------Decode the code. |\n"); 63 printf("| P--------------------------Print the codefile. |\n"); 64 printf("| T--------------------------Print the Huffman tree. |\n"); 65 printf("| |\n"); 66 printf("*-----------------------------------------------------*\n"); 67 } 68 ////////////////////////////////////////////////////////////////////////////////////// 69 /*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/ 70 void Init() 71 { 72 FILE *fp; 73 int i, n, w[52]; //w数组存放n个字符的权值 74 char character[52]; //存放n个字符 75 printf("\n输入字符个数 n:"); 76 scanf("%d", &n); //输入字符集大小 77 printf("输入%d个字符及其对应的权值:\n", n); 78 for (i = 0; i < n; i++) 79 { 80 char b = getchar();//? 81 scanf("%c", &character[i]); 82 scanf("%d", &w[i]); //输入n个字符和对应的权值 83 } 84 HuffmanCoding(HT, character, w, n); //建立赫夫曼树 85 if ((fp = fopen("hfmtree.txt", "w")) == NULL) 86 printf("Open file hfmtree.txt error!\n"); 87 for (i = 1; i <= 2 * n - 1; i++) 88 { 89 if (fwrite(&HT[i], sizeof(HTNode), 1, fp) != 1) //将建立的赫夫曼树存入文件hfmtree.txt中 90 printf("File write error!\n"); 91 } 92 printf("\n建立赫夫曼树成功，已将其存于文件hfmtree.txt中\n"); 93 fclose(fp); 94 } 95 /////////////////////////////////////////////////////////////////////////////////// 96 //////建立赫夫曼树的算法/////////////////////////////////////////////////////////// 97 void HuffmanCoding(HuffmanTree &HT, char *character, int *w, int n) 98 { 99 int m, i, s1, s2; 100 HuffmanTree p; 101 if (n <= 1) 102 return; 103 m = 2 * n - 1; 104 HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode)); 105 for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++character, ++w) 106 { 107 p->ch = *character; 108 p->weight = *w; 109 p->parent = 0; 110 p->lchild = 0; 111 p->rchild = 0; 112 } 113 for (; i <= m; ++i, ++p) 114 { 115 p->ch = 0; 116 p->weight = 0; 117 p->parent = 0; 118 p->lchild = 0; 119 p->rchild = 0; 120 } 121 for (i = n + 1; i <= m; ++i) 122 { 123 select(HT, i - 1, &s1, &s2); 124 HT[s1].parent = i; 125 HT[s2].parent = i; 126 HT[i].lchild = s1; 127 HT[i].rchild = s2; 128 HT[i].weight = HT[s1].weight + HT[s2].weight; 129 } 130 } 131 /////////////////////////////////////////////////////////////////////////////// 132 /*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/ 133 void select(HuffmanTree HT, int j, int *s1, int *s2) 134 { 135 int i; 136 //找weight最小的结点 137 for (i = 1; i <= j; i++) 138 if (HT[i].parent == 0) 139 { 140 *s1 = i; 141 break; 142 } 143 for (; i <= j; i++) 144 if ((HT[i].parent == 0) && (HT[i].weight < HT[*s1].weight)) 145 *s1 = i; 146 HT[*s1].parent = 1; 147 //找weight次小的结点 148 for (i = 1; i <= j; i++) 149 if (HT[i].parent == 0) 150 { 151 *s2 = i; break; 152 } 153 for (; i <= j; i++) 154 if ((HT[i].parent == 0) && (i != *s1) && (HT[i].weight < HT[*s2].weight)) 155 *s2 = i; 156 } 157 /////////////////////////////////////////////////////////////////////////////// 158 /*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/ 159 void Coding() 160 { 161 FILE *fp, *fw; 162 int i, f, c, start; 163 char *cd; 164 HuffmanCode HC; 165 if (n == 0) 166 n = Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 167 /////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中 168 { 169 HC = (HuffmanCode)malloc((n + 1)*sizeof(char*)); 170 cd = (char *)malloc(n*sizeof(char)); 171 cd[n - 1] = \'\0\'; 172 for (i = 1; i <= n; ++i) 173 { 174 start = n - 1; 175 for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) 176 if (HT[f].lchild == c) 177 cd[--start] = \'0\'; 178 else cd[--start] = \'1\'; 179 HC[i] = (char *)malloc((n - start)*sizeof(char)); 180 strcpy(HC[i], &cd[start]); 181 } 182 free(cd); 183 } 184 ///////////////////////////////////////////////////////////////////////////////////// 185 if ((fp = fopen("tobetrans.txt", "rb")) == NULL) 186 printf("Open file tobetrans.txt error!\n"); 187 if ((fw = fopen("codefile.txt", "wb+")) == NULL) 188 printf("Open file codefile.txt error!\n"); 189 char temp; 190 fscanf(fp, "%c", &temp); //从文件读入第一个字符 191 while (!feof(fp)) 192 { 193 for (i = 1; i <= n; i++) 194 if (HT[i].ch == temp) break; //在赫夫曼树中查找字符所在的位置 195 for (int r = 0; HC[i][r] != \'\0\'; r++) //将字符对应的编码存入文件 196 fputc(HC[i][r], fw); 197 fscanf(fp, "%c", &temp); //从文件读入下一个字符 198 } 199 fclose(fw); 200 fclose(fp); 201 printf("\n对文件hfmtree.txt编码成功,结果已存入codefile.txt中。\n\n"); 202 } 203 204 ///////////////////////////////////////////////////////////////////////// 205 /*将文件codefile中的代码进行译码，结果存入文件textfile中*/ 206 void Decoding() 207 { 208 FILE *fp, *fw; 209 int m, i; 210 char *code, *text, *p; 211 if (n == 0) 212 n = Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 213 if ((fp = fopen("codefile.txt", "rb")) == NULL) 214 printf("Open file codefile.txt error!\n"); 215 if ((fw = fopen("textfile.txt", "wb+")) == NULL) 216 printf("Open file textfile.txt error!\n"); 217 code = (char *)malloc(sizeof(char)); 218 fscanf(fp, "%c", code); //从文件读入一个字符 219 for (i = 1; !feof(fp); i++) 220 { 221 code = (char *)realloc(code, (i + 1)*sizeof(char)); //增加空间 222 fscanf(fp, "%c", &code[i]); //从文件读入下一个字符 223 } 224 code[i - 1] = \'\0\'; 225 /////////到此codefile.txt文件中的字符已全部读入，存放在code数组中 226 text = (char *)malloc(100 * sizeof(char)); 227 p = text; 228 m = 2 * n - 1; 229 if (*code == \'0\') 230 find(HT, code, text, HT[m].lchild, m); //从根节点的左子树去找 231 else 232 find(HT, code, text, HT[m].rchild, m); //从根节点的右子树去找 233 for (i = 0; p[i] != \'\0\'; i++) //把译码好的字符存入文件textfile.txt中 234 fputc(p[i], fw); 235 fclose(fp); 236 fclose(fw); 237 printf("\n对codefile.txt文件译码成功，结果已存入textfile.txt文件。\n\n"); 238 } 239 ////////////////////////////////////////////////////////////////////////////////////////////////////// 240 /*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/ 241 void Print_code() 242 { 243 FILE *fp, *fw; 244 char temp; 245 int i; 246 if ((fp = fopen("codefile.txt", "rb")) == NULL) 247 printf("Open file codefile.txt error!\n"); 248 if ((fw = fopen("codeprint.txt", "wb+")) == NULL) 249 printf("Open file codeprint.txt error!\n"); 250 printf("\n文件codefi1e以紧凑格式显示如下:\n"); 251 fscanf(fp, "%c", &temp); //从文件读入一个字符 252 for (i = 1; !feof(fp); i++) 253 { 254 printf("%c", temp); 255 if (i % 50 == 0) printf("\n"); 256 fputc(temp, fw); //将该字符存入文件codeprint.txt中 257 fscanf(fp, "%c", &temp); //从文件读入一个字符 258 } 259 printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n"); 260 fclose(fp); 261 fclose(fw); 262 } 263 ////////////////////////////////////////////////////////////////////////////////////////////////// 264 /*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/ 265 void Print_tree() 266 { 267 unsigned char T[100][100]; 268 int i, j, m = 0; 269 FILE *fp; 270 if (n == 0) 271 n = Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 272 273 Convert_tree(T, 0, &m, 2 * n - 1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中 274 if ((fp = fopen("treeprint.txt", "wb+")) == NULL) 275 printf("Open file treeprint.txt error!\n"); 276 printf("\n以凹凸表形式打印已建好的赫夫曼树：\n"); 277 for (i = 1; i <= 2 * n - 1; i++) 278 { 279 for (j = 0; T[i][j] != 0; j++) 280 { 281 if (T[i][j] == \' \') { printf(" "); fputc(T[i][j], fp); } 282 else 283 { 284 printf("%d", T[i][j]); fprintf(fp, "%d\n", T[i][j]); 285 } 286 } 287 printf("\n"); 288 } 289 fclose(fp); 290 printf("\n此字符形式的哈夫曼树已写入文件treeprint.txt中.\n\n"); 291 292 } 293 ////////////////////////////////////////////////////////////////////////////////// 294 /*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/ 295 int Read_tree(HuffmanTree &HT) 296 { 297 FILE *fp; 298 int i, n; 299 HT = (HuffmanTree)malloc(sizeof(HTNode)); 300 if ((fp = fopen("hfmtree.txt", "r")) == NULL) 301 printf("Open file hfmtree.txt error!\n"); 302 for (i = 1; !feof(fp); i++) 303 { 304 HT = (HuffmanTree)realloc(HT, (i + 1)*sizeof(HTNode)); //增加空间 305 fread(&HT[i], sizeof(HTNode), 1, fp); //读入一个节点信息 306 } 307 fclose(fp); 308 n = (i - 1) / 2; 309 return n; 310 } 311 //////////////////////////////////////////////////////////////// 312 /*译码时根据01字符串寻找相应叶子节点的递归算法*/ 313 void find(HuffmanTree &HT, char *code, char *text, int i, int m) 314 { 315 316 if (*code != \'\0\') //若译码未结束 317 { 318 code++; 319 if (HT[i].lchild == 0 && HT[i].rchild == 0) //若找到叶子节点 320 { 321 *text = HT[i].ch; //将叶子节点的字符存入text中 322 text++; 323 if ((*code == \'0\')) 324 find(HT, code, text, HT[m].lchild, m); //继续从根节点的左子树找 325 else 326 find(HT, code, text, HT[m].rchild, m); //继续从根节点的右子树找 327 } 328 else //如果不是叶子节点 329 if (*code == \'0\') 330 find(HT, code, text, HT[i].lchild, m); //从该节点的左子树去找 331 else 332 find(HT, code, text, HT[i].rchild, m); //从该节点的右子树去找 333 334 } 335 else 336 *text = \'\0\'; //译码结束 337 } 338 //////////////////////////////////////////////////////////////////////// 339 /*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/ 340 void Convert_tree(unsigned char T[100][100], int s, int *i, int j) 341 { 342 int k, l; 343 l = ++(*i); 344 for (k = 0; k < s; k++) 345 T[l][k] = \' \'; 346 T[l][k] = HT[j].weight; 347 if (HT[j].lchild) 348 Convert_tree(T, s + 1, i, HT[j].lchild); 349 if (HT[j].rchild) 350 Convert_tree(T, s + 1, i, HT[j].rchild); 351 T[l][++k] = \'\0\'; 352 }
版权声明：本文为yuanqi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。