Адреса

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

При страничной организации памяти адреса являются составными и состоят из номера сегмента памяти и смещения ячейки относительно начала этого сегмента.

Лучшая иллюстрация страничной организации памяти компьютера - это страничная организация любой печатной книги. Для того чтобы найти нужную строчку, нет необходимости задавать ее номер, считая от начала текста. Вместо этого можно задать сначала номер страницы (= сегмент) и только затем номер строки, считая от начала этой страницы (= смещение).

Для обращения к статически заданной переменной можно использовать как ее имя, объявленное в разделе var, так и ее физический адрес.

Например, "адрес" одной и той же географической точки можно записать по-разному: "49°47' северной широты и 86°36' восточной долготы" или просто "вершина пика Белуха Восточная1)".

Динамически распределяемая память

Поскольку к любой переменной можно обратиться двояко - по имени и по адресу, - есть возможность сократить эту избыточность и оставить только один способ. Как мы уже видели, наличие имени означает и наличие адреса. Иными словами, если вы дали переменной имя в разделе var, то в процессе компиляции у нее появится и адрес.

Задумаемся теперь: а если у переменной есть адрес, но нет имени, можно ли оперировать ею с прежней легкостью? Ответ на этот вопрос: "Да, можно!"

Итак, пусть у некоторой переменной нет имени. Тем не менее можно расположить ее в памяти, выделив под нее необходимое количество байтов, и т.д. У переменной будет адрес, будет значение, но не будет имени. Следовательно, обратиться к такой переменной можно будет только с помощью указателя.

"Безымянные" переменные отличаются от "нормальных" переменных:

Нет имени - нечего описывать в разделе var.Ничего не описано, значит, на этапе компиляции память под переменную не выделена. Следовательно, необходима возможность выделять память (и отменять это выделение) прямо в процессе работы программы. Именно из-за этой гибкости такие переменные и называют динамическими.Если "потерять" указатель на переменную, то "никто не узнает, где могилка" ее: переменная останется недоступным "мусором", занимая место в памяти, вплоть до конца работы программы.

Хранение списка

Для того чтобы сохранить информацию обо всем списке, достаточно только одной переменной - указателя на первый элемент этого списка. Обычно его называют головой списка. Указатель на голову должен быть выделенным: с ним нельзя производить никаких действий, которые могут стать причиной утери всего списка. Для работы со списком обычно заводят вспомогательный указатель.

Например:

var head,p,q: uk_spisok;

Но, вообще говоря, нет никаких специальных правил, которые обязали бы программиста давать выделенным указателям особые имена. Например, на рис. 10.1 выделенные указатели имеют имена head, tail, tree_root и start.

Нетипизированные указатели

Для того чтобы выделить память, на которую будет указывать нетипизрованный указатель pointer, нужно воспользоваться стандартной процедурой getmem(p: pointer; size: word), которая выделит столько байт свободной памяти, сколько указано в переменной size.

Нетипизированные указатели

Для того чтобы освободить память, на которую указывает нетипизрованный указатель, нужно воспользоваться стандартной процедурой freemem(p: pointer; size: word), которая освободит в памяти столько байтов (начиная с указанного в переменной p адреса), сколько задано в переменной size.

Нетипизированные указатели

Обращение к элементам списка

Если есть указатель, указывающий на некоторый элемент списка, то содержимое полей этого элемента и даже следующих за ним можно получить так (см. рис. 10.2):

p	- адрес текущего элемента списка;
p^	- запись из нескольких полей, хранящаяся по адресу p;
p^.znachenie	- значение первого поля этой записи;
p^.next_element	- значение второго поля этой записи, являющееся адресом следующего элемента списка;
p^.next_element^.znachenie	- значение, хранящееся в первом поле элемента списка, следующего за тем, на который указывает р.

Рис. 10.2. Правила обращения к элементам списка

Описание списков

Сначала мы рассмотрим только самый простой случай: односвязный список (см. рис. 10.1 (а)). Напомним, что каждый элемент этого списка должен хранить адрес другого элемента из этого же списка.

Рис. 10.1. Примеры списочных структур

Логичнее всего было бы дать этой структуре такое описание:

type element_spiska = record znachenie : integer; next_element : ^element_spiska; end;

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

type ukazatel = ^element_spiska; element_spiska = record znachenie : integer; next_element : ukazatel; end;

Обратите внимание: это единственный случай, когда компилятор согласится принять использование структуры (element_spiska) до ее описания.

