我的任务是删除链接列表中的所有重复条目。假设列表是从最小到最大的顺序，因此我所需要做的就是删除相邻的重复项。
例如：如果列表在调用remove_duplicates((之前包含｛1,2,2,2,3,4,5,5,5,6｝，那么它应该在之后包含｛1,3,4,5,6}。
我的问题是，每当调用remove_duplicates()时，我的代码也会打印重复项。这是我的代码：
list.cpp:
#include <iostream>
using namespace std;
#include "list.h"
// on some machines member variables are not automatically initialized to 0
List::List()
{
m_head = NULL;
m_length = 0;
}
// delete all Nodes in the list
// since they are dynamically allocated using new, they won't go away
// automatically when the list is deleted
// Rule of thumb: destructor deletes all memory created by member functions
List::~List()
{
while (m_head)
{
Node *tmp = m_head;
m_head = m_head->m_next;
delete tmp;
}
}
// always insert at the front of the list
// Note: this works even in the SPECIAL CASE that the list is empty
void List::insert(int value)
{
if (!m_head || value < m_head->m_value)
{
m_head = new Node(value, m_head);
}
else
{
Node *ptr = m_head;
while (ptr->m_next != NULL && value > ptr->m_next->m_value)
{
ptr = ptr->m_next;
}
ptr->m_next = new Node(value, ptr->m_next);
}
m_length++;
}
// iterate through all the Nodes in the list and print each Node
void List::print()
{
for (Node *ptr = m_head; ptr; ptr = ptr->m_next)
{
cout << ptr->m_value << endl;
}
}
void List::remove_duplicates()
{
Node *curr = m_head;
Node *temp = m_head;
Node *delPtr = NULL;
if(curr == NULL)
{
return;
}
if(curr != NULL)
{
if(curr -> m_value == curr ->m_next ->m_value)
{
delPtr = curr;
curr = curr -> m_next;
temp ->m_next = curr;
delete delPtr;
}
else
{
curr = curr -> m_next;
}
}
}
list.h:
class List
{
public:
List();
~List();
void insert(int value); // insert at beginning of list
void print(); // print all values in the list
int length() {return m_length;}
void remove_duplicates();
int *convert_to_array(int &size);
private:
class Node
{
public:
Node(int value, Node *next)
{m_value = value; m_next = next;}
int m_value;
Node *m_next;
};
Node *m_head;
int m_length;
};
main.cpp:
#include <assert.h>
#include <iostream>
using namespace std;
#include "list.h"
int main()
{
List list;
int value;
// read values and insert them into list
while (cin >> value)
{
list.insert(value);
}
cout << "printing original list: n";
list.print();
list.remove_duplicates();
cout << "printing list after removing duplicates: n";
list.print();
}
注意：所有的东西都是我的老师给我的，我唯一应该写的代码是void List::remove_duplicates()
我查阅了stackoverflow的其他例子，但似乎没有一个能帮助我解决我的问题。此外，我还想提一下，我对链表及其功能还很陌生。因此，我不确定该从这里走向何方。如有任何帮助，将不胜感激
您需要使用当前指针的Address和当前指针来迭代列表。参见Linus关于理解指针。由于您不只是想删除具有某个值的节点，而是想在列表中向前扫描，删除具有该值的所有节点，因此您希望在每个节点上循环，并在循环中向前扫描删除具有当前节点值的所有节点。
通过检查m_next->m_value，如果它与当前节点值相同，则用下一个节点内容替换当前指针ADDRESS处的节点。由于仍然有一个指向已替换节点的指针，因此可以简单地delete该节点，然后从当前节点的地址更新指针。
这假设您的列表是排序的，正如您在问题中显示的那样。如果不是，则需要多次扫描列表。按照如图所示的排序顺序，您可以执行：
/* list must be in sort order */
void List::remove_duplicates()
{
Node **pp = &m_head, /* current address of head (pointer-to-pointer) */
*p = m_head; /* pointer to head */
/* loop over each node */
for (; p; pp = &p->m_next, p = p->m_next) {
/* while m_next and current value == next value */
while (p->m_next && (*pp)->m_value == p->m_next->m_value)
{
*pp = p->m_next; /* set node at current address to next node */
delete p; /* delete original node at that address */
p = *pp; /* update pointer to current node address */
}
}
}
(本质上，如果当前节点和下一个节点具有相同的m_value，则丢弃当前节点(并正确删除内存(并用下一个替换它(
例如，如果您的列表最初包含：
0 0 1 1 1 2 3 4 4 5 6 6 6 7 8 9 9 9
调用list.remove_duplicates()将导致：
0 1 2 3 4 5 6 7 8 9
仔细看看，如果你还有问题，请告诉我。