Вопрос 22-23.doc

Вопрос 22-23.

18. Статические и динамические структуры данных. Указатели.

Все переменные, которые необходимо объявлять в разделе описания переменных VAR и которые обозначаются идентификаторами, называются статическими переменными. Транслятор после анализа этого раздела отводит каждой переменной соответствующее число ячеек памяти и закрепляет их за данной переменной на всё время работы блока.

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

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

Каждый элемент такой структуры должен знать, за кем он стоит, т.е. содержать ссылку на предшествующий элемент цепочки.

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

С помощью ссылок легко вставить новый компонент в цепочку данных. Для этого нужно изменить 2 ссылки.

Динамическая переменная – это невидимка в программе – идентификатором она не обозначается, транслятор её в памяти места не отводит. память под неё резервируется и освобождается в процессе счета.

Обращение к динамической переменой происходит посредством ссылочной переменной, которая содержит её адрес. Ссылочная переменная имеет имя и явно упоминается в программе. Ссылочная переменная образует новый тип – ссылки или указатели.

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

Указатель – это переменная, которая в качестве своего значения содержит адрес байта памяти.

19. Объявление указателей.

В ТР указатель, как правило, связывается с некоторым типом данных. Такие указатели наз. типизированными. Для их объявления используется символ « ^ », который помещается перед соответствующим типом.

Var

            PI:^integer;

            P2:^real;

Type

            Person = ^Personrecord;

                        Personrecord = record

                        Name, Adres:string;

                        Next:Person

end,                

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

В ТР можно объявлять указатель и не связывать его с каким-то конкретным типом данных. Для этого служит стандартный тип POINTER. Н-р, VAR   PP: pointer.

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

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

20. Процедура NEW.

Процедура NEW резервирует определенное число ячеек в памяти под динамическую переменную и засылает этот адрес в ссылочную перемен­ную.

Динамические переменные, созданные посредством процедуры NEW(R), называются указанными переменными R (указатель R). Параметром обращения к процедуре является типизированный указатель.

Пример. Пусть переменная R имеет тип РТ, описанный выше. Тогда после обращения к процедуре NEW(R) будет создана указанная переменная, в которой предусмотрено поле под значение типа Integer и поле ссылки. При этом ссылочная переменная R содержит адрес указанной пере­менной. Через R^A обозначается сама указанная переменная; R^I - поле це­лых значений I; R'\P - поле ссылки Р.

Замечание. Объем памяти персонального компьютера обычно не ме­нее 640 Кбайт.

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

Var

i.j: integer;     r: "real;

Begin

new(i);

Указатель i приобретает значение, которое перед этим имел указатель кучи HeapPtr, а указатель кучи увеличивает свое значение на 2, т.к. длина внутреннего представления типа integer, с которым связан указатель i, со­ставляет два байта. На самом деле это не совсем так: память под любую пе­ременную выделяется порциями, кратными 8 байтам. Оператор new(r) вызо­вет смещение указателя HeapPtr на 6 байт (длина внутреннего представления типа real).

После того, как указатель приобрел некоторое значение, т.е. стал ука­зывать на конкретный физический байт памяти, по этому адресу можно раз­местить любое значение соответствующего типа. Для этого сразу за указате­лем ставится символ “ ^Л ”. Например,

i^:2; {в области памяти i помещается значение 2}

r^:=2*3.14; { в области памяти r помещается значение 6.28}

Еще раз подчеркнем: если за указателем нет символа “ ^{^} ”, то имеется в виду адрес, по которому размещены данные; а если есть, то имеются в виду данные, размещенные по этому адресу.

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

Рассмотрим описание (фрагмент некоторой программы):

