【数据结构】【程序填空】赫夫曼编码
题目描述
给定n个叶子的权值，根据这些权值构造huffman树，并输出huffman编码
参考课本第6.6节的算法6.12，注意算法中数组访问是从位置1开始
赫夫曼构建中，默认左孩子权值不大于右孩子权值
如果遇到两个孩子权值相等，那么按输入顺序或生成顺序来排列。
例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子
例如有两个叶子权值都是4，那么按输入顺序，先输入权值的叶子是左孩子
请完成以下程序填空
输入
第1行输入n，表示有n个叶子
第2行输入n个权值，权值都是正整数
输出
输出n行，每行输出格式：权值-赫夫曼编码 请参考样例
输入样例1
8 5 29 7 8 14 23 3 11
输出样例1
5-0001 29-10 7-1110 8-1111 14-110 23-01 3-0000 11-001
提示
如果你用二维字符数组保存赫夫曼编码，参考课本算法6.12的代码，不必理会以下内容。
如果用C++的string串保存赫夫曼编码，因为赫夫曼编码是逆序生成的，可以参考以下代码
string s1; //用临时字符串保存编码生成过程
循环生成编码：
if (是左分支) s1= '0‘+s1; if (是右分支) s1= '1‘+s1;
循环结束
HuffCode[i]=s1; //把s1保存到对应叶子的字符串中
如果搞不定赫夫曼编码保存在字符串数组中，那么就在Coding函数中直接输出好了，记得给printCode函数定义一个空函数体
最好还是能搞定O_O
思路分析
一开始尝试用的是数组下标从0开始的，但是后面发现不行，因为算法是通过让权重为0来表示未访问，所以只能从1开始。
构建赫夫曼树比较关键的是每次挑选的两个最小元素的select函数，这里需要格外注意。
还有就是编码的时候，循环的条件是 while (HuffTree[j].parent!=0)。
如果用string的insert函数就不用把编码倒过来，直接每次插头就可以了。
AC代码
HuffMan::HuffMan(int n, int *w) {
lnum = n;
len = lnum * 2 - 1;
HuffTree = new HuffNode[len+1];
HuffCode = new string[lnum];
for (int i = 1; i <= lnum; i++) {
HuffTree[i].weight = w[i-1];
HuffTree[i].parent = HuffTree[i].lchild = HuffTree[i].rchild = 0;
}
for (int i = lnum+1; i <= len; i++)
HuffTree[i].weight = HuffTree[i].parent = HuffTree[i].lchild = HuffTree[i].rchild = 0;
}
void HuffMan::buildTree() {
int a, b;
for (int i = lnum+1; i <= len; i++) {
selectMin(i-1, a, b);
HuffTree[a].parent = HuffTree[b].parent = i;
HuffTree[i].lchild = a;
HuffTree[i].rchild = b;
HuffTree[i].weight = HuffTree[a].weight + HuffTree[b].weight;
}
}
void HuffMan::selectMin(int n, int &x1, int &x2) {
x1=x2=0;
for (int i =1; i <= n; i++)
if (HuffTree[i].parent == 0) {
if(x1==0)
x1=i;
else if(x2==0)
x2=i;
if (HuffTree[i].weight < HuffTree[x1].weight) {
x2 = x1;
x1 = i;
} else if (x2 != 0 && HuffTree[i].weight < HuffTree[x2].weight)
x2 = i;
}
}
void HuffMan::Coding() {
for (int i = 1; i <= lnum; i++) {
int j=i;
while (HuffTree[j].parent!=0) {
if (HuffTree[HuffTree[j].parent].lchild == j)
HuffCode[i-1].insert(HuffCode[i-1].begin(),'0');
else if(HuffTree[HuffTree[j].parent].rchild==j)
HuffCode[i-1].insert(HuffCode[i-1].begin(),'1');
j = HuffTree[j].parent;
}
}
}
void HuffMan::printCode() {
for (int i = 1; i <= lnum; i++) {
cout << HuffTree[i].weight << '-' << HuffCode[i-1] << endl;
}
}
HuffMan::~HuffMan() {
if (HuffTree)
delete[]HuffTree;
if (HuffCode)
delete[]HuffCode;
}腾讯云开发者
