C 程序与链表到 add/delete 整数并计算平均值

Question

我正在尝试修改此代码以使用符号“+”将新数字添加到列表中并使用符号“-”删除。如果输入的数字是偶数，则应将数字插入列表的开头，如果是奇数，则应将其插入列表的末尾。程序将在输入 0（+0 或 -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;
}

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

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);
            }
            printf("\n");
        }
    } while(num);

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

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


    head = delete_if_less( head, num );

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

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

    return 0;
}

然后我希望它计算 1) 所有添加的整数的总和 2) 所有删除的整数的总和 3) 列表中剩余数字的总和 4) 剩余整数的数量 5)剩余数的算术平均数。输入应如下所示：

Enter +/- to add/del a number: +1
1 
Enter +/- to add/del a number: +2
2 1
Enter +/- to add/del a number: +3
2 1 3 
Enter +/- to add/del a number: +1
2 1 3 1
Enter +/- to add/del a number: +5
2 1 3 1 5
Enter +/- to add/del a number: -4
Numbers not in list.
2 1 3 1 5
Enter +/- to add/del a number: -3
2 1 1 5
Enter +/- to add/del a number: -1
2 1 5
Enter +/- to add/del a number: +0
2 1 5

add sum: 13
del sum: 5
total sum: 8
elements: 3
average: 2.67

谁能帮我解决这个问题？我会很感激。 :)

Answer 1

这是我对您的代码的处理方法！

我使用带哨兵的链表来优化一下。此外，由于在您的示例中您想保留有关已删除值的信息，因此程序中实际上有两个链表，一个用于 present 值，另一个用于 bin 个值。

它的工作原理与您在输入部分中描述的完全一样，尽管我添加了更多功能。

以下是可能的输入：其中n是0到9的整数

+on -> 添加 n 到链表

-on -> 如果存在则从链表中删除 n，如果 n 不存在则打印错误消息

-an -> 从链表中删除所有出现的 n，如果 n 不存在则打印错误消息

+m -> 删除链表的最大值

-m -> 删除链表的最小值

0 -> 终止函数

当然你可以用不同的方式解析它以包含更大的 int 值，但我想我会把那部分留给你！

在每次操作时，两个链表将在终端上打印出来，这样您就可以看到您的操作结果和两个链表的当前状态。如果您的消息与解析不匹配，则会引发错误并将打印在终端上。删除链表中不存在的值也是如此。

输入 0 后，程序将根据您在示例中提出的要求计算列表的不同属性。

#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <err.h>
#include <errno.h>
#include <string.h>
#include <limits.h>

typedef struct node
{
    int value;
    struct node *next;
} node;

// Prints a string of characters.
static inline void print(const char* f, ...)
{
    va_list args;
    va_start(args, f);
    vprintf(f, args);
    va_end(args);
}

// Prints a string of characters followed by a new line.
static inline void println(const char* f, ...)
{
    va_list args;
    va_start(args, f);
    vprintf(f, args);
    va_end(args);
    printf("\n");
}

static inline void* mem_alloc(size_t size)
{
    void* p = malloc(size);

    if (p == NULL)
    {
        err(EXIT_FAILURE, "Problem with malloc().");
    }
    return p;
}



// Verify if node is empty 
int node_is_empty(node * head)
{
    return head == NULL;
}

// Verify if node is not empty 
int node_is_not_empty(node * head)
{
    return head != NULL;
}

//Builds the sentinell of the node structure

node* node_build_sentinel()
{
    // Creates the sentinel.
    node* head = mem_alloc(sizeof(node));
    head->value = 0;
    head->next = NULL;


    // Returns the head of the node which is the sentinell.
    return head;
}

//Prints the contents of a node 
void node_print(node* head)
{
    print("{");
    while(head->next)
    {
        head = head->next;
        print(" %d", head->value);
    }
    println(" }");
}

//Frees the allocated node
void node_free(node* head)
{
    node* previous;

    while (head)
    {
        previous = head;
        head = head->next;
        free(previous);
    }
}

// Inserts a value right after the head
/*

    HEAD -> 1 -> 2 -> ..... -> 8 
    node_insert_beg(node* HEAD, int 42);
    HEAD -> 42 -> 1 -> 2 -> ..... -> 8

*/
void node_insert_beg(node* head, int value)
{
    node* tmp = mem_alloc(sizeof(node));
    tmp->value = value;
    tmp->next = head->next;
    head->next = tmp;
}

// Inserts a value right after the head
/*

    HEAD -> 1 -> 2 -> ..... -> 8 
    node_insert_end(node* HEAD, int 42);
    HEAD -> 1 -> 2 -> ..... -> 8 -> 42

*/
void node_insert_end(node* head, int value)
{
    node* tmp = mem_alloc(sizeof(node));
    for (; node_is_not_empty(head->next); head = head->next)
    {
        //This loop runs to the last node and quits with head being that last node
        continue;
    }
    tmp->value = value;
    tmp->next = head->next;
    head->next = tmp;
}

//Inserts odd values to the end and even values to the beginning
void node_insert_num(node* head, int value)
{
    //odd
    if(value % 2)
    {
        node_insert_end(head, value);
    }
    //even
    else
    {
        node_insert_beg(head, value);
    }
}

//Extracts the minimum value of the node (in other words deletes it from the node)
void node_extract_min(node* list,node *sup)
{
    node *before_min = list;
    while (list->next != NULL)
    {
        if (list->next->value < before_min->next->value)
        {
            before_min = list;
        }   
        list = list->next;
    }
    node *output = before_min->next;
    before_min->next = before_min->next->next;
    output->next = NULL;
    while (sup->next!=NULL)
    {
        sup = sup->next;
    }
    sup->next = output;
}


