C++ 二叉搜索树创建段错误

Question

我正在尝试制作一个通过操作码识别 AVR 汇编指令的程序，因为它们只是 1 和 0 的列表，我认为制作二叉搜索树是一个很好的项目。

可悲的是，我在尝试搜索树时不断遇到段错误。据我了解，段错误通常是尝试使用不指向任何东西的指针执行操作的结果，但由于我有一个 bool 值，所以我首先检查它应该永远不会发生。

我很确定这与我使用指针的方式有关，因为我对这些不是很有经验。但我似乎无法弄清楚出了什么问题。

下面是涉及的代码(SearchTree 只是这个最小示例中的一个全局变量，在实际程序中不是。):

代码:

#include <iostream>

void ADD(short &code) {std::cout << code << "\n";}
void LDI(short &code) {std::cout << code << "\n";}
void SBRC(short &code){std::cout << code << "\n";}

struct node
{
    void(* instruct)(short &code);
    bool hasInst = false;

    struct node *zero;
    bool hasZero = false;

    struct node *one;
    bool hasOne = false;
};

node SearchTree;

auto parseOpcode(short code, node *currentRoot)
{
    std::cout << "Looking for a:  " << ((code >> 15) & 0b01 == 1) << std::endl;
    std::cout << "Current node 1: " << (*currentRoot).hasOne << std::endl;
    std::cout << "Current node 0: " << (*currentRoot).hasZero << std::endl;

    // Return instruction if we've found it.
    if ((*currentRoot).hasInst) return (*currentRoot).instruct;

    // Case current bit == 1.
    else if ((code >> 15) & 0b01 == 1)
    {
        if ((*currentRoot).hasOne) return parseOpcode((code << 1), (*currentRoot).one);
        else throw "this instruction does not exist";
    }
    // Case current bit == 0.
    else {
        if ((*currentRoot).hasZero) return parseOpcode((code << 1), (*currentRoot).zero);
        else throw "this instruction does not exist";
    }
}

void addopcode(void(& instruct)(short &code), int opcode, int codeLength)
{
    node *latest;
    latest = &SearchTree;
    for (int i = 0; i <= codeLength; i++)
    {
        // Add function pointer to struct if we hit the bottom.
        if (i == codeLength)
        {
            if ((*latest).hasInst == false)
            {
                (*latest).instruct = &instruct;
                (*latest).hasInst = true;
            }
        }
        // Case 1
        else if (opcode >> (codeLength - 1 - i) & 0b01)
        {
            if ((*latest).hasOne)
            {
                latest = (*latest).one;
            }
            else{
                node newNode;
                (*latest).one = &newNode;
                (*latest).hasOne = true;
                latest = &newNode;
            }
        }
        // Case 0
        else {
            if ((*latest).hasZero)
            {
                latest = (*latest).zero;
            }
            else{
                node newNode;
                (*latest).zero = &newNode;
                (*latest).hasZero = true;
                latest = &newNode;
            }
        }
    }
}


int main()
{
    addopcode(ADD, 0b000011, 6);
    addopcode(LDI, 0b1110, 4);
    addopcode(SBRC, 0b1111110, 7);

    short firstOpcode = 0b1110000000010011;

    void(* instruction)(short &code) = parseOpcode(firstOpcode, &SearchTree);
    instruction(firstOpcode);
    return 0;
}

编辑:我的文件顶部仍然有一些#includes 链接到我没有放在 StackOverflow 上的代码。

Answer 1

错误发生是因为我忘记使用 new 关键字，因此用局部变量填充了我的搜索树(当我开始搜索树时，显然现在已经更长了)。

通过使用修复:

node *newNode = new node();
(*latest).one = newNode;
(*latest).hasOne = true;
latest = newNode;

代替:

node newNode;
(*latest).one = &newNode;
(*latest).hasOne = true;
latest = &newNode;