50250. Huffman Coding
難度：5/5
用助教的方法，每一步都qsort()一遍的話，會TLE，所以在合併樹的時候要insertion進去才不會耗太多時間。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#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "huffmanTree.h"
// typedef struct Node {
// char symbol[SYM_MAX_LEN];
// int frequency;
// struct Node *left, *right;
// } Node;
static inline Node* new_node(int f, Node* l, Node* r){
Node* n = (Node*) malloc(sizeof(Node));
n->frequency = f;
n->left = l;
n->right = r;
return n;
}
int cmp(const void* aa, const void* bb){ // a < b than 1
Node* a = *(Node**)aa;
Node* b = *(Node**)bb;
if(a->frequency != b->frequency) return a->frequency > b->frequency ? 1 : -1;
else return strcmp(a->symbol, b->symbol);
}
int rev_cmp(const void* a, const void* b){
return -cmp(a, b);
}
Node* buildHuffmanTree(char* s[SYM_MAX_NUM], int n){
Node* arr[100000]; int len_arr = 0;
for(int i = 0; i < n; i++){
int idx = -1;
for(int j = 0; j < len_arr; j++){
if(strcmp(s[i], arr[j]->symbol) == 0){
idx = j; break;
}
}
if(idx == -1){
Node* n = new_node(1, NULL, NULL);
strcpy(n->symbol, s[i]);
arr[len_arr++] = n;
}
else{
arr[idx]->frequency += 1;
}
}
qsort(arr, len_arr, sizeof(Node*), rev_cmp);
while(len_arr > 1){
// for(int i = 0; i < len_arr; i++) printf("%s %d, ", arr[i]->symbol, arr[i]->frequency); printf("\n");
Node* temp = new_node(arr[len_arr - 2]->frequency + arr[len_arr - 1]->frequency,
arr[len_arr - 2], arr[len_arr - 1]);
if(strcmp(arr[len_arr - 2]->symbol, arr[len_arr - 1]->symbol) < 0) strcpy(temp->symbol, arr[len_arr - 2]->symbol);
else strcpy(temp->symbol, arr[len_arr - 1]->symbol);
// printf("merging %s %d, %s %d\n", arr[len_arr - 2]->symbol, arr[len_arr - 2]->frequency, arr[len_arr - 1]->symbol, arr[len_arr - 1]->frequency);
// printf("get %s %d\n", temp->symbol, temp->frequency);
int insert_idx = 0;
for(int i = len_arr - 3; i >= 0; i--){
if(cmp(&arr[i], &temp) < 0) continue;
else{
insert_idx = i + 1;
break;
}
}
for(int i = len_arr - 2; i > insert_idx; i--) arr[i] = arr[i - 1];
arr[insert_idx] = temp;
len_arr--;
// for(int i = 0; i < len_arr; i++) printf("%s %d, ", arr[i]->symbol, arr[i]->frequency); printf("\n");
// printf("====================================================\n");
}
return arr[0];
}