如何删除链表输入中的重复条目?

福吉

我的任务是删除链接列表中的所有重复条目。假设列表是按从小到大的顺序排列的,那么我要做的就是将重复项彼此相邻地删除。

例如:如果列表在调用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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章