|
发表于 2019-2-20 16:51:12
|
显示全部楼层
本楼为最佳答案
好了
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #define DATA_SIZE 256
- #define CODE_TABLE_SIZE 256
- typedef struct noeud_tag
- {
- char ch;
- size_t freq;
- struct noeud_tag *fils_g; // 左枝点
- struct noeud_tag *fils_d; // 右枝点
- } noeud_t;
- typedef struct
- {
- char code[100];
- } code_item_t;
- // 能不改的函数尽量不改
- void frequence(int *freq, char *chaine) // 此函数是为了找出字符串里每个ASCII字符的频率
- {
- char car;
- int i;
- int length;
- // 计算字符串的长度
- length = strlen(chaine);
- //建立一个表格 现在频率全是0
- for(i = 0; i < 256; i++)
- {
- freq[i] = 0;
- }
- // 计算字符串里每个字母的频率
- for(i = 0; i < length; i++)
- {
- car = chaine[i];
- freq[car]++;
- }
- return;
- }
- // 重写此函数
- size_t init_noeud(noeud_t *data, int *freq)
- {
- size_t index = 0;
- for(size_t i = 0; i < DATA_SIZE; ++i)
- {
- if(freq[i] > 0)
- {
- memset(&data[index], 0, sizeof(data[index]));
- data[index].ch = (char)i;
- data[index].freq = freq[i];
- ++index;
- }
- }
- return index;
- }
- // 按频率从小到大排序
- void sort(noeud_t *data, size_t length)
- {
- for(size_t i = 0; i < length; ++i)
- {
- for(size_t j = i + 1; j < length; ++j)
- {
- if(data[i].freq > data[j].freq)
- {
- noeud_t tmp = data[i];
- data[i] = data[j];
- data[j] = tmp;
- }
- }
- }
- }
- noeud_t *huffman_tree(noeud_t *data, size_t length)
- {
- size_t index = DATA_SIZE; // 指向最后一个可用位置
- while(length != 1)
- {
- sort(data, length);
- data[--index] = data[0];
- data[--index] = data[1];
- memset(&data[0], 0, sizeof(data[0]));
- data[0].fils_g = &data[index + 1];
- data[0].fils_d = &data[index];
- data[0].freq = data[0].fils_g->freq + data[0].fils_d->freq;
- for(size_t i = 1; i < length - 1; ++i)
- data[i] = data[i + 1];
- --length;
- }
- return &data[0];
- }
- void preorder_traversal(noeud_t *root)
- {
- if(root)
- {
- printf("\nch:\t\'%c\'\n", root->ch);
- printf("pre:\t%u\n", root->freq);
- preorder_traversal(root->fils_g);
- preorder_traversal(root->fils_d);
- }
- }
- void traverse_tree(noeud_t *root, code_item_t *code_table, char code[1024], size_t index)
- {
- if(!root->fils_g && !root->fils_d)
- {
- code[index] = '\0';
- strcpy(code_table[root->ch].code, code);
- }
- if(root->fils_g)
- {
- code[index] = '0';
- traverse_tree(root->fils_g, code_table, code, index + 1);
- }
- if(root->fils_d)
- {
- code[index] = '1';
- traverse_tree(root->fils_d, code_table, code, index + 1);
- }
- }
- void init_code_table(code_item_t *code_table, noeud_t *code_tree)
- {
- char code[1024];
- size_t index = 0;
- memset(code_table, 0, sizeof(code_item_t) * CODE_TABLE_SIZE);
- traverse_tree(code_tree, code_table, code, index);
- }
- // 尽量保证和原来一样,这里也使用数组
- // 说真的,数组很不好用
- // 为了和原来尽量一样,不得不用
- int main(void)
- {
- char *chaine = "aaababaaababbbbbbbbbbbbabcddddbcaaabbbbbbbbbbbabbaa";
- int freq[256];
- size_t length;
- noeud_t data[DATA_SIZE];
- noeud_t *code_tree;
- code_item_t code_table[CODE_TABLE_SIZE];
- frequence(freq, chaine);
- length = init_noeud(data, freq);
- code_tree = huffman_tree(data, length);
- init_code_table(code_table, code_tree);
- printf("a: %s\n", code_table['a'].code);
- printf("b: %s\n", code_table['b'].code);
- printf("c: %s\n", code_table['c'].code);
- printf("d: %s\n", code_table['d'].code);
- preorder_traversal(code_tree);
- return(EXIT_SUCCESS);
- }
复制代码
- a: 01
- b: 1
- c: 000
- d: 001
- ch: ' '
- pre: 51
- ch: ' '
- pre: 21
- ch: ' '
- pre: 6
- ch: 'c'
- pre: 2
- ch: 'd'
- pre: 4
- ch: 'a'
- pre: 15
- ch: 'b'
- pre: 30
- 请按任意键继续. . .
复制代码
|
|