在计算机领域有一棵树，叫做哈夫曼树，最近一周我都被挂在这棵树上，今天晚上，也就是在写博客之前，我才灰溜溜地做完了我的哈夫曼树。
言归正传，所谓哈夫曼树，其实就是最优树，解决文件的压缩与解压，下来就是我对哈夫曼的一些细节问题小结：
0. 首先得知道它的结构体类型:
typedef struct huffman
{
char data; //用来存放字符信息
int weight; //权重，即文件中出现data的次数
int parent, Lhild, Rchild; //结点，用来记录当前结点的双亲，左右孩子
}HTNode, HuffmanTree[MAX + 1]; //HuffmanTree 为结构体数组类型
1.计算结点权重的问题：
typedef struct
{
char ch;
int num;
}Array;
int func(char ch[], int w[], int len, char t[]) //ch为从文件file1.txt中读出的字符串，w将获得权重， len是字符串的长度, t则为得到的有用字符
{
int i, j, count = 0;
Array temp;
Array array[len];
for(i = 1; i <= len; i ++)
{
array[i].ch = ch[i - 1]; //将字符逐个付给结构体成员ch
array[i].num = 0;
printf("array[%d].ch = %c\n", i, array[i].ch);
}
for(i = 1; i <= len; i++) //选择排序
{
if(array[i].ch != ' ') //判断字符是否为空
{
array[i].num = array[i].num + 1;
for(j = i + 1; j <= len; j++)
if(array[i].ch == array[j].ch) //比较字符是否相同
{
array[j].ch = ' '; //将相同字符置空，避免重复使用
array[i].num ++;
}
}
if(array[i].ch != ' ' && array[i].ch != '\n' && array[i].num != 0) //存在字符，并且weight不为空
{ printf("%d, %c\n", array[i].num, array[i].ch);
count++;
w[count] = array[i].num;
t[count] = array[i].ch;
printf("w[%d] = %d, t[%d] = %c\n", count, w[count], count, t[count]);
}
}
return count;
}这是我的个人做法，感觉不是一点点的麻烦，但是蛮实用的。。。在做这块的过程中，也向别人请教过，那就只说说思路，具体做法就自己实现吧。
首先让i = ch; ch是从文件中得到的字符,以ch 的ASCII作为数组Array[]的下标，while((ch = fgetc(fp)) != EOF),如果遇到相同的字符,即ch 的ASCII码值相同,则a[i] ++;
最后也会得到字符串中各个字符的权值。
2 . my_select()函数的建立
原理:从哈夫曼树ht的前i- 1项中选双亲为0,且权值最小的两个结点s1, s2。
void my_select(HuffmanTree ht, int x, int *min1, int *min2)
{
int i, j, temp[x], count = 0;
for(i = 1, j = 1; i <= x; i ++)
{
if(ht[i].parent == 0) //将双亲为0 的结点挑出来，并记录其下标
{
temp[j] = i;
count++;
j ++;
}
}
if(ht[temp[1]].weight < ht[temp[2]].weight) //分别将ht[temp[1]].weight 和ht[temp[2]].weight 中权值小的下标赋给*min1和*min2
{
*min1 = temp[1];
*min2 = temp[2];
} else {
*min1 = temp[2];
*min2 = temp[1];
}
for(j = 3; j <= count; j++)
{
i = temp[j];
if(ht[*min1].weight >ht[i].weight) //从第三个结点开始，判断当前结点和*min1下标的结点的权值大小
{
*min2 = *min1;
*min1 = i;
} else if(ht[*min2].weight > ht[i].weight) { //ht[*min1].weight <= ht[i].weight < ht[*min2].weight
*min2 = i;
}
}
}我个人觉得这个函数还是比较成功的，继续努力！
3.译码原理:
从哈夫曼的根出发，根据每一位编码的‘0’或 ‘1’确定进入左子树或右子树,直到达到叶子结点，便结识了一个相应字符，并把它写在文件里，就是想要得到的结果,贴一段代码：
void HuffmanCode2(HuffmanTree ht, int n)
{
int i, p, q, count = 0;
int l, j = 0;
char ch; //暂时存放从file.txt中读取的内容
FILE *fp, *fs;
fp = fopen("file2.txt", "r");
fs = fopen("file3.txt", "w");
while(1)
{
i = n;
while(ht[i].Lchild != 0 && (ch = fgetc(fp)) != EOF) //判断左孩子是否为空和字符是否存在
{
count ++；
if(ch == '0')
{
i = ht[i].Lchild;
} else if (ch == '1') {
i = ht[i].Rchild;
}
}
if(ht[i].Lchild == 0) //若左孩子为空，则证明该结点为根结点，将字符写入file3.txt中
{
printf("%c", ht[i].data);
fputc(ht[i].data, fs);
continue;
}
if(ch == EOF)
break;
}
printf("\n");
fclose(fs);
fclose(fp);
}写到这里，说实话，我觉得我对文件的压缩与解压还是云里雾里的；不过还好，知道了一棵哈夫曼树应该如何正确建立，以及应该怎样吧编码和哈夫曼结合起来。
通过这段学习，觉得自己成熟了许多，尽管离自己的目标还很远，但是，加油，共勉！