[已解决]哈夫曼码结构体的疑问

qpwoeiruyt

人造人 发表于 2019-2-19 18:19
我还是没有问到我需要的内容，我举个例子

下面这个程序

a：001
b：01
c：1

这样子啊  但上面的001 01 1是我随便写的 正确的要写完huffman code才能显示出来

人造人

qpwoeiruyt 发表于 2019-2-20 01:29
a：001
b：01
c：1

嗯，要的就是这个
我需要研究研究

人造人

我看懂这个代码了，但是我没办法做到只是修改huffman_code函数
我可以随意修改这个代码，是吧？

qpwoeiruyt

人造人 发表于 2019-2-19 19:11
我看懂这个代码了，但是我没办法做到只是修改huffman_code函数
我可以随意修改这个代码，是吧？

可以

人造人

这棵树已经创建好了，时间不早了，先睡了，睡醒以后再想如何得到你想要的输出

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. #define DATA_SIZE 256
   
6. 
   
7. typedef struct noeud_tag
   
8. {
   
9.         char ch;
   
10.         size_t freq;
    
11.         struct noeud_tag *fils_g;        // 左枝点
    
12.         struct noeud_tag *fils_d;        // 右枝点
    
13. } noeud_t;
    
14. 
    
15. // 能不改的函数尽量不改
    
16. void frequence(int *freq, char *chaine)                // 此函数是为了找出字符串里每个ASCII字符的频率
    
17. {
    
18.         char car;
    
19.         int i;
    
20.         int length;
    
21. 
    
22.         // 计算字符串的长度
    
23.         length = strlen(chaine);
    
24. 
    
25.         //建立一个表格 现在频率全是0
    
26.         for(i = 0; i < 256; i++)
    
27.         {
    
28.                 freq[i] = 0;
    
29.         }
    
30. 
    
31.         // 计算字符串里每个字母的频率
    
32.         for(i = 0; i < length; i++)
    
33.         {
    
34.                 car = chaine[i];
    
35.                 freq[car]++;
    
36.         }
    
37. 
    
38.         return;
    
39. }
    
40. 
    
41. // 重写此函数
    
42. size_t init_tab_noeud(noeud_t *data, int *freq)
    
43. {
    
44.         size_t index = 0;
    
45.         for(size_t i = 0; i < DATA_SIZE; ++i)
    
46.         {
    
47.                 if(freq[i] > 0)
    
48.                 {
    
49.                         memset(&data[index], 0, sizeof(data[index]));
    
50.                         data[index].ch = (char)i;
    
51.                         data[index].freq = freq[i];
    
52.                         ++index;
    
53.                 }
    
54.         }
    
55. 
    
56.         return index;
    
57. }
    
58. 
    
59. // 按频率从小到大排序
    
60. void sort(noeud_t *data, size_t length)
    
61. {
    
62.         for(size_t i = 0; i < length; ++i)
    
63.         {
    
64.                 for(size_t j = i + 1; j < length; ++j)
    
65.                 {
    
66.                         if(data[i].freq > data[j].freq)
    
67.                         {
    
68.                                 noeud_t tmp = data[i];
    
69.                                 data[i] = data[j];
    
70.                                 data[j] = tmp;
    
71.                         }
    
72.                 }
    
73.         }
    
74. }
    
75. 
    
76. noeud_t *huffman_code(noeud_t *data, size_t length)
    
77. {
    
78.         size_t index = DATA_SIZE;        // 指向最后一个可用位置
    
79.         while(length != 1)
    
80.         {
    
81.                 sort(data, length);
    
82. 
    
83.                 data[--index] = data[0];
    
84.                 data[--index] = data[1];
    
85. 
    
86.                 memset(&data[0], 0, sizeof(data[0]));
    
87.                 data[0].fils_g = &data[index + 1];
    
88.                 data[0].fils_d = &data[index];
    
89.                 data[0].freq = data[0].fils_g->freq + data[0].fils_d->freq;
    
90. 
    
91.                 for(size_t i = 1; i < length - 1; ++i)
    
92.                         data[i] = data[i + 1];
    
93.                 --length;
    
94.         }
    
95.         return &data[0];
    
96. }
    
97. 
    
98. void preorder_traversal(noeud_t *root)
    
99. {
    
100.         if(root)
     
101.         {
     
102.                 printf("\nch:\t\'%c\'\n", root->ch);
     
103.                 printf("pre:\t%u\n", root->freq);
     
104.                 preorder_traversal(root->fils_g);
     
105.                 preorder_traversal(root->fils_d);
     
106.         }
     
107. }
     
108. 
     
109. // 尽量保证和原来一样，这里也使用数组
     
110. // 说真的，数组很不好用
     
111. // 为了和原来尽量一样，不得不用
     
112. int main(void)
     
