C++ 指针每次新分配时都分配相同的地址吗？

Question

我是 C++ 的新手，我正在尝试在其中实现霍夫曼代码。为此，我必须在其中实现一个树状结构，这需要我在一个结构中实现指针。但我面临的问题是，每次我为变量分配一个新值时，它都会获得相同的地址，而我试图实现的树在最顶层的元素上变得自引用，这阻止了我遍历它.

这是我的代码 -

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;

struct node{
    int freq;
    string symbol;
    node *left = nullptr, *right=nullptr;
    string huff;
};

vector<node> nodes;

vector<node> nodeSort(vector<node> arr, int s){
    for(int x=0;x<s;x++){
        for(int y=x+1;y<s;y++){
            if(arr[x].freq>arr[y].freq){
                node temp = arr[x];
                arr[x] = arr[y];
                arr[y] = temp;
            }
        }
    }
    return arr;
}

void printHuff(node Node, string val=""){
    string newval = val+Node.huff;
    if(Node.left!=nullptr){
        printHuff(*Node.left,newval);
    }
    if(Node.right!=nullptr){
        cout<<2;
        printHuff(*Node.right,newval);
    }
    if(Node.left==nullptr and Node.right==nullptr){
        cout<<Node.symbol<<" -> "<<newval;
    }
}

int main(){
    char symbols[] = {'A','B','C','D'};
    int freq[] = {5,1,6,3};
    for(int x=0;x<4;x++){
        node temp;
        temp.freq = freq[x];
        temp.symbol = symbols[x];
        temp.huff = "";
        nodes.push_back(temp);
    }

    while(nodes.size()>1){
        nodes = nodeSort(nodes,nodes.size());
        node left = nodes[0];
        node right = nodes[1];
        node temp;
        left.huff += "0";
        right.huff += "1";
        temp.freq = left.freq + right.freq;
        temp.symbol = left.symbol + right.symbol;
        temp.left = &left;
        temp.right = &right;
        nodes.erase(nodes.begin());
        nodes.erase(nodes.begin());
        nodes.push_back(temp);
    }
    node a = nodes[0];
    cout<<a.left->symbol<<endl;
    cout<<a.right->symbol<<endl;
    cout<<a.right->left->symbol<<endl;
    cout<<a.right->right->symbol<<endl;
    // printHuff(nodes[0]);
    return 0;
}

这是预期的霍夫曼树 -

这是输出 -

C
BDA
C
BDA

这绝对是错误的。但是我无法找出我做错了什么参考？我是 C++ 的新手，虽然我在 Python 中实现了相同的算法，但我无法理解这里出了什么问题。

Answer 1

问题出在 node.erase() 它正在删除您通过 temp.left 和 temp.right 指向的节点。稍微好一点的方法是先形成node*的vector，然后通过new运算符形成节点，并将指针存入vector中。这样，当您执行 node.erase() 时，它只会擦除指针而不是节点本身。代码如下：

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;

struct node{
    int freq;
    string symbol;
    node *left = nullptr, *right=nullptr;
    string huff;
};

vector<node *> nodes;

vector<node*> nodeSort(vector<node*> arr, int s){
    for(int x=0;x<s;x++){
        for(int y=x+1;y<s;y++){
            if(arr[x]->freq>arr[y]->freq){
                node *temp = arr[x];
                arr[x] = arr[y];
                arr[y] = temp;
            }
        }
    }
    return arr;
}

void printHuff(node *Node, string val=""){
    
    if(Node->left!=NULL){
        printHuff(Node->left,val+"0");
    }
    if(Node->right!=NULL){
        // cout<<2;
        printHuff(Node->right,val+"1");
    }
    if(Node->left==NULL and Node->right==NULL){
        cout<<Node->symbol<<" -> "<<val<<endl;
    }
}

int main(){
    char symbols[] = {'A','B','C','D'};
    int freq[] = {5,1,6,3};
    for(int x=0;x<4;x++){
        node *temp = new node;
        temp->freq = freq[x];
        temp->symbol = symbols[x];
        temp->huff = "";
        nodes.push_back(temp);
    }

    for(auto it: nodes){
        cout<<it->symbol<<" "<<it->freq<<endl;
    }
    while(nodes.size()>1){
        nodes = nodeSort(nodes,nodes.size());
        node *left  = nodes[0];
        node *right = nodes[1];
        node *temp = new node;
        // left.huff += "0";
        // right.huff += "1";
        temp->freq = left->freq + right->freq;
        temp->symbol = left->symbol + right->symbol;
        temp->left = left;
        temp->right = right;
        nodes.erase(nodes.begin());
        nodes.erase(nodes.begin());
        nodes.push_back(temp);
    }
    // node a = nodes[0];
    // cout<<a.left->symbol<<endl;
    // cout<<a.right->symbol<<endl;
    // cout<<a.right->left->symbol<<endl;
    // cout<<a.right->right->symbol<<endl;
    printHuff(nodes[0]);
    return 0;
}

也不要使用using namespace std。阅读 this question 并欢迎使用 C++。

C++ 指针每次新分配时都分配相同的地址吗？

Are C++ pointers allocated same address every time they are newly allocated?

c++

algorithm

stl

huffman-code