因为课程的要求开始做霍夫曼编码，我这里的方法主要用到：冒泡法，函数的嵌套，创建树，二叉树
题目要求如下：
代码如下：
#include<stdio.h>
#include<stdlib.h>
typedef struct Huffmantree //定义霍夫曼树
{
float num; //用来接收每个字符出现的概率
char id; //表示每个字符的id
struct Huffmantree *lchild; //它们所对应的左右子树，也就是每一次排序最低的两个数字
struct Huffmantree *rchild;
}Hnode;
//构建树
Hnode *creat_tree(float *a,int n)
{
int i, j, z, f;
Hnode *huffmantree, **change, *temp; //temp用来中转，在排序法中使用
change = (Hnode**)malloc(n*sizeof(Hnode)); //change是指向这个结构体指针的指针，简单说可以表示为一个数组，数组里面的元素都是结构体
temp = (Hnode*)malloc(sizeof(Hnode));
for(i=0;i<n;i++) //change里面的每个结构体数据初始化
{
change[i] = (Hnode*)malloc(sizeof(Hnode));
change[i]->num = a[i];
change[i]->id = i+97; //这里加97，是因为a的ascall是97
change[i]->lchild = change[i]->rchild = NULL;
}
f = n; //后面用来改变排序的长度
for(i=0;i<n-1;i++) //有n个信息，就需要进行n-1次的排列
{
for(j=1;j<f;j++) //使用冒泡法进行排序,由大到小
{
for(z=0;z<f-1;z++)
{
if(change[z]->num < change[z+1]->num )
{
temp = change[z+1];
change[z+1] = change[z];
change[z] = temp;
}
}
}
huffmantree = (Hnode*)malloc(sizeof(Hnode)); //这里很重要，每次都要对huffmantree进行内存的更新，不然会影响到后面change[f-2]，因为是地址的传递，改变都是一起改变
huffmantree->num = change[f-1]->num + change[f-2]->num ; //这里就表示把概率进行相加，传递给huffmantree
huffmantree->lchild = change[f-1]; //给左右子树赋值
huffmantree->rchild = change[f-2];
change[f-2] = huffmantree; //就是这里，如果前面没有重新对内存的申请，当前面的huffmantree改变时，change[f-2]也会相应改变，从而影响后面
change[f-1] = NULL; //最后一位舍弃，已经没有用了
f = f-1; //这里用f来表示冒泡发的循环次数
}
return huffmantree;
}
//编码并打印
void print_code(Hnode *huffmantree,int depth)
{
static int code[10]; //设置一个静态变量数组，不然会因为函数的嵌套而发生改变
int i;
if(huffmantree == NULL)
return;
if(huffmantree->lchild == NULL && huffmantree->rchild == NULL) //当没有左右子树的时候就表示，这里就是 叶子节点，也就是我们输入的最开始的数字，这个时候就可以生成编码了
{
printf("%c的编码结果是：", huffmantree->id );
for(i=0;i<depth;i++)
{
printf("%d", code[i]);
}
printf("\n");
}
else
{
code[depth] = 0; //走左边子树表示0，右边子树表示1，左子树也就是前面的最小的那一位
print_code(huffmantree->lchild , depth+1);
code[depth] = 1;
print_code(huffmantree->rchild , depth+1);
}
}
int main()
{
int i, n;
float a[100]; //数组存放输入的值
Hnode *huffmantree;
printf("你要输入的消息序列有多少个？\n");
scanf("%d", &n); //接收序列的个数
printf("请输入个个消息序列的概率:\n");
for(i=0;i<n;i++)
{
scanf("%f", &a[i]);
}
//getchar();
huffmantree = NULL;
huffmantree = creat_tree(a,n); //创建霍夫曼树
print_code(huffmantree,0); ///生成霍夫曼编码并打印
}
注意：
当生成树的时候，代码中两个结构体之间的赋值，是地址的赋值，一个的改变会影响都另一个，所以，每次都要重新进行一次内存的覆盖
就是这里，change[f-2]的值会随着huffmantree的值的改变而改变，所以要重新进行内存的申请
结果如下：
