一、Huffman编码
Huffuman编码的过程主要分为两步，第一步根据字符出现的权值构建Huffuman树，第二步，遍历Huffuman树找出对应字符的编码
1. 构建Huffuman树代码如下：
typedef struct iNode { int weight; int parent, lchild, rchild; } huffman_tree, *phuffman_tree;
int sum_weight(int *weight, int len)//计算权值之和 { int sum = 0; for(int i = 0; i < len; i++) sum += weight[i]; return sum; }
void select(huffman_tree *ht, int len, int &s1, int &s2)//搜索ht数组中parent为0的最小两个节点，分别存入s1，s2，len为要搜索的长度
{ s1 = s2 = 0; for(int i = 1; i <= len; i++) { if(ht[i].parent == 0) { if(ht[s1].weight >= ht[i].weight) { s1 = i; s2 = s1; } } } }
void make_tree(int *weight, huffman_tree* ht, int len)//weight是字符的权重，ht是存储二叉树的节点数组 { int m = 2*len - 1; int s1 = 0, s2 = 0; ht[0] = {sun_weight(weight, len) + 1, 0, 0, 0};//0号节点权设置为总权值加1便于select时设置比较初值 for(int i = 1; i <= len; i++) ht[i] = {weight[i - 1], 0, 0, 0}; for( ; i <= m; i++) ht[i] = {0, 0, 0, 0}; for(i = n + 1; i <= m; i++) { select(ht, i - 1, s1, s2); ht[s1].parent = i; ht[s2].parent = i; ht[i].lchild = s1; ht[i].rchild = s2; ht[i].weight = ht[s1].weight + ht[i].weight; } }
1. 构建Huffuman编码
这里有两种构建方法，第一种是由叶子到根的构建，代码如下：
vodi make_code_from_leaf(huffman_tree *ht, int len, huffman_code *hc)//从叶子结点到根的编码过程 { char code[len]; //int start = len; //code[len - 1] = "\0"; for (int i = 1; i <= len; i++) { int start = len; code[--start] = "\0"; int next = i; while (ht[next].parent ! = 0) { if (ht[ht[next].parent].lchild = next) code[--start] = "0"; else code[--start] = "1"; next = ht[next].parent; } strncpy(hc[i], &code[start], len - start); } }
从根节点开始遍历求huffuman编码的代码如下（注意weight这里发挥标记的作用：
void make_code_from_root(huffman_tree *ht, int len, huffman_code *hc) { char code[len]; int clen = 0; int p = 2*len - 1; for ( int i = 1; i <= p ; i++) ht[i].weight = 0; while (p) { if(ht[p].weight == 0) {//左节点遍历 ht[p].weight = 1; if(ht[p].lchild != 0) { p = ht[p].lchild; code[clen++] = "0"; } else if(ht[p].rchild == 0) { code[clen++] = "\0"; hc[p] = (char *)malloc(clen + 1); strcpy([hc[p], code); } } else if (ht[p].weight == 1) {//右子树遍历 ht[p].weight = 2; if (ht[p].rchild != 0) { code[clen++] = "1"; p = ht[p].rchild; } } else { //到达叶子结点回溯另一分支 ht[p].weight = 0; p = ht[p].parent; clen--; } } }
void make_code_from_root(huffman_tree *ht, int len, huffman_code *hc) { char code[len]; int clen = 0; int p = 2*len - 1; for ( int i = 1; i <= p ; i++) ht[i].weight = 0; while (p) { if(ht[p].weight == 0) { ht[p].weight = 1; if(ht[p].lchild != 0) { p = ht[p].lchild; code[clen++] = "0"; } else if(ht[p].rchild == 0) { code[clen++] = "\0"; hc[p] = (char *)malloc(clen + 1); strcpy([hc[p], code); } } else if (ht[p].weight == 1) { ht[p].weight = 2; if (ht[p].rchild != 0) { code[clen++] = "1"; p = ht[p].rchild; } } else { ht[p].weight = 0; p = ht[p].parent; clen--; } } }
void make_code_from_root(huffman_tree *ht, int len, huffman_code *hc) { char code[len]; int clen = 0; int p = 2*len - 1; for ( int i = 1; i <= p ; i++) ht[i].weight = 0; while (p) { if(ht[p].weight == 0) { ht[p].weight = 1; if(ht[p].lchild != 0) { p = ht[p].lchild; code[clen++] = "0"; } else if(ht[p].rchild == 0) { code[clen++] = "\0"; hc[p] = (char *)malloc(clen + 1); strcpy([hc[p], code); } } else if (ht[p].weight == 1) { ht[p].weight = 2; if (ht[p].rchild != 0) { code[clen++] = "1"; p = ht[p].rchild; } } else { ht[p].weight = 0; p = ht[p].parent; clen--; } } }
一、Huffman译码
根据Huffuman编码规则的规则可知，如果所有左子树代表“0”，右子树代表“1”则，可以用搜索码中的“0”来作为字符的分割码，但是要注意最后的全1码的识别其代码如下：
int select_hc(huffman_code *hc, huffman_code s_hc, int len)//根据获得的编码与Huffuman编码表进行比较获取该码字在码表中的位置 { for (int i = 0; i < len; i++) if (strcmp(hc[i], s_hc) == 0) return i; return -1; } /*******************encode function********************** ********************input : code is 0 an 1 serial************************* ********************hc is huffman code table, chars is the encoded characters, hc_len is char sum, len is code length****/ void decode(char *code, huffuman_code *hc, char *chars, char *encode_char, int hc_len, int len)// { char temp_code[10]; for (int i = 0, j = 0, k = 0; i < len; i++) { if (code[i] == "0") { temp_code[k++] = "0"; temp_code[k++] = "\0"; int select_pos = select_hc(hc, temp_code, hc_len); if (select_pps >= 0) encode_char[j++] = chars[select_pos]; else printf("error code : %s invalid", temp_code); k = 0; } else {
temp_code[k++] = "1";
if (strcmp(temp_code, hc[hc_len - 1]) == 0) {//注意处理“1”
temp_code[k++] = "\0";
encode_char[j++] = chars[hc_len - 1];
k = 0;
}
} } }
