Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

infa_1 / 10.Динамические структуры данных

..doc
Скачиваний:
32
Добавлен:
05.06.2015
Размер:
501.76 Кб
Скачать

10. Динамические структуры данных

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

Статистические данные -- размер которых фиксируется заранее при написании программ.

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

Для объявления динамических данных используется строчный тип. Каждый байт имеет свой адрес. Адреса создаются 2-мя значениями – сегментом и смещениями.

Сегмент – это фрагмент памяти объемом 64 кБ. Смещение – определяет число байтов, на которых нужно отступить от начала сегмента, чтобы обратиться к нужному адресу.

Описание строчного типа

t – ptr = ^t;

t – стандартный или заранее описанный тип данных, называемых базовым типом

t – ptr – тип данных области памяти, в котором хранится значение типа t

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

Var

p: t-ptr;

q:^integer; -- адрес, где хранится переменная.

Для присваивания указателю пустого значения, которое никакому адресу не соответствует

q:=nil;-q - ссылается на пустой адрес

Указатели p и q – типизированные указатели

Поскольку связаны с адресными значениями конкретных базовых типов (t и integer)

Нетипизированные указатели могут ссылаться на данные любого типа. Для описания нетипизированных указателей используется слово pointer.

var

but: pointer;

В объявлении ссылочных типов nane ^ может использоваться простой тип (real, word, string, integer, byte)

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

type

vector = array[1,5] of integer;

p:^vector

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

var

i_ptr,pl:^integer;

s_ptr, ^string;

p:pointer;

В этом случае разрешены следующие операторы присваивания:

не разрешены:

Указателю можно присвоить пустое значение в этом случае он не ссылается не на какие данные. Для указателей существует 2 операции отношения := равно, <> не равно.

Можно проверить ссылается на что-нибудь указатель или нет путем его сравнения с nil.

P<>nil =true – ссылается, =false – не ссылается.

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

Результат выполнения 2-х операций:

1) 2)

1)-указатель меняет значение, 2)-данные меняют значение.

Чтобы связывать указатель с отдельными данными, необходимо выделять для них память:

getmem(var p:pointer; size:word).

Резервируется для указателя p объем памяти размером size byte (65521 байт)

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

freemem( var p: pointer; size: word)

Если размер памяти, необходимой для данных базового типа, неизвестен, то можно определить при помощи функции sizeof(x) которая возвращает число байтов, необходимых для размещения в памяти объема x. Память можно выделять при помощи процедуры new(var p). При этом размер выделяемой памяти не указывается. Выделяется столько байтов, сколько занимает переменная базового типа указателя p. Эта процедура используется для типизир. Указателя. Освобождение памяти, выделенной под типизированный указатель у, осуществляемый при помощи процедуры lispose(p). Для работы с типизированными указателями используется также процедура mark(var p), которая запоминает состояние динамической памяти в тот момент, когда эта процедура вызывается. В указателе р сохраняется адрес 1го байта свободной памяти, и далее можно несколько раз выделять память, а затем используется процедура release(р), release (var p: pointer), которая возвращает память в состояние которое было запомнено ранее при помощи процедуры mark.