Очевидно, что в вашем insertLLInOrder(), если в первый раз, когда l oop дает previous == NULL, это означает, что вы должны вставить в начало списка, а это не то, что вы делаете.
Просто изменить n->next = NULL; к n->next = h; и это должно улучшить поведение.
Шаг назад и перспектива
Это очень простая ошибка, но ее сложнее обнаружить из-за То, как вы написали свой код.
Сама по себе ошибка не очень интересна, но она может помочь понять, почему это произошло, и как избежать таких ошибок. И нет, запуск отладчика не очень полезен для таких случаев! Иногда возникает необходимость запустить отладчик, но это просто означает, что вы потеряли контроль над своей программой. Подобно тому, как наличие парашюта может быть мерой безопасности для пилота, но если он должен его использовать, это также означает, что пилот потерял контроль и его самолет рухнул.
Знаете ли вы историю Трех Ниндзя? Программисты?
Три ниндзя
Вождь ниндзя приказывает трем ниндзя показать ему свой уровень подготовки. Есть нуб, новичок и старший. Он просит их добраться до небольшой хижины на другой стороне поля, взять какой-нибудь предмет внутрь и вернуться.
Первый ниндзя - нуб, он бежит и прыгает по полю со всей своей скоростью, но достаточно скоро он идет на (гипсовую) шахту. Он возвращается на стартовую линию и признает свою неудачу, что очевидно, потому что его ранее черная рубашка теперь покрыта белой штукатуркой.
Второй ниндзя демонстрирует некоторую практику. Вы можете сказать, что он потерпел неудачу, как Нуб с предыдущей попытки, и что теперь он настороже. Он очень медленный и очень осторожный. Он очень медленно пробирается через поле, пристально наблюдая за каждым шагом. Он подходит совсем близко к каюте, и все считают, что у него все получится, но в конце концов он также был взорван миной в последнюю секунду. Он также возвращается разочарованным к исходной точке, но он почему-то верит, что третьему ниндзя будет трудно добиться большего успеха.
Третий ниндзя - старший. Он спокойно идет по полю по прямой линии, входит в каюту и возвращается без каких-либо видимых проблем, все еще просто идя по полю.
Когда он возвращается к исходной точке, два других ниндзя ошеломлены и жадно спрашиваю его: - Как ты избежал мин? - Очевидно, я вообще не ставил мин на своем пути; почему вы поставили мины в свою?
Вернуться к коду
Итак, что может быть сделано по-другому при написании такой программы?
Сначала использование случайных значений в коде - плохая идея. Следствием этого является то, что поведение кода не может повторяться от одного запуска к следующему.
Также важно, чтобы код четко разделял пользовательские вводы (данные) и код, управляющий этими данными.
В этом случае это означает, что функция createLinkedList(), вероятно, должна иметь другую подпись. Возможно что-то вроде node *createlinkedList(int num, int data[]), где массив data[] будет содержать значения для сортировки. Все еще возможно заполнить входные данные случайными значениями, если это то, что мы хотим.
Таким образом, мы можем легко создавать наборы тестов и модульные тесты, как в коде ниже:
Самодельный набор модульных тестов
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *next;
} node;
node *createlinkedList(int num, int * data);
node *insertLLInOrder(node * h, node * n);
/* No need to have a test framework to write unit tests */
/* Check_LL is some helper function comparing a linked list with test data from an array */
int check_LL(node * head, int num, int * data)
{
node *p = head;
int n = 0;
for (; n < num ; n++){
if (!p){return 0;}
if (p->data != data[n]){return 0;}
p = p->next;
}
return p == NULL;
}
void test_single_node()
{
printf("Running Test %s: ", __FUNCTION__);
int input_data[1] = {1};
int expected[1] = {1};
node * HEAD = createlinkedList(1, input_data);
printf("%s\n", check_LL(HEAD, 1, expected)?"PASSED":"FAILED");
}
void test_insert_after()
{
printf("Running Test %s: ", __FUNCTION__);
int input_data[2] = {1, 2};
int expected[2] = {1, 2};
node * HEAD = createlinkedList(2, input_data);
printf("%s\n", check_LL(HEAD, 2, expected)?"PASSED":"FAILED");
}
void test_insert_before()
{
printf("Running Test %s: ", __FUNCTION__);
int input_data[2] = {2, 1};
int expected[2] = {1, 2};
node * HEAD = createlinkedList(2, input_data);
printf("%s\n", check_LL(HEAD, 2, expected)?"PASSED":"FAILED");
}
/* We could leave test code in program and have a --test command line option to call the code */
int
main()
{
test_single_node();
test_insert_after();
test_insert_before();
}
node *
createlinkedList(int num, int * data)
{
int i;
node *head = NULL;
for (i = 0; i < num; i++) {
node * newNode = (node *) malloc(sizeof(node));
newNode->next = NULL;
newNode->data = data[i];
head = insertLLInOrder(head, newNode);
}
return head;
}
node *
insertLLInOrder(node * h, node * n)
{
//h is the head pointer, n is the pointer to new node
node *ptr = h;
node *previous = NULL;
while ((ptr != NULL) && (ptr->data < n->data)) {
previous = ptr; // remember previous node
ptr = ptr->next; // check for the next node
}
if (previous == NULL) {
//h is an empty list initially
n->next = NULL;
return n; // return the pointer of the new node
}
else {
//if there are nodes in the linked list
// previous will point to the node that has largest value, but smaller than new node
n->next = previous->next; // insert new node between previous, and previous->next
previous->next = n;
return h; // return old head pointer
}
}
Как вы можете видеть в третьем тестовом месте, ошибка.
Конечно, вы можете использовать некоторую доступную стороннюю библиотеку модульных тестов, но самый важный момент не в библиотеке тестов, а в написании тестов.
Другой момент заключается в том, что на самом деле вы должны чередовать написание тестов и написание кода реализации. Обычно это помогает для написания хорошего кода и это то, что люди называют TDD. Но мой ответ, вероятно, уже достаточно длинный, поэтому я не буду подробно останавливаться на TDD.