Курс лекций по Теме 3

Конспект лекций по Теме 3.

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

Указатели

Формирование динамических объектов осуществляется с помощью стандартных процедур и функций языка Паскаль.

При разработке программ часто возникает проблема, связанная с тем, что размер обрабатываемой информации может быть определен только в процессе работы программы. Например, размер файла можно определить только после того, как он будет открыт (после выполнения в программе оператора Reset).

Все объявления данных в разделе их описания (раздел var) требуют точного значения размерности (например, …array[1..10] of …), так как компилятор "распределяет" память для используемой информации до начала выполнения программы и может получить эту размерность только из текста программы (в частности из раздела описания переменных). Такое распределение памяти, до начала выполнения программы, называют

статическим.

Распределение памяти в процессе работы программы называют динамическим. Для получения памяти в этом случае в программе необходимо выполнить запрос к операционной системе (ОС). По этому запросу ОС выделяет память в динамической области оперативной памяти компьютера – "куче" (heap) и возвращает программе начальный адрес, выделенного участка оперативной памяти. Доступ к данным, значения которых расположены в выделенной динамической области памяти, требует использования в программе переменной, значением которой и будет возвращаемый ОС адрес. Такая переменная имеет специальный, ссылочный тип данных – указатель.

Формат:

Type

<имя типа> = pointer;

<имя типа> = ^<идентификатор типа>;

Например:

type

T = pointer; {указатель не связан с определенным типом данных} T1 = ^integer; {указатель связан с данными целого типа}

Var

{ переменные типа указатель} ptr1: T;

ptr2: T1;

Для правильной работы с указателями очень важно четко различать два понятия:

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

В приведенном примере это значение переменных ptr1, ptr2

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

обозначаются :

<имя переменной типа указатель>^

Для данного примера значения по адресу обозначаются так: ptr1^, ptr2^

.

Чтобы "почувствовать разницу" между значением указателя и значением данных, адресуемых этим указателем, рассмотрим следующую схему:

ОПЕРАЦИЯ

РЕЗУЛЬТАТ

ЗНАЧЕНИЕ

ptrX^

ПО АДРЕСУ

ЗНАЧЕНИЕ

(значение

ptrX

X

X

УКАЗАТЕЛЯ

данных)

(адрес)

ptrY:= ptrX

УКАЗАТЕЛЬ

Изменяется значение

ptrX^

указателя

ptrX

ptrY

X

X

X

X

Данные

потеряны!

ptrY^

ptrY

ptrX^

Y

X

ptrX

X

X

ptrY^:= ptrX^

Изменяется

ptrY^

значение данных

ptrY

Y

X

После выполнения операции ptrY:= ptrX изменяется значение указателя ptrY и доступ к данным по предыдущему значению этого указателя потерян (данные превращаются в "мусор")!

После выполнения операции ptrY^:= ptrX^ изменяется значение данных по указателю ptrY. Значение указателя ptrY не изменяется!

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

программе, может использоваться для других программ или в целях самой ОС.

Состояния указателей

Указатели могут иметь 3 состояния:

1.Инициированный указатель. Указатель указывающий на какие-то данные.

2.Пустой указатель. Указатель содержащий пустое значение – NIL. В C/C++ это NULL, уж не знаю почему тут его так назвали. ВАЖНО! Значением NIL нельзя инициировать переменные других типов (не указатели), это приведет к ошибке при компиляции так как само значение NIL имеет тип Pointer!

3.Мусорный указатель. Очень опасный тип указателя. Он содержит какое-то значение, но не указывает никуда. Указатель оказывается в таком состоянии сразу после объявления и после того как память, на которую он указывает, уже освободили. Ошибки, основанные на попытках использования мусорных указателей, доставляют больше всего хлопот. Поэтому рекомендуется своевременно устанавливать неиспользуемым указателям значение NIL и проверять их при использовании на это значение.

Разыменование

Хорошо, указатели указателями, но как использовать данные адресуемые ими? Для этой цели используется операция разыменования — операция обратная объявлению указателя.

…
myInt	:	^integer;
…
myInt^	:= 1;	//	присвоим ячейки памяти на которую
указывает myInt значение 1
		// (не самому указателю!)
