删除单向链表中所有出现的元素[关闭]

问题描述 投票：0回答：4

我花了几个小时编写一个函数 - 给定一个链表单向列表，将删除给定元素的所有出现。这是我设法写的功能：

void remove_by_value(struct Node **head, int value) {
    while( *head!=NULL && (*head)->value == value ) {
        struct Node *tmp = *head;
        if((*head)->next != NULL)
            *head = (*head)->next;
        else
            *head = NULL;
        free(tmp);
    }

    struct Node *iterator = *head;
    while(iterator->next != NULL) {
        if(iterator->next->value == value) {
            struct Node *tmp = iterator;
            iterator = iterator->next;
            free(tmp);
            continue;
        }
        iterator = iterator->next;
    }
}

在我的例子中，我使用了一个简单的列表，如下所示：2->1->1和运行remove_by_value(&head, 1)后程序的输出：

0 
1242177584 
Segmentation fault (core dumped)

这与期望的效果相去甚远。问题是我不明白我的错误在哪里。这是我想要应用的算法：

  1. 检查此列表的头部是否具有所需的值。如果是这样，将头部向右移动并移除第一个节点。重复此操作，直到新头的值与此函数的参数不同
  2. 检查下一个节点的值是否等于所需的值。如果是，请删除此节点，并将当前节点与已删除的节点之后的节点相链接。

我知道我的算法并不完美 - 例如，当节点没有指向任何东西时，它不处理这种情况。但事情的核心是，我不明白为什么我的程序表现得像这样。你能给我一些建议吗？有没有更好的方法来编写这个算法？

编辑： 我认为它可能很重要，所以我决定包含我的打印功能，因为它可能会导致一些潜在的内存泄漏，因为我之前的功能：

void print(struct Node *head) {
    while(head != NULL) {
        printf("%d \n", head->value);
        head = head->next;
    }
}
c list data-structures linked-list singly-linked-list
4个回答
2
投票

我认为这应该工作，但是太复杂，无法验证。如果没有，将删除帖子。

void remove_by_value(struct Node **head, int value) {
    while( *head!=NULL && (*head)->value == value ) {
        struct Node *tmp = *head;
        *head = (*head)->next;     /*removed some useless code here*/
        free(tmp);
    }
    struct Node *iterator = *head;
    if(iterator == NULL)
        return;
    while(iterator->next != NULL) {
        if(iterator->next->value == value) {
            struct Node *tmp = iterator->next;
            iterator->next = iterator->next->next; 
            free(tmp);
        }
        iterator = iterator->next;
    }
}

解释（感谢下面的评论）：

原始代码测试是否应该删除iterator-> next但是错误地删除了iterator it self。例如2-> 1-> 1，将删除2，因为下一个节点为1，但实际上应该删除1。

删除链表中的元素时，仅释放应删除的节点是不够的。还必须将先前节点的“下一个”变量设置为已删除元素之后的节点。

例如2-> 1-> 3 OP代码：2-> Null Nothing-> 3;正确：2-> 3

附：我的答案有问题，但似乎我无法删除我接受的答案。

从下面更好的答案：https://stackoverflow.com/users/2877241/vlad-from-moscow

你的函数太复杂并且有一个bug，因为在第二个while循环中没有检查head是否等于NULL并且循环改变了局部变量迭代器而不是更改节点本身。

该功能可以更简单地实现。例如

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

这是一个示范计划

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int value;
    struct Node *next;
};

void insert(struct Node **head, const int a[], size_t n)
{
    for (size_t i = 0; i < n; i++)
    {
        struct Node *current = ( struct Node * )malloc(sizeof(struct Node));

        current->value = a[i];
        current->next = *head;

        *head = current;
        head = &(*head)->next;
    }
}

void print( struct Node *head ) 
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d ", head->value );
    }
}

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

int main(void) 
{
    struct Node *head = NULL;
    int a[] = { 2, 1, 1 };

    insert( &head, a, sizeof( a ) / sizeof( *a ) );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 1 );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 2 );

    print( head );
    putchar( '\n' );

    return 0;
}

它的输出是

2 1 1 
2
2
投票

你的函数太复杂并且有一个bug，因为在第二个while循环中没有检查head是否等于NULL并且循环改变局部变量iterator而不是改变节点本身。

该功能可以更简单地实现。例如

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

这是一个示范计划

#include <stdio.h>
#include <stdlib.h>

struct Node
{
    int value;
    struct Node *next;
};

void insert(struct Node **head, const int a[], size_t n)
{
    for (size_t i = 0; i < n; i++)
    {
        struct Node *current = ( struct Node * )malloc(sizeof(struct Node));

        current->value = a[i];
        current->next = *head;

        *head = current;
        head = &(*head)->next;
    }
}

void print( struct Node *head ) 
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d ", head->value );
    }
}

void remove_by_value( struct Node **head, int value ) 
{
    while ( *head )
    {
        if ( ( *head )->value == value )
        {
            struct Node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

int main(void) 
{
    struct Node *head = NULL;
    int a[] = { 2, 1, 1 };

    insert( &head, a, sizeof( a ) / sizeof( *a ) );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 1 );

    print( head );
    putchar( '\n' );

    remove_by_value( &head, 2 );

    print( head );
    putchar( '\n' );

    return 0;
}

它的输出是

2 1 1 
2
2
投票

曾经有一段时间程序员不得不做很多这样的事情，并且在你做足够多次之后你的代码变得非常高效。为了帮助保持古老的艺术活力，这就是这样的功能应该是这样的：

void removeByValue(Node **head, int val){
    Node *n;
    while(n=*head) {
        if (n->value == val) {
            *head = n->next;
            free(n);
        } else {
            head = &(n->next);
        }
    }
}
1
投票

所以删除功能的第一个循环是好的，但有点笨重。这个代码是非常多余的，因为无论next是什么值，你都将它分配给*head

if((*head)->next != NULL)
    *head = (*head)->next;
else
    *head = NULL;

但它正在做的就是删除第一个节点，同时匹配你正在寻找的值，这不是特别有用。

这是问题的下一个循环，因为它没有正确更新列表。想象一下你的列表是1 - > 2 - > 3并且你正在删除2.你迭代你的列表直到你到达中间节点。您获取当前节点的临时副本，将自己指向下一个节点，然后释放它。这留下你的列表像1 - > 2 ??? 3，因为您尚未更新上一个节点以指向下一个节点。

只需一个循环即可完成整个过程。您使用head作为跟踪指向当前节点的任何内容的方式。所以在循环开始时它指向列表的开头。如果节点不匹配，则指向当前节点的下一个指向的任何节点。

如果匹配，则再次获取当前节点的临时副本，但这次更新*head以指向下一个节点。因此它将保持先前的连接或列表的开始。

void remove_by_value(struct Node **head, int value) {
    while( *head!=NULL ) {
        if ((*head)->value == value) {
            struct Node *tmp=*head;
            *head=(*head)->next;
            free(tmp);
        } else {
            head=&((*head)->next);
        }
    }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.