Учебное пособие по курсу Программирование на языке высокого уровня для вузов по специальности 230105 Программное обеспечение вычислительной техники и автоматизированных систем
 Скачать 0.64 Mb.
|
|
Пример списочной структуры данных В Турбо Паскале можно обьявлять указатель и не связывать его при этом с каким-либо конкретным типом данных. Для этого служит стандартный тип POINTER, например: var pp : pointer; Указатели такого рода будем называть нетипизированными. Поскольку нетипизированные указатели не связаны с конкретным типом, с их помощью удобно динамически размещать данные, структура и тип которых меняются в ходе работы программы. Значениями указателей являются адреса переменных в памяти, поэтому следовало бы ожидать, что значение одного указателя можно передавать другому. На самом деле это совсем не так. В Турбо Паскале можно передавать значения только между указателями, связанными с одним и тем же типом данных. Если, например, var p1, p2 : ^integer; p3 : ^real; pp : pointer; то присваивание p1 := p2; вполне допустимо, в то время как p1 := p3; запрещено, поскольку p1 и p3 указывают на разные типы данных. Это ограничение, однако, не распространяется на нетипизированные указатели, поэтому мы могли бы записать pp := p3; p1 := pp; и тем самым достичь нужного результата. Все дело в том, что любое ограничение, с одной стороны, вводится для повышения надежности программ, а с другой - уменьшает мощность языка, делает его менее пригодным для каких- то применений. В Турбо 1-ый элемент списка указатель 2-ой элемент списка указатель Последний Элемент Списка NIL … PDF created with pdfFactory Pro trial version www.pdffactory.com 59 Паскале немногочисленные исключения в отншении типов данных придают языку необходимую гибкость, но их использование требует от программиста дополнительных усилий и таким образом свидетельствует о вполне осознанном действии. Выделение и освобождение динамической памяти . Вся динамическая память в Турбо Паскале рассматривается как сплошной массив байтов, который называется кучей. Физически куча располагается в старших адресах сразу за областью памяти, которая занимает тело программы. Начало кучи хранится в стандартной переменной HEAPORG , конец- в переменной HEAPEND. Текущую границу незанятой динамической памяти указывает указатель HEAPPTR. 0 Старшие адреса 640 HeapOrg HeapPtr HeapEnd Память под любую динамически размещаемую переменную выделяется процедурой NEW. Параметром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значение, соответствующее динамическому адресу, начиная с которого можно разместить данные, например: var i, j : ^integer; r : ^real; begin new(i); После выполнения этого фрогмента указатель I приобретает значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличивает свое значение на 2, так как длина внутреннего представления типа INTEGER, с которым связан указатель I, составляет 2 байта (на самом деле это не совсем так: память под любую переменную выделяется порциями, кратными 8 байтам). Оператор new(r); вызовет еще раз смещение указателя HEAPPTR, но теперь уже на 6 байт, потому что Системная область Программа КУЧА Системная область PDF created with pdfFactory Pro trial version www.pdffactory.com 60 такова длина внутреннего представления типа REAL. Аналогичным образом выделяется память и для переменной любого другого типа. После того, как указатель приобрел некоторое значение, т.е. стал указывать на конкретный физический байт памяти, поэтому адресу можно разместить любое значение соответсвующего типа. Для этого сразу за указателем без каких-либо пробелов ставится значок ^, например: i^ := 2; {в область памяти i помещено значение 2} r^ := 2*pi; {в область памяти r помещено значение 6.28} Таким образом, значение, на которое указывает указатель, т.е. собственно данные размещены в куче, обозначается значком ^, который ставится сразу над указателем. Если за указателем нет значка ^, то имеется ввиду адрес, по которому размещены данные. Имеет смысл еще раз задуматься над только что сказанным: значением любого указателя является адрес, а чтобы указать, что речь идет не об адресе, а о тех данных, которые размещены по этому адресу, за указателем ставится ^. Динамически размещенные данные можно использовать в любом месте программы, где это допустимо для констант и переменных соответствующего типа, например: r^ := sqr(r^) + i^ - 17; Разумеется, совершенно недопустим оператор r := sqr(r^) + i^ - 17; так как указателю R нельзя присвоить значение вещественного выражения. Точно так же недопустим оператор r^ := sqr(r); поскольку значением R является адрес, и его (в отличие от того значения, которое размещено по этому адресу) нельзя возводить в квадрат. Ошибочнным будет и такое присваивание: r^ := i; так как вещественным данным, на которые указывает R^, нельзя присвоить значение указателя (адрес). Динамическую память можно не только забирать из кучи, но и возращать обратно. Для этого используется DISPOSE. Например, операторы dispose(r); dispose(i); вернут в кучу 8 байт, которые ранее были выделены указателям I и R (см.выше). Отметим, что процедура DISPOSE (PTR) не изменяет значение указателя PTR, а лишь возращает в кучу память ранее связанную с этим указателем. Однако повторное применение процедуры свободному PDF created with pdfFactory Pro trial version www.pdffactory.com 61 указателю приведет к возникновению ошибки периода исполнения. Освободившийся указатель программист может поместить зарезервированным словом NIL. К указателям можно применять операции отношения, в том числе и сравнение с NIL, например: const p : ^real = NIL; if p = NIL then new(p); dispose(p); p := NIL; Этот фрагмент иллюстрирует предпочтительный способ обьявления указателя в ввиде типизированной константы с одновременным присвоением ему значения NIL (см.гл.7). Следует учесть, что начальное значение указателя (при его обьявление в разделе переменных) может быть произвольным. Использование указателй, которым не присвоено значение процедурой NEW или другим способом, не контролируется системой и мо жет привести к непредсказуемым результатам. Чередование обращений к процедурам NEW и DISPOSE обычно приводит к <<ячеистой>> структуре памяти. Дело в том, что все операции с кучей выполняются под управлением особой программы, которая называется администратором кучи. Она ведет учет всех свободных фрагментов в куче. При очередном обращении к процедуре NEW эта программа отыскивает наименьший свободный фрагмент, в котором еще может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины помечается как занятая часть кучи. Такая возможность состоит в освобождении целого фрагмента кучи. С этой целью перед началом выделения динамической памяти текущее значение указателя HEAPPTR запоминается в переменной- указателя с помощью процедуры MARK. Теперь можно в любой момент освободить фрагмент кучи, начиная от адреса, который запомнила процедура MARK, и до конца динамической памяти. Для этого используется процедура RELEASE. Например: var p,p1,p2,p3,p4,p5 : ^integer; begin PDF created with pdfFactory Pro trial version www.pdffactory.com 62 new(p1); new(p2); mark(p); new(p3); new(p4); new(p5); release(p); В этом примере процедурой MARK(P) в указатель P было помещено текущее значение HEAPPTR, однако память под переменную не резервировалась. Обращение RELEASE(P) освободило динамическую память от помеченного места до конца кучи. P1 ∧ P1 ∧ P1 ∧ P2 ∧ P2 ∧ P2 ∧ Mark (P) P3 ∧ Dispose(P) Release(P) P4 ∧ P4 ∧ P5 ∧ P5 ∧ a b c а - перед освобождением; b - после DISPOSE(P3); c - после RELEASE(P) Следует учесть,что вызов RELEASE уничтожает список свободных фрагментов в куче,созданных до этого процедурой DISPOSE,поэтому совместное использование обоих механизмов освобождения памяти в рамках одной программы не рекомендуется. Как уже отмечалось,параметром процедуры NEW может быть только типизированный указатель. для работы с нетипизированными указателями используются процедуры: GETMEM(P,SIZE)-резервирование памяти; FREEMEM(P,SIZE)-освобождение памяти; Здесь P-нетипизированный указатель; SIZE-размер в байтах требуемой или освобождаемой части кучи. За одно обращение к куче процедурой GETMEM можно зарезервировать до 65521 байта динамической памяти. Использование процедур GETMEM-FREEMEM,как и вообще вся работа с динамической памятью,требует особой осторожности и тщательного соблюдения простого правила: освобождать нужно ровно столько памяти,сколько ее было зарезервировано, и именно с того адреса, с которого она была зарезервирована. Не трудно обнаружить,что наличие нетипизированных указателей в Турбо Паскале (в стандартном Паскале их нет) открывает широкие PDF created with pdfFactory Pro trial version www.pdffactory.com 63 возможности неявного преобразования типов. К сожалению,трудно обнаруживаемые ошибки в программе, связанные с некорректно используемыми обращениями к процедурам NEW и DISPOSE, также могут привести к нежелательному преобразованию типов. В самом деле,пусть имеется прог рамма: i,j: ^integer; r : ^real; BEGIN {i :=HeapOrd; HeapPtr := HeapOrd + 2} j :=i; {j := HeapOrd} j^ :=2; dispose(i); {HeapPtr := HeapOrd} new(r); {r := HeapOrd; HeapPtr := HeapOrd + 6} r^ := pi; writeln(j^) { ?? } END. Что будет выведено на экран дисплея? Чтобы ответить на этот вопрос, проследим за значениями указателя HEAPPTR. Перед исполнением программы этот указатель имел значение адреса начала кучи HEAPORG, которое и было передано указателю I, а затем и J. После выполнения DISPOSE(I) указатель кучи вновь приобрел значение HEAPORG, этот адрес передан указателю R в процедуре NEW(R). После того, как по адресу R разместилось вещественное число PI=3.14159,первые 2 байта кучи оказались заняты под часть внутрен него представления этого числа. В то же время J все еще сохраняет адрес HEAPORG, поэтому оператор WRITELN (J^) ,будет рассматривать 2 байта числа PI как внутреннее представления целого чи числа (ведь J-это указатель на тип INTEGER) и выведет 8578. Использование указателей . Подведем некоторые итоги. Итак, динамическая память составляет 200...300 Кбайт или больше, ее начало хранится в переменной HEAPORG, а конец соответствует адресу переменной HEAPEND. Текущий адрес свободного участка динамической памяти хранится в указателе HEAPPTR. Посмотрим, как можно использовать динамическую память для размещения крупных массивов данных. Пусть, например, требуется обеспечить доступ к элементам прямоугольной матрицы 100х200 типа EXTENDED. Для размещения такого массива требуется память 200000 байт (100*200*10). PDF created with pdfFactory Pro trial version www.pdffactory.com 64 Казалось бы, эту проблему можно решить следующим образом: var i,j : integer; PtrArr : array [1..100,1..200] of ^real; for i := 1 to 100 do for j := 1 to 200 do new(PtrArr[i,j]); Теперь к любому элементу вновь созданного динамического массива можно обратиться по адресу, например: PtrArr[1,1]^ := 0; if PtrArr[i,j*2]^ > 1 then ...... Вспомним, однако, что длина внутреннего представления указателя составляет 4 байта, поэтому для размещения массива PTRARR потребуется 100*200*4 =80000 байт, что превышает размер сегмента данных (65536 байт), доступный, как уже отмечалось, программе для статического размещения данных. Выходом из положения могла бы послужить адресная арифметика,т.е. арифметика над указателями, потому что в этом случае можно было бы отказаться от создания массива указателей PTRARR и вычислять адрес любого элемента прямоугольной матрицы непосредственно перед обращением к нему. Однако в Турбо Паскале над указателями не определены никакие операции, кроме операций присвоения и отношения. Тем не менее, решить указанную задачу все-таки можно.Как мы уже знаем, любой указатель состоит из двух слов типа WORD, в которых хранятся сегмент и смещение. В Турбо Паскале определены две встроенные функции типа WORD,позволяющие получить содержимое этих слов: SEG(X)-возвращает сегментную часть адреса; OFS(X)-возвращает смещение. Аргументом X при обращении к этим функциям может служить любая переменная, в том числе и та, на которую указывает указатель. Например, если мы имеем var p : ^real; new(p); p^ := 3.14; PDF created with pdfFactory Pro trial version www.pdffactory.com 65 то функция SEG(P) вернет сегментную часть адреса, по которому располагается 4-байтный указатель P, в то время как SEG(P^)-сегмент 6-байтного участка кучи, в котором хранится число 3.14. С другой стороны, с помощью встроенной функции PTR(SEG,OFS:WORD):POINTER можно создать значение указателя, совместимое с указателями любого типа.Таким образом возможна такая последовательность действий.Вначале процедурой GETMEM из кучи забираются несколько фрагментов подходящей длины(напомню, что за одно обращение к процедуре можно зарезервировать не более 65521 байт динамической памяти). Для рассматриваемого примера удобно резервировать фрагменты такой длины, чтобы в них могли, например, разместиться строки прямоугольной матрицы, т.е. 200*10=2000 байт. Начало каждого фрагмента, т.е. фактически начало размещения в памяти каждой строки, запоминается в массиве PTRSTR, состоящем из 100 указателей. Теперь для доступа к любому элементу строки нужно вычислить смещение этого элемента от начала строки и сформировать соответствующий указатель: var i,j : integer; PtrStr : array [1..100] of pointer; pr : ^real; const SizeOfReal = 6; begin for i := 1 to 100 do GetMem(PtrStr[i],SizeOfReal*200); { обращение к элементу матрицы [i,j] } pr := ptr(seg(PtrStr[i]^), ofs(PtrStr[i]^+(j - 1)*SizeOfReal); if pr^ > 1 then ...... Поскольку оператор вычисления адреса PR:=PTR... будет, судя по всему, использоваться в программе неоднократно, полезно ввести вспомогательную функцию GETR, возвращающую значение элемента матрицы, и процедуру PUTR, устанавливающую новое значение элемента. Каждая из них, в свою очередь, обращается к функции ADDRR для вычисления адреса. Далее приводится программа, создающая в памяти матрицу из NxM случайных чисел и вычисляющая их среднее значение. const PDF created with pdfFactory Pro trial version www.pdffactory.com 66 SizeOfReal = 6; {Длина переменной типа REAL} N = 100; {Количество столбцов} M = 200; {Количество строк} var i,j : integer; PtrStr : array [1..N] of pointer; s : real; type RealPoint = ^real; {-------------} FUNCTION AddrR(i,j : word) : RealPoint; BEGIN AddrR := ptr(seg(PtrStr[i]^), ofs(PtrStr[i]^)+(j - 1)*SizeOfReal) END {AddrR}; {-------------} FUNCTION GetR(i,j : integer) : real; BEGIN GetR := AddrR(i,j)^ END {GetR}; {-------------} PROCEDURE PutR(i,j : integer; x : real); BEGIN AddrR(i,j)^ := x END{PutR}; {-------------} BEGIN {Main} for i := 1 to N do begin GetMem(PtrStr[i], M*SizeOfReal); for j := 1 to M do PutR(i , j , Random) end; s := 0; for i := 1 to N do for j := 1 to M do s := s + GetR(i,j); writeln(s / (N * M) :12:10) END {Main}. В рассмотренном примере предполагается, что каждая строка размещается в куче, начиная с границы параграфа, и смещение для каждого указателя PTRSTR равно нулю. В действительности при PDF created with pdfFactory Pro trial version www.pdffactory.com 67 последовательных обращениях к процедуре GETMEM начало очередного фрагмента следует сразу за концом предыдущего и может не попасть на границу сегмента. В результате, при размещении фрагментов максимальной длины (65521 байт) может возникнуть переполнение при вычислении смещения последнего байта. Процедуры и функции для работы с динамической памятью . Ниже приводится описание как уже рассмотренных процедур и и функций, так и некоторых других, которые могут оказаться полезными при обращении к динамической памяти. Функция ADDR. Возвращает резудьтат типа POINTER, в котором содержится адрес аргумента.Обращение: ADDR(X) Здесь Х - любой об'ект программы (имя любой переменной, процедуры, функции). Возвращаемый адрес совместим с указателем любого типа. Отметим, что аналогичный результат возвращает операция @. Функция CSEG. Возвращает значение, хранящееся в регистре CS микропроцессора (В начале работы программы в регистре CS содержится сегмент начала кода программы). Обращение: CSEG Результат возвращается в слове типа WORD. Процедура DISPOSE. Возвращает в кучу фрагмент динамической па- мяти, который ранее был зарезервирован за типизированным указателем. Обращение: DISPOSE(TP) Здесь TP - типизированный указатель. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения. При освобождении динамических об'ектов можно указывать вторым параметром обращения к DISPOSE имя деструктора. PDF created with pdfFactory Pro trial version www.pdffactory.com 68 Функция DSEG. Возвращает значение, хранящееся в регистре DS микропроцессора (в начале работы программы в регистре DS содержится сегмент начала данных программы). Обращение: DSEG Результат возвращается в слове типа WORD. Процедура FREEMEM. Возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за нетипизированным указателем. Обращение: FREEMEM(P,SIZE) Здесь P - нетипизированный указатель; SIZE - длина в байтах освобождаемого фрагмента; При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения. Процедура GETMEM. Резервирует за нетипизированным указателем фрагмент динамической памяти требуемого размера. Обращение: GETMEM(P,SIZE) За одно обращение к процедуре можно зарезервировать не более 65521 байта динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована,последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего. Процедура MARK. Запоминает текущее значение указателя кучи HEAPPTR. Обращение: MARK(PTR) Здесь PTR - указатель любого типа, в котором будет возвращено текущее значение HEAPPTR. Используется совместно с процедурой RELEASE для освобожления части кучи. Функция MAXAVAIL |