c - 链表 : remove all nodes whose next element has a larger value

Question

我想在一个链表中删除所有右边值更大的节点。

• 输入:10 -> 12 -> 15 -> 20 -> 5 -> 16 -> 25 -> 8 -> NULL
• 预期输出:20 -> 25 -> 8 -> NULL
• 实际输出:20 -> 25 ->

请帮我解决这个错误。

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

 struct node{
    int data;
    struct node *ptr;
}*start=NULL, *t, *last=NULL;

int i=0;

int main() {
    //creation
    int size;
    printf("Enter size:");
    scanf("%d", &size);

    while (size--) {
        t = (struct node *) malloc(sizeof(struct node));
        printf("Enter list:");
        scanf("%d", &(t->data));
        t->ptr = NULL;
        if (start == NULL) {
            start = t;
        } else
            last->ptr = t;
        last = t;
    }

    //display
    printf("\n");
    t = start;
    do {
        printf("%d->", t->data);
        t = t->ptr;
    } while (t != NULL);
    printf("NULL\n");

    //main objective
    struct node *t1,*t2;
    t1=start;
    t2=t1->ptr;
    t=start;
    for(t=start;t!=NULL;t=t->ptr){
        if(t1->data>t2->data||t->ptr==NULL){
            printf("%d->", t->data);
        }
        t1=t1->ptr;
        t2=t2->ptr;
    }
    printf("NULL\n");

    return 0;
}

Answer 1

您可以通过在尝试取消引用指针之前验证 t2 不为 null 来修复由于非法内存访问而导致的段错误。此版本在向 t2 添加守卫后运行干净:

for (t = start; t; t = t->ptr) {
    if (!t2 || (t1 && t1->data > t2->data)) {
        printf("%d->", t->data);
    }

    t1 = t1->ptr;

    if (t2) {
        t2 = t2->ptr;
    }
}

虽然这显示了正确的输出，但列表实际上并没有被修改，所以我们只是生成一个 side effect ，使例程无法出于其他目的操作内存中的数据。

一些额外的建议:

• 在这个程序中不需要全局变量。
• 避免不必要的变量(t 和t1 基本相同，所以很容易删除其中一个。我们也可以删除t2并改用 t->ptr)。
• 为变量命名。
• 在运算符周围使用间距。
• 将逻辑代码块分成单独的函数，而不是在 main 中添加注释来分隔它们。
• 完成后释放分配的内存。
• 无需 cast the result of malloc .

这是一个就地修改列表并实现以上几点的版本:

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

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

void remove_right_larger(struct node **head) {    
    for (struct node *curr = *head, *prev = NULL;
         curr; curr = curr->ptr) {
        if (curr->ptr && curr->data < curr->ptr->data) {
            if (prev) {
                prev->ptr = curr->ptr;
            }
            else {
                *head = curr->ptr;
            }

            free(curr);
        }
        else {
            prev = curr; 
        }
    }
}

void print_list(struct node *head) {
    for (; head; head = head->ptr) {
        printf("%d->", head->data);
    }

    puts("NULL");
}

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

struct node *input_list() {
    struct node *start = NULL;
    struct node *last = NULL;
    int size;
    printf("Enter size: ");
    scanf("%d", &size);

    while (size--) {
        struct node *tmp = malloc(sizeof(*tmp));
        tmp->ptr = NULL;
        printf("Enter list: ");
        scanf("%d", &(tmp->data));

        if (start) {
            last->ptr = tmp;
        } 
        else {
            start = tmp;
        }

        last = tmp;
    }

    return start;
}

int main() {
    struct node *head = input_list();
    print_list(head);
    remove_right_larger(&head);
    print_list(head);
    free_list(head);
    return 0;
}