为什么给定的代码(使用哈希从链表中删除重复项的程序)没有显示任何输出

Question

我想写一个程序，从链表中删除重复项并打印链表。

我使用了一种哈希方法来实现这一点：

#include <iostream>
#include <unordered_map>
using namespace std;
struct Node{
int data;
Node* next;
};
unordered_map<int,int> hashmap;
Node* head = NULL;
void deldups()
{
Node* h = head;
Node* prev = NULL;
Node* curr;
curr = h;

while (curr != NULL)
{
int val = curr->data;
if (hashmap.find(val) != hashmap.end())
{
if (hashmap[val] > 1)
{
prev->next = curr->next->next;
delete(curr);
}
}
else{
++hashmap[val];
prev = curr;
}
curr = prev->next;
}
}
void print()
{
Node* temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}
int main() 
{
Node* firstnode = new Node();
head = firstnode;
firstnode->data = 5;
Node* secondnode = new Node();
firstnode->next = secondnode;
secondnode->data = 6;
Node* thirdnode = new Node();
secondnode->next = thirdnode;
thirdnode->data = 7;
Node* forthnode = new Node();
thirdnode->next = forthnode;
forthnode->data = 5;
Node* fifthnode = new Node();
forthnode->next = fifthnode;
fifthnode->data = 9;
fifthnode->next = NULL;

deldups();
print();
return 0;
}

代码说明：

1. 在ptr不为NULL时遍历链表，检查映射(unordered<int,int>(中是否存在给定元素(h->data(。

   注意我使用元素作为映射中的键，而不是其值，该值将用于计算其重复项。

2. 如果键存在，则我们将检查其值，如果值大于"1"，即元素存在多次，则从链表中删除该节点。

3. 否则，将元素键添加到hashmap中，并将其值递增1。

运行代码后，没有输出。为什么？

Answer 1

您的代码没有输出任何内容的原因是deldups()陷入了无限循环(如果您在调试器中运行代码，或者至少让deldups()输出它正在做的事情，您会看到这种情况(。

当hashmap.find()发现重复时，curr不会前进到重复后的下一个节点，因此后续迭代会一次又一次地找到相同的重复。curr未被高级化的原因是表达式hashmap[val] > 1是nevertrue，因为hashmap[val]不会递增到1以上，所以您不会删除重复项并将curr高级化到下一个节点。

要解决此问题，您需要检查> 0而不是> 1。在这种情况下，您实际上不再需要计数重复项，您只需要知道它们是否存在，因此使用std::unordered_map就显得有些过头了。使用std::set就足够了。

修复后，这个声明也是错误的：

prev->next = curr->next->next;

你跳过了不需要跳过的节点，这是在破坏你的列表。此外，如果curr是列表中的最后一个节点，则next将为NULL，因此访问next->next将是未定义的行为。

这句话应该是这样的：

prev->next = curr->next;

话虽如此，试试这个：

#include <iostream>
#include <set>
using namespace std;
struct Node{
int data;
Node* next;
};
set<int> hashmap;
Node* head = NULL;
void deldups()
{
Node* prev = NULL;
Node* curr = head;

while (curr != NULL)
{
int val = curr->data;
if (!hashmap.insert(val).second)
{
prev->next = curr->next;
delete curr;
}
else
{
prev = curr;
}
curr = prev->next;
}
}
void print()
{
Node* temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
}
int main() 
{
Node* firstnode = new Node();
head = firstnode;
firstnode->data = 5;
Node* secondnode = new Node();
firstnode->next = secondnode;
secondnode->data = 6;
Node* thirdnode = new Node();
secondnode->next = thirdnode;
thirdnode->data = 7;
Node* forthnode = new Node();
thirdnode->next = forthnode;
forthnode->data = 5;
Node* fifthnode = new Node();
forthnode->next = fifthnode;
fifthnode->data = 9;
fifthnode->next = NULL;

deldups();
print();
return 0;
}

在线演示

也就是说，您可以考虑使用标准的std::list或std::forward_list容器，而不是实现手动链表。然后，您可以使用标准的std::unique()或std::remove_if()算法来删除重复项。