测试链表是否相等 [英] Testing if a linked list is equal to each other

问题描述

我有一组位于链表中的数字.我想比较它们以查看它们在一组中是否相同.这是我现在的代码:

I have a set of numbers that are in a linked list. I want to compare them to see if they are the same numbers in a set. Here is my code right now:

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 并且发现它们相等.

So what my code does is grab the top values for both of the sets and sets those equal to travel1/2 respectively, then while travel doesn't point to a null value in both sets, it traverses the lists and checks if values from either of the sets are in each other. If a value is not found, it sets it to false. Otherwise, it will be set to true and they are found to be equal.

但是，此代码仅起作用了一半 - 您可以通过为第一组输入 1, 2 和为第二组输入 1, 2, 3 轻松打破它，它们将被同等地返回.我认为第三个值 (3) 会使其返回 false.这里缺少的链接是什么?

However, this code only half works - you can easily break it by entering 1, 2 for the first set and 1, 2, 3 for the second set and they will be returned as equal. I would think that the third value (3) would make it return false. What is the missing link here?

推荐答案

您的代码有几个问题.首先，您没有检查 last 节点.像这样的循环条件:

Your code has several problems. First, you're not checking the last node. A loop condition like this:

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

将在其中一个枚举器到达最后一个节点时中断，但从不检查它.此外，这也意味着两组 单个-节点-每个都将始终比较为真.

will break as soon as one of the enumerators reaches the last node, but never checks it. Further, it will also mean two sets of a single-node-each will always compare true.

接下来，您只有在第一次迭代后才能硬返回，因此无法想象这种曾经在以相同节点值开始的两个集合上返回 false 的方法.

Next, You have a hard return after only the first iteration, so there is no conceivable way this ever returned false on two sets that started with the same node value.

travel2 = travel2->next;
travel1 = travel1->next;

return true; // this doesn't belong here.

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

Next, you pass your parameter by-value, which means the copy constructor is being invoked. I don't know whether you implemented it or not (and if you didn't, you have an entire different problem), but there is no reason to duplicate the list just to see if it is equal to *this*. The function should take a const-reference as the parameter.

bool set::equalset(const set& second)

最后，您的退出条件是正确的，但您不能假设两个列表都已用完.你必须验证它.您可以通过返回 false 来实现这一点，如果 任一 traveler 不为空(如果列表不均匀，其中一个将是非空的.

Finally, your exit condition is correct, but you cannot assume the lists were both exhausted. you have to verify it. You can do this by returning false if either traveler is non-null (and one of them will be if the lists are uneven.

综合起来:

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);
}

<小时>

针对排序列表进行了优化

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

If you keep the lists sorted during input and removal methods, you can significantly make this easier, seen below:

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);
}

这篇关于测试链表是否相等的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！