5 Работа с линейными списками

5.1 Указатели. Основные операции с указателями

Каждый элемент данных, хранящихся в памяти компьютера, имеет свой адрес. Адреса могут находиться в специальных переменных, называемых указателями. Мы будем рассматривать типизированные указатели, которые могут хранить адреса только объектов определенного типа.

Пусть указатели р и q содержат адрес объекта x некоторого типа tData. Графически будем изображать это следующим образом:


Рисунок 12. Равенство указателей

Стрелка начинается в указателе и указывает на объект в целом, а не на отдельную компоненту, поэтому указатели p и q равны. Заметим, что обычно адрес объекта совпадает с адресом его первой компоненты. Можно обращаться к переменной по имени, а можно по адресу. При обращении по адресу не нужно знать имени переменной.

Основные операции с указателями приведены в следующей таблице.

Таблица 2. Основные операции с указателями
Операция Псевдокод Комментарии
1. Присваивание p:=q Указателю p присвоить значение указателя q
2. Сравнение p=q, p?q Сравнение значений указателей p и q
3. Получение адреса p:=@x Указателю p присвоить адрес переменной x
4. Доступ по адресу *p=y *p=*q Переменной по адресу p присвоить значение переменной по адресу q
5. Доступ к отдельной компоненте p? comp:=x Компоненте comp пересенной по адресу p присвоить значение переменной x
6. Отсутствие адреса NIL Значение указателя p не равно никакому адресу

5.2 Основные операции с линейными списками

Списком называется последовательность однотипных элементов, связанных между собой указателями. Будем считать, что элементы списка имеют тип tLE, указатели на элементы списка имеют тип pLE.


Рисунок 13. Указатель на элемент списка

Поле Next является указателем на элемент списка и может занимать произвольное место в структуре элемента. Однако если оно является первым элементом структуры, то его адрес совпадает с адресом элемента списка, и это позволяет оптимизировать многие операции со списками. Поле Data содержит информацию, которая будет учитываться при сортировке.

Рассмотрим два вида списков: стек и очередь. Стек характеризуется тем, что новый элемент добавляется в начало последовательности, а удаляться может только первый элемент списка. При добавлении в очередь новый элемент ставится в конец списка, удаляется первый элемент последовательности.

Рассмотрим основные операции со стеком и очередью. Для работы со стеком необходимо иметь указатель на начало списка. Обозначим его Head. При работе с очередью требуется дополнительный указатель на конец очереди. Обозначим его Tail. Иногда при работе с очередью удобно объединять указатели Head и Tail в виде полей некоторой переменной Queue.

Добавление элемента по адресу р в стек.
1) p→Next:=Head
2) Head:=p
сортировка
Просмотреть
Рисунок 14. Добавление в стек

Удаление из стека или очереди (при условии, что список не пуст, т.е. Head≠NIL)
1) p:=Head
2) Head:=p→Next
   <освободить память по адресу p>
сортировка
Просмотреть
Рисунок 15. Удаление из стека

Добавление элемента по адресу р в очередь.
1) p→Next:=NIL
2) IF (Head≠NIL) Tail→Next:=p
     ELSE Head:=p 
   FI
3) Tail:=p
сортировка
Просмотреть
Рисунок 16. Добавление в очередь

Операцию добавления элемента в очередь можно оптимизировать в случае, если поле Next является первой компонентой элемента очереди и его адрес совпадает с адресом всего элемента. Зададим пустую очередь следующим образом:


Рисунок 17. Структура очереди


Эту операцию назовем инициализацией очереди. Тогда добавление элемента в очередь будет происходить в два раза быстрее:

Добавление элемента в очередь
1) Tail->Next:=p
2) Tail:=p
сортировка
Просмотреть
Рисунок 18. Добавление в очередь
Перемещение элемента из начала списка List в конец очереди Queue.
1) Queue.Tail→Next:=List
2) Queue.Tail:=List
3) List:=List→Next
сортировка
Просмотреть
Рисунок 19. Перемещение элемента