C++删除列表中的重复元素

Question

我的任务是从列表中删除任何重复的元素。我正在为我的函数使用结构和指针。这是结构和函数：

struct node
{
    int key;
    node *next;

}*start = NULL;

int SIZE = 0;

添加项目时尺寸会增加。有删除重复功能：

void del_dup() 
{
    if (!start) {
        return;
    }
    if (SIZE == 1) {
        return;
    }

    node * pointer = start->next;
    node * prev = start;

    node * mPointer = nullptr;
    node * mPrev = nullptr;

    for (int i = 0; i < SIZE - 1; i++)
    {
        if (pointer->next) 
        {
            mPointer = pointer->next;
            mPrev = pointer;
        }
        for (int j = i + 1; j <= SIZE; j++)
        {
                if (pointer->key == mPointer->key)
                {
                    mPrev->next = mPointer->next;

                    delete mPointer;
                }
                else
                {
                    mPrev = mPointer;
                    mPointer = mPointer->next;
                }
        }
        prev = pointer;
        pointer = pointer->next;
    }
}

问题是我在 if 语句中崩溃以比较两个元素是否匹配：

if (pointer->key == mPointer->key)

错误是访问冲突类型和 nullptr for mPointer。

用户每次运行程序时都会用他想要的值填充该列表。这是推送功能：

void push_start(int n) {
    elem *p = start;
    start = new elem;
    start->key = n;
    start->next = p;
    SIZE++;
}

如能帮助解决此问题，我们将不胜感激。感谢转发！

Answer 1

据推测，您在某个时候将键与已删除的节点进行比较。 ~~例如，您正在分配 mPointer = pointer->next，然后可能删除 mpointer，然后在内循环结束时分配 pointer = pointer->next。那么pointer->next是不是已经被删除了？~~

编辑

实际上，您的内部循环条件更可能是问题所在。尝试一下：

for (int j = i + 1; j < SIZE; j++)

相反。

Answer 2

对于初学者来说，在结构定义之外声明变量 SIZE 是个坏主意。在这种情况下，所有处理列表的函数都将受到访问全局变量的影响。程序中不能有多个列表。

您可以 "wrap" 另一个结构中的结构节点，例如

struct node
{
    int key;
    node *next;

};

struct list
{
    node *head;
    size_t /*int*/ size;
};

在这种情况下，每个列表都有其一个数据成员大小。

函数 del_dup 看起来很混乱，您使用了令人困惑的名称，例如 pointer 和 mPointer。您不应依赖删除节点时应递减的变量 SIZE。

我可以建议以下功能实现。

#include <iostream>
#include <cstdlib>
#include <ctime>

struct node
{
    int key;
    node *next;
} *head = nullptr;

size_t size;

void push_front( node * &head, int key )
{
    head = new node { key, head };
    ++size;
}

std::ostream & display_list( node * head, std::ostream &os = std::cout  )
{
    os << size << ": ";

    for ( const node *current = head; current; current = current->next )
    {
        os << current->key << ' ';
    }

    return os;
}

void del_dup( node * head )
{
    for ( node *first = head; first; first = first->next )
    {
        for ( node *current = first; current->next;  )
        {
            if ( current->next->key == first->key )
            {
                node *tmp = current->next;
                current->next = current->next->next;
                delete tmp;
                --size;
            }
            else
            {
                current = current->next;
            }
        }
    }
}

int main() 
{
    const size_t N = 10;

    std::srand( ( unsigned int )std::time( nullptr ) );

    for ( size_t i = 0; i < N; i++ )
    {
        push_front( head, std::rand() % ( int )N );
    }

    display_list( head ) << std::endl;

    del_dup( head );

    display_list( head ) << std::endl;

    return 0;
}

程序输出可能看起来像

10: 2 2 3 3 8 5 6 2 6 1 
6: 2 3 8 5 6 1

C++删除列表中的重复元素

Deleting duplicate elements in a list in c++

c++

struct

pointers

list

singly-linked-list

编辑