删除c中单链表中所有小于x的节点

Question

我制作了一个程序，让用户输入无数个整数，直到输入数字 0，然后显示并从小到大排序。代码：

#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;
}

但是我需要删除所有小于指定节点的数字，即最小值。然后显示删除后的列表，以及删除了多少个节点。

最后对删除前旧列表和删除后新列表的average/arithmetic均值进行计算显示

总而言之，输出应该如下所示：

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

有人可以帮忙吗？提前致谢...

Answer 1

考虑到这个输出

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

从列表中删除节点的函数似乎在每次调用中最多删除一个节点。

如果是这样，那么该函数可以通过以下方式查找示例

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;
}

并且可以在循环中调用该函数，前提是变量 num 包含目标值，例如以下方式

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 );

在此 do-while 循环之后，变量 n 将包含列表中删除的节点数。

如果你想移除所有满足条件的节点那么函数可以看下面的方式

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;
}

函数可以像

那样调用

size_t n = delete_if_less( &head, num );

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

另一种定义函数的方法如下

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;
}

并且该函数被调用为

head = delete_if_less( head, num );

删除c中单链表中所有小于x的节点

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

c

struct

linked-list

singly-linked-list

function-definition