1. 问题

前缀码：对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，比如常见的等长编码就是前缀码。
最优前缀码：平均码长或文件总长最小的前缀编码称为最优的前缀码（这里的平均码长相当于码长的期望值）
哈夫曼树的构造(哈夫曼算法)
1.根据给定的n个权值{w1,w2,…,wn}构成二叉树集合F={T1,T2,…,Tn},其中每棵二叉树 Ti中只 有一个带权为wi的根结点,其左右子树为空.
2.在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉 树的根 结点的权值为左右子树根结点的权值之和.
3.在F中删除这两棵树,同时将新的二叉树加入F中.
4.重复2、3,直到F只含有一棵树为止.(得到哈夫曼树)

2. 解析

3. 设计

void CreatHuffmanTree(Huffnode *F,int n){ //创建哈夫曼树
int loop=0;
int k1,k2;//最小次小
for(loop=0;loop for(k1=0;k1 for(k2=k1+1;k2 for(int i=k2;i if(F[i].parint==-1){
if(F[i].weight k2=k1;
k1=i;
}
else if(F[i].weight k2=i;
}
}
}
F[n+loop].weight=F[k1].weight+F[k2].weight;
F[n+loop].left=k1; //最小在左子女
F[n+loop].right=k2; //次小在右子女
F[n+loop].parint=-1;
F[n+loop].word=’X’;
F[k1].parint=F[k2].parint=n+loop;
}
}

void CreatHuffmancode(Huffnode F,int n){ //创建哈夫曼编码
int c,pa;
int p;
for(int i=0;i F[i].code=p=(int)malloc(nsizeof(int));
p[0]=0; //p[0]用来充当岗哨
c=i;
while(F[c].parint!=-1){ //当找到根结点时终止循环
pa=F[c].parint;
if(c==F[pa].left){
p[++p[0]]=0;
}
else{
p[++p[0]]=1;
}
c=pa; //再找双亲的双亲
}
}
}

4. 分析

O(nlogn)频率排序；for 循环 O(n)，插入操作 O(logn)，算法时间复杂
度是 O(nlogn)

5. 源码

https://github.com/joserfdave/arithmetic/tree/main