Каждый элемент данных, хранящихся в памяти компьютера, имеет свой адрес. Адреса могут находиться в специальных переменных, называемых указателями. Мы будем рассматривать типизированные указатели, которые могут хранить адреса только объектов определенного типа.
Пусть указатели р и q содержат адрес объекта x некоторого типа tData. Графически будем изображать это следующим образом:
Рисунок 12. Равенство указателей
Стрелка начинается в указателе и указывает на объект в целом, а не на отдельную компоненту, поэтому указатели p и q равны. Заметим, что обычно адрес объекта совпадает с адресом его первой компоненты. Можно обращаться к переменной по имени, а можно по адресу. При обращении по адресу не нужно знать имени переменной.
Основные операции с указателями приведены в следующей таблице.
Операция | Псевдокод | Комментарии |
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 не равно никакому адресу |
Списком называется последовательность однотипных элементов, связанных между собой указателями. Будем считать, что элементы списка имеют тип tLE, указатели на элементы списка имеют тип pLE.
Рисунок 13. Указатель на элемент списка
Поле Next является указателем на элемент списка и может занимать произвольное место в структуре элемента. Однако если оно является первым элементом структуры, то его адрес совпадает с адресом элемента списка, и это позволяет оптимизировать многие операции со списками. Поле Data содержит информацию, которая будет учитываться при сортировке.
Рассмотрим два вида списков: стек и очередь. Стек характеризуется тем, что новый элемент добавляется в начало последовательности, а удаляться может только первый элемент списка. При добавлении в очередь новый элемент ставится в конец списка, удаляется первый элемент последовательности.
Рассмотрим основные операции со стеком и очередью. Для работы со стеком необходимо иметь указатель на начало списка. Обозначим его Head. При работе с очередью требуется дополнительный указатель на конец очереди. Обозначим его Tail. Иногда при работе с очередью удобно объединять указатели Head и Tail в виде полей некоторой переменной Queue.
1) p→Next:=Head 2) Head:=p |
![]() |
1) p:=Head 2) Head:=p→Next <освободить память по адресу p> |
![]() |
1) p→Next:=NIL 2) IF (Head≠NIL) Tail→Next:=p ELSE Head:=p FI 3) Tail:=p |
![]() |
Операцию добавления элемента в очередь можно оптимизировать в случае, если поле Next является первой компонентой элемента очереди и его адрес совпадает с адресом всего элемента. Зададим пустую очередь следующим образом:
Рисунок 17. Структура очереди
Эту операцию назовем инициализацией очереди. Тогда добавление элемента в очередь будет происходить в два раза быстрее:
1) Tail->Next:=p 2) Tail:=p |
![]() |
1) Queue.Tail→Next:=List 2) Queue.Tail:=List 3) List:=List→Next |
![]() |