-
#include <stdio.h>
-
#include <stdlib.h>
-
#define N 7
-
-
-
//-------------------------双亲孩子表（存储huffman树）--------------------------//
-
typedef struct
-
{
-
int weight;
-
int parent,lchild,rchild;
-
}Huffmantree;
-
-
-
-
//-------------------------存储最后得出的huffman编码---------------------------//
-
typedef struct
-
{
-
char ch;
-
char bits[N+1];//由于huffman得出的编码的长度不会超过N+1（叶节点个数加‘\0’）
-
} CodeNode;
-
-
//--------------------------------定义链表结构----------------------------------//
-
-
typedef struct Node
-
{
-
int data;
-
struct Node *next;
-
}Node,*LinkedList;
-
-
LinkedList L;
-
/*由于是全局变量，所以下面不能对L直接进行赋值操作，而要间接操作，不然L就不是指向
-
正确的连表了如L=L->next是错误的，P=L ,P=P->next才是正确的*/
-
-
void LinkedListInit()
-
{
-
-
L=(Node *)malloc(sizeof(Node));
-
if(L==NULL)
-
{
-
printf("申请聊表失败!");
-
exit(0);
-
}
-
L->next=NULL;
-
-
}
-
-
-
//---------------------------------构造一个从大到小的链表------------------------------------//
-
void LinkListIn(int i,Huffmantree tree[])//链表中按节点数据大小顺序插入
-
{
-
-
-
LinkedList P,I,T;
-
P=L;
-
-
while( (P->next != NULL)&&(tree[i].weight > tree[P->next->data].weight) )
-
//两个条件不能调换，P->next!=NULL是tree[P->next->data].weight)正常运行的前提，不然会出现指针越界错误（自动退出程序的后果）
-
{
-
P = P->next;
-
}
-
I=(Node *)malloc(sizeof(Node));//以下是插入节点的操作
-
I->data = i;
-
T = P->next;
-
P->next = I;
-
I->next = T;
-
-
}
-
-
//--------------------------从链表中取最小的两个数---------------------------//
-
int LinkListInOut()//由于链表已经从小到大排好,直接取L->next,就是最小的数，
-
{
-
int i;
-
LinkedList P;
-
i = L->next->data;
-
P=L->next;
-
L->next=P->next;
-
free(P); //取出来后一定要记得 删除
-
return i;//一定要放在最后return,因为return是结束和带回返回值的标志
-
-
}
-
//-----------------------------构造huffman树---------------------------------//
-
void CreatHuffmanTree(Huffmantree tree[],int n)
-
{
-
int i,j,d,x,f;
-
LinkedListInit();
-
-
for(i=0;i<n;i++)//初始化tree数组，因为下面没有操作到得数组内容都为NULL也就是0
-
{
-
tree[i].weight=0;
-
tree[i].parent=0;
-
tree[i].lchild=0;
-
tree[i].rchild=0;
-
}
-
printf("输入权重（A,B,C,D,E,F,G）：");
-
for(i=0; i < N; i++)
-
{
-
scanf("%d",&f);//scanf的数字输入不用当心缓冲区问题
-
tree[i].weight = f;
-
LinkListIn( i, tree );//插入链表
-
}
-
-
for( j = N; j < 2*N-1; j++ )//由于这个过程会产生N-1个新节点，而且每个新节点都要放到链表中，所以构建是N-1次
-
{
-
d=LinkListInOut();//从链表中取出最小的两个数
-
x=LinkListInOut();
-
tree[j].weight = tree[d].weight + tree[x].weight;//新节点的权重
-
tree[d].parent=j;//以下是填写新节点的左右孩子，以及他的左右孩子的父母（就是这个新节点）
-
tree[x].parent=j;
-
tree[j].rchild=d;
-
tree[j].lchild=x;
-
LinkListIn(j,tree);
-
}
-
}
-
//-----------------------------------编码阶段------------------------------------//
-
void Huffman(Huffmantree tree[])
-
{
-
char cd[N];
-
char ch[7]={'A','B','C','D','E','F','G'};
-
int i,j,p;
-
-
for( i = 0; i < N; i++)
-
{
-
int start=N;//最后得出的结果要反序，在这里使用了从数组最后向前填写，在最终输出时从前读到后（从start读到数组尾部）
-
int c=i;
-
while( p = tree[c].parent )//读取路径，左为0，右为1，可以其他的（以至于答案不唯一）
-
{
-
if( tree[p].lchild == c )
-
cd[--start] ='0';//从末尾往开头写
-
else
-
cd[--start] ='1';
-
c=p;
-
}
-
printf("%c:",ch[i]);
-
for(j=start;j<N;j++)//从开头往末尾读
-
printf("%c",cd[j]);
-
printf(" ");
-
}
-
-
-
-
}
-
-
-
-
//-------------------------------------------------------------------------------//
-
main()
-
{
-
Huffmantree tree[2*N-1];//一共有2*N-1个节点
-
-
CreatHuffmanTree(tree,2*N-1);//构造哈弗曼树
-
Huffman(tree);//哈弗曼编码
-
-
return 0;
-
}
运行时输入自己定义的权重（或可以自己实现统计计算权重，这里就不说了）。
在此只有a,b,c,d,e,f四个数，可与根据要就改写ch[]数组和N。
最后得出权重越大（一般为重复出现次数越多权重越大），编码越短。。。这就是哈弗曼编码的精辟。
