strcmp в программе сбоя вставки связанного списка

В рамках задания я должен реализовать односвязный список в c. Я делал это много раз раньше на нескольких разных языках, но после нескольких часов боли я застрял на проблеме с использованием strcmp. Это структура, которую я использую:

typedef struct node {
    char *name;
    float score;
    struct node *next;
} node;

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

void insert(node **start, char *name, float score) { //  to insert a record into the linked list sorted by name in dictionary order.

//create new node
    node *n_node = new_node(name, score);

    node *current;
    current = *start;

    if (current != NULL) { //-----------if list is not empty
        node *prev = NULL;

        if (current->next != NULL) { //--if list has more than 1 element
            while (current != NULL && strcmp(name, current->name) > 0) { //cycle through list to sorted insertion point
             //                      ^^^^^^^Problem Here^^^^^^^^
            //while name is greater than current name, means lower on alphabet (z>a)
                prev = current;
                current = current->next;
            }
            if (current != NULL) { //-----not at end of list
            //once current is not < new node, connect between prev and current
                prev->next = n_node;
                n_node->next = current;
            } else { // ------------------at end of list
                prev->next = n_node;
            }

        } else { //-----------------------list has only one element
            current->next = n_node;
        }
    } else { //--------------------------List is empty - assign new node as first element
        *start = n_node;
    }

}

Проблема в том, что моя программа вылетает и горит без каких-либо ошибок или предупреждений (я использую eclipse с CDT). Программа отлично работает, когда while (current != NULL && strcmp(name, current->name) > 0) изменяется на while (current != NULL /*&& strcmp(name, current->name) > 0*/).

Мне кажется очевидным, что name или current->name вызывают проблемы с работой strcmp, но я не могу обойти это.

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

Для некоторых дополнительных деталей, вот моя функция new_node:

node *new_node(char *name, float score) {
    node *new = (struct node*) malloc(sizeof(struct node));
    new->name = malloc(strlen(name) + 1);
    strcpy(new->name, name);
    new->score = score;
    new->next = NULL;
    return new;
}

(Я понимаю, что использовать new в качестве имени узла неразумно, и я это изменю) и функция, вызывающая вставку:

int data_import(node **startp, char *infilename) { // to import data from the file and insert .
    int max_line = 100;
    char line[max_line];
    char delimiters[] = ",";

    char name[500] = "";
    char *namep;
    namep = &name[0];

    float score = 0.0f;
    int i = 0;

    FILE *fi;
    char *token;
    // open file to read
    fi = fopen(infilename, "r");
    if (fi == NULL) {  // Cannot open the file.
        perror("error");
        return 0;
    }

    // read each line, increase counter, retrieve data
    while (fgets(line, max_line, fi) != NULL) {
        //fputs(line, stdout);  //console output confirmation

        token = strtok(line, delimiters);
        strcpy(namep, token);
        token = strtok(NULL, delimiters); //increment token to mark variable
        score = atof(token);
        insert(startp, namep, score);

        i++;
    }
    //close file
    fclose(fi);
    return i;
}

person Mfib    schedule 09.02.2018    source источник
comment
Покажите свою функцию new_node и вызывающую программу для вставки. Подозрение на проблему может быть в тех.   -  person DrC    schedule 09.02.2018
comment
Обратите внимание, что если ваши первые два элемента будут не по порядку, ваш список не будет правильно упорядочен.   -  person DrC    schedule 09.02.2018
comment
вы можете запустить под gdb, когда он падает, изучите переменные, и это, по крайней мере, даст вам представление о том, почему он падает. К тому времени, когда он доходит до strcmp, current не может быть NULL, поэтому либо name является недопустимым указателем, либо возникает проблема с выходом за пределы. Вероятно, это не проблема, но вы всегда должны проверять, возвращает ли malloc действительный указатель или нет.   -  person yano    schedule 09.02.2018
comment
Примечание: использование указателя на указатель может сократить функцию вставки примерно до десяти строк кода, содержащих только один цикл и одно условие.   -  person joop    schedule 09.02.2018


Ответы (1)


что произойдет, если у вас есть элемент с именем apple в качестве первого элемента, и вы попытаетесь добавить элемент с именем about?

вы будете сразу же выброшены из цикла while, и ваш предыдущий не будет назначен:

while (current != NULL && strcmp(name, current->name) > 0) { //cycle through list to sorted insertion point
             //                      ^^^^^^^Problem Here^^^^^^^^
            //while name is greater than current name, means lower on alphabet (z>a)
                prev = current;
                current = current->next;
            }

эта конкретная часть кажется мне подозрительной:

после этого вы войдете в следующую процедуру:

 if (current != NULL) { //-----not at end of list
            //once current is not < new node, connect between prev and current
                prev->next = n_node;
                n_node->next = current;
            }

поскольку ваш *prev не назначен, и вы пытаетесь получить к нему доступ (prev->next = n_node;). здесь вы получите сбой.

person Paresh Dhandhukiya    schedule 09.02.2018
comment
Не могу поверить, что я пропустил это! Кажется, что окружив оба этих утверждения дополнительным if(strcmp(name, current->name) > 0) с помощью else для добавления в начало связанного списка, удалось добиться цели. - person Mfib; 09.02.2018