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部分：权值、父结点、左孩子、右孩子、结点字符信息。所以可以用一个结构体来描述：
typedef struct
{
double weight;//weight
int parent;//parent node
int lchild;//left child
int rchild;//right child
char value;//value
} HNodeType;
编码结构体：
typedef struct
{
int bit[MAXBIT];//存储编码的数组
int start;//编码开始下标
}HCodeType;
（2）初始化
初始化存放哈夫曼树数组HuffNode[]中的结点：
for(int i=0;i<2*n-1;i++){
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
然后输入n个叶子结点的字符和权值：
for(int i=0;i<n;i++)
{
cout<<"Please input value and weight of leaf node "<<i+1<<endl;
cin>>HuffNode[i].value>>HuffNode[i].weight;
}
（3）循环构造哈夫曼树
int i,j,x1,x2;//x1、x2位两个最小权值结点的序号
double m1,m2;
for(int i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;//初始化为最大权值
x1=x2=-1;//初始化为-1
//找出所有结点中权值最小、无父结点的两个结点
for(j=0;j<n+i;j++)
{
if(HuffNode[j].weight <m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].weight<m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}
/*更新树的信息*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
HuffNode[n+i].weight=m1+m2;
}
（4）输出哈夫曼编码
void HuffmanCode(HCodeType HuffCode[MAXLEAF],int n)
{
HCodeType cd;//定义一个临时变量来存放求解编码时的信息
int i,j,c,p;
for(i=0;i<n;i++)
{
cd.start=n-1;
c=i;//i为叶子结点的编号
p=HuffNode.parent;
while(p!=1)
{
if(HuffNode[p].lchild==c){
cd.bit[cd.start]=0;
}
else
cd.bit[cd.start]=1;
cd.start--;//start向前移动一位
c=p;
p=HuffNode.parent;
}
/*把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组*/
for(j=cd.start+1;j<n;j++)
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
}
3.代码
（关于使用优先队列的方法待后续优化）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAXBIT 100
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
//树的结点
typedef struct
{
double weight;//weight
int parent;//parent node
int lchild;//left child
int rchild;//right child
char value;//value
} HNodeType;
//编码结构体
typedef struct
{
int bit[MAXBIT];//存储编码的数组
int start;//编码开始下标
}HCodeType;
HNodeType HuffNode[MAXNODE];//定义一个结点结构体数组
HCodeType HuffCode[MAXLEAF];//定义一个编码结构体数组
/*构造哈夫曼树*/
void HuffmanTree(HNodeType HuffNode[MAXNODE], int n)
{
int i, j, x1, x2;
double m1, m2;
/*i、j：循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值
x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号*/
for (i = 0; i<2 * n - 1; i++) {
HuffNode[i].weight = 0;
HuffNode[i].parent = -1;
HuffNode[i].lchild = -1;
HuffNode[i].rchild = -1;
}
//输入权值
for (i = 0; i<n; i++)
{
cout << "Please input value and weight of leaf node " << i + 1 << endl;
cin >> HuffNode[i].value >> HuffNode[i].weight;
}
//构造哈夫曼树
for (int i = 0; i<n - 1; i++)
{//执行n-1次合并
m1 = m2 = MAXVALUE;//初始化为最大权值
x1 = x2 = -1;//初始化为-1
//找出所有结点中权值最小、无父结点的两个结点，并合为一个树
for (j = 0; j<n + i; j++)
{
if (HuffNode[j].weight <m1 && HuffNode[j].parent == -1)
{
m2 = m1;
x2 = x1;
m1 = HuffNode[j].weight;
x1 = j;
}
else if (HuffNode[j].weight<m2 && HuffNode[j].parent == -1)
{
m2 = HuffNode[j].weight;
x2 = j;
}
}
/*更新找到的两个结点和它组成的树的结点的信息*/
HuffNode[x1].parent = n + i;
HuffNode[x2].parent = n + i;
HuffNode[n + i].lchild = x1;
HuffNode[n + i].rchild = x2;
HuffNode[n + i].weight = m1 + m2;
cout << "x1.weight and x2.weight in round" << i + 1 << "\t" << HuffNode[x1].weight << "\t" << HuffNode[x2].weight << endl;//测试
}
}
//对哈夫曼树进行编码
void HuffmanCode(HCodeType HuffCode[MAXLEAF], int n)
{
HCodeType cd;//定义一个临时变量来存放求解编码时的信息
int i, j, c, p;
for (i = 0; i<n; i++)
{
cd.start = n - 1;
c = i;//i为叶子结点的编号
p = HuffNode.parent;
while (p != -1)
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.bit[cd.start] = 1;
cd.start--;//start向前移动一位，求编码的低一位
c = p;
p = HuffNode.parent;//设置下一循环的条件
}
//把叶子结点的编码信息从临时编码cd中复制出来，放入编码结构体数组
for (j = cd.start + 1; j<n; j++)
HuffCode[i].bit[j] = cd.bit[j];
HuffCode[i].start = cd.start;
}
}
int main()
{
int i, j, n;
cout << "Please input n: " << endl;
cin >> n;
HuffmanTree(HuffNode, n);//构造哈夫曼树
HuffmanCode(HuffCode, n);//哈夫曼树编码
//输出已经保存好的所有存在编码的哈夫曼编码
for (i = 0; i < n; i++)
{
cout << HuffNode[i].value << ": Huffman code is: ";
for (j = HuffCode[i].start + 1; j < n; j++)
cout << HuffCode[i].bit[j];
cout << endl;
}
system("pause");
return 0;
}
时间复杂度：O(n2)，空间复杂度O(n*MAXBIT)
最小生成树
待后续更新
文章评论