该贴无效，请删除
本帖最后由 小纸张二号 于 2019-12-21 19:32 编辑设字符集为10个字符，其出现频度如下表所示。先建哈夫曼树，输出对应字符的译码，再利用此树对报文“ADEC”进行编码和译码，输出对应
字符 A B C D E F G H I J
频度 24 20 1 7 9 11 8 15 2 3 //vs的调试功能太好用，我是在vs里写的代码，但其不支持C语言的部分功能,例如变长数组，例如直接使用strlen（即使在C环境下） \
所以使用宏定义#ifdef __cplusplus确保程序在传统C环境下也能运行；
//不使用数组代替二叉树，因为霍夫曼树可能非常“不完全”，其使用数组代替时占用空间可能过大；
#ifdef __cplusplus
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <malloc.h>
#include <memory.h>
#include <string.h>
#endif
#include <stdio.h>
#define _Out_
#ifndef NULL
#define NULL 0
#endif
typedef char string;//单个字符编码长度不超过128；
//霍夫曼书的节点
typedef struct node_t {
struct node_t* left;
struct node_t* right;
struct node_t* parent;
int freq;
char code;
}node;
//删除树
void DestroyTree(node* root) {
if (!root) return;
DestroyTree(root->left);
DestroyTree(root->right);
free(root);
};
//生成编码
string* generateHuffmanCode(char ch[], int freq[], int N, string _Out_ *codelist) {
int i, j, k;
#ifdef __cplusplus
node *pool, *pool_backup;//c++环境下不支持变长数组；
#else
node *pool, *pool_backup;
#endif
//为每个字符创建节点
for (i = 0; i < N; ++i) {
pool = (node*)malloc(sizeof(node));
pool->freq = freq;
pool->left = NULL;
pool->right = NULL;
pool->parent = NULL;
}
//做一个备份
memcpy(pool_backup, pool, sizeof(pool));
//每次选取两个节点组合，共需组合N-1次
for (i = 0; i < N - 1; ++i) {
int min_freq; //频次最低的两个节点的编号
memset(min_freq, -1, sizeof(min_freq));
for (j = 0; j < N - i; ++j) {
if (min_freq == -1 || pool->freq < pool]->freq) {
min_freq = min_freq;
min_freq = j;
}
else if (min_freq == -1 || pool->freq < pool]->freq) {
min_freq = j;
}
}
//组合两个节点，新节点的频次是两个子节点之和
node* sum = (node*)malloc(sizeof(node));
sum->left = pool];
sum->right = pool];
sum->parent = NULL;
sum->left->code = '0';
sum->right->code = '1';
sum->left->parent = sum;
sum->right->parent = sum;
sum->freq = sum->left->freq + sum->right->freq;
//于节点池中，用新节点代替原有子节点，并移除另一个子节点
pool] = sum;
for (j = min_freq; j + 1 < N - i; ++j) {
pool = pool;
}
}
//霍夫曼树生成完毕
pool->code = 0;
for (i = 0; i < 128; ++i) {
codelist = 0;
}
//对于每一个字符对应的节点（即叶节点），向上搜寻直到根节点，路径即为颠倒的编码；
for (i = 0; i < N; ++i) {
node* p = pool_backup;
char *line = codelist];
for (j = 0; p != NULL; ++j, p = p->parent) {
line = p->code;
}
j--;
//再将颠倒的编码回正
for (k = 0; k < j / 2; ++k) {
char t = codelist];
line = line;
line = t;
}
}
//删除霍夫曼树，释放空间
DestroyTree(pool);
return codelist;
}
//根据编码表编码字符串
char* encode(char* sz, string codelist[], char* _Out_ szEncoded) {
char* p = szEncoded;
while (*sz) {
int l = strlen(codelist[*sz]);
strcpy(p, codelist[*sz]);
p += l;
sz++;
}
return szEncoded;
}
//解码字符串
char* decode(char* szEncoded, string codelist[], char* _Out_ szDecoded) {
int i, j;
//根据编码表重新生成树
node* root = (node*)malloc(sizeof(node));
root->left = NULL;
root->right = NULL;
for (i = 0; i < 128; ++i) {
node* p;
char* pch;
for (p = root, pch = codelist; *pch != 0; ++pch) {
if (*pch == '0') {
if (p->left == NULL) {
p->left = (node*)malloc(sizeof(node));
p->left->left = NULL;
p->left->right = NULL;
}
p = p->left;
}
else if (*pch == '1') {
if (p->right == NULL) {
p->right = (node*)malloc(sizeof(node));
p->right->left = NULL;
p->right->right = NULL;
}
p = p->right;
}
}
p->code = i;
}
//根据编码的0或1，进入当前节点的左子树或右子树，直到到达叶节点，并记录
char* pch, *pret;
node* p;
for (p = root, pch = szEncoded, pret = szDecoded; *pch != 0; ++pch) {
if (*pch == '0') {
p = p->left;
}
else {
p = p->right;
}
if (p->left == NULL) {
*pret++ = p->code;
p = root;
}
}
//删除树，释放空间
DestroyTree(root);
*pret = '\0';
return szDecoded;
}
int main() {
string codelist;
char sz[] = { 'A','B','C','D','E','F','G','H','I','J'};
int freq[] = { 24,20,1,7,9,11,8,15,2,3};
generateHuffmanCode(sz, freq, sizeof(sz), codelist);
printf("========编码表================\n");
unsigned char c;
for (c = 0; c < 128; ++c) {
if (codelist == 0) continue;
printf("%c:%s\n", c, codelist);
}
char a[] = "ADEC";
char code;
char b;
encode(a, codelist, code);
decode(code, codelist, b);
printf("===================================\n");
printf("%s 的编码结果为%s\n", a, code);
printf("%s 的解码结果为%s\n", code, b);
#ifdef __cplusplus
system("pause");
#endif
}
页:
[1]