哈夫曼树编码
#include
#include
#define MAX_NODE 1024
#define MAX_WEIGHT 4096
typedef struct HaffmanTreeNode {
char ch, code[15];
int weight;
int parent, lchild, rchild;
} HTNode, *HaTree;
typedef struct {
HTNode arr[MAX_NODE];
int total;
} HTree;
/* 统计字符出现的频率 */
int statistic_char(char *text, HTree *t){
int i, j;
int text_len = strlen(text);
t->total = 0;
for (i=0; itotal; j++) if (t->arr[j].ch == text[i]){
t->arr[j].weight ++;
break;
}
if (j==t->total) {
t->arr[t->total].ch = text[i];
t->arr[t->total].weight = 1;
t->total ++;
}
}
printf("char frequence\n");
for (i=0; itotal; i++)
printf("'%c' %d\n", t->arr[i].ch,
t->arr[i].weight);
printf("\n");
return t->total;
}
int create_htree(HTree *t)
{
int i;
int total_node = t->total * 2 - 1;
int min1, min2; /* 权最小的两个结点 */
int min1_i, min2_i; /* 权最小结点对
应的编号 */
int leaves = t->total;
for (i=0; iarr[i].parent = -1;
t->arr[i].rchild = -1;
t->arr[i].lchild = -1;
}
while (t->total < total_node) {
min1 = min2 = MAX_WEIGHT;
for (i=0; itotal; i++) { /* 对每一个结点 */
if (t->arr[i].parent == -1 /* 结点没有被合并 */
&& t->arr[i].weight < min2) { /* 结点的权比最小权小 */
if (t->arr[i].weight < min1) { /* 如果它比最小的结点还小 */
min2_i = min1_i; min2 = min1;
min1_i = i; min1 = t->arr[i].weight;
}
else
{
min2_i = i; min2 = t->arr[i].weight;
}
}
}
t->arr[t->total].weight = min1 + min2;
t->arr[t->total].parent = -1;
t->arr[t->total].lchild = min1_i;
t->arr[t->total].rchild = min2_i;
t->arr[min1_i].parent = t->total;
t->arr[min2_i].parent = t->total;
t->arr[t->total].ch = ' ';
t->total ++;
}
return 0;
}
/* 对哈夫曼树进行编码 */
void coding(HTree *t, int head_i, char *code)
{
if ( head_i == -1) return;
if (t->arr[head_i].lchild == -1 && t->arr[head_i].rchild == -1) {
strcpy(t->arr[head_i].code, code);
printf("'%c': %s\n",
t->arr[head_i].ch, t->arr[head_i].code);
}
else {
int len = strlen(code);
strcat(code, "0");
coding(t, t->arr[head_i].lchild, code);
code[len] = '1';
coding(t, t->arr[head_i].rchild, code);
code[len] = '\0';
}
}
/* 中序打印树 */
void print_htree_ldr(HTree *t, int head_i, int deep, int* path)
{
int i;
if (head_i == -1) return;
path[deep] = 0;
print_htree_ldr(t, t->arr[head_i].lchild, deep + 1, path);
if (deep) printf(" ");
for (i=1; iarr[head_i].lchild == -1 && t->arr[head_i].rchild == -1)
printf("%s?? %d '%c'\n", dir?
"?":"?",
t->arr[head_i].weight, t->arr[head_i].ch);
else if (head_i != t->total-1)
printf("%s?%02d?\n", dir? "?":"?",
t->arr[head_i].weight);
else
printf(" %02d?\n",
t->arr[head_i].weight);
path[deep] = 1;
print_htree_ldr(t, t->arr[head_i].rchild, deep + 1, path);
}
/* 对字符进行编码 */
void code_string(char *text, HTree *t)
{
int i, j, text_len = strlen(text);
int n = 0;
for (i=0; itotal; j++) if (ch == t->arr[j].ch) {
printf("%s ", t->arr[j].code);
n += strlen(t->arr[j].code);
break;
}
}
printf("\n%d chars, Total len = %d\n", text_len, n);
}
int main(int argc, char* argv[])
{
HTree t;
char text[128]="ABAAAAEEEAAACCCCAAAACCDEA";
char code[128] = "";
int path[16]={0};
statistic_char(text, &t);
create_htree(&t);
print_htree_ldr(&t, t.total-1, 0, path);
coding(&t, t.total-1, code);
code_string(text, &t);
return 0;
}
本文档为【哈夫曼树编码】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483