在链接列表中标识重复值C++

我想确定在用户输入的链接列表中哪些值和多少值是重复的。这是我写它的代码：在链接列表中标识重复值C++

int count; 
int compare, compare2; 

    for (p = first; p != NULL; p = p->next){ 
     compare = p->num; 
     for (j = first; j != NULL; j = j->next){ 
      if (compare == j->num){ 
       compare2 = j->num; 
       count++; 
      } 
     } 
     if (count > 1){ 
      cout << "There are at least 2 identical values of: " << compare2 << " that repeat for: " << count << "times" << endl; 
     } 
    }

基本上它的想法是，我采取的第一个元素在第一循环，并将其与第二循环中的所有元素，如果有这样的情况算他们是相似的，然后打印结果 - 然后我拿下一个元素，等等。

但是，输出是所有元素，它也不能正确计数。我只是迷失在如何调整它。

我试过在两个循环中使用相同的p变量，因为它是我想要循环的同一个列表，但是一旦输入完成，那么.exe失败。

我看到了一些有关删除重复值的函数的例子，但比较部分通过while循环运行，我只是想知道 - 我在做这个错误？

来源

2014-10-28 TangoJuliet

怎样通过调试器一行一行地逐行执行代码，以获取实际出错的内容它？ – 2014-10-28 17:26:26

你可以用'std :: map '而不是写一个O（n^2）循环来轻松做到这一点。 – PaulMcKenzie 2014-10-28 17:27:29

您没有将'count'初始化为0. – PaulMcKenzie 2014-10-28 17:39:23

由于p和j都遍历整个列表，因此您的逻辑有缺陷。当p == j时，这些值必须匹配。

改变块

 if (compare == j->num){ 
      compare2 = j->num; 
      count++; 
     }

到

 if (p != j && compare == j->num){ 
      compare2 = j->num; 
      count++; 
     }

而且，你不需要行

  compare2 = j->num;

因为compare2将等于compare。

您可以通过稍微更改inner for循环来减少测试次数。然后，您将不需要0位。

for (j = p->next; j != NULL; j = j->next){ 
     if (compare == j->num){ 
      count++; 
     } 
    }

来源

2014-10-28 17:30:41

谢谢！你的建议确实可以解决一些问题，但是输出仍然很糟糕 - 它会输出重复的值，出现循环的所有时间，或者（第二次修复）它会打印出所有值，表明它们至少重复一次。 – TangoJuliet 2014-10-28 18:00:13

问题是你不排除你比较的元素（compare）。所以对于每个元素，它至少有一个重复 - 本身！尝试比较仅在内部循环中跟随当前的元素（p）。

来源

2014-10-28 17:29:45 NikolayKondratyev

我申请了第二个if语句来解决这个问题。无论如何，像count一样，它会检查自己，但是如果它更大，那么值会在列表中稍后重复。然而，这并不完全按照预期工作。 – TangoJuliet 2014-10-28 17:51:54

@Elsa在'compare = p-> num;'之前加上'count = 0;' – NikolayKondratyev 2014-10-28 18:02:36

Omg，是的！现在它工作了！随着你的建议和@ R-Sahu它终于完全奏效！谢谢！！我很抱歉，我还不能赞成，你们都帮助过:) – TangoJuliet 2014-10-28 18:07:02

你O（N * N）方法：

// Pick an element 
for (p = first; p != NULL && p->next !=NULL ; p = p->next) 
{ // Compare it with remaining elements 
    for (j = p->next ; j != NULL; j = j->next) 
    { 
     if (p->num == j->num) 
     {   
      count++; 
     } 
    if(cout > 1) 
    { 
     std::cout << p->num << " occurs "<< count << times << '\n' ; 
    } 
}

其更好地使用HashMap来解决，这是O（N）时间ň额外的空间

std::unordered_map<int, int> m ; 
for(p = first; p != NULL ; p = p->next) 
{ 
    m[ p->num ]++; 
} 
for (const auto &pair : m) 
{ 
    if(pair.second > 1) 
     std::cout << pair.first << ": " << pair.second << '\n'; 
}

来源

2014-10-28 17:31:33 P0W

在链接列表中标识重复值C++

回答

相关问题