11.19 Связные списки

Зачем нужны, если есть realloc()? А кто ж их знает…

• Картинки из будущего

Наивный список

   1 typedef struct intlist intlist;
   2 struct intlist {
   3         int value;
   4         intlist * next;
   5 };

• Задать три переменных a,b,c типа intlist и сделать список a -> b -> c

  • Вывести его «классическим» for(intlist *p=&a; p; p=p->next) printf("%d\n", p->value);

• Переделать пример на malloc / free для a,b,c

• Процедура вставки значения после элемента списка current : intlist *insert(intlist *current, int value)

  • завести новый
  • перекинуть ссылки

  • обратите внимание на intlist *current

В чём проблема написать процедуру вставки элемента в список перед current? а кто на него ссылаться будет? а если current — начальный элемент списка, его менять? а вдруг кто-то на него ссылается уже?*/

Список с крышкой

• ⇒ Заводим «крышку» — никогда не меняющийся указатель на элемент списка перед начальным

  • Даже пустой список состоит из одного элемента
  • Вставка = добавление

• Модифицируем пример, добавив в него крышку

• Функция intlist *search(intlist *lst, int what) возвращает указатель на первый элемент списка lst, содержащий what, или NULL, если такого нет.

• Функция delete_after(intlist *previous) удаления элемента, идущего после элемента previous

• Функция remove(intlist *lst, int what) удаления элемента, содержащего what, из списка

  • Нет, search() в числом виде не пригодится: нам нужен предыдущий элемент

• (неэффективный) алгоритм «сортировки списком»

  1. Написать функцию ordered_insert(intlist *lst, int what), которая добавляет what в список между элементами a и b так, что a.value < what ⩽ b.value (или в начало / конец)

  2. Добавить все элементы в список
  3. PROFIT!

• Реализовать его TODO а надо? вообще подменить список на кучу и вот уже heapsort, полезно заранее знать

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

• => Вычислительная сложность добавления / удаления элемента в заранее неизвестной позиции

Всякое:

• В поле value крышки можно что-нибудь хранить, например, длину списка (но это зависит от типа value)

• Крышка может быть не того же типа, что элемент, тогда там можно много что хранить (например, ссылку на последний элемент — для быстрого добавления в конец) — но тогда функции наподобие delete_after() будут иметь другой тип параметров

• TODO а надо? Модифицировать написанные процедуры так, чтобы обновлять поле крышки с длиной

  • delete_after() становится внутренней

Двунаправленный список

Элемент содержит две ссылки:

• Крышка: на первый и на последний элемент
• Элемент на следующий и на предыдущий

Сложность процедур добавления / удаления

Д/З

TODO