我的任务是删除链接列表中的所有重复条目。假设列表是按从小到大的顺序排列的,那么我要做的就是将重复项彼此相邻地删除。
例如:如果列表在调用remove_duplicates()之前包含{1,2,2,2,3,3,3,4,5,5,5,5,5,5,6},则该列表应包含{1,2,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的其他示例,但似乎没有一个能帮助我解决我的情况。另外,我确实要提及的是,我对链表及其功能仍然很陌生。因此,我不确定从这儿去哪里。任何帮助,将不胜感激
您需要使用当前指针的地址和当前指针来遍历列表。请参阅Linus了解指针。由于您不仅要删除具有某个值的节点,而且还想在列表中向前扫描以删除具有该值的所有节点,因此您要遍历每个节点,并在循环扫描中删除所有节点与当前节点的值。
通过检查m_next->m_value
和,如果它与当前节点值相同,则用下一个节点内容替换当前指针ADDRESS处的节点。由于您仍然有一个指向要替换的节点的指针,因此可以简单地delete
对该节点进行操作,然后从当前节点的地址更新该指针。
假设您的问题中显示的是您的列表在SORT-ORDER中。如果不是,则需要多次扫描列表。按照所示的排序顺序,您可以执行以下操作:
/* 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
仔细检查一下,如果您还有其他问题,请告诉我。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句