#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
请按任意键继续. . .
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
楼主
显身卡
发表于 2019-2-20 01:49:27
