0

目的：此函数通过与输入字符串匹配的路径后面的字符串树进行解析。当字符串中的所有字符都被解析后，true返回。如果仍有有效路径，我想跳过一个字符并返回。

应用程序：字符串是高速公路项目的位置层次结构。因此，项目 5 具有路线 C，其偏移量为 N，工作区为 3；5CN3。但是，有时我想为涵盖所有位置的项目任务的所有子位置定义一个字符串。因此，“0”是所有位置；对于像坡度泥土这样的半天操作，没有工作区 - 代表这项任务的所有工作区都是北线 C 中的所有工作区；5CN0. 如果一个操作涵盖整个项目，则相同；5000。

方法：我可以使用通配符“？” 功能，但我想保留此特定步骤以抽象位置。也许 '？' 是正确的方法，但似乎失去了一些控制。此外，这可以在没有 for 循环的情况下编写并使用位置索引参数；也许这就是问题所在 - 也许是回溯。

代码：nodeT是trie节点，word是输入字符串，这个函数是a bool，如果字符串路径存在则返回1/0。

bool Lexicon::containsWordHelper(nodeT *w, string word)) //check if prefix can be combined
{
    if(word == "") { //base case: all char found
        return true;
    } else {
        for(int i = 0; i < w->alpha.size(); i++) { //Loop through all of the children of the current node
            if (w->alpha[i].letter == word[0])
                return containsWordHelper(w->alpha[i].next, word.substr(1));
            else if (word[0] == '0') //if '0' then step over and continue searching for valid path
                containsWordHelper(w->alpha[i].next, word.substr(1)); //removed return here to allow looping through all the possible paths
        } //I think it is continuing through after the loop and triggering return false
    }
    return false; //if char is missing - meaning the exact code is not there
}

问题是当使用 '0' 通配符时返回 false。这里出了什么问题？我的知识有限。

我在这个问题上研究了一段时间，并使用了“howboutthis howboutthat”方法，发现将 放在returnstep over 语句的末尾是可行的。

bool Lexicon::containsWordHelper(nodeT *w, string word, int &time, int &wag, string compare) //check if prefix can be combined
{
    if(word == "") { //base case: all letters found
        if ((w->begin-wag) <= time && time <= (w->end+wag)) 
            return w->isWord; // case 2: timecard check for high/low date range
        else if (time == ConvertDateToEpoch(9999, 01, 01)) return w->isWord; //this is for single code lookup w/o date
    } else {
        for(int i = 0; i < w->alpha.size(); i++) { //Loop through all of the children of the current node
            if (w->alpha[i].letter == word[0])
                return containsWordHelper(w->alpha[i].next, word.substr(1), time, wag, compare);
            else if (word[0] == 'ž')
                if (containsWordHelper(w->alpha[i].next, word.substr(1), time, wag, compare)) return true;
        }
    }
    return false; //if char is missing - meaning the exact code is not there
}

似乎合乎逻辑的是，如果我只有一条以 true 结尾的路径返回，那么我应该在递归完成后放置 return，然后只有在 true 时有条件地返回。它有效，回想起来似乎合乎逻辑，但我对此的信心充其量是粗略的。

我仍然有同样的问题。出了什么问题？

4

2 回答 2

0

您可以测试后一个containsWordHelper调用的结果，如果结果为真则返回真，否则继续迭代。

于 2012-08-08T21:10:00.550 回答
0

已解决：在包含递归调用的 if 语句之后放置一个 return

bool Lexicon::containsWordHelper(nodeT *w, string word) 
    {
        if(word == "") return w->isWord;
        else {
            for(int i = 0; i < w->alpha.size(); i++) {
                if (w->alpha[i].letter == word[0])
                    return containsWordHelper(w->alpha[i].next, word.substr(1));
                else if (word[0] == 'ž')
                    if (containsWordHelper(w->alpha[i].next, word.substr(1))) return true;
            }
        }
        return false;
    }
于 2012-08-13T16:25:29.130 回答