Deleting all nodes smaller than x in singly linked list in c-CodePudding

I making a program that the lets the user enter countless integers until the number 0 is entered, then display and sort it from smallest to largest. Code:

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

typedef struct node{
    int data;
    struct node *ptr;
} node;

node * insert(node *head, int num)
{
    node *temp = malloc(sizeof(node));
    temp->data = num;

    if (head == NULL || head->data > num)
    {
        temp->ptr = head;
        head = temp;
    }
    else
    {
        node *current = head;
        while ((current->ptr != NULL) && !(num < current->ptr->data))

        {
            current = current->ptr;
        }

        temp->ptr = current->ptr;
        current->ptr = temp;
    }

    return head;
}

void free_list(node *head) {
    node *prev = head;
    node *cur = head;
    while(cur) {
        prev = cur;
        cur = prev->ptr;
        free(prev);
    }
}

int main(){
    int num, min;
    node *head, *p;
    head = NULL;

    do {
        printf("Enter a number: ");
        scanf("%d",&num);
        if(num) {
            head = insert(head, num);
            for ( p = head; p != NULL; p = p->ptr )
            {
                printf("%d->", p->data);
            }
            puts( "NULL " );
        }
    } while(num);

    p = head;
    printf("\nThe entered numbers are:\n");

    while(p) {
        printf("%d->", p->data);
        p = p->ptr;
    }
    free_list(head);
    printf("NULL\n");

    printf("\nEnter minimum: ");
    scanf("%d", & min);

    return 0;
}

I however need then to delete all the numbers that are smaller than a specified node, i.e. minimum. Then display the list after the deletion, and how many nodes were deleted.

Finally the average/arithmetic mean of the old list before deletion, and the new list after the deletion to be calculated and displayed.

All in all, the output should look like something like this:

Enter number: 5
5->NULL
Enter number: 6
5->6->NULL
Enter number: 3
3->5->6->NULL
Enter number: 9
3->5->6->9->NULL
Enter number: 4
3->4->5->6->9->NULL
Enter number: 0

Entered numbers :
3->4->5->6->9->NULL

Enter minimum: 6
3->4->5->6->9->NULL
4->5->6->9->NULL
5->6->9->NULL
6->9->NULL

Deleted nodes: 3

Old average: 5.4
New average: 7.5

Can anyone help? Thanks in advance...

CodePudding user response：

Taking into account this output

Enter minimum: 6
3->4->5->6->9->NULL
4->5->6->9->NULL
5->6->9->NULL
6->9->NULL

it seems that the function that removes a node from the list should remove at most one node in each its call.

If so then the function can look for example the following way

int delete_if_less( node **head, int data )
{
    while ( *head != NULL && !( ( *head )->data < data ) )
    {
        head = &( *head )->ptr;
    }

    int success = *head != NULL

    if ( success )
    {
        node *temp = *head;
        *head = ( *head )->ptr;
        free( temp );
    }

    return success;
}

And the function can be called in a loop provided that the variable num contains the target value for example the following way

size_t n = 0;
do
{            
    for ( p = head; p != NULL; p = p->ptr )
    {
        printf("%d->", p->data);
    }
    puts( "NULL" );
} while ( delete_if_less( &head, num ) &&   n );

After this do-while loop the variable n will contain the number of removed nodes in the list.

If you want to remove all nodes that satisfy the condition then the function can look the following way

size_t delete_if_less( node **head, int data )
{
    size_t n = 0;

    while ( *head != NULL )
    {
        if ( ( *head )->data < data )
        {
            node *temp = *head;
            *head = ( *head )->ptr;
            free( temp );
              n;
        }
        else
        {
            head = &( *head )->ptr;
        }
    }

    return n;
}

and the function can be called like

size_t n = delete_if_less( &head, num );

if ( n != 0 ) printf( "There are deleted %zu nodes.\n", n );

Another way to define the function is the following

node * delete_if_less( node *head, int data )
{
    while ( head != NULL && head->data < data )
    {
        node *temp = head;
        head = head->ptr;
        free( temp );
    }

    if ( head != NULL )
    {
        for ( node *current = head; current->ptr != NULL; )
        {  
            if ( current->ptr->data < data )
            {
                node *temp = current->ptr;
                current->ptr = current->ptr->ptr;
                free( temp );
            } 
            else
            {
                current = current->ptr;
            }
        }
    }

    return head;
}

And the function is called like

head = delete_if_less( head, num );