 |
Адресный тип-указатель, ссылочные переменные, простейшие действия с указателями.
|
|
|
|
Московский государственный технический
Университет им. Н.Э. Баумана
Просуков Е.А., Пащенко О.Б.
Работа с динамическими структурами данных
Часть 1
Ссылки, структуры, списки записей
Учебно-методическое пособие по курсу
«Вычислительная техника и информационная технология»
(упрощенная версия для однонаправленных списков)
Москва 2002
Содержание
1. Ссылки, динамические переменные и структуры.
1.1 Адресный тип-указатель, ссылочные переменные,
простейшие действия с указателями.
1.2 Динамическое распределение памяти в области кучи,
процедуры управления кучей, не связанные динамические данные.
1.3 Практические примеры работы с не связанными динамическими данными.
- Связанные динамические данные.
2.1 Разновидности связанных списков.
3.Приемы программирования при обработке связанных списков.
3.1 Создание и опустошение списка.
3.2 Вывод содержимого информационных полей списка.
3.3 Включение и исключение узлов.
3.3.1 Включение узла в список.
3.3.2 Исключение узла из списка.
4.Практикум по программированию с динамическими переменными на языке
Turbo Pascal 7.0.
4.1 Темы заданий для лабораторных работ.
Ссылки, динамические переменные и структуры.
Адресный тип-указатель, ссылочные переменные, простейшие действия с указателями.
Динамическими структурами данных считаются такие, размер которых заранее неизвестен и определяется и изменяется в процессе работы программы. Необходимость в динамических структурах данных возникает в следующих случаях:
1. Когда нужен массив или иная структура, размер которой изменяется в широких пределах.
|
|
|
2. Когда в определённых частях программы требуется получить дополнительную память под переменные довольно большого размера.
3. Когда размер переменной (массива или записи) превышает 64 килобайта.
Во всех этих случаях возникающие проблемы можно решить, применяя динамические переменные и ссылочные типы данных. Для организации динамических данных выделяется специальная область памяти, называемая " кучей " (heap), непрерывный участок определённого размера. При этом в специальной переменной сохраняется адрес начала этого участка. Такие переменные называют ссылочными переменными. Синоним этого термина - " указатель " (pointer).
В Турбо Паскале 7.0 для определения ссылочной переменной нужно описать её как переменную, имеющую ссылочный тип. В качестве ссылочного можно использовать встроенный тип Pointer или любой другой тип, определяемый пользователем следующим образом:
TYPE Имя_ссылочного_типа=^Имя_базового_типа;
где Имя_базового_типа – любой идентификатор типа.
В результате такого определения создаваемые затем ссылочные переменные будут указы-вать на объекты базового типа, определяя тем самым динамические переменные базового
типа. Например: {базовые типы} Type DimType = array [1..100] of Byte;
MyRecType = record
a: real; b: integer;
end;
{ссылочные типы} IntPtr=^Integer; {ссылка на целое значение}
DimPtr=^DimType; {ссылка на массив данных}
RecPtr=^MyRecType; {ссылка на запись}
Компилятор отводит под " указатель " четыре байта статической памяти. Переменная типа " указатель " занимает в памяти двойное слово, в котором младшее слово содержит адрес смещения, а старшее – адрес сегмента размещения, связанного с указателем участка динамической памяти.
" Указатель " (указательная переменная P) может находиться в трёх состояниях:
1. Неопределённое состояние в начале работы программы (" указатель " ещё не инициализирован) рис 1.1 а.
2. Содержит адрес какой-либо переменной (адрес размещения) рис 1.1 б.
|
|
|
3. Содержит значения предопределённой константы nil, такой " указатель " называют пустым, т.е. он не указывает ни на какую переменную и содержит " 0 " в каждом из четырёх байтов рис 1.1 в.
|
Р P P^ Р
?
|
|
" Указатели " можно сравнивать друг с другом, присваивать " указателю " адрес другого " указателя ", передавать указатель как параметр.
Использование идентификатора " указателя " в программе означает обращение к
адресу ячейки памяти, на которую он указывает. Для обращения к содержимому
ячейки, на которую указывает " указатель ", требуется после его идентификатора
поставить символ ^. Эта операция называется операцией разименовывания.
Пример: var P:^Byte; Begin P^:=1; end;
Простейшие действия с указателями представлены в таблице 1.1 [2].
Таблица 1.1
| Действие | Результат | ||||||
| 1. Объявление type Plnt=^integer; var a,b: Plnt; | а? b? | ||||||
| 2. Выделение памяти (ячеек памяти) Процедура New(a); Процедура New(b); | a a^ b b^ | ||||||
| 3. Занесение информации в ячейки памяти a^:=1; b^:=2; | a a^ b b^ | ||||||
| 4. Копирование информации из ячейки в ячейку a^:=b^; | a a^ a^=b^ b b^ a<>b | ||||||
| 5. Копирование адреса ячейки a:=b; | a a^=b^ a^ b b^ a=b | ||||||
| 6. Освобождение ячейки памяти Процедура Dispose(a); a:=b; | А a^ b b^ | ||||||
7.   
b:=nil; | a a^ b b^ |
Пример простых действий с указателями (программа инициализации массива):
Вариант 1. Обычные переменные. Вариант 2.Динамические переменные
type Vect=array[1..3] of Byte; type Vect=array[1..3] of Byte;
var X: Vect; var PX:^Vect;
i: Byte; i: Byte;
begin begin
New(PX);
for i:=1 to 3 do for i:=1 to 3 do
X[i]:=i; PX^[i]:=i; Dispose(PX);
end. end.
Рис.1.2
|
|
|
