Иванова Г.С. - Основы программирования

7. Программирование с использованием динамической памяти

nil, и выполнение программы не будет прервано. Действия по обработке возникшей ситуации выполняет программист, который должен проверить указатели после возврата из процедур вьщеления памяти.

Пример 7.1. Разработать программу для определения суммы элементов массива большой размерности (п < 10000, m < 10000, nxm ^ 50000).

Для размещения массива nxm вещественных чисел (real) потребуется бхпхт = 300000 байт памяти, что превышает 64 кб, следовательно, исполь­ зовать стандартный тип «массив» нельзя.

Если создать массив указателей размерности nxm, то потребуется 4xnxm = 200000 байт памяти, что также превышает 64 кб.

Решением задачи явлйется реализация массива в виде статически разме­ щенного массива указателей ptrstr на п элементов (по числу строк), каждый указатель которого хранит адрес динамически размещенного массива - стро­ ки матрицы (рис. 7.7).

Тогда одного сегмента достаточно для размещения около 64000/4 = = 16000 указателей на строки матрицы. Так как указат^ь может адресовать целый сегмент, то в каждой строке можно разместить 64000/6 = 10677 эле­ ментов типа real, т.е. даже больше, чем требуется по условию задачи. Одна­ ко конкретный размер массива, который можно разместить, определяется размером доступной динамической памяти (1^чи). Поэтому в программе осуществляется контроль выделения памяти методом «перехвата» систем­ ной ошибки с помощью собственной функции обработки ошибок.

Наибольшую сложность в данной программе представляет определение адреса элемента матрицы с индексами 1, j . Этот адрес складывается из сег­ ментного адреса, хранящегося в указателе - Seg(ptrstr[i]), и смещения, состо­ ящего из смещения начала динамического массива, которое хранится в том же указателе - Ofs(ptrstr[i]), и смещения на j-1 элемент внутри динамически размещенного массива - (j-l)xSizeOf(real). Эти вычисления в программе це­ лесообразно реализовать в виде подпрограммы-функции, которая возвраща­ ет результат типа ^eal.

	Статический		Динамические массивы строк
	массив
	указателей	1			j	m
	1		I	I
		Н			I I Z I
		H	IJiLI		I	I Z E
		•I	I	I	h i d	T
		H	I	I	I	I
		>!	I	I	I

Рис. 7.7. Размещение матрицы в динамической памяти

221

Часть 1. Основы алгоритмизации и процедурное программирование