//Extracts the maximum value of the node (in other words deletes it from the node)
void node_extract_max(node* list, node* sup)
{
    node *before_max = list;
    while (list->next != NULL)
    {
        if (list->next->value > before_max->next->value)
        {
            before_max = list;
        }   
        list = list->next;
    }
    node *output = before_max->next;
    before_max->next = before_max->next->next;
    output->next = NULL;
    while (sup->next!=NULL)
    {
        sup = sup->next;
    }
    sup->next = output;
}

//Deletes the first occurence of value in node
int node_delete_first_occurence(node* head, node* sup, int value)
{
    int seen = 0;
    node *tmp = head;
    while (head->next != NULL)
    {
        if (head->next->value == value)
        {
            tmp = head;
            seen+=1;
            break;
        }   
        head = head->next;
    }
    if(seen == 0)
    {
        return seen;
    }
    node *output = head->next;
    tmp->next = tmp->next->next;
    output->next = NULL;
    while (sup->next!=NULL)
    {
        sup = sup->next;
    }
    sup->next = output;
    return seen;
}

//Deletes all occurences of value in node
int node_delete_all_occurences(node* head, node* sup, int value)
{
    int seen = 0;
    node *tmp = head;
    while (head->next != NULL)
    {
        if (head->next->value == value)
        {
            seen+=1;
            tmp = head;
            node *output = head->next;
            tmp->next = tmp->next->next;
            output->next = NULL;
            while (sup->next!=NULL)
            {
                sup = sup->next;
            }
            sup->next = output;
            continue;
        } 
        head = head->next;
    }
    return seen;
}

//Get a node at index if index invalid return NULL
//DOES NOT DELETE THE NODE
node * node_get_at(node* node, unsigned long index)
{
    while (node != NULL && index > 0)
    {
        node = node->next;
        index--;
    }
    if (node != NULL)
    {
        node = node->next;
    }
    return node;
}

int* node_sum(node * head)
{
    int * sum_elem = malloc(sizeof(int)*2);
    int sum = 0;
    int elements = 0;
    while (head->next != NULL)
    {
        elements+=1;
        sum += head->next->value;
        head = head->next;
    }
    sum_elem[0] = sum;
    sum_elem[1] = elements;
    return sum_elem;
}


int main()
{
    node * present_node = node_build_sentinel();
    node * deleted_nodes = node_build_sentinel();
    char message[4];
    while (1)
    {
        printf("Enter +/- followed by type (o = one/a = all/m = min or max) followed by the number to add/del a number or 0 to quit the app:");
        scanf("%3s",message);
        if(message[0] == '+')
        {
            if(message[1] == 'o')
            {
                node_insert_num(present_node,message[2] - '0');
                node_print(present_node);
                node_print(deleted_nodes);
                continue;
            }
            if(message[1] == 'm')
            {
                node_extract_max(present_node,deleted_nodes);
                node_print(present_node);
                node_print(deleted_nodes);
                continue;
            }
            if(message[1] == 'a')
            {
                printf("Invalid syntax on opperand 2 after + (no a is possible) please try again!\n");
            }
            else
            {
                printf("Invalid syntax on opperand 2 after + please try again!\n");
            }
            continue;
        }
        if(message[0] == '-')
        {
            if(message[1] == 'o')
            {
                int err = node_delete_first_occurence(present_node,deleted_nodes,message[2] - '0');
                if(err == 0)
                {
                    printf("The number to delete was not present in the node!\n");
                }
                node_print(present_node);
                node_print(deleted_nodes);
                continue;
            }
            if(message[1] == 'a')
            {
                int err = node_delete_all_occurences(present_node,deleted_nodes,message[2] - '0');
                if(err == 0)
                {
                    printf("The number to delete was not present in the node!\n");
                }
                node_print(present_node);
                node_print(deleted_nodes);
                continue;
            }
            if(message[1] == 'm')
            {
                node_extract_min(present_node,deleted_nodes);
                node_print(present_node);
                node_print(deleted_nodes);
                continue;
            }
            else
            {
                printf("Invalid syntax on opperand 2 after - please try again!\n");
            }
            continue;
        }
        if(message[0] == '0')
        {
            break;
        }
        else
        {
            printf("Invalid syntax on opperand 1 please try again!\n");
        }
        
    }


    int * present_sum_elem = node_sum(present_node);
    printf("The sum of present node: %d \n",present_sum_elem[0]);
    printf("The number of elements in present node: %d\n",present_sum_elem[1]);
    if(present_sum_elem[1]!=0)
    {
        printf("The average of the present node %4f \n", (float)present_sum_elem[0]/(float)present_sum_elem[1]);
    }
    
    
    int * deleted_sum_elem = node_sum(deleted_nodes);
    printf("The sum of deleted node: %d \n",deleted_sum_elem[0]);
    printf("The number of elements in deleted node: %d\n",deleted_sum_elem[1]);
    if(deleted_sum_elem[1] != 0)
    {
        printf("The average of the deleted node %4f \n", (float)deleted_sum_elem[0]/(float)deleted_sum_elem[1]);
    }

    free(present_sum_elem);
    free(deleted_sum_elem);
    node_free(present_node);
    node_free(deleted_nodes);
    return 0;
}

C 程序与链表到 add/delete 整数并计算平均值

C program with linked list to add/delete integers & calculate avg

c

sorting

linked-list

insert