Списки | Связные списки (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


Уроки 71 - 73
Списки
(§41. Списки)



Содержание урока

Что такое список?

Использование динамического массива

Модульность

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

Вопросы и задания

Задачи


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


Линейный список иногда представляется в программе в виде связного списка, в котором каждый элемент может быть размещён в памяти в произвольном месте, но должен содержать ссылку (указатель) на следующий элемент. У последнего элемента эта ссылка нулевая (в Паскале — nil), она показывает, что следующего элемента нет. Кроме того, нужно хранить где-то (в указателе Head) адрес первого элемента («головы») списка, иначе список будет недоступен (рис. 6.3).

Рис. 6.3

Рис. 6.3

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

Рис. 6.4

Рис. 6.4

Поскольку элементы связного списка содержат ссылки только на следующий элемент, к предыдущему перейти нельзя. Поэтому перебор возможен только в одном направлении. Этот недостаток устранён в двусвязном списке, где каждый элемент хранит адрес как следующего, так и предыдущего элемента (рис. 6.5).

Рис. 6.5

Рис. 6.5

Для такого списка обычно хранятся два адреса: «голова» списка (указатель Head) и его «хвост» (указатель Tail). Можно организовать и циклический двусвязный список. Использование двух указателей для каждого элемента приводит к дополнительному расходу памяти и усложнению всех операций со списком, потому что при добавлении и удалении элемента нужно правильно расставить оба указателя.

Применение связных списков приводит к более сложным алгоритмам, чем работа с динамическими массивами; рассматривать соответствующие программы мы не будем.

Следующая страница Вопросы и задания



Cкачать материалы урока







Наверх