Program		exjargejnas;
Const	««=76000; {максимальное количество строк}
Var iJ,n,m:word; s.real;
ptrstr: array[L.nn]			of pointer; {статический массив указателей на
Туре	tpreal=^real;			строки матрицы}
{функция формирования адреса элемента матрицы}
Function AddrR(iJ :word) :tpreal:
begin
AddrR: =Ptr(Seg(ptrstr[i]''), OfsfptrstrfiJ'^)+(/-1) *SizeOf(real))
end;
{собственная функция обработки ошибок}
function		heapfunc(size:word):integer; far;
begin heapfunc:^!;			end;
{основная программа}
begin
Randomize;
heaperror:=@heapfunc; {подключаем собственную функцию обра­
WriteLnCВведите п,т');				ботки ошибок}
ReadLn(n,m);
for	i;=] to п do
begin
	GetMem(ptrstrfiJ,m*sizeof(real));{запрашиваем память подстро­
	ifptrstr[ij=nil		then	ку матрицы}
				{если памяти не хватает,}
		begin		{то завершаем программу}
		WriteLnC Не хватает памяти под матрш^у,');
		forj:'==l to i'l		do
		FreeMem(ptrstr[j]ym*sizeof(real)); {освобождаем уже
				выделенную память}

Halt(2);

end;

forj:=l to m do AddrR(iJ)\'=Random; {если память есть, то за­ полняем строку случайными числами}

end;
s;=0;		to m do s:=s + AddrR(ij)^;
for i;==I to n do	forj:=l
WriteLn('3Ha4eHue суммы		=\s;15:10);
WriteLn(VpedHee	значение	=\s/(n*m):]5:J0);

for i:=] to n do FreeMem(ptrstr[iJ,m*SizeOf(real)); {освобождаем использованную память}

End

222

7. Программирование с использованием динамической памяти

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

Как упоминалось выше, переменные типа «указатель» обычно использу­ ют при реализации динамических переменных, в том числе и динамических структур данных.

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

Линейная динамическая структура представляет собой изменяемую по­ следовательность элементов. Частными случаями таких структур являются:

•стеки, в которых разрешено добавлять элементы только в конец и уда­ лять только последние элементы (рис. 7.8, а);

•очереди, в которых добавление элементов осуществляется в конец, а удаление -из начала (рис. 7.8, б);

•деки, которые допускают добавление и удаление элементов и с нача­ ла, и с конца (рис. 7.8, в).

Вдревовидной структуре каждый элемент (вершина) ссылается на один или более элементов следующего уровня (рис. 7.8, г).

Всетевой структуре никаких ограничений на связи элементов не на­ кладывается (рис. 7.8, д).

Линейные динамические структуры, такие, как стеки, очереди и деки, при известном максимальном количестве элементов в них можно реализо­

вать в виде динамических или статических одномерных массивов. В против-

" l J ^ "з Х4

^1 М^г ^ 3 ^4

Рис. 7.8. Динамические структуры:

а - стек; б - очередь; в - дек; г - древовидная; д - сетевая

223

Часть I. Основы алгоритмизации и процедурное программирование

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

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

•линейные односвязные списки - единственное адресное поле содер­ жит адрес следующего элемента, если следующий элемент отсутствует, то в адресное поле заносят константу nil (рис. 7.9, а)\

•кольцевые односвязные списки - единственное адресное поле содер­ жит адрес следующего элемента, а последний элемент ссылается на первый (рис. 7.9, б);

" ^ ХЭНИЕВНИШ]

I3HIIB*C

^гжд^дш^гтп^ тк.

^

Рис. 7.9. Списки:

а- линейный односвязный; 5-линейный односвязный кольцевой; в - линейный двусвязный; г - двусвязный кольцевой; д - п-связный

224

7.Программирование с использованием динамической памяти

•линейные двусвязные списки - каждый элемент содержит адреса пре­ дыдущего и последующих элементов, соответственно^ первый элемент в ка­ честве адреса предыдущего, а последний - в качестве адреса следующего элемента содержат nil (рис. 7.9, в);

•кольцевые двусвязные списки - каждый элемент содержит адреса пре­ дыдущего и последующих элементов, причем первый элемент в качестве предьщущего содержит адрес последнего элемента, а последний элемент в

качестве следующего - адрес первого элемента (рис. 7.9, г);

• П'Связные списки - каждый элемент включает несколько адресных по­ лей, в которых записаны адреса других элементов или nil (рис. 7.9, д).

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

Туре ре	= ^element;	{тип указателя}
element = record
	name: string[16];			{информационное поле 1}
	telefon:string[7];			{информационное поле 2}
	р: ре;			{адресное поле}
	end;
Элемент двусвязного списка описывается с двумя адресными полями,
например:
Туре ре	= ^element;	{тип указателя}
element = record
	name: stringfldj;		{информационное поле 1}
	telefon:string[7];		{информационное поле 2}
	prev: ре;	{адресное поле «предыдущий»}
	next: ре;	{адресное поле «следующий»}
	end;

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

У любого списка имеется хотя бы один указатель, размещенный в стати­ ческой памяти, который содержит адрес первого элемента списка или кон­ стант)^ nil, если список пуст. Достаточно часто используют дополнительные указатели, в которых хранят адреса других элементов, например, адрес теку­ щего элемента, адрес последнего элемента и т.п. Эти указатели также описы­ ваются как «указатели на элемент», например:

Varfirst, last, q: ре;...

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

225

Часть 1. Основы алгоритмизации и процедурное программирование

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

7.4. Линейные односвязные списки

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

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

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

Недостатком этой структуры является то, что при поиске элемента по номеру приходится просматривать все ранее расположенные элементы, в то время как в одномерном массиве возможен прямой доступ к элементу по ин­ дексу. К тому же реализация линейного односвязногр списка требует допол­ нительной памяти для хранения адресной части элементов.

Рассмотрим более подробно, как выполняются основные операции с ли­ нейными односвязными списками.

Исходные установки. В начале программы необходимо описать эле­ мент и его тип:

Туре tpel=^element; {тип «указатель на элемент»} element^record

num:mteger; {число}

p:tpel; {указатель на следующий элемент} end;

В статической памяти описываем переменную-указатель списка и не­ сколько переменных-указателей, используемых при выполнении операций со списком:

Varfirst, {указатель списка - адрес первого элемента списка} n,f,q:tpel; {вспомогательные указатели}

Исходное состояние «список пуст»:

first :^ml;

Добавление нового элемента к списку. Добавление элемента к списку включает запрос памяти для размещения элемента и заполнение его инфор­ мационной части. Построенный таким образом элемент добавляется к уже существующей части списка.

В общем случае при добавлении элемента к списку возможны следую­ щие варианты:

226

7.Программирование с использованием динамической памяти

•список пуст, добавляемый элемент станет единственным элементом

списка;

•элемент необходимо вставить перед первым элементом списка;

•элемент необходимо вставить перед заданным (не первым) элементом списка;

•элемент необходимо дописать в конец списка.

Добавление элемента к пустому списку состоит из записи адреса эле­ мента в указатель списка, причем в поле «адрес следующего» добавляемого элемента необходимо поместить nil:

new(first); {запрашиваем память под элемент}

first ^.пит:=5; {заносим число в информационное поле} first \р:^пИ; {записываем nil в поле «адрес следующего»}

На рис. 7.10 показана последовательность операций при добавлении элемента к пустому списку.

Добавление элемента перед первым элементом списка. При выполнении этой операции необходимо в поле «адрес следующего» переписать адрес первого элемента списка, а в указатель списка занести адрес добавляемого элемента (рис. 7.11):

new(q); {запрашиваем память под элемент} q^.num:=4; {заносим число в информационное поле}

q\p:=first; {в поле «адрес следующего» переписываем адрес первого элемента}

first: =q; ... {в указатель списка заносим адрес нового элемента}

Добавление элемента перед заданным (не первым). Для выполнения операции необходимо знать адреса элементов, между которыми вставляется элемент, так как адресные части этих элементов при выполнении операции

first	first		first		first
first:-nil:	I	I I	\	S \ I	I 5 101
	\ =	^	%	^	"%
	new(first):		first Л пит: =5;		first Лр; =«//;
a	б			в	г

Рис. 7.10. Последовательность операций при добавлении элемента к пустому списку:

а- исходное состояние; б - запрос памяти под элемент;

е- заполнение элемента; г - занесение nil в поле адреса следующего элемента

227

Часть I. Основы алгоритмизации и процедурное программирование

	first	first
1=^™	t o	Ьи]
	new(q);	q\ пит: =4;
	б	в
	first	first

