Dijkstra算法

待后续补充

哈夫曼编码

1.算法介绍

哈夫曼编码采取的贪心策略是每次从树的集合中取出没有双亲且权值最小的两个树为左右子树,构造一棵新树,新树根结点的权值为其左右孩子的结点权值之和,将新树插入到树的集合之中。

求解步骤如下:

(1)确定合适的数据结构,编写程序前要考虑:

①哈夫曼树中没有度为1的结点,则一棵有n个叶子结点的哈夫曼树共有2n-1个结点(n-1次合并,每次产生一个结点);

②构成哈夫曼树后,为求编码,需从叶子结点除法走一条从叶子到根的路径。

译码需要从跟除法走一条从根到叶子的路径,那么我们需要知道每个结点的权值双亲左孩子右孩子和结点的信息。

(2)初始化。

(3)如果T中只剩一棵树,那么哈夫曼树构造成功,跳到步骤(6)。否则,从集合T中取出没有双亲且权值最小的两棵树ti和tj,将它们合并成一棵新树zk,新树的左孩子为ti,右孩子为tj,zk的权值为ti和tj的权值之和。

(4)从集合T中删除ti和tj,加入zk

(5)重复以上(3)~(4)步骤。

(6)约定左分支上的编码为“0”,右分支上的编码为“1”。从叶子结点到根结点逆向求出每个字符的哈夫曼编码,从根结点到叶子结点路径上的字符组成的字符串为该叶子结点的哈夫曼编码。算法结束。

2.伪码详解

(1)数据结构

每个结点的定义包括5部分:权值、父结点、左孩子、右孩子、结点字符信息。所以可以用一个结构体来描述:

 

编码结构体:

 

(2)初始化

初始化存放哈夫曼树数组HuffNode[]中的结点:

 

然后输入n个叶子结点的字符和权值:

 

(3)循环构造哈夫曼树

 

(4)输出哈夫曼编码

 

3.代码

(关于使用优先队列的方法待后续优化)

 

时间复杂度:O(n2),空间复杂度O(n*MAXBIT)

最小生成树

待后续更新