- •Содержание
- •Введение
- •Структуры данных Классификация структур данных
- •Операции над данными
- •Понятие алгоритма
- •Массивы Описание массива
- •Представление массивов в памяти
- •Рис 1. Представление вектора в памяти
- •Рис 2. Представление вектора ml в памяти
- •Алгоритмы поиска
- •Алгоритмы сортировки
- •Пример сортировки простыми вставками.
- •Описание записи
- •Операции над записями
- •Записи с вариантами
- •Представление записи в памяти
- •Общие процедуры и функции для работы с файлами
- •Процедуры и функции для работы с типизированными файлами.
- •Сортировка содержимого файлов (Внешняя сортировка)
- •Пример внешней сортировки прямым слиянием
- •Пример внешней сортировки естественным слиянием
- •Динамическая память и данные с динамической структурой
- •Ссылочный тип в языке Pascal
- •Типизированные указатели
- •Нетипизированные указатели
- •Операции над переменными ссылочного типа.
- •Динамические списки
- •Реализация списков на языке Pascal.
- •Стек, очередь, дек
- •Рекурсия
- •Нелинейные структуры данных. Деревья
- •Бинарные деревья
- •Реализация бинарных деревьев
- •Способы обхода бинарных деревьев
- •Сортировка с прохождением бинарного дерева
Нетипизированные указатели
Нетипизированные указатели — указатели, базовый тип которых не фиксируется. Такие указатели задают только место (адрес оперативной памяти), без конкретизации типа значения, содержащегося по этому адресу.
Такие указатели определяются с помощью предопределенного идентификатора Pointer.
<переменная~указатель>: Pointer;
var
pntr: Pointer;
Для выделения и освобождения области динамической памяти без учета типа используются процедуры
GetMem (<нетипизированный указатель>, <размер памяти в байтах>)
FreeMem (<нетипизированный указатель>, <размер памяти в байтах >),
соответственно.
Они вызываются с двумя параметрами: указатель типа и размер выделяемой (макс. - 64К) или освобождаемой памяти в байтах.
Замечания:
! освобождать следует ровно столько байтов сколько было выделено, и по тому же самому указателю.
Type
TR = record
a, b: real;
end;
TPr = ^TR;
TI=^integer;
Var
pntr: pointer;
rec: TR;
q: TI;
Begin
Rec.a:=0.5;
Rec.b:= 0.6;
GetMem(pntr, SizeOf(TR));
new(q);
pntr:=q;
TI (pntr)^:=q^;
TPr(pntr)^:=rec;
End.
Использование нетипизированных указателей позволяет осуществлять неявное преобразование типов: по одному и тому же адресу можно размещать различные типы данных, лишь бы они занимали одинаковый объём памяти.
Операции над переменными ссылочного типа.
Операция взятия указателя (получения адреса).
Значение указателя может определяться оператором присваивания:
<указатель>:=<ссылочное выражение>;
В качестве ссылочного выражения можно использовать:
указатель; например, p2:=p1;
операция @, которая ориентирует переменную указателя на область памяти, содержащую существующую переменную, включая и те переменные, которые имеют идентификаторы р:=@i.
ссылочную функцию (т.е. функцию, значением которой является указатель);
константу nil. Например, pl:=nil.
Замечание:
! базовые типы указателей должны быть совместим, поскольку соблюдается принцип соответствия типов.
! если динамическая величина теряет свой указатель, то она становится «мусором». В программировании под этим словом понимают информацию, которая занимает память, но уже не нужна.
Доступ к динамическим переменным
Чтобы получить доступ к значению динамической переменной надо выполнить операцию разыменования указателя: p1^:=2.
Разыменование допускается для любых ссылочных типов.
! разыменование является некорректным, если ссылочная переменная имеет значение nil. В этом случае не существует переменной, на которую ссылается указатель, поэтому последовательность операторов pl:=nil; pl^:=2 является недопустимой.
Т.о. идентификаторы динамических переменных имеют вид:
<переменная-указатель>^
Например, обозначение p1^ можно расшифровать так: динамическая переменная, на которую ссылается указатель p1.
Дальнейшая работа с динамическими переменными происходит точно так же, как со статическими переменными соответствующих типов. Им можно присваивать значения, их можно использовать в качестве операндов в выражениях, параметров подпрограмм и пр. Например:
р1^:=25;
р3^:= 'Write';
for i:=1 to 100 do pMass^[I]:=I;
Операции сравнения
Над значениями ссылочных типов допускаются две операции сравнения: на равенство (=) и неравенство (<>). Эти операции проверяют, ссылаются ли два указателя (ОДНОГО ТИПА) на один и тот же адрес памяти.
Для связи элементов динамических структур необходимо наличие поля для данных, а также поля для указателя на следующий элемент. Для описания таких структур может служить структура запись. Пример динамической структуры запись:
Type
TUkNaZapis=^TZapis;
TZapis=record
i: integer;
j: char;
end;
Var
ukNaZapis: TUkNaZapis;
Begin
New (ukNaZapis);
UkNaZapis^.i:=1;
UkNaZapis^.j:='a';
End.
Процедуры и функции для работы с динамической памятью.
Функция MemAvail: LongInt (без параметров) возвращает размер (в байтах) общей свободной области памяти в текущий момент.
Функция MaxAvail: LongInt (без параметров) возвращает размер максимальной свободной области памяти в текущий момент.