|
| 1 | +/*************************************************************************** |
| 2 | + > Filename : 006-phuffman.c |
| 3 | + > Author : oneface - one_face@sina.com |
| 4 | + > Company : 一尊还酹江月 |
| 5 | + > Time : 2018-05-16 18:57:49 |
| 6 | + > Description: 采用指针形式而不是坐标形式，重新实现哈夫曼树的创建和哈夫曼编码 |
| 7 | +
|
| 8 | + - This program is free software; you can redistribute it and/or modify it |
| 9 | + - under the terms of the GNU General Public License as published by the |
| 10 | + - Free Software Foundation; either version 2 of the License, or (at your |
| 11 | + - option) any later version. |
| 12 | + **************************************************************************/ |
| 13 | +#include <stdio.h> |
| 14 | +#include <stdlib.h> |
| 15 | +#include <string.h> |
| 16 | + |
| 17 | +typedef struct _hftree { |
| 18 | + int weight; |
| 19 | + struct _hftree *parent, *lchild, *rchild; |
| 20 | +} hftree; |
| 21 | + |
| 22 | +typedef char *hfcode; |
| 23 | + |
| 24 | +static void huffman_creat(hftree ** hft, int *w, int s) |
| 25 | +{ |
| 26 | + int i, j, tmp, s1, s2; |
| 27 | + |
| 28 | + int m = 2 * s - 1; |
| 29 | + |
| 30 | + *hft = (hftree *) malloc((m + 1) * sizeof(**hft)); |
| 31 | + if (!*hft) { |
| 32 | + printf("*hft malloc failed\n"); |
| 33 | + return; |
| 34 | + } |
| 35 | + |
| 36 | + for (i = 1; i <= s; i++) { |
| 37 | + (*hft)[i].weight = w[i - 1]; |
| 38 | + (*hft)[i].parent = (*hft)[i].lchild = (*hft)[i].rchild = NULL; |
| 39 | + } |
| 40 | + for (; i <= m; i++) { |
| 41 | + (*hft)[i].weight = -1; |
| 42 | + (*hft)[i].parent = (*hft)[i].lchild = (*hft)[i].rchild = NULL; |
| 43 | + } |
| 44 | + |
| 45 | + for (i = s + 1; i <= m; i++) { |
| 46 | + j = 1; |
| 47 | + while ((*hft)[j].parent != NULL && j <= i - 1) { |
| 48 | + j++; |
| 49 | + } |
| 50 | + s1 = j; |
| 51 | + |
| 52 | + ++j; |
| 53 | + while ((*hft)[j].parent != NULL && j <= i - 1) { |
| 54 | + j++; |
| 55 | + } |
| 56 | + s2 = j; |
| 57 | + |
| 58 | + if ((*hft)[s1].weight > (*hft)[s2].weight) { |
| 59 | + tmp = s1; |
| 60 | + s1 = s2; |
| 61 | + s2 = tmp; |
| 62 | + } |
| 63 | + |
| 64 | + ++j; |
| 65 | + for (; j <= i - 1; j++) { |
| 66 | + if ((*hft)[j].parent == NULL) { |
| 67 | + if ((*hft)[j].weight < (*hft)[s1].weight) { |
| 68 | + s2 = s1; |
| 69 | + s1 = j; |
| 70 | + } else if ((*hft)[j].weight > (*hft)[s1].weight && (*hft)[j].weight < (*hft)[s2].weight) { |
| 71 | + s2 = j; |
| 72 | + } |
| 73 | + } |
| 74 | + } |
| 75 | + |
| 76 | + printf("s1=%d, s2=%d\n", s1, s2); |
| 77 | + (*hft)[s1].parent = (*hft)[s2].parent = &(*hft)[i]; |
| 78 | + (*hft)[i].lchild = &(*hft)[s1]; |
| 79 | + (*hft)[i].rchild = &(*hft)[s2]; |
| 80 | + (*hft)[i].weight = (*hft)[s1].weight + (*hft)[s2].weight; |
| 81 | + } |
| 82 | + |
| 83 | +} |
| 84 | + |
| 85 | +static void huffman_code(hfcode ** hfc, hftree * hft, int s) |
| 86 | +{ |
| 87 | + int i; |
| 88 | + |
| 89 | + *hfc = (hfcode *) malloc(s * sizeof(**hfc)); |
| 90 | + if (!*hfc) { |
| 91 | + printf("*hfc malloc failed\n"); |
| 92 | + return; |
| 93 | + } |
| 94 | + |
| 95 | + char *code = (char *)malloc(s * sizeof(char)); |
| 96 | + if (!code) { |
| 97 | + printf("code malloc failed\n"); |
| 98 | + goto fail1; |
| 99 | + } |
| 100 | + code[s - 1] = '\0'; |
| 101 | + |
| 102 | + for (i = 1; i <= s; i++) { |
| 103 | + int start = s - 1; |
| 104 | + hftree *phft = &hft[i]; |
| 105 | + while (phft->parent) { |
| 106 | + if (phft->parent->lchild == phft) {
6D4E
|
| 107 | + code[--start] = '0'; |
| 108 | + } else if (phft->parent->rchild == phft) { |
| 109 | + code[--start] = '1'; |
| 110 | + } else { |
| 111 | + printf("hehe: no way\n"); |
| 112 | + } |
| 113 | + phft = phft->parent; |
| 114 | + } |
| 115 | + |
| 116 | + (*hfc)[i] = (hfcode) malloc((s - start + 1) * sizeof(***hfc)); |
| 117 | + strncpy((*hfc)[i], &code[start], s - start + 1); |
| 118 | + } |
| 119 | + |
| 120 | + return; |
| 121 | + fail1: |
| 122 | + free(*hfc); |
| 123 | + return; |
| 124 | +} |
| 125 | + |
| 126 | +static void print_hfcode(hfcode * hfc, int *w, int s) |
| 127 | +{ |
| 128 | + int i; |
| 129 | + for (i = 1; i <= s; i++) { |
| 130 | + printf("%d: %s\n", w[i - 1], hfc[i]); |
| 131 | + } |
| 132 | +} |
| 133 | + |
| 134 | +int main() |
| 135 | +{ |
| 136 | + int w[] = { 2, 8, 7, 6, 5, 4 }; |
| 137 | + int s = sizeof(w) / sizeof(w[0]); |
| 138 | + |
| 139 | + hftree *hft = NULL; |
| 140 | + huffman_creat(&hft, w, s); |
| 141 | + |
| 142 | + hfcode *hfc = NULL; |
| 143 | + huffman_code(&hfc, hft, s); |
| 144 | + |
| 145 | + print_hfcode(hfc, w, s); |
| 146 | + |
| 147 | + return 0; |
| 148 | +} |
0 commit comments