网站群建设的目的/百度收录查询

注意哈夫曼编码的贪心选择性质，以及构造哈夫曼树的特点，构件相应的哈夫曼树。（注意哈夫曼树只是根据最优编码生成的，因此其可以不用为完全二叉树。）

针对下面几个节点，我们设计相应的哈夫曼树结构如下，根据相应结构设计对应的代码，由于不同的节点结构我们设计了两份代码，大体思路一直，只是在某处可能稍有不同。。。

代码一

#include <iostream>
#include <string>
#define MAX 1000000
using namespace std;typedef struct{double weight;char ch;int lchild, rchild, parent;
}HTNode;void select(HTNode htnodes[], int *a, int* b, int k){double weight = MAX;for (int i = 0; i < k; i++){if (htnodes[i].parent == -1 && htnodes[i].weight < weight){weight = htnodes[i].weight;*a = i;}}weight = MAX;for (int i = 0; i < k; i++){if (htnodes[i].parent == -1 && i != *a&&htnodes[i].weight < weight){weight = htnodes[i].weight;*b = i;}}//排序根节点的左右节点的顺序，因为huffuman树中根节点的做左节点和右节点的顺序稍有违背，因此我们进行少许修改int temp;if (htnodes[*a].lchild < htnodes[*b].lchild){temp = *a;*a = *b;*b = temp;}}
void HuffmanTree(HTNode htnodes[], int w[], char ch[], int n){for (int i = 0; i < 2 * n - 1; i++){htnodes[i].parent = -1; htnodes[i].lchild = -1;htnodes[i].rchild = -1;}for (int i = 0; i < n; i++){htnodes[i].weight = w[i];htnodes[i].ch = ch[i];}for (int k = n; k < 2 * n - 1; k++){int i1 = 0;int i2 = 0;select(htnodes, &i1, &i2, k);htnodes[i1].parent = k;htnodes[i2].parent = k;htnodes[k].weight = htnodes[i1].weight + htnodes[i2].weight;htnodes[k].lchild = i1;htnodes[k].rchild = i2;}
}
void HuffmanCode(HTNode htnodes[], int n){int i, j, k;string s = "";for (int i = 0; i < n; i++){s = "";j = i;while (htnodes[j].parent != -1){k = htnodes[j].parent;if (j == htnodes[k].lchild){s = s + "0";}else{s = s + "1";}j = htnodes[j].parent;}cout << "字符" << htnodes[i].ch << "的编码:" << endl;for (int i = s.size() - 1; i >= 0; i--){cout << s.at(i) << " ";}cout << endl;}
}
int main(){const int n = 6;HTNode node[2 * n-1];char ch[] = { 'a', 'b', 'c', 'd', 'e', 'f' };int w[] = { 50, 60, 150, 200, 240, 300 };HuffmanTree(node, w, ch, n); HuffmanCode(node, n);return 0;
}

运行结果：

代码二：

在代码二中我们针对节点结构进行了一个新的设计，加入了用于表示代码是否被选中的flag部分，给程序的设计带来了极大的方便，下面我们就过来分析代码：

#include <iostream>
#include <string>
#define MAX 1000000
using namespace std;struct HTNode{int weight;char ch;int lchild, rchild, parent;bool flag;
};void select(HTNode htnodes[], int* lchild, int* rchild, int n){double weight = MAX;for (int i = 0; i < n; i++){if (htnodes[i].flag != true && htnodes[i].weight < weight){weight = htnodes[i].weight;*lchild = i;}}htnodes[*lchild].flag = true;weight = MAX;for (int i = 0; i < n; i++){if (htnodes[i].flag != true && htnodes[i].weight < weight){weight = htnodes[i].weight;*rchild = i;}}htnodes[*rchild].flag = true;int temp = 0;if (htnodes[*lchild].lchild<htnodes[*rchild].lchild){temp = *lchild;*lchild = *rchild;*rchild = temp;}
}
void HuffuTree(HTNode htnodes[],int weight[],char ch[],int n){for (int i = 0; i < 2 * n - 1; i++){htnodes[i].lchild = -1;htnodes[i].rchild = -1;htnodes[i].parent = -1;htnodes[i].flag = false;}for (int i = 0; i < n; i++){htnodes[i].weight = weight[i];htnodes[i].ch = ch[i];}int lchild=0, rchild=0;for (int k = n; k < 2 * n - 1; k++){select(htnodes, &lchild, &rchild, k);htnodes[lchild].parent = k;htnodes[rchild].parent = k;htnodes[k].lchild = lchild;htnodes[k].rchild = rchild;htnodes[k].weight = htnodes[lchild].weight + htnodes[rchild].weight;}
}
void HuffuCode(HTNode htnodes[],int n){int j, parent;string s = " ";for (int i = 0; i < n; i++){s = " ";j = i;while (j!=2*n-2){//等价于htnodes[j].parent!=-1parent = htnodes[j].parent;if (j == htnodes[parent].lchild){s = s + "0";}if (j == htnodes[parent].rchild){s = s + "1";}j = htnodes[j].parent;}cout << "字符" << htnodes[i].ch << "的编码:" << endl;for (int k = s.length() - 1; k >= 0; k--){cout << s.at(k) << " ";}cout << endl;}
}
int main(){const int n = 6;HTNode htnodes[2 * n - 1];char ch[] = { 'a', 'b', 'c', 'd', 'e', 'f' };int weight[] = { 50, 60, 150, 200, 240, 300 };HuffuTree(htnodes,weight,ch, n);HuffuCode(htnodes, n);return 0;
}

运行结果：

代码参考：http://www.xuebuyuan.com/2072443.html