数据结构实验—哈夫曼树的编码和译码
1.建立哈夫曼树
以数组的形式建立哈夫曼树
类似于一下形式
每次找出两个最小的权,将其和放在数组weight位置第一个权为空的位置,将两个最小权的下标放入该点的lchild,rchild中,将两个最小权的parent改为该点,第一次执行后变为
每次循环找出最小的两个权,记录其位置,然后进行相应的赋值就行
实现代码
for (int i = num; i < 2 * num - 1; i++) { int m = 999, n = 999; int loc1 = -1, loc2 = -1; for (int j = 0; j < i; j++) { if (T[j][0] < m && T[j][1] == 0) { m = T[j][0]; loc1 = j; } } for (int j = 0; j < i; j++) { if (T[j][0] < n && T[j][1] == 0) { if (j != loc1) { n = T[j][0]; loc2 = j; } } } T[loc1][1] = i; T[loc2][1] = i; T[i][0] = m + n; T[i][2] = loc1; T[i][3] = loc2; }
建立哈夫曼编码
示例哈夫曼树
搜索数组下标为1在左右孩子那两列中的位置,若为左则记0,右记1,再搜索1的双亲节点在左右孩子那两列的中的位置,依次找到每个节点的编码,这样搜索出来是编码的倒置,最后在逆置就好了。
实现代码
for (int i = 0; i < num; i++) { int m; m = i; for (int j = num; j < 2*num - 1; j++) { int status = 0; if (T[j][2] == m) { T_code[i] = T_code[i] + '0'; status = 1; } if (T[j][3] == m) { T_code[i] = T_code[i] + '1'; status = 1; } if (status == 1) { m = j; } } } for (int i = 0; i < num; i++) { reverse(T_code[i].begin(), T_code[i].end()); }
2.编码,建立与权值下标一一对应的数组,存放字母
依次读入每个字母,找到对应的编码并输出
实现代码
for (int i = 0; message[i] != '\0'; i++) { tree.setCode(message[i]); } void setCode(char a) { for (int i = 0; i < num; i++) { if (words[i] == a) { code = code + T_code[i]; } } }
3.译码
输入代码,设一个string变量,将代码第一个数字赋给变量,如有对应项则记录信息,将变量重置为空。如没有,则将代码前两位赋给变量,直到找到对应项为止。
实现代码
void setMessage(char a) { int status = 0; code_message = code_message + a; for (int i = 0; i < num; i++) { if (code_message == T_code[i]) { status = 1; message = message + words[i]; } } if (status == 1) { code_message = ""; } }