Основы программирования (947332), страница 38

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 38)

Основы алгоритмизации и процедурное программированBegin1:423456789;P1:=@L; {операция @ возвращает нетипизированный указатель}к:^Р1^[1]: {младший байт внутреннего представления числа L,младший потому, что числа в памяти для данного типа компью­теров хранятся с младшего байта}Контроль корректности значений, полученных в результате выполнен­ных действий, системой не осуществляется, а ложится целиком на програм­миста.7.2.

Управление динамической памятьюОпределяемые в примерах предьщущего параграфа указатели для на­глядности содержали адреса статически размещенных переменных. Однакоосновное назначение указателей ~ адресация динамических переменных. Та­кие переменные располагаются в свободной области, называемой динамиче­ской памятью или «кучей». Эта область расположена после программы, и ееобъем составляет около 200 ... 300 кБ, как это представлено на рис. 7.6.(GooTBeTCTBeHHO, чем больше объем программы, тем меньше размер свобод­ной области памяти.) На этом рисунке также показаны значения стандартныхпеременных Borland Pascal, используемых для управления динамической об­ластью:HeapOrg - указатель на начало динамической области;HeapEnd - указатель на конец динамической области;HeapPtr - указатель на те!0^щее значение границы свободной динамиче­ской области.Заказать и освободить память требуемого объема из динамической об­ласти можно, используя специальные процедуры и функции.1.

