Как удалить несколько вхождений нескольких переменных в связанном списке в c

Question

Я новичок в c программировании и несколько дней пытался решить следующий вопрос:

как убрать числа, которые появляются не менее 3 раз в следующем списке:

3 → 3 → 1 → 2 → 4 → 3 → 5 → 3 → 5 → 4

, что дает результат:

1 → 2 → 4 → 5 → 5 → 4 .

Теперь я знаю, как удалить несколько вхождений ключа «один» в связанном списке, например, удалить все вхождения «1» в связанном списке, но не могу понять, как удалить несколько вхождения нескольких переменных. Это просто убивает меня. Буду очень признателен, если кто-нибудь сможет помочь. заранее спасибо.

Answer 1

Кажется, никто не спешит вам помочь. :)

Проще написать функцию, если передать указатель на функцию по ссылке.

Вот демонстрационная программа, которая показывает, как эта функция может быть реализована.

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

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

int insert( struct Node **head, int data )
{
    struct Node *node = malloc( sizeof( struct Node ) );
    int success = node != NULL;

    if ( success )
    {
        node->data = data;
        node->next = *head;
        *head = node;
    }

    return success;
}

void out( struct Node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }
    puts( "null" );
}

void remove_repetitive( struct Node **head )
{
    const size_t LIMIT = 3;

    while ( *head != NULL )
    {
        size_t count = 1;

        int data = ( *head )->data;

        for ( struct Node *node = ( *head )->next; 
              count < LIMIT && node != NULL; node = node->next )
        {
            if ( node->data == data ) ++count;
        }

        if ( count == LIMIT )
        {
            for ( struct Node **node = head; *node != NULL; )
            {
                if ( ( *node )->data == data )
                {
                    struct Node *tmp = *node;
                    *node = ( *node )->next;
                    free( tmp );
                }
                else
                {
                    node = &( *node )->next;
                }
            }
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

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

    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ )
    {
        insert( &head, a[i] );
    }

    out( head );

    remove_repetitive( &head );

    out( head );

    return 0;
}

Выход программы:

3 -> 3 -> 1 -> 2 -> 4 -> 3 -> 5 -> 3 -> 5 -> 4 -> null
1 -> 2 -> 4 -> 5 -> 5 -> 4 -> null

Функция remove_repetitive может быть разделена на две функции, как показано ниже.

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

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

int insert( struct Node **head, int data )
{
    struct Node *node = malloc( sizeof( struct Node ) );
    int success = node != NULL;

    if ( success )
    {
        node->data = data;
        node->next = *head;
        *head = node;
    }

    return success;
}

void out( struct Node *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }
    puts( "null" );
}

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

void remove_repetitive( struct Node **head )
{
    const size_t LIMIT = 3;

    while ( *head != NULL )
    {
        size_t count = 1;

        int data = ( *head )->data;

        for ( struct Node *node = ( *head )->next; 
              count < LIMIT && node != NULL; node = node->next )
        {
            if ( node->data == data ) ++count;
        }

        if ( count == LIMIT )
        {
            remove_all( head, data );   
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

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

    const size_t N = sizeof( a ) / sizeof( *a );

    for ( size_t i = 0; i < N; i++ )
    {
        insert( &head, a[i] );
    }

    out( head );

    remove_repetitive( &head );

    out( head );

    return 0;
}

Вывод программы такой же, как показано выше.