Связанный список: удалить все узлы, следующий элемент которых имеет большее значение - PullRequest
Новая
       16

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

1 голос
/ 20 октября 2019

Я хотел бы удалить из связанного списка все узлы, которые имеют большее значение справа от них.

  • Ввод: 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;
}

Ответы [ 2 ]

0 голосов
/ 20 октября 2019

Вы можете исправить ошибку сегментации из-за несанкционированного доступа к памяти, проверив, что t2 не равно нулю, прежде чем пытаться разыменовать указатель. Эта версия работает без ошибок после добавления охранников к 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;
    }
}

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

Несколько дополнительных предложений:

  • В этой программе нет необходимости в глобальных переменных.
  • Избегайте ненужных переменных (t и t1 в основном одинаковы, поэтому одну из них легко удалить. Мы также можем удалить t2 и использовать вместо нее t->ptr).
  • Дать переменныеописательные имена.
  • Используйте интервалы вокруг операторов.
  • Разделяйте логические порции кода на отдельные функции вместо добавления комментариев в main для их разделения.
  • Освободите выделенную память прис этим покончено.
  • Не нужно приводить результат malloc.

Вот версия, которая изменяет список на месте и реализует вышеприведенноеPOINts: 

#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;
}
0 голосов
/ 20 октября 2019

Вы сталкиваетесь с Core Dump/Segmentation fault, что является специфической ошибкой, вызванной доступом к памяти, которая «не принадлежит вам».

Итерация перед последней, вы устанавливаете t1 <- 8 &t2 <- NULL. Поэтому, когда вы вводите последнюю итерацию, вы проверяете t1->data с t2->data с помощью in if(), что приводит к получению доступа к NULL->data (вам не разрешено).

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

...