PTA 6-7 哈夫曼树及哈夫曼编码
该函数SelectTwoMin(int upbound, HuffmanTree HT, int &s1, int &s2)是从指定范围内的所有节点中筛选出父节点为零的节点，并将其赋值给s1和s2变量。为了确保唯一性，请确保s1对应的节点编号小于s2。该函数HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)用于生成哈夫曼树并计算相应的哈夫曼编码。需要注意的是，在此过程中我们假设输入权重值不会超过设定的最大限制（即不超过1000）。
函数接口说明：
该函数用于从一个包含至少两个元素的一维整型数组中选择最小的两个元素并返回它们的位置索引。其中upbound表示数组的最大索引值；HT是一个被表示为HuffmanTree类型的指针变量；s1和s2分别通过引用参数返回最小元素的位置索引值。
该函数用于实现哈夫曼编码算法的基本编码过程。其中HT是一个被引用为当前构造状态下的Huffman树；HC是一个被引用为当前构造状态下的哈夫曼编码表；w是一个权值数组；n是叶子节点的数量。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
一种节点结构HTNode包含四个整数字段：权重、父节点、左子节点和右子节点，并由指针变量HuffmanTree表示。
char ** HuffmanCode;
函数声明部分
具体实现部分
int main() {
HuffmanTree ht;
HuffmanCode hc;
int n;
scanf("%d", &n);
int *w = (int *) malloc (n * sizeof(int));
for(int i = 0; i < n; ++ i)
scanf("%d", &w[i]);
HuffmanCoding(ht, hc, w, n);
for (int i = 1; i <= 2 * n - 1; ++ i) {
printf("%d %d %d %d\n",
ht[i].weight, ht[i].parent, ht[i].lchild, ht[i].rchild);
}
for (int i = 1; i <= n; ++ i)
printf("%s\n", hc[i]);
free(w);
free(ht);
for (int i = 1; i <= n; ++ i)
free(hc[i]);
return 0;
代码解读输入一行数据：
第一行输入一个数n（代表叶子节点的数量）；
之后输入n个整数（包含每个节点对应的数值）。
输入一行数据：
第一行输入一个数n（表示叶子节点的数量）；
之后接着输入n个整数（其中每个整数值代表每个节点对应的数值）。
####输出格式： 只要建树即可，输出已经确定了
输入样例：
4
1 2 3 4
输出样例：
1 5 0 0
2 5 0 0
3 6 0 0
4 7 0 0
3 6 1 2
6 7 3 5
10 0 4 6
110
111
10
0
void SelectTwoMin(int upbound, HuffmanTree HT, int &s1, int &s2)
{
int x1=0,x2=0;
int m1= 1000;
int m2= 1000;
for(int i=1; i<=upbound; i++)
{
if(HT[i].parent == 0&& HT[i].weight < m1)//更新
{//因为s1的编号要比s2的小 所以当出现一个比当前最小的还要小的时候
//就要重新更新数据 因为s2为第二小 所以把原先最小的数给s2就完成了更新
//然后把最新的最小的给s1 就使得s1为当前第一小 s2为当前第二小
m2= m1;//深度更新
x2 = x1;//位置更新
m1 = HT[i].weight;//重新赋值
x1 = i;//更新位置
}
else if(HT[i].parent == 0 && HT[i].weight <m2)
{//要是新出现的数比当前第二小的小但是比第一小要大时 只要更新s2即可
m2 = HT[i].weight;
x2 = i;
}
}
s1 = x1;
s2 = x2;
//最后把位置传递给s1，s2
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int s1=0;
int s2=0;
HT = (HuffmanTree)malloc(sizeof(HTNode)*(2*n));
HC = (char **)malloc(sizeof(char *)*(n+1));
for(int i=1;i<=n;i++)
{
HC[i] = (char *)malloc(sizeof(char)*(n+1));
memset(HC[i],0,sizeof(char)*(n+1));
}
for (int i = 0; i <n ; ++i) {
HT[i+1].weight = w[i];//把之前读入的每一位的权重导入weight
}//给结构体赋值
for (int i = 1;i<=2*n-1;i++) {
HT[i].parent =0;
HT[i].lchild =0;
HT[i].rchild =0;
}
for (int i=n+1;i<=2*n-1;i++){
SelectTwoMin(i-1,HT,s1,s2);//找权值最小的两个点
HT[i].lchild =s1;//找到它的孩子
HT[i].rchild =s2;
HT[s1].parent =i;//新找到的孩子节点的父节点为当前节点
HT[s2].parent =i;
HT[i].weight =HT[s1].weight +HT[s2].weight ;//新的节点的权重为两个相加
}//下面为哈夫曼树的编码
for (int i=1;i<=n;i++){
int start =n-1;//是从孩子节点一直找父节点 所以是逆着往上取 所以从后往前存
char cd[n];//开个数组来保存
cd[n-1]='\0';
int c=i;
int f=HT[i].parent ;//先找当前节点的父节点
while (f!=0){//只要存在父节点
start--;
if(HT[f].lchild ==c){//看当前节点是父节点的左娃还是右娃
cd[start]='0';//左娃为0
}
else {
cd[start]='1';//右娃为1
}
c=f;//找完之后当前节点成为孩子节点 找到当前父节点的父节点 重复上述操作
f=HT[f].parent ;
}
HC[i]=new char [n-start];
strcpy(HC[i],&cd[start]);//找完之后把编码赋值给HC
}
}
代码解读