输入：字符及其权值，待译码字符串，待解码字符串
功能要求：输出各字符的哈夫曼编码，输出译码字符串，输出解码字符串
哈夫曼树构造过程：
1.从所有待编码的节点中选取权值最小的两个节点S1,S2，合并成一颗二叉树T1，T1的叶子节点为S1,S2，根节点为S1,S2之和。
2.选取除这两个节点以外最小的节点，将其和T1作为叶子构造一棵新的树。
3.重复上述过程，直到所有代编码的节点都加入到树中。
解码过程：
按照构造的哈夫曼树，从根节点开始，遇到0往左子树走，遇到1走向右子树，这样就可以达到解码的过程
代码：
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<conio.h> 5 #define MAXNUM 60 6 typedef struct 7 { 8 char ch; 9 int weight; //权值，这个字符出现的频率 10 int parent; 11 int left; 12 int right; 13 }HuffNode; 14 15 typedef struct 16 { 17 char code[MAXNUM]; 18 int start; 19 }HuffCode; 20 21 HuffNode ht[MAXNUM * 2]; //存放哈夫曼树 22 23 HuffCode hcd[MAXNUM]; //存放ht数组中对应的字符的编码 24 25 int n; //字符的个数 26 27 //初始化哈夫曼树ht 28 void initHt() 29 { 30 FILE * fp; 31 char ch; 32 int i = 0; 33 //从文件1.txt中读出要编码的字符和权值 34 if ((fp = fopen("d:\1.txt", "r")) == NULL){ 35 printf("can not open the file 1.txt"); 36 exit(0); 37 } 38 ht[i].left = ht[i].right = ht[i].parent = -1; 39 while ((ch = fgetc(fp)) != EOF){ 40 if (ch == ' '){ 41 i++; 42 ht[i].left = ht[i].right = ht[i].parent = -1; 43 } 44 else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) 45 ht[i].ch = ch; 46 else if (ch >= '0'&&ch <= '9') 47 ht[i].weight = ht[i].weight * 10 + ch - '0'; 48 } 49 n = i + 1; 50 if (fclose(fp)){ 51 printf("can not close the file 1.txt"); 52 exit(0); 53 } 54 } 55 //构造哈夫曼树,看成有n棵树，选择权值最小的两棵树合并 56 void createHuffTree() 57 { 58 59 int i = 0, k; 60 int minI, minJ; 61 int f = 0; 62 minI = minJ = -1; //minI<minJ 63 for (k = n; k<2 * n - 1; k++){ 64 //寻找ht中权值最小且无父结点的两个结点 65 i = 0; 66 f = 0; 67 while (ht[i].ch != ' '){ 68 if (ht[i].parent == -1){ 69 if (f == 0){ 70 minI = i; 71 f++; 72 } 73 else if (f == 1){ 74 if (ht[i].weight<ht[minI].weight){ 75 minJ = minI; 76 minI = i; 77 } 78 else 79 minJ = i; 80 f++; 81 } 82 else{ 83 if (ht[i].weight<ht[minI].weight){ 84 minJ = minI; 85 minI = i; 86 } 87 else if (ht[i].weight<ht[minJ].weight) 88 minJ = i; 89 } 90 } 91 i++; 92 } 93 //合并两个结点 94 ht[k].ch = '#'; 95 ht[k].left = minI; 96 ht[k].right = minJ; 97 ht[k].weight = ht[minI].weight + ht[minJ].weight; 98 ht[k].parent = -1; 99 ht[minI].parent = ht[minJ].parent = k; 100 } 101 } 102 103 //将一个字符串反转 104 void reverse(char *str) 105 { 106 int i, j; 107 char ch; 108 for (i = 0, j = strlen(str) - 1; i<j; i++, j--){ 109 ch = str[i]; 110 str[i] = str[j]; 111 str[j] = ch; 112 } 113 } 114 115 //哈夫曼编码，通过父节点从下往上找 116 void createHuffCode() 117 { 118 int i, j, length; 119 FILE * fp; 120 for (i = 0; i<n; i++){ 121 length = 0; 122 j = i; 123 //给每个字符进行编码 124 while (ht[j].parent != -1){ 125 if (ht[ht[j].parent].left == j){ 126 hcd[i].code[length++] = 0 + '0'; 127 } 128 else 129 hcd[i].code[length++] = 1 + '0'; 130 j = ht[j].parent; 131 } 132 133 hcd[i].start = hcd[i].code[length - 1] - '0'; 134 hcd[i].code[length] = ' '; 135 reverse(hcd[i].code); 136 } 137 //把hcd字符编码写入文件document/code.txt中 138 if ((fp = fopen("d:\2.txt", "w")) == NULL){ 139 printf("can not open the file 2.txt"); 140 exit(0); 141 } 142 for (i = 0; i<n; i++){ 143 fputc(ht[i].ch, fp); 144 fputs(" ", fp); 145 fputs(hcd[i].code, fp); 146 fputc(' ', fp); 147 } 148 if (fclose(fp)){ 149 printf("can not close the file 2.txt"); 150 exit(0); 151 } 152 } 153 //哈夫曼解码，每次都从根节点开始搜索 154 int releaseHuffCode(char *str, char* code) 155 { 156 int root = 2 * n - 2; 157 int length = 0, i = 0; 158 while (code[i]){ 159 if (code[i] == '0' + 0) 160 root = ht[root].left; 161 else if (code[i] == '0' + 1) 162 root = ht[root].right; 163 else 164 return 0; 165 if (ht[root].left == -1 && ht[root].right == -1){ 166 str[length++] = ht[root].ch; 167 root = 2 * n - 2; 168 } 169 i++; 170 } 171 str[length] = ' '; 172 if (root == 2 * n - 2) 173 return 1; 174 return 0; 175 } 176 177 //用户输入编码字符 178 void encode() 179 { 180 int i = 0, j, f = 1; 181 char str[50]; 182 char code[500] = { ' ' }; 183 printf(" 请输入要编码的字符串(length<50) "); 184 scanf("%s", str); 185 while (str[i]){ 186 if ((str[i] >= 'a'&&str[i] <= 'z') || (str[i] >= 'A'&&str[i] <= 'Z')){ 187 for (j = 0; j<n; j++) 188 if (str[i] == ht[j].ch){ 189 strcat(code, hcd[j].code); 190 break; 191 } 192 i++; 193 } 194 else{ 195 f = 0; 196 break; 197 } 198 } 199 if (f) 200 puts(code); 201 else 202 printf("你输入的字符串错误！ "); 203 printf("按任意键后重新选择！ "); 204 _getch(); 205 } 206 207 //用户输入解码字串 208 void decode() 209 { 210 char str[50]; 211 char code[500]; 212 printf(" 请输入要解码的字串(用0和1表示) "); 213 scanf("%s", code); 214 if (releaseHuffCode(str, code)) 215 puts(str); 216 else 217 printf("你输入的字串错误！ "); 218 219 printf("按任意键后重新选择！ "); 220 _getch(); 221 } 222 223 //主函数 224 int main() 225 { 226 int choice = 1; 227 initHt(); 228 createHuffTree(); 229 createHuffCode(); 230 while (choice){ 231 system("cls"); 232 printf("/****************哈夫曼编码与解码*********************/ "); 233 printf(" 在H:\1.txt 文件中存放着各个字母的权值 "); 234 printf(" 程序从中读出各个字母的权值构造哈夫曼树并进行编码 "); 235 printf(" 各个字符的编码存在H:\2.txt文件中 "); 236 printf("/*****************************************************/ "); 237 printf(" 请输入你的选择：1 ---- 编码 2 ---- 解码 0 ---- 退出 "); 238 scanf("%d", &choice); 239 switch (choice){ 240 case 1: 241 encode(); 242 break; 243 case 2: 244 decode(); 245 break; 246 case 0: 247 printf("谢谢使用！ "); 248 break; 249 default: 250 choice = 1; 251 printf("你的输入错误！按任意键后重新输入！ "); 252 _getch(); 253 break; 254 } 255 } 256 }
所需要的两个文件：
1.txt（存储代编码字符及其频率）
2.txt（存储字符的编码）
运行截图：
