Связные списки
Узлы, соединённые указателями
- Связный список — это цепочка малых структур, называемых узлами, разбросанных по куче.
- Каждый узел содержит значение и указатель на следующий узел. Следуйте указателям, чтобы пройти по списку.
- В отличие от массива, список может расти на один узел за раз без перемещения остальных.
Самореферентная структура
- Узел — это структура, содержащая указатель на сам тип:
struct Node { int data; struct Node *next; };—dataявляется значением,nextуказывает на следующий узел.- Это предоставляется вам как
Nodeв каждом старте. Последний узел имеетnext=NULL.
Head (голова) и NULL конец
- Один указатель, head (голова), указывает на первый узел. Оттуда вы достигаете остальных.
- Самый последний узел указывает на
NULL, что обозначает конец списка. - Пустой список — это просто
head == NULL; узлов нет совсем.
#include <stdio.h>
typedef struct Node { int data; struct Node *next; } Node;
int main(void) {
// A tiny list on the stack: 10 -> 20 -> 30 -> NULL
Node n3 = {30, NULL};
Node n2 = {20, &n3};
Node n1 = {10, &n2};
const Node *head = &n1;
// Walk it: follow ->next until NULL, counting nodes
int count = 0;
const Node *cur = head; // start at the head
while (cur != NULL) { // stop at the NULL end
count++;
cur = cur->next; // step to the next node
}
printf("length = %d\n", count); // length = 3
return 0;
}
Добавление узла в начало
- Чтобы добавить в начало, создайте новый узел, направьте его
nextна старый head, и верните новый узел как новый head. - Это быстро — оно не затрагивает другие узлы.
- Поскольку head изменяется, функция возвращает новый head, и вызывающий код сохраняет его.
Распространенные ошибки
- Никогда не теряйте указатель
head, иначе весь список станет недоступным. - Освободите каждый узел; последний узел указывает на
NULL.
Теперь попробуйте сами
- Проходите по списку с помощью указателя
curиcur = cur->next, останавливаясь приNULL. - Новые узлы поступают из
malloc(sizeof(Node)); проверчик освобождает список. Не пишите неmain.
Узлы и указатели
Каждый узел указывает на следующий; вставка/удаление осуществляется путем пересоединения ссылок.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Заполните код ⟨int length(const Node *head)⟩ так, чтобы он подсчитывал узлы в списке (возвращает ⟨0⟩ для пустого списка). Проходите по списку с помощью ⟨->next⟩, пока условие ⟨NULL⟩ истинно. Тип ⟨Node⟩ задан. Не пишите оператор ⟨main⟩.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Заполните int sum_list(const Node *head), чтобы вернуть сумму data каждого узла (0 для пустого списка). Тип Node задан. Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 5/5 · 400 монет + небольшой бонус за первое завершение сегодня
Заполните Node *push_front(Node *head, int value), чтобы создать новый узел (со malloc), направить его next на старый head и вернуть его как новую голову. Проверка освободит список. Не пишите main.
Нажмите Запустить, чтобы увидеть результат здесь.