113. {
     
114.         char *chaine = "aaababaaababbbbbbbbbbbbabcddddbcaaabbbbbbbbbbbabbaa";
     
115.         int freq[256];
     
116.         size_t length;
     
117.         noeud_t data[DATA_SIZE];
     
118.         noeud_t *racine;
     
119. 
     
120.         frequence(freq, chaine);
     
121.         length = init_tab_noeud(data, freq);
     
122.         racine = huffman_code(data, length);
     
123.         preorder_traversal(data);
     
124. 
     
125.         return(EXIT_SUCCESS);
     
126. }
     

复制代码

1. 
   
2. ch:     ' '
   
3. pre:    51
   
4. 
   
5. ch:     ' '
   
6. pre:    21
   
7. 
   
8. ch:     ' '
   
9. pre:    6
   
10. 
    
11. ch:     'c'
    
12. pre:    2
    
13. 
    
14. ch:     'd'
    
15. pre:    4
    
16. 
    
17. ch:     'a'
    
18. pre:    15
    
19. 
    
20. ch:     'b'
    
21. pre:    30
    
22. 请按任意键继续. . .

复制代码

qpwoeiruyt

人造人 发表于 2019-2-19 20:30
这棵树已经创建好了，时间不早了，先睡了，睡醒以后再想如何得到你想要的输出

大佬辛苦了   早点休息

人造人

好了

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. 
   
5. #define DATA_SIZE        256
   
6. #define CODE_TABLE_SIZE        256
   
7. 
   
8. typedef struct noeud_tag
   
9. {
   
10.         char ch;
    
11.         size_t freq;
    
12.         struct noeud_tag *fils_g;        // 左枝点
    
13.         struct noeud_tag *fils_d;        // 右枝点
    
14. } noeud_t;
    
15. 
    
16. typedef struct
    
17. {
    
18.         char code[100];
    
19. } code_item_t;
    
20. 
    
21. // 能不改的函数尽量不改
    
22. void frequence(int *freq, char *chaine)                // 此函数是为了找出字符串里每个ASCII字符的频率
    
23. {
    
24.         char car;
    
25.         int i;
    
26.         int length;
    
27. 
    
28.         // 计算字符串的长度
    
29.         length = strlen(chaine);
    
30. 
    
31.         //建立一个表格 现在频率全是0
    
32.         for(i = 0; i < 256; i++)
    
33.         {
    
34.                 freq[i] = 0;
    
35.         }
    
36. 
    
37.         // 计算字符串里每个字母的频率
    
38.         for(i = 0; i < length; i++)
    
39.         {
    
40.                 car = chaine[i];
    
41.                 freq[car]++;
    
42.         }
    
43. 
    
44.         return;
    
45. }
    
46. 
    
47. // 重写此函数
    
48. size_t init_noeud(noeud_t *data, int *freq)
    
49. {
    
50.         size_t index = 0;
    
51.         for(size_t i = 0; i < DATA_SIZE; ++i)
    
52.         {
    
53.                 if(freq[i] > 0)
    
54.                 {
    
55.                         memset(&data[index], 0, sizeof(data[index]));
    
56.                         data[index].ch = (char)i;
    
57.                         data[index].freq = freq[i];
    
58.                         ++index;
    
59.                 }
    
60.         }
    
61. 
    
62.         return index;
    
63. }
    
64. 
    
65. // 按频率从小到大排序
    
66. void sort(noeud_t *data, size_t length)
    
67. {
    
68.         for(size_t i = 0; i < length; ++i)
    
69.         {
    
70.                 for(size_t j = i + 1; j < length; ++j)
    
71.                 {
    
72.                         if(data[i].freq > data[j].freq)
    
73.                         {
    
74.                                 noeud_t tmp = data[i];
    
75.                                 data[i] = data[j];
    
76.                                 data[j] = tmp;
    
77.                         }
    
78.                 }
    
79.         }
    
80. }
    
81. 
    
82. noeud_t *huffman_tree(noeud_t *data, size_t length)
    
83. {
    
84.         size_t index = DATA_SIZE;        // 指向最后一个可用位置
    
85.         while(length != 1)
    
86.         {
    
87.                 sort(data, length);
    
88. 
    
89.                 data[--index] = data[0];
    
90.                 data[--index] = data[1];
    
91. 
    
92.                 memset(&data[0], 0, sizeof(data[0]));
    
93.                 data[0].fils_g = &data[index + 1];
    
94.                 data[0].fils_d = &data[index];
    
95.                 data[0].freq = data[0].fils_g->freq + data[0].fils_d->freq;
    
96. 
    
97.                 for(size_t i = 1; i < length - 1; ++i)
    
98.                         data[i] = data[i + 1];
    
99.                 --length;
    
100.         }
     
101.         return &data[0];
     
102. }
     
103. 
     
104. void preorder_traversal(noeud_t *root)
     
105. {
     
106.         if(root)
     
107.         {
     
108.                 printf("\nch:\t\'%c\'\n", root->ch);
     
109.                 printf("pre:\t%u\n", root->freq);
     
110.                 preorder_traversal(root->fils_g);
     
111.                 preorder_traversal(root->fils_d);
     
112.         }
     
113. }
     
114. 
     
