0

这是我的添加功能。我还没有完成，我必须使用顺序搜索将字符串添加到数组中，以找到要按字母顺序添加的插入点。我刚刚包含了这个 b/c，我们在添加随机字符串时使用它。

void StringList::add(string s) 
{
    str[numberOfStrings++]=s;       
}

这是我的二等分搜索功能

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

这是我将随机数的字符串添加到数组中的代码。（在使用传感器的单独 cpp 文件中）

if((token[0]=="ADDRAND")||(token[0]=="AR"))
{
    int count = stringToInt(token[1]);
    for(int i=0;i<count;i++)
    {
        stringList.add(randString(20));
    }
    result = "Random Strings added.\n";

}

如何使用 Bi-section search 按字母顺序将随机字符串添加到数组中？

4

2 回答 2

0

首先要做的是修改您的 bsearch() ，以便它可以返回在未找到时插入字符串的索引（一个好的开始可能会返回start而不是-1，但我不知道这是否足够）。

于 2013-07-03T14:25:56.457 回答
0

如果即使您能够找到要插入的索引，您也必须将该索引之后的所有元素推入一个步骤，以便为该字符串腾出位置。因此，这将花费每个步骤的线性时间。我不认为您将能够使用您的双向搜索方法来动态更新数组并使其保持排序。如果您尝试将已排序的字符串保留在连续的字符串索引中，则在数组中插入字符串或搜索索引都需要时间。

为此，您需要使用一些树结构，例如 AVL 树或 RB 树。此外，如果您需要现成的结构，stl set 可以达到目的。

于 2013-07-03T16:07:04.857 回答