c#:在两种不同的数据结构中递归搜索
本文关键字:数据结构 递归 搜索 两种 | 更新日期: 2023-09-27 18:12:20
我需要在c#中执行两种不同数据结构的搜索,下面是交易:我有一个名字(这是一个字符串),我想执行搜索。我有一个名为Exists
的函数,它将返回一个bool
,指示它是否存在。
如果存在,我增加名称(简单地在字符串末尾添加1),然后我需要再次执行搜索(通过方法exists
),以查看是否存在具有新名称的对象。
这个过程会一直持续下去,直到有一个我可以使用的未使用的名称,但是,如果它不存在,现在我应该执行搜索另一个包含被删除的对象的数据结构,如果在那里找到字符串,那么我必须再次增加名称,并从头开始搜索。如果没有使用Exists
方法或在所有被删除的对象所在的数据结构中没有具有此名称的对象,则这一切都将结束。
我该如何解决这个问题?
我希望我清楚地表达了自己:-)
提前感谢!
string BuildNextName(string originalName)
{
string name = originalName;
while( Exists(name) || deletedNames.Contains(name))
{
name = Increment(name);
}
return name;
}
还是我错过了什么?
使用for循环:
string BuildNextName(string originalName)
{
for (string name=originalName;
Exists(name) || deletedNames.Contains(name);
name = Increment(name));
return name;
}
顺便说一句,我猜你的名字增量算法比简单地加1更复杂:name, name1, name2,…基本上,如果名称不是以数字结尾,则附加"1"。如果是,则增加该数字。对吧?
非递归的简单解决方案可能是这样的(我认为在这种情况下不需要递归)
//pseudocode
String name;
bool condition = true;
while(condition)
{
if(ExistInFirstDataStructure(name))
{
//increment name
}
else
{
if(ExistInDeletedDataStructure(String name))
{
//increment name
}
else
{
condition = false;
}
}
}
bool ExistInFirstDataStructure(String name)
{
}
bool ExistInDeletedDataStructure(String name)
{
}
为什么要使用循环??(我知道LINQ会在引擎盖下)
var LastUsedObjectName =
MyObjects.Select(mo => mo.Name)
.Union( MyDeletedObjects.Select(mo => mo.Name))
.OrderByDescending(name => /*Function to order by integer part of name*/).First();
// Now add 1 to LastUseObjectName and use that.
这个怎么样:
var listOfExistingNames = new List<string> { "MyName", "MyName1", "MyName3" };
var listOfDeletedNames = new List<string> { "MyName2", "MyName5" };
int counter = 0;
string baseToFindFreePlace = "MyName";
string newName = baseToFindFreePlace;
var allNames = listOfExistingNames.Concat(listOfDeletedNames);
while (allNames.Contains(newName))
{
counter++;
newName = baseToFindFreePlace + counter;
}
listOfExistingNames.Add(newName);
如果你为两个数据结构都创建了Exists
方法,你可以像这样递归搜索:伪代码:
string resultName;
void Search(string name)
{
if(ExistsInFirstStructure(name)) //name is in first data structure
Search(name + "1"); //add 1 and try again
else
if(ExistsInSecondStructure(name)) //name exists in second data structure
Search(name + "1"); //perform search again
else
resultName = name; //current name wasn't found in first and second data structures - we have result
}