Var Number: integer; {указываем компилятору на необходимость зарезервировать область в памяти по имени Number, на которую будет ссылаться пользователь.

P1: pointer; {описание нетипизированного указателя}

Begin P1:=@Number; {в переменную P1 будет записан адрес переменной Number}

Память в ПК реализуется двумя 16-ми словами.

Word (BA:BS); BA - сегментный адрес, BS - смещение.

Сегмент - участок памяти длиной 64 Кбайта, который начинается с физического адреса, кратного 16.

Смещение - это число, определяющее номер байта в сегменте, к кото­рому необходимо обратиться. Сегмент

Фрагмент памяти в 16 байт называется параграфом. Поэтому можно сказать, что сегмент адресует память с точностью до параграфа, а смещение с точностью до байта. Каждому сегменту соответствует непрерывная и отдель­но адресуемая область памяти. Сегменты могут следовать в памяти один за другим без промежутков или с некоторыми интервалами, или, наконец, пере­крывать друг друга.

Операции над указателями.

Пример. Пусть Q, R: pointer. Тогда оператор Q:=R; зашлет в Q тот же адрес, что хранится в R. Рассмотрим действия с указателями на следующей схеме. Пусть Q и R указывают на различные компоненты динамической пе­ременной типа С:

С= record

I: integer;

Р: pointer

end;

Пусть в памяти машины размещены две цепочки динамических пере­менных:

1. После выполнения оператора Q:=R; переменная Q указывает на ту же динамическую переменную, что и R:

 

2. После выполнения оператора Q^:=R^; получим

т.е. в области Q будут размещены те же данные, что и в области R; на место указанной переменной  , имеющей ссылку на элемент 30, заслана переменная , имеющая ссылку на элемент 25.

3. После Выполнения оператора Q^.I:R^.I; из исходного состояния получим

т.е. на место целого значения 20 заслано значение 15; поле указателя не изменилось.

Замечание. Операторы 1,2, 3 рассматриваются не как последовательно выполняемые, а как примененные к ситуации (*).

4. После выполнения оператора Q^.P:=R^.P; из исходного состояния получим

т.е. на место ссылки на компонент 30 заслана ссылка на компонент 25; поле целого значения не изменилось.

 

Ссылочные переменные могут указывать на одну и ту же переменную, т.е. быть равными, как R и Q в случае 1.

Ссылочные переменные можно сравнивать посредством операций = и о. Логическое выражение Q==R имеет значение True для случая 1 и значе­ние False для случаев 2, 3, 4. Например, для случая 2 ссылочные переменные R и Q указывают на разные динамические переменные, имеющие равные значения.

В качестве аналога нуля для ссылочных переменных принято специ­альное значение NIL. Если переменная имеет значение NIL, то она не указы­вает ни на какую переменную. Значение NIL в поле указателя имеет первый компонент цепочки динамических переменных.

Пример.        L

Значение nil можно заслать оператором присваивания L^nil. Если L=nil, то цепочка пуста. Чтобы проверить, что данный элемент является пер­вым в цепочке переменных, достаточно проверить на nil значение поля ука­зателя этой переменной.

Пример. If L^.P=nil then ....

Замечание. Попытка обратиться к указанной переменной с указате­лем, имеющем значение nil, приводит к ошибке. Диагностика в этом случае не всегда выдается.

Процедура DISPOSE.

Процедура DISPOSE. Динамическая переменная, созданная процеду­рой NEW, может быть “стерта” только процедурой Dispose.

Формат: DISPOSE (R);

Здесь R - ссылочная переменная, указывающая на ту динамическую переменную, которую надо стереть. После стирания динамической перемен­ной •R^A нельзя использовать значение R. Такая ошибка может привести к порче памяти и другим неприятным последствиям.

Динамические переменные, не стертые посредством процедуры Dispose, продолжают занимать место в памяти после окончания работы соот­ветствующего блока программы (становятся “мусором”). Поэтому перед окончанием работы блока динамические переменные надо стереть. 3.6. Стек

Стек (“магазин”) - такая структура динамических данных, которая со­стоит .из переменного числа компонентов одинакового типа. Компоненты из­влекаются из стека таким образом, что первым выбирают тот компонент, ко­торый был помещен последним. Извлеченный компонент в стеке не сохраня­ется.

Опишем стек (стек – переменную), в который можно поместить цепочку динамических переменных:

Type

            StackP=^StackComp;

            StackComp = record

                        I:integer;

                        P: StackP

                        end;

Var      S: StackP;

Если поместить в этот стек последовательно числа 1, 2, 3, то получится стек такого вида:

Поместить в этот стек новый компонент можно, например, процедурой SN:

Procedure SN(k: integer);

Var INew: StackP;    {тип StackP должен быть описан выше} Begin

New(INew); {резервируется память под новый компонент, а

в INew засылается адрес этого компонента} With INew do Begin I:=k; P:=S end;

S:= INew End;

Замечание. Процедура написана для общего случая, поэтому до обра­щения к ней надо выполнить оператор S:= nil; и затем работать с тем значе­нием S, которое получается.

Если в стек вида 1 с помощью процедуры SN занести новый компонент - число 4, to получим стек вида 2:

Процедура извлечения компонента из стека может иметь вид:

Procedure OUT(var k: integer);

Var lOld: StackP;    {тип StackP должен быть описан выше} Begin

I01d:=S;             {адрес последнего компонента} k:= I01d'\I; {извлекается и засылается в S значение соответ -

ствующего указателя на 3, см. пред. пример} ¹ S^IOk^.P;

