2. Теоретические сведения

УКАЗАТЕЛИ

Операционная система MS - DOS все адресуемое пространство делит на сегменты. Сегмент - это участок памяти размером 64 К байт. Для задания адреса необходимо определить адрес начала сегмента и смещение относительно начала сегмента.

В TURBO PASCAL определен адресный тип Pointer - указатель. Переменные типа Pointer содержат адрес какого - либо элемента программы и занимают 4 байта, при этом адрес хранится как два слова, одно из них определяет сегмент, второе - смещение.

Пример: var p: Pointer;

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

type NameType= ^T;

var p: NameType;

Здесь p - переменная типа указатель, связанная с типом Т с помощью имени типа NameType.

Описать переменную типа указатель можно непосредственно в разделе описания переменных:

var p: ^T;

Необходимо различать переменную типа указатель и переменную, на которую этот указатель ссылается. Например если p - ссылка на переменную типа Т, то p^ - обозначение этой самой переменной.

Для переменных типа указатель введено стандартное значение NIL, которое означает, что указатель не ссылается ни к какому объекту. Константа NIL используется для любых указателей.

ДИНАМИЧЕСКИЕ ПЕРЕМЕННЫЕ

Статической переменной (статически размещенной) называется описанная явным образом в программе переменная, обращение к ней осуществляется по имени. Место в памяти для размещения статических переменных определяется при компиляции программы.

В отличие от таких статических переменных в программах, написанных на языке ПАСКАЛЬ, могут быть созданы динамические переменные. Основное свойство динамических переменных заключается в том, что они создаются и память для них выделяется во время выполнения программы.

Размещаются динамические переменные в динамической области памяти (heap - области).

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

Работа с динамической областью памяти в TURBO PASCAL реализуется с помощью процедур и функций New, Dispose, GetMem, FreeMem, Mark, Release, MaxAvail, MemAvail, SizeOf.

Процедура	New(var p:Pointer )	выделяет место в динамической области памяти для размещения динамической переменной p^ и ее адрес присваивает указателю p
Процедура	Dispose(var p:Pointer )	освобождает участок памяти, выделенный для размещения динамической переменной процедурой New, и значение указателя p становится неопределенным
Процедура	GetMem(var p:Pointer; size:Word)	выделяет участок памяти в heap - области, присваивает адрес его начала указателю p, размер участка в байтах задается параметром size
Процедура	FreeMem(var p:Pointer; size:Word)	освобождает участок памяти, адрес начала которого определен указателем p, а размер - параметром size (значение указателя p становится неопределенным)
Процедура	Mark( var p:Pointer )	записывает в указатель p адрес начала участка свободной динамической памяти на момент ее вызова
Процедура	Release(var p:Pointer)	освобождает участок динамической памяти, начиная с адреса, записанного в указатель p процедурой Mark, то есть, очищает ту динамическую память, которая была занята после вызова процедуры Mark
Функция	MaxAvail:Longint	возвращает длину в байтах самого длинного свободного участка динамической памяти
Функция	MemAvail:Longint	полный объем свободной динамической памяти в байтах
Функция	SizeOf( X )	Вспомогательная функция Word возвращает объем в байтах, занимаемый X, причем X может быть либо именем переменной любого типа, либо именем типа

Рассмотрим некоторые примеры работы с указателями.

var p1, p2: ^Integer;

Здесь p1 и p2 - указатели или переменные ссылочного типа.

p1:=NIL; p2:=NIL;

После выполнения этих операторов присваивания указатели p1 и p2 не будут ссылаться ни на какой конкретный объект.

New(p1); New(p2);

Процедура New(p1) выполняет следующие действия:

• в памяти ЭВМ выделяется участок для размещения величины целого типа;

• адрес этого участка присваивается переменной p1:

Аналогично, процедура New(p2) обеспечит выделение участка памяти, адрес которого будет записан в p2.

После выполнения операторов присваивания p1^:=2; p2^:=4; в выделенные участки памяти будут записаны значения 2 и 4 соответственно.

В результате выполнения оператора присваивания p1^:=p2^; в участок памяти, на который ссылается указатель p1, будет записано значение 4.

После выполнения оператора присваивания p2:=p1; оба указателя будут содержать адрес первого участка памяти.

Переменные p1^, p2^ являются динамическими, так как память для них выделяется в процессе выполнения программы с помощью процедуры New.

Динамические переменные могут входить в состав выражений,

например:

p1^:=p1^+8; Write('p1^=',p1^:3);

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

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

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

Описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти ЭВМ и увеличивает время решения задач.

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

Поле данных может быть переменной, массивом, множеством или записью.

Для дальнейшего рассмотрения описание этой компоненты дадим следующим образом:

type

Pointer = ^Comp;

Comp = record

D:T;

pNext:Pointer

end;

здесь T - тип данных.

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

ЛИНЕЙНЫЕ СПИСКИ

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

Каждая компонента списка определяется ключом. Обычно ключ - либо число, либо строка символов. Ключ располагается в поле данных компоненты, он может занимать как отдельное поле записи, так и быть частью поля записи.

Основные свойства связного списка:

• для чтения доступна любая компонента списка;

• новые компоненты можно добавлять в любое место списка;

• при чтении компонента не удаляется из списка.

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

• начальное формирование списка (запись первой компоненты);

• добавление компоненты в конец списка;

• чтение компоненты с заданным ключом;

• вставка компоненты в заданное место списка (обычно после компоненты с заданным ключом);

• исключение компоненты с заданным ключом из списка.

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

Описание компоненты списка и переменных типа указатель дано в приложении (pBegin - указатель начала списка, pEnd - указатель конца списка, остальные - вспомогательные указатели).

Пример начального формирования списка и добавления компонент в конец списка представлен в Приложении 3.

4.ОФОРМЛЕНИЕ ОТЧЕТА

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

5.КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Результат выполнения программы (вид экрана пользователя):

Program DemoPointer;

var p1,p2,p3:^Integer;

begin

p1:=NIL; p2:=NIL; p3:=NIL;

New(p1); New(p2); New(p3);

p1^:=2; p2^:=4;

p3^:=p1^+Sqr(p2^);

writeln('p1^=',p1^:3,' p2^=',p2^:3,' p3^=',p3^:3);

p1:=p2;

writeln('p1^=',p1^:3,' p2^=',p2^:3)

end.

2. var p,q:^integer; r:^char;

Какие из следующих операторов неправильные и почему?

1. p:q;

2. q:=r;

3. p:=nil;

4. r:=nil;

5. q:=p^;

6. p^:=nil;

7. r^:=p^;

8. q^:=ord(r^);

9. if r<>nil then r^:=nil^;

10. if q>nil then q^:=p^;

11. if q=p then write(q);

12. if q<>r then read(r^);

6. ВАРИАНТЫ ЗАДАНИЙ

№ задания	1	2	3	4	1	2	3	4
№ по журналу

Создать однонаправленный список, элементы списка  целые числа, признак окончания ввода элементов  число 0.

1. Подсчитать количество отрицательных элементов списка.

2. Определить, есть ли в списке элемент, равный следующему за ним.

3. Подсчитать количество вхождения в список значения первого элемента.

4. Определить, есть ли в списке элемент, равный числу, введенному с клавиатуры.

Лабораторная работа N27.

РАБОТА С ЭЛЕМЕНТАМИ ЛИНЕЙНОГО ОДНОНАПРАВЛЕННОГО СПИСКА.

1. ЦЕЛЬ И ЗАДАЧИ РАБОТЫ

Целью работы является изучение приемов вставки и удаления элементов списка.