8000 huffman: hfcode未完成 · home-coder/data-abstraction-001@6905e40 · GitHub
[go: up one dir, main page]
Skip to content

Commit 6905e40

Browse files
author
oneface
committed
huffman: hfcode未完成
1 parent d7fa04f commit 6905e40

File tree

2 files changed

+274
-122
lines changed

2 files changed

+274
-122
lines changed

‎006-huffman.c

Lines changed: 126 additions & 114 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22
> Filename : 006-huffman.c
33
> Author : oneface - one_face@sina.com
44
> Company : 一尊还酹江月
5-
> Time : 2018-04-25 16:14:57
5+
> Time : 2018-05-02 11:31:02
66
> Description:
77
88
- This program is free software; you can redistribute it and/or modify it
@@ -11,146 +11,158 @@
1111
- option) any later version.
1212
**************************************************************************/
1313
#include <stdio.h>
14-
#include<stdlib.h>
15-
#include<string.h>
14+
#include <stdlib.h>
1615

17-
//哈夫曼树结点结构
1816
typedef struct {
19-
int weight; //结点权重
20-
int parent, left, right; //父结点、左孩子、右孩子在数组中的位置下标
21-
} HTNode, *HuffmanTree;
22-
//动态二维数组，存储哈夫曼编码
23-
typedef char **HuffmanCode;
24-
//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
25-
void Select(HuffmanTree HT, int end, int *s1, int *s2)
17+
int weight;
18+
int parent, left, right;
19+
}hftree;
20+
21+
typedef char* hfcode;
22+
23+
static void weight_select(hftree *h, int n, int *d1, int *d2)
2624
{
27-
int min1, min2;
28-
//遍历数组初始下标为 1
29-
int i = 1;
30-
//找到还没构建树的结点
31-
while (HT[i].parent != 0 && i <= end) {
25+
int i = 1, tmp;
26+
27+
while (h[i].parent != -1 && i <= n) {
3228
i++;
3329
}
34-
min1 = HT[i].weight;
35-
*s1 = i;
30+
*d1 = i;
3631

3732
i++;
38-
while (HT[i].parent != 0 && i <= end) {
33+
while (h[i].parent != -1 && i <= n) {
3934
i++;
4035
}
41-
//对找到的两个结点比较大小，min2为大的，min1为小的
42-
if (HT[i].weight < min1) {
43-
min2 = min1;
44-
*s2 = *s1;
45-
min1 = HT[i].weight;
46-
*s1 = i;
47-
} else {
48-
min2 = HT[i].weight;
49-
*s2 = i;
36+
*d2 = i;
37+
38+
if (h[*d1].weight > h[*d2].weight) {
39+
tmp = *d1;
40+
*d1 = *d2;
41+
*d2 = tmp;
5042
}
51-
//两个结点和后续的所有未构建成树的结点做比较
52-
for (int j = i + 1; j <= end; j++) {
53-
//如果有父结点，直接跳过，进行下一个
54-
if (HT[j].parent != 0) {
55-
continue;
56-
}
57-
//如果比最小的还小，将min2=min1，min1赋值新的结点的下标
58-
if (HT[j].weight < min1) {
59-
min2 = min1;
60-
min1 = HT[j].weight;
61-
*s2 = *s1;
62-
*s1 = j;
63-
}
64-
//如果介于两者之间，min2赋值为新的结点的位置下标
65-
else if (HT[j].weight >= min1 && HT[j].weight < min2) {
66-
min2 = HT[j].weight;
67-
*s2 = j;
43+
44+
i++;
45+
while (i <= n) {
46+
if (h[i].parent != -1) {
47+
i++;
48+
} else {
49+
if (h[i].weight < h[*d1].weight) {
50+
*d2 = *d1;
51+
*d1 = i;
52+
} else if (h[i].weight >= h[*d1].weight && h[i].weight < h[*d2].weight) {
53+
*d2 = i;
54+
}
55+
i++;
6856
}
6957
}
7058
}
7159

72-
//HT为地址传递的存储哈夫曼树的数组，w为存储结点权重值的数组，n为结点个数
73-
void CreateHuffmanTree(HuffmanTree * HT, int *w, int n)
60+
static void creat_hftree(hftree **hft, int *w, int s)
7461
{
75-
if (n <= 1)
76-
return; // 如果只有一个编码就相当于0
77-
int m = 2 * n - 1; // 哈夫曼树总节点数，n就是叶子结点
78-
*HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode)); // 0号位置不用
79-
HuffmanTree p = *HT;
80-
// 初始化哈夫曼树中的所有结点
81-
for (int i = 1; i <= n; i++) {
82-
(p + i)->weight = *(w + i - 1);
83-
(p + i)->parent = 0;
84-
(p + i)->left = 0;
85-
(p + i)->right = 0;
62+
int m = 2 * s - 1,
63+
i = 0;
64+
65+
if (s <= 1) {
66+
return ;
67+
}
68+
69+
*hft = (hftree *)malloc((m+1) * sizeof(hftree));
70+
if (NULL == *hft) {
71+
printf("huffman tree malloc failed\n");
72+
return ;
8673
}
87-
//从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
88-
for (int i = n + 1; i <= m; i++) {
89-
(p + i)->weight = 0;
90-
(p + i)->parent = 0;
91-
(p + i)->left = 0;
92-
(p + i)->right = 0;
74+
75+
//init ...
76+
hftree *h = *hft;
77+
for (i = 1; i <= s; i++) {
78+
(h + i)->weight = w[i - 1];
79+
(h + i)->parent = -1;
80+
(h + i)->left = -1;
81+
(h + i)->right = -1;
82+
}
83+
for (; i <= m; i++) {
84+
(h + i)->weight = -1;
85+
(h + i)->parent = -1;
86+
(h + i)->left = -1;
87+
(h + i)->right = -1;
9388
}
94-
//构建哈夫曼树
95-
for (int i = n + 1; i <= m; i++) {
96-
int s1, s2;
97-
Select(*HT, i - 1, &s1, &s2);
98-
(*HT)[s1].parent = (*HT)[s2].parent = i;
99-
(*HT)[i].left = s1;
100-
(*HT)[i].right = s2;
101-
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
89+
90+
//creat ...
91+
for (i = s + 1; i <= m; i++) {
92+
int d1, d2;
93+
weight_select(h, i - 1, &d1, &d2);
94+
printf("d1 = %d, d2 = %d\n", d1, d2);
95+
h[d1].parent = h[d2].parent = i;
96+
h[i].left = d1;
97+
h[i].right = d2;
98+
h[i].weight = h[d1].weight + h[d2].weight;
10299
}
100+
103101
}
104102

105-
//HT为哈夫曼树，HC为存储结点哈夫曼编码的二维动态数组，n为结点的个数
106-
void HuffmanCoding(HuffmanTree HT, HuffmanCode * HC, int n)
103+
static void inorder_traverse(hftree *h, int m, int *w)
107104
{
108-
*HC = (HuffmanCode) malloc((n + 1) * sizeof(char *));
109-
char *cd = (char *)malloc(n * sizeof(char)); //存放结点哈夫曼编码的字符串数组
110-
cd[n - 1] = '\0'; //字符串结束符
111-
112-
for (int i = 1; i <= n; i++) {
113-
//从叶子结点出发，得到的哈夫曼编码是逆序的，需要在字符串数组中逆序存放
114-
int start = n - 1;
115-
//当前结点在数组中的位置
116-
int c = i;
117-
//当前结点的父结点在数组中的位置
118-
int j = HT[i].parent;
119-
// 一直寻找到根结点
120-
while (j != 0) {
121-
// 如果该结点是父结点的左孩子则对应路径编码为0，否则为右孩子编码为1
122-
if (HT[j].left == c)
123-
cd[--start] = '0';
124-
else
125-
cd[--start] = '1';
126-
//以父结点为孩子结点，继续朝树根的方向遍历
127-
c = j;
128-
j = HT[j].parent;
129-
}
130-
//跳出循环后，cd数组中从下标 start 开始，存放的就是该结点的哈夫曼编码
131-
(*HC)[i] = (char *)malloc((n - start) * sizeof(char));
132-
strcpy((*HC)[i], &cd[start]);
105+
int l, r;
106+
107+
if (h[m].left == -1) {
108+
printf("%d, m=%d w=%d\n", h[m].left, m, w[m-1]);
109+
} else if (h[m].right == -1) {
110+
printf("%d, m=%d w=%d\n", h[m].right, m, w[m-1]);
111+
} else {
112+
l = h[m].left;
113+
printf("l = %d\n", l);
114+
inorder_traverse(h, l, w);
115+
r = h[m].right;
116+
printf("r = %d\n", r);
117+
inorder_traverse(h, r, w);
133118
}
134-
//使用malloc申请的cd动态数组需要手动释放
135-
free(cd);
136119
}
137120

138-
//打印哈夫曼编码的函数
139-
void PrintHuffmanCode(HuffmanCode htable, int *w, int n)
121+
static void huffman_coding_nodeorder(hftree *h, hfcode **hc, int s)
140122
{
141-
printf("Huffman code : \n");
142-
for (int i = 1; i <= n; i++)
143-
printf("%d code = %s\n", w[i - 1], htable[i]);
123+
char *cd = (char *)malloc((n-1) * sizeof(char));
124+
*hc = (hfcode *)malloc(s * sizeof(hfcode));
125+
126+
for (i = 1; i <= s; i++) {
127+
start = n - 1;
128+
while (h[i].parent != -1) {
129+
j = h[i].parent;
130+
if (h[j].left == i) {
131+
cd[--start] = '0';
132+
} else {
133+
cd[--start] = '1';
134+
}
135+
136+
i = j;
137+
}
138+
(*hc)
139+
memcpy((*hc)[i], &cd[start], s - start);
140+
}
141+
144142
}
145143

146-
int main(void)
144+
int main()
147145
{
148-
int w[5] = { 2, 8, 7, 6, 5 };
149-
int n = 5;
150-
HuffmanTree htree;
151-
HuffmanCode htable;
152-
CreateHuffmanTree(&htree, w, n);
153-
HuffmanCoding(htree, &htable, n);
154-
PrintHuffmanCode(htable, w, n);
146+
int i;
147+
int w[] = {2, 8, 7, 6, 5, 4};
148+
int s = sizeof(w)/sizeof(w[0]);
149+
hftree *hft = NULL;
150+
151+
creat_hftree(&hft, w, s);
152+
for (i = 0; i < s; i++) {
153+
printf("%d ", w[i]);
154+
}
155+
printf("\n");
156+
157+
inorder_traverse(hft, 2 * s - 1, w);
158+
159+
hfcode *hc = NULL;
160+
//from node
161+
huffman_coding_nodeorder(hft, &hc, s);
162+
163+
//from root
164+
//huffman_coding_rootorder(hft, 2 * s - 1);
165+
166+
free(hft);
155167
return 0;
156168
}

0 commit comments

Comments
 (0)
0