Замечание: Кажется, что гораздо более естественным было бы отнести поле next_element к типу pointer: тогда не пришлось бы вводить дополнительный тип данных ukazatel. Однако неудобства, которые непременно возникнут из-за нетипизированности указателей в процессе написания программы, будут гораздо серьезнее, чем одна лишняя строчка при описании типов.

В качестве примера приведем описания всех четырех структур, представленных на рис. 10.1 (см. табл. 10.1):

Таблица 10.1. Примеры описаний списочных структур

a)	Односвязный список	type ukazatel = ^elem_spiska; elem_spiska = record znach : integer; sled : ukazatel; end;
b)	Двусвязный линейный список	type point = ^element_spiska; list = record znachenie : integer; sled : point pred : point; end;
с)	Бинарное дерево (иерархический список)	type point = ^tree; tree = record data : integer; left_sibling : point; right_sibling: point; end;
d)	Ориентированный граф (двусвязный нелинейный список)		type uk_versh = ^versh; uk_duga = ^duga; vershina = record nomer : integer; sled_versh : uk_versh; spisok_dug : uk_duga; end; duga = record konec_dugi : uk_versh; sled_duga : uk_duga; end;

Описание указателей

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

var <имя_указателя>: ^<тип_адресуемой_переменной>;

Например:

var p: ^integer; q: ^real; s: ^array[1..10] of byte;

Кроме того, существуют универсальные нетипизированные указатели, которые могут хранить адрес переменной любого типа:

var <имя_указателя>: pointer;

Определение адреса

Физический адрес любой переменной можно узнать при помощи стандартной функции addr(<имя_переменной>):<указатель> или унарной операции @<имя_переменной>.

В зависимости от значения директивы компилятора {$T}, результатом операции @ будет либо типизированный указатель (если установлено {$T+}), тип которого будет определен в соответствии с типом использованной переменной, либо нетипизированный указатель pointer (если установлено {$T-}).

Результат функции addr() совместим с указателями любых типов:

p:= addr(x); {x: real; p: ^byte)

Перестройка списков

Разницу между структурой статической (массив) и структурой динамической (список) очень доступно проиллюстрировал Никлаус Вирт в своей книге "Алгоритмы и структуры данных". Мы позволим себе позаимствовать оттуда, хотя и не дословно, красивый пример.

Представим обычную очередь у прилавка в магазине. Первый покупатель - это тот, кто в данную минуту стоит непосредственно возле прилавка; следующий за ним - второй, за вторым - третий и т.д. Покупатели занумерованы строго в порядке следования, и вновь пришедшие встают в хвост. В принципе, взглянув на очередь, всегда можно сказать, кто за кем стоит. А что происходит, если один из покупателей желает покинуть очередь? Хвост тут же сдвигается: каждый человек делает шаг вперед, чтобы очередь не утратила целостности. Если же, наоборот, некто желает встроиться в середину очереди (невзирая на крики "А вас тут не стояло!"), то задним приходится пятиться, чтобы освободить ему место. Точно так же ведут себя элементы линейного массива.

Теперь возьмем другую очередь: в приемной у зубного врача. Во-первых, посетители уже не привязаны так жестко к линии прилавка: они сидят в креслах, расположенных там и сям, где только нашлось удобное место. Во-вторых, каждому вновь пришедшему нет необходимости знать, кто в этой очереди первый, а кто второй: достаточно лишь выяснить, кто последний. И вовсе не обязательно садиться рядом с последним пациентом: вновь пришедший может занять любое свободное кресло в приемной. А если у кого-то вдруг перестали болеть зубы и он радостно уходит из очереди, то "стоявшему" за ним достаточно спросить: - "А вы за кем занимали?" При этом физического перемещения пациентов в пространстве не происходит. Аналогично, если вдруг появляется пациент с талончиком на более раннее время, "задние" пропускают его вперед, не сдвигаясь со своих кресел. Именно так ведут себя и элементы динамических списков1).

Примеры перестройки линейных списков

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

Удаление всех нулей из списка.Вставка в список, хранящий все нечетные числа от 1 до 11, трех новых элементов - 0, 8 и 12 - с сохранением его упорядоченности.Обмен второго и третьего элементов списка.Обращение порядка всех четных элементов списка.

Присваивания

Для указателей действуют гораздо более жесткие правила совместимости типов, чем для обычных переменных. В операции присваивания могут фигурировать только указатели, адресующие переменные одинаковых типов данных. Нельзя, скажем, записать

