测试链表是否彼此相等

Question

我有一组在链表中的数字。 我想比较它们，看看它们是否是一组中的相同数字。 这是我现在的代码：

bool set::equalset(set second)
{
     Data *travel1, *travel2;
     travel1 = top;
     travel2 = second.topval(); //gets the top value for the second set
     while (travel2->next != NULL && travel1->next != NULL)
     {
           if (!in(travel2->value))  //in checks if the value is in the set
               return false;
           if (!second.in(travel1->value)) //same idea here
               return false;
           travel2 = travel2->next;
           travel1 = travel1->next;
           return true;
     }
     return false;
}

因此，我的代码所做的是获取两个集合的顶部值，并将这些值分别等于 travel1/2，然后虽然 travel 不指向两个集合中的空值，但它遍历列表并检查来自任何一个集合的值是否彼此。 如果未找到值，则将其设置为 false。 否则，它将设置为 true，并且发现它们相等。

但是，此代码仅工作一半 - 您可以通过为第一组输入 1、2 和为第二组输入 1、2、3 来轻松打破它，它们将相等返回。我认为第三个值 (3( 会使其返回 false。这里缺少什么环节？

Answer 1

您的代码有几个问题。首先，您没有检查最后一个节点。像这样的循环条件：

while (travel2->next != NULL && travel1->next != NULL)

一旦其中一个枚举器到达最后一个节点，就会中断，但从不检查它。此外，这也意味着两组单节点将始终比较真实。

接下来，仅在第一次迭代后，您就有一个硬返回，因此无法想象在以相同节点值开头的两个集合上返回 false。

travel2 = travel2->next;
travel1 = travel1->next;
return true; // this doesn't belong here.

接下来，按值传递参数，这意味着正在调用复制构造函数。我不知道您是否实现了它(如果您没有实现，那么您将面临完全不同的问题(，但是没有理由复制列表以查看它是否等于*this*.该函数应将常量引用作为参数。

bool set::equalset(const set& second)

最后，您的退出条件是正确的，但您不能假设列表都已用尽。 你必须验证它。您可以通过返回 false 来做到这一点，如果任何一个旅行者是非空的(其中一个是如果列表不均匀。

把所有的东西放在一起：

bool set::equalset(const set& second)
{
     const Data *travel1 = top;
     const Data *travel2 = second.top;
     while (travel1 && travel2)
     {
           if (!in(travel2->value))  //in checks if the value is in the set
               return false;
           if (!second.in(travel1->value)) //same idea here
               return false;
           travel2 = travel2->next;
           travel1 = travel1->next;
     }
     return !(travel1 || travel2);
}

---

针对排序列表进行了优化

如果在输入和删除方法期间保持列表排序，则可以大大简化此操作，如下所示：

bool set::equalset(const set& second)
{
     const Data *travel1 = top;
     const Data *travel2 = second.top;
     while (travel1 && travel2 && travel1->value == travel2->value)
     {
           travel1 = travel1->next;
           travel2 = travel2->next;
     }
     return !(travel1 || travel2);
}

Answer 2

在您描述的情况下，在搜索第二个集合的第三个元素之前，第一个集合的迭代器将为 NULL，从而中断您的 while 循环。您也可以单独遍历每个集合。您还可以在比较每个集合的元素之前检查两个集合是否具有相同数量的元素。

Answer 3

您需要调整返回条件，因为截至目前，如果每个列表中都存在this和second中的第一个值，则返回 true。

请改为执行以下操作：

bool set::equalset(set second)
{
     Data *travel1, *travel2;
     travel1 = top;
     travel2 = second.topval(); //gets the top value for the second set
     while (travel2->next != NULL && travel1->next != NULL)
     {
           if (!in(travel2->value))  //in checks if the value is in the set
               return false;
           if (!second.in(travel1->value)) //same idea here
               return false;
           travel2 = travel2->next;
           travel1 = travel1->next;
     }
     return true;
}

Answer 4

如果

两个集合具有不同数量的成员，则使用您的代码。 您的循环将以 travel1 或 travel2 的形式退出，其中 no. 的元素将指向 NULL ，而其他元素仍未NULL。在您的情况下，travel1将指向NULL，并且仍然有元素需要解析travel2

通过以下代码检查

bool set::equalset(set second)
{
     Data *travel1, *travel2;
     travel1 = top;
     travel2 = second.topval(); //gets the top value for the second set
     while (travel2->next != NULL && travel1->next != NULL)
     {
           if (!in(travel2->value))  //in checks if the value is in the set
               return false;
           if (!second.in(travel1->value)) //same idea here
               return false;
           travel2 = travel2->next;
           travel1 = travel1->next;

     }
     if (travel2->next == NULL && travel1->next == NULL)
     {
      return true;
     }
     return false;
}

在此代码中，对于两个带有元素 1 2 2 和 1 2 的集合，它将返回 false