#c #linked-list #nodes
#c #связанный список #узлы
Вопрос:
Я пытаюсь вставить узел в начало связанного списка, и я не совсем уверен, почему эта функция не работает. Я думал, что это довольно простая задача, но, похоже, мне здесь чего-то не хватает. Я также включил свои структуры и часть main, чтобы вы могли получить более четкое представление о коде. Спасибо
typedef struct node
{
struct node *next;
int data;
} node;
typedef struct LinkedList
{
node *head;
node *tail;
} LinkedList;
LinkedList *create_list(void)
{
return calloc(1, sizeof(LinkedList));
}
node *create_node(int data)
{
node *ptr = calloc(1, sizeof(node));
ptr->data = data;
return ptr;
}
void head_insert(LinkedList *list, int data) // problem
{
node *newHead = create_node(data);
newHead->next = list->head;
}
void print_list_helper(node *head)
{
if (head == NULL)
return;
printf("%d%c", head->data, (head->next == NULL) ? 'n' : ' ');
print_list_helper(head->next);
}
void print_list(LinkedList *list)
{
if (list == NULL || list->head == NULL)
return;
print_list_helper(list->head);
}
int main(void)
{
LinkedList *list = create_list();
head_insert(list, 8);
print_list(list); // print linked list function
return 0;
}
Итак, я создал новый узел и установил node-> рядом с заголовком списка. Я не уверен, чего еще мне здесь не хватает. У меня есть другая функция, которая печатает списки, поэтому функция недействительна.
Комментарии:
1.
node *newHead = create_node(data); newHead->next = list->head;
. Как вы думаете, что происходитnewHead
после завершения функции? Он исчез. Ни одна / переменная больше не имеет на нее ссылки. Вам нужно так или иначе вернуть новый заголовок вызывающему.2. Как вызываемый код
head_insert()
узнает о новом узле, который теперь является главой списка? Вы ведь не изменилисьlist->head
, не так ли? Тем не менее, вы должны, не так ли? Это очень распространенная проблема с кодом обработки списков. На самом деле это проще решить, поскольку у вас естьLinkedList
структура. Часто люди просто используют указатели наnode
, и тогда вам приходится работать усерднее.3. Впервые
head_insert()
list->head
возникает проблема, посколькуhead == NULL
.4. Вы можете извлечь выгоду из односвязного списка целых чисел (пример)
Ответ №1:
Добавьте эти строки в конец определения вашей head_insert()
функции:
if (list->head == NULL)
{
list->tail = newHead;
}
list->head = newHead;
В вашей функции после добавления нового узла в начало структура LinkedList по-прежнему указывала на предыдущий заголовок. Вы должны изменить этот заголовок на недавно вставленный заголовок. И если в списке не было узлов, вы также должны установить вновь созданный заголовок
Вот полная функция.
void head_insert(LinkedList *list, int data)
{
node *newHead = create_node(data);
newHead->next = list->head;
if (list->head == NULL)
{
list->tail = newHead;
}
list->head = newHead;
}
Комментарии:
1. Поскольку
node *tail;
используется указатель, вы должны проверить, есть лиlist->head
NULL
перед добавлением узла, и установитьlist->head = list->tail = newHead;
в этом случае для инициализацииtail
указателя.2. @DavidC.Rankin Спасибо, я этого не заметил. Но хвост не должен постоянно изменяться. Его следует изменять, только если в качестве head / tail не было узлов. Потому что мы вставляем только в первую позицию. После первой вставки хвост всегда будет одинаковым. Я изменил свой код.
3. Я бы написал код как
if (list->tail == NULL) list->tail = newHead;
, проверяя и присваивая одному и тому же члену, а не тестируяhead
и присваиваяtail
. Это кажется более последовательным. Тем не менее, результат тот же.4. @JonathanLeffler Если мы это сделаем, и каким-то образом хвост станет нулевым, следующая вставка сделает вновь вставленный узел хвостовым и приведет к несогласованности. В противном случае вы должны проверить, имеет ли значение tail значение null, и если это так, вы должны пройти по списку и добавить последний элемент в качестве хвоста.
5. Вы можете думать об этом так.
tail
Указатель всегда указывает на последний узел в списке. Это позволяет выполнять O (1) вставок в конце без необходимости перебора списка. Когда вставляется первый узел, обаhead
иtail
указывают на один и тот же узел. Когда затем добавляется следующий узел, вы делаетеtail->next = newnode; tail = newnode;
это при добавлении нового заголовка, еслиhead
нетNULL
, тоnewnode->next = head; head = newnode;
в этом случаеtail
он не изменяется. Взгляните на ссылку в моем комментарии под исходным вопросом.