2015-06-04
493
Если есть указатель, указывающий на некоторый элемент списка, то содержимое полей этого элемента и даже следующих за ним можно получить так (см. рис. 4.4):
| p | - адрес текущего элемента списка; |
| p^ | - запись из нескольких полей, хранящаяся по адресу p; |
| p^.znachenie | - значение первого поля этой записи; |
| p^.next_element | - значение второго поля этой записи, являющееся адресом следующего элемента списка; |
| p^.next_element^.znachenie | - значение, хранящееся в первом поле элемента списка, следующего за тем, на который указывает р. |
Рис. 4.4. Правила обращения к элементам списка
С линейными списками можно выполнять те же действия, что и с одномерными массивами, поскольку назначение списков и массивов одно и то же — обработка данных в оперативной памяти. Перечислим типовые действия со списками:
¨ добавить новый узел непосредственно перед заданным узлом;
¨ удалить заданный узел;
¨ объединить два (или более) линейных списка в один список;
¨ разбить линейный список на два (или более) списка;
¨ сделать копию списка;
|
|
|
¨ выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах;
¨ найти в списке узел с заданным значением в некотором поле.
Очень часто встречаются линейные списки, в которых добавление и удаление производятся только в первом или последнем узлах. Назовем эти списки.
¨ Стек — линейный список, в котором все добавления и удаления (и обычно всякий доступ) делаются в одном конце списка (последним пришел – первым вышел).
¨ Очередь — линейный список, в котором все добавления производятся на одном конце списка, а все удаления делаются на его другом конце.
¨ Дек (очередь с двумя концами) — линейный список, в котором все добавления и удаления делаются на обоих концах списка.