Процедура New (Var <типизированный указатель>) - возвращает ад­рес выделенного участка памяти через параметр-переменную. Размер участ­ка памяти определяется базовым типом указателя.Свободная памятьРис. 7.6. Размещение динамической области2187. Программирование с использованием динамической памятиНапример:Varpi: ^integer; ...New(pi); {теперь pi содержит адрес двух байт, выделенных издинамической памяти под размещение переменной целого типа}2. Функция New (<^тип типизированного указателя>^;/7<?ш/^г~ возвраща­ет адрес выделенного участка памяти.

Размер участка памяти также опреде­ляется базовым типом указателя.Например:Туре tpi: ^integer;Varpi:tpi; ...pi:- New(tpi); {pi также содержит адрес двух байт, выделенных издинамической памяти под размещение переменной целого типа}Для размещения изученных нами типов переменных можно использо­вать как процедуру New, так и функцию New.3.

Процедура Dispose ('<типизированный указатель>^ - освобождает па­мять по адресу, хранящемуся в указателе.Например:Dispose(pi);...При попытке применить процедуру к указателю, имеющему значениеnil, или освободить уже освобожденную память фиксируется ошибка и,выдается соответствующее сообщение.Серия последовательных обращений к New и Dispose обычно приводитк фрагментации памяти - память разбивается на небольшие фрагменты счередованием свободных и занятых участков. В результате может возник­нуть ситуация: свободной памяти для размещения новой переменной доста­точно, но она не может быть размещена из-за отсутствия непрерывного уча­стка требуемого размера.Дпя уменьшения явления фрагментации используют специальные про­цедуры.4. Процедура Л/лгА (Varp:pointer)-запоминает значение HeapPtr в ука­зателе р, полученном в качестве параметра.5.

UpoiXQjxypa. Release (Var p:pointer) - освобождает весь фрагмент памя­ти, начиная с адреса р, зафиксированного в указателе процедуры Mark. На­пример:new(pl);new(p2);mark(p);new(p3);219Часть J. Основы алгоритмизации и процедурное программированиеnew(p4);release(p);.,.Примечание. Совместное использование процедур Dispose и Release недопустимо, таккак Release разрушает список освобожденных фрагментов, создаваемый при выполненииDispose.Динамическую память можно выделять фрагментами, указывая их раз­мер.6.

Процедура GetMem (Var p:pointer; size:word) - запрашивает у систе­мы память размера, указанного в параметре size (запрашиваемый объем недолжен превышать 64КБ), и помещает адрес выделенного системой фраг­мента в переменную типа pointer с именем р. Как правило, данный способвыделения памяти используется, если требуется память под размещение бу­феров, формат которых программисту не известен.7. Функция SizeOf(x): word- возвращает длину указанного объекта х вбайтах.8.

Процедура FreeMem (p:pointer; size:word) - освобождает область па­мяти, вьщеленную процедурой GetMem.Однако каким бы способом не запрашивалась память, может возникнутьситуация, когда оставшаяся свободная память меньше требуемой, и памятьвыделить невозможно. В этом случае система по умолчанию выдает сооб­щение об ошибке выполнения и аварийно завершает задачу.Избежать подобной ситуации можно несколькими способами.П е р в ы й с п о с о б заключается в предварительной проверке нали­чия свободной памяти требуемого размера.9.

Функция Maxavail: longint ~ возвращает длину максимального непре­рывного участка памяти.10. Функция Memavail: longint - возвращает размер всей свободной па­мяти - сумму длин всех свободных фрагментов.В т о р о й с п о с о б базируется на возможности перехвата системнойобработки ошибки выделения памяти. Для этого необходимо определитьсвою подпрограмму обработки ошибки, в которой вместо признака ошибкираспределения динамической памяти О, установленного по умолчанию, не­обходимо задать Heapfunc:=l, например:Function HeapFuncfsize: word) : integer; far;begin HeapFunc: =7; end;В программе необходимо определить адрес подпрограммы обработкиошибки НеарЕггог, указав собственную программу HeapFunc:HeapError:=@HeapFunc; ...Использование такой подпрограммы приведет к тому, что процедурыNew и GetMem при исчерпании памяти вернут указатели, установленные в2207.

Программирование с использованием динамической памяти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Динамические массивы строк1jmНHI II IJiLI IZII I ZE•IIIhidHIII>!IIITIРис.

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:beginAddrR: =Ptr(Seg(ptrstr[i]''), OfsfptrstrfiJ'^)+(/-1) *SizeOf(real))end;{собственная функция обработки ошибок}function heapfunc(size:word):integer; far;begin heapfunc:^!; end;{основная программа}beginRandomize;heaperror:=@heapfunc; {подключаем собственную функцию обра­ботки ошибок}WriteLnCВведите п,т');ReadLn(n,m);for i;=] to п dobeginGetMem(ptrstrfiJ,m*sizeof(real));{запрашиваем память подстро­ку матрицы}ifptrstr[ij=nil then{если памяти не хватает,}begin{то завершаем программу}WriteLnC Не хватает памяти под матрш^у,');forj:'==l to i'l doFreeMem(ptrstr[j]ym*sizeof(real)); {освобождаем ужевыделенную память}Halt(2);end;forj:=l to m do AddrR(iJ)\'=Random; {если память есть, то за­полняем строку случайными числами}end;s;=0;for i;==I to n do forj:=l to m do s:=s + AddrR(ij)^;WriteLn('3Ha4eHue суммы =\s;15:10);WriteLn(VpedHee значение =\s/(n*m):]5:J0);for i:=] to n do FreeMem(ptrstr[iJ,m*SizeOf(real)); {освобождаемиспользованную память}End2227.

Программирование с использованием динамической памяти7.3. Динамические структуры данныхКак упоминалось выше, переменные типа «указатель» обычно использу­ют при реализации динамических переменных, в том числе и динамическихструктур данных.Динамические структуры данных могут быть организованы линейно, ввиде дерева и в виде сети.Линейная динамическая структура представляет собой изменяемую по­следовательность элементов. Частными случаями таких структур являются:• стеки, в которых разрешено добавлять элементы только в конец и уда­лять только последние элементы (рис. 7.8, а);• очереди, в которых добавление элементов осуществляется в конец, аудаление - и з начала (рис. 7.8, б);• деки, которые допускают добавление и удаление элементов и с нача­ла, и с конца (рис. 7.8, в).В древовидной структуре каждый элемент (вершина) ссылается на одинили более элементов следующего уровня (рис.

7.8, г).В сетевой структуре никаких ограничений на связи элементов не на­кладывается (рис. 7.8, д).Линейные динамические структуры, такие, как стеки, очереди и деки,при известном максимальном количестве элементов в них можно реализо­вать в виде динамических или статических одномерных массивов. В против-"lJ^"зХ4^1 М^г ^ 3^4Рис. 7.8. Динамические структуры:а - стек; б - очередь; в - дек; г - древовидная; д - сетевая223Часть I.

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

7.9, а)\• кольцевые односвязные списки - единственное адресное поле содер­жит адрес следующего элемента, а последний элемент ссылается на первый(рис. 7.9, б);" ^ХЭНИЕВНИШ]^гжд^дш^гтп^I3HIIB*C^тк.Рис. 7.9. Списки:а- линейный односвязный; 5-линейный односвязный кольцевой;в - линейный двусвязный; г - двусвязный кольцевой; д - п-связный2247. Программирование с использованием динамической памяти• линейные двусвязные списки - каждый элемент содержит адреса пре­дыдущего и последующих элементов, соответственно^ первый элемент в ка­честве адреса предыдущего, а последний - в качестве адреса следующегоэлемента содержат nil (рис. 7.9, в);• кольцевые двусвязные списки - каждый элемент содержит адреса пре­дыдущего и последующих элементов, причем первый элемент в качествепредьщущего содержит адрес последнего элемента, а последний элемент вкачестве следующего - адрес первого элемента (рис.

Характеристики

Список файлов книги