115. void traverse_tree(noeud_t *root, code_item_t *code_table, char code[1024], size_t index)
     
116. {
     
117.         if(!root->fils_g && !root->fils_d)
     
118.         {
     
119.                 code[index] = '\0';
     
120.                 strcpy(code_table[root->ch].code, code);
     
121.         }
     
122.         if(root->fils_g)
     
123.         {
     
124.                 code[index] = '0';
     
125.                 traverse_tree(root->fils_g, code_table, code, index + 1);
     
126.         }
     
127.         if(root->fils_d)
     
128.         {
     
129.                 code[index] = '1';
     
130.                 traverse_tree(root->fils_d, code_table, code, index + 1);
     
131.         }
     
132. }
     
133. 
     
134. void init_code_table(code_item_t *code_table, noeud_t *code_tree)
     
135. {
     
136.         char code[1024];
     
137.         size_t index = 0;
     
138.         memset(code_table, 0, sizeof(code_item_t) * CODE_TABLE_SIZE);
     
139.         traverse_tree(code_tree, code_table, code, index);
     
140. }
     
141. 
     
142. // 尽量保证和原来一样，这里也使用数组
     
143. // 说真的，数组很不好用
     
144. // 为了和原来尽量一样，不得不用
     
145. int main(void)
     
146. {
     
147.         char *chaine = "aaababaaababbbbbbbbbbbbabcddddbcaaabbbbbbbbbbbabbaa";
     
148.         int freq[256];
     
149.         size_t length;
     
150.         noeud_t data[DATA_SIZE];
     
151.         noeud_t *code_tree;
     
152.         code_item_t code_table[CODE_TABLE_SIZE];
     
153. 
     
154.         frequence(freq, chaine);
     
155.         length = init_noeud(data, freq);
     
156.         code_tree = huffman_tree(data, length);
     
157.         init_code_table(code_table, code_tree);
     
158. 
     
159.         printf("a: %s\n", code_table['a'].code);
     
160.         printf("b: %s\n", code_table['b'].code);
     
161.         printf("c: %s\n", code_table['c'].code);
     
162.         printf("d: %s\n", code_table['d'].code);
     
163. 
     
164.         preorder_traversal(code_tree);
     
165.         return(EXIT_SUCCESS);
     
166. }
     

复制代码

1. a: 01
   
2. b: 1
   
3. c: 000
   
4. d: 001
   
5. 
   
6. ch:     ' '
   
7. pre:    51
   
8. 
   
9. ch:     ' '
   
10. pre:    21
    
11. 
    
12. ch:     ' '
    
13. pre:    6
    
14. 
    
15. ch:     'c'
    
16. pre:    2
    
17. 
    
18. ch:     'd'
    
19. pre:    4
    
20. 
    
21. ch:     'a'
    
22. pre:    15
    
23. 
    
24. ch:     'b'
    
25. pre:    30
    
26. 请按任意键继续. . .

复制代码

qpwoeiruyt

人造人 发表于 2019-2-20 09:51
好了

谢谢啦  问一下最后那个图是怎样打印出来的？

人造人

qpwoeiruyt 发表于 2019-2-20 19:54
谢谢啦  问一下最后那个图是怎样打印出来的？

用PPT自己画的
^_^

人造人

qpwoeiruyt 发表于 2019-2-20 19:54
谢谢啦  问一下最后那个图是怎样打印出来的？

演示文稿1.zip (28.45 KB, 下载次数: 1)

2019-2-20 20:05 上传

点击文件名下载附件

qpwoeiruyt

人造人 发表于 2019-2-20 13:05

谢谢啦   大神的code能不能写点注释进去  有一些你写的东西不是太清楚 就是每个函数前头简单解释一下我就会了

人造人

qpwoeiruyt 发表于 2019-2-21 14:37
谢谢啦   大神的code能不能写点注释进去  有一些你写的东西不是太清楚 就是每个函数前头简单解释一下我就 ...

哪个函数看不懂？
^_^

qpwoeiruyt

人造人 发表于 2019-2-21 07:42
哪个函数看不懂？
^_^

大致都懂了

现在又来了个新问题

大佬会用flex编写词法分析器吗？写了个逆波兰表达式的c文件 如何将它写成flex呢？ 里面的结构看上去挺相近的

人造人

qpwoeiruyt 发表于 2019-2-22 00:15
大致都懂了

现在又来了个新问题

加我qq：1440332527
我没试过，不过可以研究研究
^_^

qpwoeiruyt

人造人 发表于 2019-2-21 17:38
加我qq：1440332527
我没试过，不过可以研究研究
^_^

大佬有微信吗？qq忘了密码 现在一直用微信

人造人

qpwoeiruyt 发表于 2019-2-22 00:40
大佬有微信吗？qq忘了密码 现在一直用微信

没有微信，我一直用qq
我的微信密码忘了
^_^

人造人

qpwoeiruyt 发表于 2019-2-22 00:15
大致都懂了

现在又来了个新问题

那就在这里说吧
详细描述一下这个问题