p:= q; {p:= ^integer; q: ^byte}

Обойти эти ограничения позволяет универсальность нетипизированного указателя pointer, совместимого с указателями любых типов:

{p:= ^integer; q: ^byte; t: pointer} t:= q; p:= t;

У указателей также существует свой "ноль", который означает, что указатель не указывает никуда:

p:= nil;

Замечание: Если указатель не хранит конкретного адреса (его значение не определено), то это вовсе не означает, что он никуда не указывает. Скорее всего, он все-таки указывает, но только в какую-нибудь неожиданную (хорошо, если не системную) область памяти.

Просмотр элементов списка

Для того чтобы распечатать значения, хранящиеся в элементах линейного односвязного списка, заданного указателем на голову, годится такая программа:

p:= head; {начать просмотр с головы списка} while p<>nil do begin writeln(p^.znach); p:= p^.next; {переход к следующему элементу списка} end;

Замечание: Для того чтобы во время работы со списком не произошло выхода за его пределы, любой список обязательно должен оканчиваться "нулевым" указателем nil.

Разыменование

Для того чтобы воспользоваться значением, хранящимся по некоторому адресу, необходимо его оттуда "извлечь". Унарная операция ^ называется разыменованием и записывается по следующему шаблону:

<имя_указателя>^

Результатом операции ^ является значение, хранящееся по указанному адресу. Тип этого значения будет определяться типом (типизированного) указателя. К нетипизированным указателям операцию разыменования применять нельзя.

Из-за вольностей, допускаемых процедурой addr(), при разыменовании порой могут возникнуть забавные ситуации. Например, в результате выполнения такой вот программы:

const a: array[1..3] of char ='ААА'; {код(А)=128 или 01000000} var p: ^word; begin p:= addr(a); writeln(p^) end

на экран будет выведено 32896, что в двоичной системе счисления выглядит как 01000000.01000000 (точкой помечена граница двух байтов). Иными словами, коды двух первых букв оказались слитыми в значение типа word.

Замечание: Операции @ и ^ являются взаимно обратными, то есть для любой переменной a и для любого типизированного указателя p верны следующие равенства:

@(p^)= p и (@a)^ = a

Реализация

Приведем фрагменты программ, решающих первую и третью задачи:

{- голову списка обрабатываем отдельно -} while (head<>nil)and(head^.znach =0)do begin p:= head; head:= head^.next; dispose(p); end; {- середина и конец списка обрабатываются вместе -} p:= head; while p^.next <> nil do if p^.next^.znach = 0 then begin q:= p^.next; p^.next:= p^.next^.next; dispose(q); end else p:= p^.next;p:= head^.next; head^.next:= p^.next; p^.next:= p^.next^.next; head^.next^.next:= p;

Рис. 10.5. Примеры перестройки односвязных списков

Создание списков

Предположим, что есть некоторый набор значений (например, в файле), которые необходимо записать в создаваемый односвязный список. Тогда у нас есть две возможности создавать этот список: от хвоста к голове или от головы к хвосту.

Мы приведем здесь обе программы, позволив себе для краткости опустить описания типов, воспользовавшись описанием, показанным в табл. 1 (a):

var head,p: ukazatel; f: text; begin ... head:= nil; while not eof(f) do begin new(p); read(f,p^.znach); p^.next:= head; head:= p; end; end.

Рис. 10.3. Очередной шаг процесса генерации списка "от хвоста к голове"

var head,p,q: ukazatel; f: text; begin ... if eof(f) then head:= nil else begin new(head); {головной элемент создается отдельно} read(f,head^.znach); head^.next:= nil;

q:= head; while not eof(f) do begin new(p); read(f,p^.znach); p^.next:= nil; q^.next:= p; q:= q^.next; end; end; end.

Рис. 10.4. Очередной шаг процесса генерации списка "от головы к хвосту"

Списочные структуры

Если для каждой динамической переменной описывать и хранить ее "личный" указатель, то никакой выгоды на этапе выполнения программы получить не удастся: часть памяти, как и прежде, будет выделяться статически, а ее общий объем даже увеличится - ведь каждый указатель требует для себя четыре байта.

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

Списки применяются, например, в таких ситуациях:

программист заранее ничего не знает о том, какой именно объем памяти может потребоваться его программе;некоторые (особенно "тяжелые") переменные нужны поочередно, и после того как первые "отработали свое", их можно смело стирать из памяти, не дожидаясь конца работы программы, - освобождать место для других "тяжелых" переменных;в процессе обработки данных нужно провести большую работу по перестройке всей структуры "на ходу"; и т.д.