inc(myInt^);		//	увеличим значение в ячейке с адресом myInt
…

Выражение myInt^ дословно означает следующее: «значение по адресу myInt«. Запомнить несложно: чтобы создать указатель ставим галочку (^) перед типом, чтобы разыменовать — после имени.

Взятие адреса

Важно понимать, что указатель всегда указывает на какой-то байт в памяти, а не на объект (если точнее — на первый байт объекта). И для того, чтобы

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

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

…

myPointer_1 := @myIntegerVariable; myPointer_2 := @myStringVariable; myPointer_3 := @myObject; myPointer_4 := @nameOfMyFunction;

…

Имена объектов и переменных в этом коде говорят о типе этих объектов. Здесь мы получили адреса переменных (первые 2 строки), объекта какого-то класса (3я строка), какой-то функции (4я строка). Обратите внимание, чтобы получить адрес функции, надо указать её имя без параметров и поставить перед ним @.

Приведение типов

Второй очень важной возможностью, является приведение типов. Приведение типов — это указание компилятору каким образом работать с переменной, непосредственно при её использовании.

Необходимо понимать один очень важный момент: приводить к типу нужно именно данные, адресуемые указателем, а не сам указатель. Пример:

…
myPointer	:	pointer;
myVar	:	integer;
…

// пусть myPointer указывает на какое-то целое число (4 байта), тогда

myVar := integer(myPointer);

…

Этот код отлично скомпилируется, но он содержит ошибку. Дело в том, что здесь мы привели сам указатель к целому знаковому числу. Результат в итоге будет не предсказуем. Нужно помнить, что указатель, это тоже переменная в стеке, а операция типа @myPointer вполне легальна. Более того, мы можем использовать в качестве указателя любую переменную размером 4 байта. ( pointer(myDwordValue) ) вполне может послужить указателем. Чтобы

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

…
myPointer	:	pointer;
myVar	:	integer;
…

// пусть myPointer указывает на какое-то целое число (4 байта),

тогда
myVar := integer(myPointer^);	// указатель разыменован
…

Этот код сделает то, что нам нужно.

Ошибки

Об ошибках связанных с использованием указателей, в кругах программистов ходят легенды. На самом деле все не так страшно. Основной принцип, при работе с указателями — не надеяться на компилятор. Вы должны всегда знать, на что указывает ваш указатель. Если возникают хоть какие-то сомнения, лучше переписать этот участок. Так же стоит всегда держать неиспользуемые указатели инициированными значением NIL и проверять их перед использованием.

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

Утечки памяти происходят в том случае если, программист забывает освобождать выделенную память. Также не стоит смешивать разные методы выделения и освобождения динамической памяти. Например, если выделить память средствами Delphi, а затем освободить её уже средствами API, могут возникнуть проблемы.

Неинициированные или мусорные указатели появляются тогда, когда программист создает указатель или освобождает память, на которую они указывают и не заботится об установке этих указателей в NIL. Еще один момент, часто приводящий к появлению указателей такого типа — это создание двух и более указателей, адресующих одну и ту же область памяти. При освобождении такой памяти, часто, «сбрасываются» не все указатели.

Процедуры работы с динамическими структурами данных

Процедуры New и Dispose

В этих процедурах размер запрашиваемой и освобождаемой памяти явно не указывается в процедуре и определяется типом данных. Поэтому описание указателя должно быть только такого вида: ^<имя типа данных>.

New(P) – выделить память, размер которой определяется типом данных указателя P. После выделения памяти значением переменной P становится начальный адрес выделенный области памяти.

Выделяемая процедурой New память не инициализируется каким-либо значением.

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

Процедуры GetMem и FreeMem

В этих процедурах размер запрашиваемой и освобождаемой памяти явно указывается в процедуре.

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

GetMem(P, Size) – выделить память размером Size (единовременно не более 65528 байт) и поместить значение начального адреса выделенной области памяти в укзатель P.

FreeMem(P, Size) – освободить выделенную память размером Size, начальный адрес которой определяется значением указателя P.

Применение динамических структур для организации списков

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

Указатель

