从链接列表中搜索和删除

Question

我在使用此功能时遇到问题。该函数应该在链表中搜索学生并删除该节点，或者如果找不到该学生则打印一条错误消息。以下代码无法正常运行，它会删除正在搜索的节点之后的下一个节点。

void vymazstudenta(STUDENT **head,const char *priezvisko)
{
    STUDENT *traverse = *head;
    while(traverse!=NULL)
    {
        if(!strcmp(traverse->priezvisko,priezvisko))
        {
        STUDENT *hladany = traverse->next;
        traverse->next = hladany->next;
        free(hladany);
        return;
        }
        traverse = traverse->next;
    }
        fprintf(stderr,"Student %s sa nenasiel.\n",priezvisko);
        return;
}

Answer 1

当遍历列表时，您必须存储您正在检查的节点之前的节点（我在下面的代码片段中使用了名为 previous 的指针）。

当您找到匹配节点时，您只需将前一个节点上的 next 设置为当前节点的 next，这样列表就会跳过要删除的节点。然后就可以free()匹配节点了。

请注意，您应该处理要删除的节点是第一个节点的特殊情况（head）

在下面的代码片段中，您会在 if( previous == NULL ) 块中看到这一点 - 它不言自明。

void vymazstudenta(STUDENT **head,const char *priezvisko)
{
    STUDENT *traverse = *head;
    STUDENT *previous = NULL;
    while( traverse != NULL )
    {
        if( strcmp(traverse->priezvisko,priezvisko) == 0 )
        {
            if( previous == NULL )
            {
                *head = traverse->next;
            }
            else
            {
                previous->next = traverse->next;
            }
            free( traverse );
            return;
        }
        else
        {
            previous = traverse;
            traverse = traverse->next; 
        }
    }

    fprintf(stderr,"Student %s sa nenasiel.\n",priezvisko);
    return;
}

Answer 2

您需要在之前跟踪元素 traverse，以便您可以更改该元素的下一个指针以指向元素在 traverse 之后。之后你可以free(traverse)

另外你需要处理一个特殊情况。那是当匹配在 *head 元素上时。在这种情况下，您必须更新 *head 以获得新的列表头。

类似于：

void vymazstudenta(STUDENT **head,const char *priezvisko)
{
    if (*head == NULL)
    {
        // empty list
        return;
    }

    if(!strcmp(*head->priezvisko,priezvisko))
    {
        // Special case:
        // Remove the *head element

        STUDENT *hladany = *head;  // Save a pointer to current head
        *head = *head->next;       // Update head
        free(hladany);             // Free the previous head
        return;
    }

    STUDENT *traverse = *head->next;
    STUDENT *previous = *head;

    while(traverse!=NULL)
    {
        if(!strcmp(traverse->priezvisko,priezvisko))
        {
            previous->next = traverse->next;  // Update previous to point
                                              // to element after traverse.

            free(traverse);                   // Now free traverse
            return;
        }

        previous = traverse;                  // Move previous to next element
        traverse = traverse->next;            // Move traverse to next element
    }

    fprintf(stderr,"Student %s sa nenasiel.\n",priezvisko);
    return;
}

Answer 3

该函数至少是错误的，因为它忽略了 header 满足条件时的大小写。

另外你应该保留删除节点之前的节点。

函数可以如下所示

void vymazstudenta( STUDENT **head, const char *priezvisko )
{
    STUDENT *tmp = NULL;

    if ( *head != NULL )
    {
        if ( strcmp( head->priezvisko, priezvisko ) == 0 )
        {
            tmp = *head;
            *head = ( *head )->next;
        }
        else
        {        
            STUDENT *traverse = *head;
            while( traverse->next != NULL && strcmp( traverse->next->priezvisko, priezvisko ) != 0 )
            {
                traverse = traverse->next;
            }

            if ( traverse->next != NULL )
            {
                tmp = traverse->next;
                traverse->next = traverse->next->next;
            }
        }
    }

    if ( tmp != NULL )
    {
        free( tmp );
    }
    else
    {
        fprintf( stderr, "Student %s sa nenasiel.\n", priezvisko );
    }
}

从链接列表中搜索和删除

Search and delete from linked list

c

linked-list

singly-linked-list