Dispose (lOld) End;

После обращения к процедуре OUT стек вернется к виду 1. Пустым стеком называется стек, не содержащий компонентов. Такой стек можно получить, присвоив значение nil соответствующей ссылочной переменной (в нашем случае S:= nil;).

Если к пустому стеку несколько раз применить процедуру SN, а затем столько же раз процедуру OUT, то получим снова пустой стек.

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

 

Очередь. Очередь - такая структура данных, при которой изъятие компонентов

происходит из начала цепочки, а запись - в конец цепочки. В этом случае вводятся два указателя: на начало очереди и на конец очереди.

Занесение новых компонентов в очередь. Пример. Пусть имеется цепочка динамических переменных:

Переменные имеют описанный выше тип StackComp. Требуется вставить в цепочку новый компонент 3 после компонента 4, если известен указатель

Для записи нового компонента надо выполнить операторы:

NEWP^.P:=L^.P;

L. P:=NEWP;

Первый оператор засылает в поле указателя нового компонента ссылку на компонент 2, т.е. получим

Второй оператор помещает в поле указателя 4 ссылку на компонент 3 и цепочка L получает вид:

Стек и очередь можно объединить одним понятием: списки.

Основными операциями над списками являются:

- переход от элемента к следующему элементу;

- включение нового элемента в список;             *

- исключение элемента из списка.

Пусть переменные р, q, r описаны как указатели:

Type        uk^elem;

elem^record

inf: integer;

sled: uk end;

Var     р, q, r: uk;

Пусть значением переменной р является ссылка на первый элемент, а значением переменной q - ссылка на некоторый элемент списка целых чисел. Тогда после присваивания q^q^sled ее значением будет или ссылка на сле­дующий элемент этого списка (если такой элемент имеется) или nil. Пользу­ясь таким способом перехода от одного элемента к другому, можно просмат­ривать весь список или его часть. Переменную г будем использовать в качестве запасной.

Переменные р и q указывают на одну и ту же область. После выполнения операторов:

new (r); r^inf^ 17; r^sled^ q'\sled; получим

и после выполнения оператора   q^.sled:=r; получим

т.е. в список  включили элемент 17  между элементами 5 и 12.

.е. из списка исключен элемент 12, стоявший между элементами 17 и -8.

Первое присваивание r:= q^sled; выполняется для того, чтобы сохра­нить ссылку на исключенный элемент, т.е. после исключения из списка он оставался бы доступным и с ним можно было бы выполнять некоторые дей­ствия (например, вставить его на другое место в списке или освободить за­нимаемую им память с помощью процедуры Dispose ).

•   Второе присваивание q^sled^ q^sled^sled; - это собственно исклю-

* .• чение элемента из списка? Третье присваивание r^sled^nil; - окончательное

исключение элемента из списка; теперь из исключенного элемента нельзя по ссылке попасть в список, из которого этот элемент был исключен.

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

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

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

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