Сортировка вставок с указателями на связанный список в C - PullRequest
Новая
       70

Сортировка вставок с указателями на связанный список в C

0 голосов
/ 25 марта 2020

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

У меня возникли некоторые проблемы при работе со связанными списками - в основном сортировка значений с вторичный указатель с использованием сортировки вставкой.

Список генерируется с номерами, используя указатель 'next', указывающий направление, я пытаюсь отсортировать список по случайно сгенерированному значению, содержащемуся в каждом элементе, с помощью 'sort1 'указатель, указывающий порядок отсортированных списков.

Проблемная область в коде, по-видимому, следующая: l oop: 

while(new->value >= current->value && current != NULL){
    current = current->sort1;
}

используется для go через элементы, которые уже отсортированы и найти, где должен быть расположен «новый» элемент, но я получаю ошибку ошибки сегментации здесь, я думаю, когда он достигает конца списка, и новый элемент должен быть помещен в конец списка, так текущий указатель указывает на ноль.

Есть понимание? TIA!

Код теста, для справки: 

int main(){

    int i, length;
    Node *head, *current, *new, *sorthead;

    head = NULL;
    sorthead = NULL;
    length = 5;

    //create linked list
    for(i=0;i<length; i++){

        new = (Node*) malloc(sizeof(Node));

        new->value = (int)rand_double(0,10);
        new->sort1 = NULL;

        new->next = head;
        head = new;
    }   

    //print list
    current = head;
    while(current != NULL){
        printf("<  %d  >\n", current->value);
        current = current->next;
    }

    //sort with sort 1
    new = head;
    while(new!=NULL){

        if(sorthead == NULL || new->value < sorthead->value){
            new->sort1 = sorthead;
            sorthead = new;
        }
        else{
            current = sorthead;

            while(new->value >= current->value && current != NULL){
                current = current->sort1;
            }
            new->sort1 = current;
            current->sort1 = new;

        }
       new=new->next;
    }

    //print sorted
    current = sorthead;
    while(current != NULL){
        printf("<  %d  >\n", current->value);
        current = current->sort1;
    }

    return 0;
}

1 Ответ

1 голос
/ 25 марта 2020

Учитывайте это l oop: 

while(new->key1 < current->key1 || current->sort1 == NULL){
    current = current->sort1;
}

Если первое сравнение всегда true (т. Е. Если ключ «нового» узла меньше любого значения, уже имеющегося в отсортированном списке), то l oop достигнет узла, чей sort1 равен нулю, установит current равным NULL, а затем разыменует его в следующем проходе - Неопределенное поведение, ошибка сегмента, если вам повезет.

Поправка к условному условию проста, но я думаю, что важно, чтобы вы разработали ее для себя.

...