1

我有 2 个功能。函数 Find 进行双向搜索，这意味着它按部分搜索数组，直到找到键并返回其位置。函数 removef 或 (remove fast) 抓取该位置并将其从字符串数组中删除。我正在使用命令行界面，它要求用户输入命令和字符串（字符串被删除），因此不需要提示用户输入字符串。

这是我的查找功能

int StringList::Find(string key, int start, int end)
{
    int middle = (end + start)/2;
    if (key > str[middle])
    {
        return Find(key,middle,end);
    }
    else if ( key < str[middle])
    {
        return Find(key,start,middle);
    }
    else if (key == str[middle])
    {
        return middle;
    }
}

Find 函数应该确定键是在数组的上半部分还是下半部分（中间以上或中间以下），然后继续划分，直到找到需要删除的键或字符串。

这是removef：

void StringList::removef(string s)
{
    int loc = Find(s,0,10000); //ignore these parameters, i know they are wrong they are just an example


        for(int j=loc; j<(numberOfStrings)-1; j++)
        {
            str[j] = str[j+1];
        }
        numberOfStrings--;

}

我的问题是我的 Find 功能使用双向搜索。关于我可以解决的任何问题的任何建议？我真的卡住了。谢谢！

4

2 回答 2

2

我可以看到的一个问题是，当键大于中间元素时，您将新范围设置为[midde,end]，但它应该是[middle+1,end]- 再次考虑中间元素没有意义，因为您已经知道它不是匹配项。

所以第一个条件应该是这样的：

if (key > str[middle])
{
    return Find(key,middle+1,end);
}

此外，正如其他人所提到的，您需要检查字符串是否不在数组中。我建议在您的Find方法开始时添加类似的内容。

if (start == end) return -1;

一旦您将数组细分到起点等于终点，就没有更多空间可供搜索，也不会找到您的字符串。

除此之外，我唯一能想到的可能是错误的就是你调用Find了错误范围的方法。它应该这样调用：

int loc = Find(s,0,numberOfStrings);
于 2013-07-01T20:51:16.587 回答
1

首先，我假设您已经对字符串“str”数组进行了排序……否则二进制搜索将不起作用。

在您的“查找”函数中，您访问“str”数组，我假设它是您的字符串数组，但是您不将此数组作为参数传递。因此，除非它是一个试图访问它的全局数组，否则它将不起作用。

最后，由于您正在递归调用此函数，因此您需要有一个案例来处理根本不包含在数组中的字符串。

于 2013-07-01T20:03:28.953 回答