q\p:=^first;

Рис. 7.11. Последовательность операций при добавлении элемента перед первым:

а - исходное состояние; б - запрос памяти под элемент; в - заполнение элемента; г, д- шаги включения элемента в список

будут корректироваться (рис. 7.12). Пусть f- адрес предыдущего элемента, а п - адрес следующего элемента, тогда:

new(q): {запрашиваем память под элемент} q\num:=3; {заносим число в информационное поле}

q\p:='n; {в поле «адрес следующего» нового элемента переписы­ ваем адрес следующего элемента}

f".p:^q; ... {в поле «адрес следующего» предыдущего элемента за­ носим адрес нового элемента}

Минимально для вставки элемента в линейный односвязныи список не­ обходимо знать только адрес предьщущего элемента, так как тогда адрес сле­ дующего элемента известен -п о f^.p:

new(q); {запрашиваем память под элемент} q\num:=3; {заносим число в информационное поле}

q\p:=f\p; {в поле «адрес следующего» нового элемента переписы­ ваем адрес следующего элемента}

f^.p:=q; ... {в поле «адрес следующего» предыдущего элемента за­ носим адрес нового элемента}

228

7. Программирование с использованием динамической памяти

first JL

Dn34ZI34 8T0I

1XEEW3IEHX1S)

q^.num:=3;

I 3 I I

first

f^-p-q:

first f

8~rg1

q

first f

ТхПЕНЗтЗЧ ^

оЛр.=л;

T O

Рис. 7.12. Добавление элемента перед заданным (не первым):

а - исходное состояние; б - запрос памяти под элемент; в - заполнение элемента; г, д- шаги включения элемента в список

Добавление элемента в конец списка. В этом случае должен быть извес­ тен адрес элемента, после которого добавляется новый элемент (рис. 7.13):

new(q): {запрашиваем память под элемент} q\num:=7; {заносим число в информационное поле}

q\p:=nil; {в поле «адрес следующего» элемента записываем nil} f^.p:=q;... {в поле «адрес следующего» предыдущего элемента за­

носим адрес нового элемента}

229

Часть 1. Основы алгоритмизации и процедурное программирование

first

I

first

'

8Т01

new(q);

\

I I

first

I

q Л mwi: = 7;

L~i-J—I

/Л/?; =^;

first

ixr34zi3bzz

^Л;?; ==«//;

Рис. 7.13. Добавление элемента в конец списка:

а - исходное состояние; б ~ запрос памяти под элемент; в - заполнение элемента; г.д- включение элемента в список

Анализ показывает, что этот случай можно свести к предьщущему, так как адресная часть последнего элемента содержит nil:

new(q); {запрашиваем память под элемент} q^Mum:=7; {заносим число в информационное поле}

q^.p:=f^.p; {в поле «адрес следующего» нового элемента записыва­ ем nil}

f^.p:=q; ... {в поле «адрес следующего» предыдущего элемента за­ носим адрес нового элемента}

230