Все о динамических структурах данных. Опции

[Altair]

Содержание:

• Указатели
• Списки
  + Модуль для работы со списками. + Двусвязные списки
  
• Стеки
  + Модуль для работы со стеками.
• Очереди
  + Модуль для работы с очередями.
• Деки (двусторонние очереди)
  + Модуль для работы с деками.
• Деревья
  + Модуль для работы с деревьями.
• Сортировка стека
• Сортировка очереди
• Демонстрационные программы с ДСД
• Двусвязные списки

Есть материал по теме? высылайте! ваша информация будет размещена здесь!

[Altair]

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

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

var 
  p1:^integer; { p1 может хранить адрес целого числа }
  p2:^real; { p2 может хранить адрес вещественного числа }

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

var 
  pp:pointer;

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

var 
  pp: pointer;
  p1,p2: ^integer;
  p3: ^real;
 { ... }
Begin
 { ... }
 { связь указателей одного типа данных (разрешено) }
 p1:=p2;

 { попытка присваивания разнотипных указателей (запрещено)}
 p1:=p3;

 { с нетипизированными указателями таких ограничений не существует.}
 pp:=p3; p1:=pp;

Казалось бы, а стоило ли вводить ограничения (нельзя присваивать разнотипные указатели), и тут же давать средство для обхода этого ограничения (обмен значений через дополнительную НЕтипизированную переменную)? Стоило !!! Дело в том, что использование обмена через переменную типа Pointer придает языку дополнительную гибкость, но это также требует от программиста дополнительных усилий, и свидетельствует о вполне осознанном действии, а не случайной ошибке.
Volvo

Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64КБ), стека, и тела программы.

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

HEAРORG — начало кучи хранится в этой переменной.
HEAPEND — конец кучи.
HEAPPTR — текущая граница незанятой динамической памяти.

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

var 
  i:^integer;
  j:^real;
begin
  new(i);

После выполнения этого фрагмента указатель i приобретает значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличивает свое значение на 2, так как внутреннее представление типа integer, с которым связан указатель i, составляет 2 байта.

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

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

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

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

DISPOSE(i) — возвращает в кучу 2 байта, которые ранее были выделены указателем i.

Для работы с нетипизированными указателями используются процедуры:
GETMEM(P,SIZE) — резервирование памяти.
FREEMEM(P,SIZE) — освобождение памяти.

Указательная переменная Р может быть в 3-х состояниях:

• Содержать адрес какой-либо переменной, память под которую уже выделена.
• Содержать постоянный пустой адрес nil.
• Находится в неопределенном состоянии.

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

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

Type 
  TPtr = ^Telem;
  Telem = record
    Inf: Real;
    Link: TPtr
  End;