Сравнения

Для указателей определены две операции сравнения: = и <>.

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

Для разнотипных указателей сравнения невозможны: попытка записать

if p = q then writeln('yes'); {p: ^byte; q: ^integer}

вызовет ошибку уже на этапе компиляции.

Однако сравнивать типизированный и нетипизированный указатели можно.

Сравнения

Для указателей определены две операции сравнения: = и <>.

Для разнотипных указателей сравнения невозможны: попытка записать

if p = q then writeln('yes'); {p: ^byte; q: ^integer}

вызовет ошибку уже на этапе компиляции.

Однако сравнивать типизированный и нетипизированный указатели можно.

Статически выделяемая память

Для того, чтобы лучше понять специфику динамически выделяемой памяти, рассмотрим сначала ее "антипод" - память, распределяемую статически.

Такое выделение памяти используется всякий раз при объявлении "обычных" переменных в разделе var. Каждая переменная обладает двумя атрибутами: именем и описанием.

var a: integer;

Описание переменной нужно для того, чтобы компилятор знал, сколько ячеек памяти необходимо выделить для ее хранения. Память под статическую переменную выделяется один раз (до начала работы программы), и затем до конца работы выделенная область памяти считается "занятой" - никакая другая информация не может быть записана в эту ячейку.

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

Структура списков

Итак, каждый элемент создаваемого списка должен содержать:

полезную информацию, которая может иметь любой формат: integer, real, array, record и т.п.;специально выделенное поле (и, может быть, не одно), которое хранит адрес другого элемента этой же структуры.

Приведем примеры различных списочных структур:

a) Односвязный (линейный) список: структура, каждый элемент которой "знает" адрес только следующего за ним элемента (см. рис. 10.1 (a)). Очень удобно представлять таким списком стек и очередь (см. лекцию 9).b) Двусвязный линейный список: структура, каждый элемент которой "помнит" адрес не только следующего, но и предыдущего элемента списка (см. рис. 10.1 (b)). Этот список удобен для работы с деками (см. лекцию 9)c) Бинарное дерево (см. лекцию 11) может быть представлено двусвязным нелинейным списком: каждая вершина помнит обоих своих возможных потомков (см. рис. 10.1 (c)). Если каждой вершине необходимо помнить не только потомков, но и предка, то список становится трехсвязным.d) Для представления ориентированного графа (см. лекцию 11) можно использовать иерархические списки - комбинацию из двух различных линейных списков (см. рис. 10.1 (d): вершины задаются структурой, содержащей три поля, а дуги - два; справа показан орграф, представленный приведенной списочной структурой).

Типизированные указатели

Для выделения памяти служит стандартная процедура new():

new(<имя_указателя>);

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

Например, если переменная p была описана как указатель на integer-переменную, то процедура new(p) выделит два байта; под real-переменную необходимо выделить четыре байта и т.д.

Типизированные указатели

Для уничтожения динамической переменной, то есть для освобождения занимаемой ею памяти, предназначена стандартная процедура

dispose(<имя_типизир_указателя>).

Процедура dispose() снимает пометку "занято" с определенного количества байтов, начиная с указанного адреса. Эта область памяти в дальнейшем считается свободной (хотя старое значение бывшей переменной в ней может некоторое время еще оставаться). Количество освобождаемых байтов определяется типом указателя p.

В результате освобождения памяти при помощи процедуры dispose() значение указателя, хранившего адрес освобожденной области, становится неопределенным. Во избежание проблем его лучше сразу же "обнулить":

dispose(p); p:= nil;

Типизированные указатели

Для выделения памяти служит стандартная процедура new():

new(<имя_указателя>);

Типизированные указатели

dispose(<имя_типизир_указателя>).

dispose(p); p:= nil;

Удаление элементов списка

Для того чтобы при удалении элемента из середины списка не терялась целостность всей структуры, необходимо при поиске удаляемого элемента "остановиться" за один шаг до него: в тот момент, когда следующий за текущим элемент должен быть удален (см. рис. 10.5):

p:= head; {начать с головы списка} while p^.next^.zhach<>х do p:= p^.next; {поиск} q:= p^.next; {удаляемый элемент} p^.next:= q^.next; {связка "через один"} dispose(q); {освобождение памяти}

Указатели

Для того чтобы хранить (цифровые) адреса, нужны особые переменные. Их называют указателями и относят к специальному типу данных.