Данные

Данные

Данные

NIL

на начало

списка

Указатель

Указатель

Указатель

Структура элемента списка может быть объявлена в программе, например, следующим образом:

type

ptrList = ^TList;{ тип указателя связан со структурой элемента списка }

TList	= record	{ структура элемента списка:		}
inf	: <тип данных>;	{	информация (данные)	}
next: ptrList;		{	указатель на элемент списка	}
end;

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

Создания списка.

var
p1, p2, pList: ptrList; { p1 – указатель на новый элемент списка			}
		{ p2 – вспомогательный указатель, в начале = NIL}
		{ pList – указатель на начало списка	}
begin
p2	:= NIL;	{ список пуст	}
<Цикл добавления элементов в список>
begin
New(p1);		{ выделяем память для элемента списка	}
p1^.inf := <данные>; { формируем данные элемента списка			}
p1^.next := p2; { "связываем" элементы списка			}
p2	:= p1; { сохраняем адрес элемента списка в p2		}
end;
pList:= p2;		{ Список создан. pList – адрес начала списка	}
end.

Схема создания списка (шаг 1 и шаг 2) приведена на схеме

ШАГ 1 (добавление первого элемента в список)

New (p1);	p1
p1^. Inf := <данные>; p1
p1^.next := p2;
	p1										NIL
	p2
p2 := p1;	p1										NIL
ШАГ 2 (добавление второго элемента в список)
New (p1);	p2										NIL
	p1
	p2										NIL
p1^. Inf := <данные>;
	p1
	p2										NIL
p1^.next := p2;
p2 := p1;	p1										NIL
	p2
	p1

Выделение памяти:

p1 – адрес нового элемента

Формирование данных элемента списка

«Пустой» указатель (NIL) – это адрес конца списка

Сохранение адреса элемента списка в p2

Первый элемент создан на шаге 1

Выделение памяти:

p1 – адрес нового элемента

Формирование данных второго элемента списка

«Связывание» второго элемента списка с первым элементом

Сохранение адреса элемента списка в p2

Схема создания списка из двух элементов

Просмотр списка.

var
p1, pList: ptrList; { pList – указатель на начало списка		}
begin
p1	:= pList;

while p1<> NIL do begin

<.использование данных элемента списка (p1^.inf) >;

p1 := p1^.next; { перемещаем указатель p1 на следующий элемент } end;

end.

Удаление списка.

var
p1, p2, pList: ptrList; { pList – указатель на начало списка			}
begin
p1	:= pList;
while p1<> NIL do begin
	p2:=p1;	{ сохраняем адрес элемента списка в p2	}
	p1 := p1^.next; { перемещаем указатель p1 на следующий элемент }
	dispose(p2); { удаляем элемент списка, адрес которого p2		}

end;
pList:=NIL;	{ список пуст	}
end.

Работа со списком

Структура элемента списка может быть объявлена в программе, например, следующим образом:

type
TList	= record		{ структура элемента списка:	}
inf	: <тип данных>;	{	информация (данные)	}

next: ^ptrList; // указатель на следующий элемент списка pred: ^ptrList; // указатель на предыдущий элемент списка end;

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

Создание списка

Procedure AddItemToList(Item,Cur: ^TList, key: Integer);

//Item – указатель на новый элемент списка

//cur – указатель на объект в списке

Begin

//пять способов добавления элемента в список (в пустой список

//в начало, в конец, в середину после текущего и до текущего)

//всегда проверка на пустой список?

If Cur == NIL then { список пуст } Cur :=Item;

item^.next:=Nil; // зануляем указатели на следующий и item^.pred:=Nil; // предыдущий элементы.

// конец процедуры

End

Else

case key of

1:// в начало списка begin

while Cur^.Pred<>Nil do // переход на начало списка Cur=Cur^.Pred;

Item^.Next:=Cur;

Item^.Pred:=Nil;

Cur^.Pred:=Item;

end;

2:// в конец списка

begin

while Cur^.Next<>Nil do // переход на конец списка Cur=Cur^.Next;

Item^.Next:=Nil;

Item^.Pred:=Cur;

Cur^.Next:=Item;