c++ - 将属性数据推送到 trie，添加到多个键

Question

我的知识有限，但我已经在这个特定的数据结构上工作(破解)了一段时间

我使用 trie 来存储本体字符串，然后在调用 get (string) 时将其作为堆栈返回，包括“间隙”接近度。作为对 trie 的添加，将属性存储在键上。字符串越往下，属性的详细信息就越多。这对我的目的来说效果很好。

作为附加功能，我使用通配符将属性应用于所有子节点。例如，将“paws”添加到“mammals.dogs”的所有子节点。我推(哺乳动物。狗。*。爪子)。现在，所有的狗都有爪子。

问题是只有第一只狗得到爪子。该函数适用于没有 wild 的推送属性

如果你愿意，我可以清理它并提供一个简化版本，但过去我在 stackoverflow 上发现最好只提供代码；我使用 'z' 作为 '*' 野

void Trie::push(ParseT & packet)
{
    if (root==NULL) AddFirstNode(); // condition 1: no nodes exist, should this be in wrapper
    const string codeSoFar=packet.ID;
    AddRecord(root, packet, codeSoFar); //condotion 2: nodes exist
}

void Trie::AddFirstNode(){ // run-once, initial condition of first node
    nodeT *tempNode=new nodeT;
    tempNode->attributes.planType=0;
    tempNode->attributes.begin = 0;
    tempNode->attributes.end = 0;
    tempNode->attributes.alt_end = 0;
    root=tempNode;
}



//add record to trie with mutal recursion through InsertNode
//record is entered to trie one char at a time, char is removed
//from record and function repeats until record is Null
void Trie::AddRecord(nodeT *w, ParseT &packet, string codeSoFar)
{
    if (codeSoFar.empty()) {

        //copy predecessor vector at level n, overwrites higher level vectors
        if (!packet.predecessorTemp.empty())
            w->attributes.predecessorTemp = packet.predecessorTemp;

        return;  //condition 0: record's last char
    }
    else { //keep parsing down record path

        for (unsigned int i = 0; i < w->alpha.size(); i++) {
            if (codeSoFar[0] == w->alpha[i].token_char || codeSoFar[0] == 'z') {
                return AddRecord(w->alpha[i].next, packet, codeSoFar.substr(1)); // condition 2: char exists
            }
        }
        InsertNode(w, packet, codeSoFar); //condition 3: no existing char --> mutal recursion
    }
}

//AddRecord() helper function
void Trie::InsertNode(nodeT *w, ParseT &packet, string codeSoFar) // add new char to vector array
{
    for (unsigned int i=0; i <=w->alpha.size(); i++) { // loop and insert tokens in sorted vector
        if (i==w->alpha.size() || codeSoFar[0] < w->alpha[i].token_char) { //look for end of vector or indexical position

            //create new TokenT
            tokenT *tempChar=new tokenT;
            tempChar->next=NULL;
            tempChar->token_char=codeSoFar[0];

            //create new nodeT
            nodeT *tempLeaf=new nodeT;
            tempLeaf->attributes.begin = 0;
            tempLeaf->attributes.end = 0;
            tempLeaf->attributes.planType = 0;
            tempLeaf->attributes.alt_end = 0;

            //last node
            if (codeSoFar.size() == 1){

                tempLeaf->attributes.predecessorTemp = packet.predecessorTemp;
            }

            //link TokenT with its nodeT
            tempChar->next=tempLeaf;
            AddRecord(tempLeaf, packet, codeSoFar.substr(1)); //mutual recursion --> add next char in record, if last char AddRecord will terminate

            w->alpha.insert(w->alpha.begin()+i, *tempChar); 
            return; 
        }
    }
}

root is global nodeT *w

    struct ParseT {

        string ID; //XML key

        int begin = 0; //planned or actual start date
        int end = 0; //planned or actual end date - if end is empty then assumed started but not compelted and flag with 9999 and 
        int alt_end = 0; //in case of started without completion 9999 case, then this holds expected end
        int planType = 0; //actuals == 1, forecast == 2, planned == 3

        map<string, string> aux;

        vector<string> resourceTemp;
        vector<string> predecessorTemp;
    };

Answer 1

在这段代码中

    for (unsigned int i = 0; i < w->alpha.size(); i++) {
        if (codeSoFar[0] == w->alpha[i].token_char || codeSoFar[0] == 'z') {
            return AddRecord(w->alpha[i].next, packet, codeSoFar.substr(1)); // condition 2: char exists
        }
    }

您一调用 AddRecord 就会返回，即使是因为通配符。当 codeSoFar[0] == 'z' 遍历所有 alpha 并添加记录时，使用单独的循环可能会更容易。然后有一个 else 子句来执行您当前的代码。

编辑:这就是我的意思，代码形式:

else { //keep parsing down record path
    // Handle wildcards
    if (codeSoFar[0] == 'z') {
        for (unsigned int i = 0; i < w->alpha.size(); i++) {
            AddRecord(w->alpha[i].next, packet, codeSoFar.substr(1)); // condition 2: char exists
        }
    }
    else {
        // Not a wildcard, look for a match
        for (unsigned int i = 0; i < w->alpha.size(); i++) {
            if (codeSoFar[0] == w->alpha[i].token_char) {
                return AddRecord(w->alpha[i].next, packet, codeSoFar.substr(1)); // condition 2: char exists
            }
        }
        InsertNode(w, packet, codeSoFar); //condition 3: no existing char --> mutal recursion
    }
}