Алфавитная сортировка связанного списка

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

Я сделал функцию, которая сравнивает двух учеников по их имени и возрасту, как показано в файле comeBefore. Это прекрасно работает.

Проблема, с которой я сталкиваюсь, заключается в том, что при связывании четырех имен я получаю ошибку сегментации. Если кто-нибудь может дать мне несколько советов о том, где я ошибаюсь, или об отладке в c, это было бы здорово.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

typedef struct name_s Name;

//Struct name_s contains a character pointer to a name, an age, and a
// pointer to the next name in a linked list

struct name_s{
    char* name;
    int age;
    Name* next;
};

//comesBefore takes a pointer to student1 and student2.
//The two students are compared to see which one comes first in
//alphabetical order.
//If both names are the same then their ages are compared.
//The function returns true if student1 should come first else false

bool comesBefore(const Name* student1, const Name* student2)
{
    int i  = 0;
    if (student2 == NULL){
        return true;
    }
    while (student1->name[i]!= '\0' && student2->name[i] != '\0'){
        if (student1->name[i] < student2->name[i]){
            return true;
        }
        i++;
    }

    if (student1->name == student2->name){
        if (student1->age < student2->age){
            return true;
        }
    }

    return false;
}

//creates a linked list in alphabetical order of the names
//if any two names are the same the one with the lowest age comes first

Name* linkedList(Name names[], int n)
{
    Name* head = NULL;
    Name* previous = NULL;
    Name* last = NULL;
    Name* current = &names[0];
    int i = 0;
    while (i < n) {
        if (head == NULL){
            head = current;
        } else {
            if (comesBefore(current, head)){
                current->next = head;
                head = current;
            } else {
                previous = head;
                while(comesBefore(current, previous->next) == false 
                    && previous->next != NULL){
                    previous = previous->next;
                }

                current->next = previous->next;
                previous->next = current;
            }

        }
        last = head;
        int k = 0;
        while (k <= i){
            last = last->next;
            k++;
        }

        last->next = NULL;
        i++;
        current = &names[i];
    }


    return head;
}


int main(void)
{

    Name a;
    Name b;
    Name c;
    Name d;
    Name* s1 = &a;
    Name* s2 = &b;
    Name* s3 = &c;
    Name* s4 = &d;

    s1->name = "Zaphod Beeblebrox";
    s1->age = 250;
    s2->name = "Albert Einstein";
    s2->age = 133;
    s3->name = "Albert Einstein";
    s3->age = 7;
    s4->name = "Brook Fleming";
    s4->age = 20;

    Name names[4];
    names[0] = a;
    names[1] = b;
    names[2] = c;
    names[3] = d;

    Name* list = linkedList(names, 4);
    while (list!=NULL){
        printf("Name: %s\nAge: %d\n--------\n",
        list->name,
        list->age
        );
        list = list->next;
    }



    return 0;
}

person Brook Renzi    schedule 31.08.2016    source источник
comment
У вашей функции сравнения есть проблемы. Предположим, код сравнивает Зафода с Альбертом; первое сравнение обнаруживает, что Z не меньше A, поэтому оно продолжает сравнивать a с l, что дает неверный результат. Вам нужно протестировать if (student1->name[i] > student2->name[i]) return false; и продолжить цикл только тогда, когда имена равны. Последующий тест if (student1->name == student2->name) тоже фальшивый; сравнение указателей на равенство - это не то, что вам нужно - и снова вам нужно проверить как меньше, так и больше, а затем решить, что вернуть, если возрасты равны.   -  person Jonathan Leffler    schedule 31.08.2016


Ответы (2)


Проблема в том, что указатели "next" не инициализированы. Вам нужно их аннулировать.

Name a = {0};
Name b = {0};
Name c = {0};
Name d = {0};

Другое дело, что ваша функция сортировки плохо справляется со сравнением строк. Вы должны изменить его на:

bool comesBefore(const Name* student1, const Name* student2)
{
    int i  = 0;
    if (student2 == NULL)
    {
        return true;
    }
    while (student1->name[i]!= '\0' && student2->name[i] != '\0')
    {
        if (student1->name[i] < student2->name[i]){
            return true;
        }
        else if (student1->name[i] > student2->name[i]){
            return false;
        }

    i++;
}
...

или еще лучше, используйте strcmp()

также обратите внимание, что вся «k» и «последняя» часть в вашем коде вообще не требуется

person eyalm    schedule 31.08.2016
comment
Пустые фигурные скобки недействительны в C; вам нужно хотя бы одно 0 в них: … = { 0 };. - person Jonathan Leffler; 31.08.2016
comment
Спасибо за помощь! - person Brook Renzi; 31.08.2016
comment
@Brook Renzi: Вы можете использовать отладчик, чтобы очень быстро находить подобные проблемы. - person eyalm; 31.08.2016
comment
Любые рекомендации по отладчику и как получить к нему доступ? - person Brook Renzi; 01.09.2016

Изменять

 while (list->next!=NULL){

to

 while ( list != NULL ){

Могут быть и другие проблемы, но это первое, что я заметил.

person Peter Skarpetis    schedule 31.08.2016
comment
У меня изначально было это на самом деле спасибо за помощь на этом фронте. - person Brook Renzi; 31.08.2016