0

我正在开发一个二叉搜索树控制台应用程序，特别是一种列出两个目标节点之间最短路径的方法。我的方法是

1) 创建树中从根节点到目标的每个目标节点的值的 ArrayList（每个路径一个 ArrayList） 2) 比较两个 ArrayList，删除除最后一个之外的所有重复项（这将表示两个路径分支 3) 将剩余的两个 ArrayList 组合成一个数组并使用 for 循环打印到控制台

这是我正在使用的方法。我遇到的问题是我永远不会进入读取“if (list1[n] == list2[n])”的块，即使 ArrayLists 正在打印出 _pathArrayList1 的值 Contents: 5, 7 , 9 _pathArrayList2 的内容: 5, 7, 9, 10, 12, 11

我尝试了打字，但这没有帮助。

array<T>^ removeDuplicates(ArrayList^ list1, ArrayList^ list2)
{
    int forLoopCount;
    int i; // for loop iterator for this method
    Console::WriteLine(L"Contents of _pathArrayList1: ");
    for (i = 0; i < list1->Count; i++)
        Console::WriteLine(list1[i]);

    Console::WriteLine(L"Contents of _pathArrayList2"); 
    for (i = 0; i < list2->Count; i++)
        Console::WriteLine(list2[i]);

    // find out which array is the shortest; we need to use the shorter of the two
    if (list1->Count - list2->Count < 0)
        forLoopCount = list1->Count;
    else
        forLoopCount = list2->Count;
    Console::WriteLine("Value of forLoopCopunt is " + forLoopCount);
    array<T>^ combineArray = gcnew array<T>(forLoopCount);

    for (int n = 0; n < forLoopCount; n++)
    {
        Console::WriteLine(L"List1[n] = " + list1[n]);
        Console::WriteLine(L"list2[n] = " + list2[n]);

        if (list1[n] == list2[n])  // never entering this block of code
        {
            if (list2[n+1] == list1[n+1])
            {
                Console::WriteLine(L"Removing " + list1[n] + " and " + list2[n]);
                list1->RemoveAt(n);
                list2->RemoveAt(n);
                n --;
            }
            else
            {
                Console::WriteLine(L"Deleting " + list1[n]);
                list1->RemoveAt(n);
                //_pathArrayList1->Reverse();
                return combineArray = combineArrays(_pathArrayList1, _pathArrayList2);
            }
        }
    }
    return combineArray = combineArrays(_pathArrayList1, _pathArrayList2);
}
4

1 回答 1

0

请澄清“我试过打字，但没有帮助。”。

ArrayList不使用泛型，因此它将所有内容都作为对象处理。即使这两个对象是整数，当它们被键入为 Object 时，==也不会像您期望的那样比较整数值。

Object^ o1 = 1;
Object^ o2 = 1;

bool asObject = (o1 == o2); // false
bool asInt = ((int)o1 == (int)o2); // true

如果您切换出ArrayListfor List<int>，那么==将按您的预期工作，并具有类型安全的额外好处。

其他注意事项：

  • 设置时使用Math.MinforLoopCount。如果其他人不得不停下来思考一下代码是否正确，那么对于这么简单的事情，请使用该函数。
  • 在检查 if 之前list2[n+1] == list1[n+1]，请确保两个列表中都有一个额外的项目。list1[n]在您的示例数据（5-7-9 和 5-7-9-10-12-11）中，当9时，这会给您一个例外。
  • 您可以删除gcnew array<T>(forLoopCount)，甚至combineArray完全删除。当您分配 combineArrays 的返回值时，该对象将被丢弃。

编辑

如果传递列表中的对象是项目本身（不是它们的节点地址，或者其他总是 的东西int），那么我建议添加where T : IEquatable<T>到通用定义中。这为您提供了一个Equals(T)方法，您可以使用它来代替==，它不是为所有类型定义的。（如果你在你的类型上实现这个，只要确保实现所有三个方法 Equals(T)、Equals(object) 和 GetHashCode()，这样一切都是一致的。）

为了帮助首先构建搜索树，您可能会发现它IComparable<T>很有用。使用 CompareTo 方法而不是比较运算符（例如，<）。

于 2013-02-04T19:47:50.917 回答