链表保留功能不起作用

Question

这是数据结构课程的旧作业。 objective 是为了完成保留功能，其工作方式如下：listy.retain(listx) 结果是删除 listy 中不包含在 listx 中的元素。

我尝试编写自己的代码如下。

template<class Type>
void linkedList<Type>::retain(const linkedList<Type>& other) 
{
    // Implement this function
    node<Type>* y = first;
    node<Type>* x;

    while(y != NULL)
    {
        x = other.first;

        while(x != NULL)
        {
            if(x->info == y->info)
                break;
        }
        if(x == NULL)
            remove(x->info);
        y = y->link;
    }
}

另外，在作业的一部分中提供了使用的删除功能。

template<class Type>
void linkedList<Type>::remove(const Type& x) 
{   //remove the first instance of x in the list

    node<Type> *p, *q;
    p = first;
    q = NULL;

    while (p != NULL && p->info != x)
    {
        q = p;
        p = p->link;
    }

    if (p != NULL)
    {
        if (p == first)         
            first = first->link;         
        else         
            q->link = p->link;

        if (p == last)
            last = q;

        delete p;
        count--;        
    }
}

构建没有错误，但最初它应该显示新列表，但现在它在初始条件后完全停止输出。

**** Part-1 unordered linkedList ****

-- Test 1A --
listx (len = 7) : 5 3 7 7 5 4 3 
listy (len = 7) : 2 8 4 7 3 1 9

有什么想法吗？？这是我第一次发帖，欢迎任何反馈，在此先感谢！

Answer 1

我相信这如果（x == NULL）删除（x->信息）；应该如果（x！= NULL）删除（x->信息）；

Answer 2

函数 retain 有一个无限循环。

    x = other.first;

    while(x != NULL)
    {
        if(x->info == y->info)
            break;
    }

如果第一个 x->info != y->info 当循环对同一个节点重复相同的迭代 x 因为 x 没有被改变。

和这个声明

    if(x == NULL)
        remove(x->info);

应替换为

    if(x == NULL)
        remove(y->info);

但在任何情况下，最好删除函数保留内的节点，而不是单独调用函数删除。

和这个声明

    y = y->link;

如果节点 y 将被前面的函数 remove 调用删除，则可能导致未定义的行为。

至少内部循环应该是这样的

x = other.first;

while( x != NULL && x->info != y->info ) x = x->link;

if ( x == NULL )
{
    node<Type>* tmp = y->link;
    remove( y->info );
    y = tmp;
}
else
{
    y = y->link;
}

你还应该检查删除节点是否是节点first。否则节点 first 可能无效。

链表保留功能不起作用

Linked List Retain Function Not Working

c++

linked-list