使用初学者问题的C++链表

Question

在过去的几个月里，我一直在学习C++，在完成了一门在线课程后，我开始使用原始指针进行一些挑战。我已经成功地创建了一个可以初始化和遍历链表的类，尽管我很难创建一个删除其元素的方法，但我很难编写一个删除所有重复项的方法。

我有一种方法，比如

void linked_list::remove_dups(){
Node *p = first;
Node *g = first;
while(p!=NULL){
int x = 0;
g = new Node;
g = first;
Node *remove = first;
while (g!=NULL){
if(p->data == g->data){
x++;
}

if(x>1){
remove = new Node;
remove = p;
p = p->next;
remove->next = p->next;
delete remove;
x--;
}
g = g->next;
}
p = p->next;
}
}

其中Node是标准

struct Node{
int data;
struct Node *next;
};

首先是私人会员

Node *first;

有人能指出这个函数的错误并解释一下吗？我用指针启动了列表int a[] = {3,5,5,7,65,5,65,65,4,4,15};它删除了大部分副本，但不是全部。如果我添加更多，我会出现EXC_BAD_ACCESS错误。

非常感谢您的帮助！

Answer 1

主要问题是：

p = p->next;
remove->next = p->next;
delete remove;

您尝试将remove->next设置为指向新的下一个元素。但是remove将被删除。因此remove之前的元素仍然指向已删除的内容。因此，在删除之后，您将得到一个包含指向已删除元素的指针的破碎列表。下一次循环迭代，它将中断。

下面是我边走边编辑的代码。请注意

remove = new Node;
remove = p;

不仅没用，还会泄露内存。你可以直接做remove = p;

我边走边起草代码。未修复。适当的做法是保留一个prev指针或其他什么。

void linked_list::remove_dups()
{
Node *p = first;
Node *g = first;
while(p!=NULL)
{
// int x = 0; remove this
// g = new Node; remove this
g = first;

Node *remove = first;
while (g != NULL)
{
if(p->data == g->data) // test directly, no x
{
// remove = new Node; remove this
remove = p;
p = p->next;
// remove->next = p->next; You are going to delete this, no point modifying it
delete remove;
}
g = g->next;
}
p = p->next;
}
}

Answer 2

我为我的自定义双链接列表写的东西，它将删除重复项。不一定是最高效的，但它能完成任务。

void unique()
{
std::map<int, int> hash;
Node<T>* temp = this->head;
while(temp)
{
hash[temp->data]++;
if(hash[temp->data] > 1)
{
Node<T>* next = temp->next;
Node<T>* prev = temp->prev;
delete temp;
temp = nullptr;
if(!next)
{          
temp = prev;
temp->next = nullptr;
hash[temp->data]--;
break;
}
next->prev = prev;
prev->next = next;
temp = next;
hash[temp->data]--;
}
else
{
temp = temp->next;
}
}
}