求解哈夫曼树，最小权值和

Question

dev写求哈夫曼树，思路是每次从权值数组里找出两个最小和第二最小的值合成新的父节点，把父节点的值放进数组后，把这两个节点的权值再改成最大，代码里的printf语句是我加上方便看各个变量怎么变化的（因为刚上手debug用的还不太熟，结果就是找了第一轮之后找出1和2，合成3并加入了数组后，然后debug到下一步数组后多了个16，不知道哪里来的，求佬解答

#include <iostream>
#include <string>
using namespace std;
#define maxint 10000000

//本程序用于实现构造最小哈夫曼数，给出n个节点，和节点的权值weight[]


//输出数组
void display(int a[]){
    int i=0;
    while(a[i]!='\0'){
        printf("%d  ",a[i]);
        i++;
    }
}

void select(int a[],int n,int &min1,int &min2,int &pos1,int &pos2){
    //找出数组里的最小和次小
    int m1=maxint;
    int m2=maxint+1;
    pos1=pos2=-1;
    int j;
    for(int i=0;i<n;i++){
        if (a[i]<m1){
            m2=m1;
            pos2=pos1;
            m1=a[i];
            pos1=i;            
        }
        else if(a[i]>=m1&&a[i]<m2){
            m2=a[i];
            pos2=i;
        }
    }
    min1=m1;
    min2=m2;
}

void Huffuman(int n,int weight[],int &ans){
    int min1,min2;//最小和次小
    int i=n;//合成的父节点从n开始存放
    int j=1;
    int pos1,pos2;
    while(j<n){//共需n-1次合并
        select(weight,i,min1,min2,pos1,pos2);
        printf("第%d次合并获得最小权值：  %d      和次最小权值%d：  \n",j,min1,min2);
        ans=ans+min1+min2;
        printf("权值和为%d\n",ans);
        weight[i]=weight[pos1]+weight[pos2];
        i++;
        printf("i=%d\n",i);
        printf("----------\n");
        //    printf("修改值%d\n",weight[i])        
        weight[pos1]=weight[pos2]=maxint;
        display(weight);    
        j++;        
        }
    
}

int main(){
    int weight[]={1,2,2,5,9};
    int ans;
    Huffuman(5,weight,ans);
    printf("%d",ans);
    return 0;
}

Answer 1

基于GPT的解答
根据你的描述，可能出现问题的地方在于数组中存储的元素数量不正确。在代码中，数组的长度应该为 $n$，而不是 $n+1$，因为父节点不会超过 $n-1$ 个。

另外，根据你的描述，第一次合并后数组中多出了一个值 $16$，可能是因为你在数组初始化时将元素数量设置为 $n+1$，但实际上只有 $n$ 个元素是有效的。这样，如果在调用 'select

因此，你需要将数组的长度改为 $n$，并在初始化时只给前 $n$ 个元素赋值。具体来说，可以在 '

int weight[] = {1, 2, 2, 5, 9};
int n = sizeof(weight) / sizeof(weight[0]);
int ans = 0;
Huffuman(n, weight, ans);
cout << ans << endl;

同时，你需要修改display函数，让它根据数组的有效长度来输出元素。可以改为

void display(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

最后，记得加上头文件 'cstdio

#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
#define maxint 10000000

// 输出数组
void display(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void select(int a[], int n, int& min1, int& min2, int& pos1, int& pos2) {
    // 找出数组里的最小和次小
    int m1 = maxint;
    int m2 = maxint + 1;
    pos1 = pos2 = -1;
    int j;
    for (int i = 0; i < n; i++) {
        if (a[i] < m1) {
            m2 = m1;
            pos2 = pos1;
            m1 = a[i];
            pos1 = i;
        }
        else if (a[i] >= m1 && a[i] < m2) {
            m2 = a[i];
            pos2 = i;
        }
    }
    min1 = m1;
    min2 = m2;
}

void Huffuman(int n, int weight[], int& ans) {
    int min1, min2; // 最小和次小
    int i = n;      // 合成的父节点从n开始存放
    int j = 1;
    int pos1, pos2;
    while (j < n) { // 共需n-1次合并
        select(weight, i, min1, min2, pos1，pos2）;
printf（“第%d次合并获得最小权值： %d 和次最小权值%d： \n”， j， min1， min2）;
ans = ans + min1 + min2;printf("权值和为%d\n", ans);
weight[i] = weight[pos1] + weight[pos2];
i++;
printf("i=%d\n", i);
printf("----------\n");
// 将合成的父节点放入数组中，并将合并的子节点的权值设为maxint
weight[pos1] = weight[pos2] = maxint;
display(weight);
j++;
}
}

int main() {
int weight[] = { 1, 2, 2, 5, 9 };
int ans = 0;
Huffuman(5, weight, ans);
printf("最小权值和为%d", ans);
return 0;
}

回答不易，希望采纳。