78216

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

Лекция

Информатика, кибернетика и программирование

Стандартные процедуры размещения и освобождения динамической памяти. Стандартные функции обработки динамической памяти. Работа с динамическими массивами. Динамические структуры данных и их организация с помощью указателей Цель: изучить принципы организации памяти дать понятие указателю сформировать знания о применяемых процедурах и функциях. Эти области памяти для переменных из раздела VR данного блока существуют до конца работы блока даже если эти переменные уже не нужны.

Русский

2015-02-07

95.5 KB

3 чел.

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

Оглавление

[1] Оглавление

[2] Динамическая память

[2.1] Указатель

[2.2] Стандартные процедуры размещения и освобождения динамической памяти

[2.3] Стандартные функции обработки динамической памяти

[2.4] Примеры и задачи

[2.5] Работа с динамическими массивами

[3] Контрольные вопросы:

Комбинированный урок №19

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

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

Динамическая память

В предшествующих разделах использовались переменные, память под которые выделялась статически, то есть на стадии компиляции. Эти области памяти (для переменных из раздела VAR данного блока) существуют до конца работы блока, даже если эти переменные уже не нужны. При этом память нередко используется неэффективно, достаточно вспомнить «настройку» массива на фактическое количество элементов, а также, если, например, объявлено несколько массивов большого объема статической памяти, а в каждый конкретный момент используются не все. Исправить положение можно, применив специальный механизм распределения памяти. Турбо Паскаль предоставляет возможность выделять и освобождать память в процессе выполнения программы, динамически.

Можно отметить следующие достоинства динамической памяти:

- экономичность и эффективность ее использования;

- возможность динамического изменения числа элементов в связанных структурах, например, списках (в статической памяти число элементов фиксировано для каждой компиляции);

- статические переменные существуют только в течение жизни блока, в котором они объявлены, а динамические - и после выхода из блока до окончания программы. Переменная, размещаемая динамически, не объявляется в разделе VAR и не имеет имени в программе («невидимка»). Компилятор не планирует выделение места в памяти под такие переменные.

Указатель

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

Формат описания типа «указатель» следующий:

TYPE <идентификатор указателя>=^<тип>;

Примеры объявления типов «указатель» и переменных типа «указатель».

TYPE { правильные объявления типов}

P1=^WORD; {p1 - идентификатор типа «указатель» на данные типа WORD.}

P2=^CHAR; {p2 - идентификатор типа «указатель» на данные типа CHAR}

P4=ARRAY[1..10] OF ^REAL; {p4 - идентификатор типа «указатель» на массив указателей, ссылающихся на данные типа REAL}

{ неправильные объявления типов}

P5=^ARRAY[1..10] OF REAL;

P6=^STRING[25];

P7=^RECORD

FIELD1 : STRING [15];

FIELD2 : REAL;

END;

В формате объявления типа «указатель» должен быть указан идентификатор типа, поэтому стандартные идентификаторы (INTEGER, REAL и т.д.) можно указывать непосредственно в описаниях типа «указатель». Ошибки в описаниях типов P5, P6 и P7 будут отмечены компилятором из-за того, что, в таких случаях надо прежде описать идентификатор типа, а затем использовать его в других описаниях.

Следующие описания будут правильными:

TYPE MAS = ARRAY[1..10] OF REAL;

ST = STRING[25];

REC = RECORD

FIELD1 : STRING [15];

FIELD2 : REAL;

END;

VAR

P5 : ^MAS;

P6 : ^ST;

P7 : ^REC;

Указатель может находиться в одном из трех состояний, а именно:

1) еще не инициализирован;

2) содержит адрес размещения;

3) содержит значение предопределенной константы NIL; такой указатель называется пустым, то есть не указывает ни на какую переменную. Указатель со значением NIL содержит 0 в каждом из четырех байтов. Указатели можно сравнивать с другими указателями ( =, <> ), присваивать им адрес или значение другого указателя, передавать как параметр. Указатель нельзя отпечатать или вывести на экран.

Обращение к выделенной динамический памяти кодируется следующим образом:

<идентификатор указателя>^.

Рассмотрим пример обращения к переменным, размещенным в динамической памяти:

TYPE SYM=^CHAR;

ZAP=RECORD

FIELD1, FIELD2: REAL;

END;

M=ARRAY[0..9] OF WORD;

VAR CH : SYM;

REC : ^ZAP;

MAS : ^M;

Begin

CH^:='*'; {обращение к динамической переменной типа CHAR, запись в эту область символа звездочка}

READLN (REC^.FIELD1); {обращение к полю FIELD1 динамической записи, ввод в него данных с клавиатуры}

WRITELN (MAS[5]^); {обращение к элементу MAS[5] динамического массива, вывод на экран значения указанного элемента}

End.

Фактически можно говорить, что CH^, REC^.FIELD1 и MAS[5]^ исполняют роль имён динамических объектов в программе, адреса которых хранятся в указателях СH, REC и MAS соответственно. Следует отметить, что обращение к переменным типа POINTER (указателям, которые не указывают ни на какой определенный тип и совместимы со всеми другими типами указателей) приводит к ошибке.

Стандартные процедуры размещения и освобождения динамической памяти

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

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

1. С помощью стандартной процедуры  New (P); где Р - переменная типа «типизированный указатель».

Эта процедура создает новую динамическую переменную (выделяет под нее участок памяти) и устанавливает на нее указатель P P записывается адрес выделенного участка памяти). Размер и структура выделяемого участка памяти задается размером памяти для того типа данных, с которым связан указатель P. Доступ к значению созданной переменной можно получить с помощью P^.

2. С помощью стандартной процедуры GetMem (P,size);  где P - переменная типа «указатель» требуемого типа; size - целочисленное выражение размера запрашиваемой памяти в байтах.

Эта процедура создает новую динамическую переменную требуемого размера и свойства, а также помещает адрес этой созданной переменной в переменную Р типа «указатель». Доступ к значению созданной переменной можно получить с помощью P^.

Например:

TYPE REC =RECORD

FIELD1:STRING[30];

FIELD2:INTEGER;

END;

PTR_REC = ^ REC;

VAR P : PTR_REC;

BEGIN

GETMEM(Р,SIZEOF(REC)); {Выделение памяти, адрес выделенного участка фиксируется в Р; размер этой памяти в байтах определяет и возвращает стандартная функция SizeOf, примененная к описанному типу данных; однако, зная размеры внутреннего представления используемых полей, можно было бы подсчитать размер памяти «вручную» и записать в виде константы вместо SizeOf(Rec)}

...

{использование памяти}

...

FREEMEM(P, SIZEOF(REC)); {освобождение уже ненужной памяти}

...

Динамическая память может быть освобождена четырьмя способами.

1. Автоматически по завершении всей программы.

2. С помощью стандартной процедуры  Dispose (P); где P - переменная типа «указатель» (типизированный).

В результате работы процедуры DISPOSE(P) участок памяти, связанный с указателем P, помечается как свободный для возможных дальнейших размещений. При этом физической чистки указателя P и связанной с ним памяти не происходит, поэтому, даже удалив этот экземпляр записи, можно все же получить значения ее полей, однако использовать это обстоятельство не рекомендуется. Ввиду различия в способах реализации процедуру DISPOSE не следует использовать совместно с процедурами MARK и RELEASE.

3. С помощью стандартной процедуры FreeMem (P, size); где P - переменная типа «указатель», size - целочисленное выражение размера памяти в байтах для освобождения.

Эта процедура помечает память размером, равным значению выражения SIZE, связанную с указателем P, как свободную (см. пример для GETMEM).

4. С помощью стандартных процедур  Mark (P);   Release (P); где P - переменная типа «указатель»;

MARK - запоминает состояние динамической области в переменной-указателе Р;

RELEASE - освобождает всю динамическую память, которая выделена процедурами NEW или GETMEM после запоминания текущего значения указателя Р процедурой MARK.

Обращения к MARK и RELEASE нельзя чередовать с обращениями к DISPOSE и FRЕЕМЕM ввиду различий в их реализации.

Например:

VAR P:POINTER;

P1, P2, P3:^INTEGER;

BEGIN

NEW(P1); P1^:=10;

MARK(P); {пометка динамической области}

NEW(P2); P2^:=25;

NEW(P3); P3^:=P2^+P1^;

WRITELN (P3^);

RELEASE(P); {память, связанная с P2^ и P3^, освобождена, а P1^ может использоваться}

END.

Стандартные функции обработки динамической памяти

В процессе выполнения программы может возникнуть необходимость наблюдения за состоянием динамической области. Цель такого наблюдения - оценка возможности очередного выделения динамической области требуемого размера. Для этих целей Турбо Паскаль предоставляет две функции (без параметров).

MaxAvail; - эта функция возвращает размер в байтах наибольшего свободного в данный момент участка в динамической области. По этому размеру можно судить о том, какую наибольшую динамическую память можно выделить. Тип возвращаемого значения - longint.

TYPE ZAP=RECORD

FIELD1: STRING [20];

FIELD2: REAL;

END;

VAR P: POINTER;

BEGIN

...

IF MAXAVAIL <SIZEOF(ZAP) THEN

WRITELN ('HE ХВАТАЕТ ПАМЯТИ!')

ELSE

GETMEM(Р, SIZEOF(ZAP));

...

MemAvail; - эта функция возвращает общее число свободных байтов динамической памяти, то есть суммируются размеры всех свободных участков и объем свободной динамической области. Тип возвращаемого значения - longint.

...

WRITELN('Доступно', MEMAVAIL, ' байтов');

WRITELN('Наибольший свободный участок=', MAXAVAIL, 'байтов');

...

Это решение основано на следующем обстоятельстве. Динамическая область размещается в специально выделяемой области, которая носит название «куча» (HEAP). Куча занимает всю или часть свободной памяти, оставшейся после загрузки программы. Размер кучи можно установить с помощью директивы компилятора М: {$М <стек>, <минимум кучи>, <максимум кучи>}, где <стек> - определяет размер сегмента стека в байтах. По умолчанию размер стека 16 384 байт, а максимальный размер стека 65 538 байт. <минимум кучи> - определяет минимально требуемый размер кучи в байтах; по умолчанию минимальный размер 0 байт. <максимум кучи> - определяет максимальное значение памяти в байтах для размещения кучи; по умолчанию оно равно 655 360 байт, что в большинстве случаев выделяет в куче всю доступную память; это значение должно быть не меньше наименьшего размера кучи.

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

{$М 16384,0,655360}

{$M $4000, $0, $A000}

Если указанный минимальный объем памяти недоступен, то программа выполняться не будет.

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

Примеры и задачи

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

TYPE ST1=STRING[7];

ST2=STRING[3];

VAR I,I1,I2,I3,I4:^INTEGER;

R^:REAL;

S1:^ST1;

S2:^ST2;

BEGIN

NEW(I);

I1^:=1;

NEW(I2);

I2^:=2;

NEW(I3);

I3^=3;

NEW(I4);

I4^:=4; (*1*)

DISРОSЕ (I2);{освобождается второе размещение}

NEW (I); {память нужного размера (в данном случае два байта) выделяется на первом свободном месте от начала кучи, достаточном для размещения данной переменной; в этом примере - это участок, который занимала переменная I2^, ее адрес остался в указателе I2}

I^:=5; (*2*)

DISPOSE(I3); {освобождается третье размещение}

NEW(R); {память под переменную типа REAL выделяется в вершине кучи, так как размер дырки с адресом I3 (2 байта) мал для размещения переменной типа REAL, для которой необходимо 6 байт }

R^:=6; (*3*)

WRITELN (R^); { ВЫВОД: 6.0000000000E+00}

END.

В следующем примере используется массив указателей.

USES CRT;

VAR R: ARRAY [1..10] OF ^REAL;

I :   1..10;

BEGIN

RANDOMIZE; {инициализация генератора случайных чисел}

FOR I:=1 TO 10 DO

BEGIN

NEW(R[I]);

R[I]^:=RANDOM; {генерация случайных вещ.чисел в диапазоне 0 <= r[i]^ < 1}

WRITELN(R[I]^);{Вывод случайных чисел в экспоненциальной форме}

END;

END.

Работа с динамическими массивами

При работе с массивами практически всегда возникает задача настройки программы на фактическое количество элементов массива. В зависимости от применяемых средств решение этой задачи бывает различным.

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

PROGRAM FIRST;

CONST N : INTEGER = 10; { либо N = 10; }

VAR A : ARRAY [1..N] OF REAL;

I : INTEGER;

BEGIN

FOR I := 1 TO N DO

BEGIN

WRITELN (' Введите ', I , ' -ый элемент массива ');

READLN (A[I])

END;  { И далее все циклы работы с массивом используют N}

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

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

PROGRAM SECOND;

VAR A : ARRAY [1..25] OF REAL;

I, NF : INTEGER;

BEGIN

WRITELN ('Введите фактическое число элементов массива <= 25 ');

READLN (NF);

FOR I:= 1 TO NF DO

BEGIN

WRITELN ('Введите ', I , ' -ый элемент массива ');

READLN (A[I])

END; { И далее все циклы работы с массивом используют NF}

Этот вариант более гибок и технологичен по сравнению с предыдущим, так как не требуется постоянная перекомпиляция программы, но очень нерационально расходуется память, ведь ее объем для массива всегда выделяется по указанному максимуму. Используется же только часть ее.

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

PROGRAM DYNAM_MEMORY;

TYPE MAS = ARRAY [1..2] OF < требуемый_тип_элемента >;

MS = ^MAS;

VAR A : MS;

I, NF : INTEGER;

BEGIN

WRITELN ('Введите фактическое число элементов массива');

READLN (NF);

GETMEM (A, SIZEOF( < требуемый_тип_элемента>)*NF);

FOR I := 1 TO NF DO

BEGIN

WRITELN('Введите ', I , ' -ый элемент массива ');

READLN(A^[I])

END; {И далее все циклы работы с массивом используют NF}

. . . . .

FREEMEM (A, NF*SIZEOF (< требуемый_тип_элемента>));

END.

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

USES CRT;

TYPE  T1=ARRAY[1..1] OF INTEGER;

VAR   A:^T1;

N,M,I,J,K,P:INTEGER;

MAX:INTEGER;

BEGIN

CLRSCR;

WRITE('N='); READLN (N);

WRITE('M='); READLN (M);

GETMEM (A,SIZEOF(INTEGER)*N*M);

FOR I:=1 TO N*M DO READ(A^[I]);

MAX:=A^[1]; K:=1; P:=1;

FOR I:=1 TO N DO

FOR J:=1 TO M DO

IF A^[(I-1)*M+J] > MAX THEN

BEGIN

MAX:=A^[(I-1)*M+J];

K:=I; P:=J

END;

WRITE('строка=',K:2,' столбец=',P:2);

FREEMEM(A,2*N*M);

READKEY;

END.

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

местами.

USES CRT;

TYPE VK=^T1;

T1=ARRAY[1..1] OF INTEGER;

MT=^T2;

T2=ARRAY[1..1] OF VK;

VAR  A:MT;

M,N,I,J,K,L:INTEGER;

MAX,MIN:INTEGER;

R:POINTER;

BEGIN

CLRSCR;

READLN (N,M);

GETMEM(A,SIZEOF (POINTER)*M); {выделение памяти под указатели столбцов матрицы}

FOR J:=1 TO M DO

GETMEM (A^[J],SIZEOF(INTEGER)*N); {выделение памяти под элементы столбцов}

FOR I:=1 TO N DO

FOR J:=1 TO M DO

READ(A^[J]^[I]);

FOR I:=1 TO N DO

BEGIN

FOR J:=1 TO M DO

WRITE (A^[J]^[I]:4);

WRITELN

END;

MAX:=A^[1]^[1]; K:=1; MIN:=MAX; L:=1;

FOR J:=1 TO M DO

FOR I:=1 TO N DO

IF A^[J]^[I]<MIN THEN

Begin MIN:=A^[J]^[I]; L:=J; end

ELSE

IF A^[J]^[I]>MAX THEN

BEGIN MAX:=A^[J]^[I]; K:=J; END;

{для обмена столбцов достаточно поменять указатели на столбцы}

IF K<>L THEN R:=A^[K]; A^[K]:=A^[L]; A^[L]:=R

FOR I:=1 TO N DO

BEGIN

FOR J:=1 TO M DO

WRITE(A^[J]^[I]:3,' ');

WRITELN

END;

FOR I:=1 TO M DO

FREEMEM (A^[I],N*SIZEOF(INTEGER));

FREEMEM (A,M*SIZEOF(POINTER))

END.

Контрольные вопросы:

  1.  Назначение динамической памяти. В чем состоит отличие динамической памяти от статической?
  2.  Дайте определение понятию «указатель». Формат описания. Примеры. Какие состояния может принимать указатель?
  3.  Как выполняется обращение к выделенной динамической памяти? Примеры.
  4.  Процедуры и функции для работы с динамическими данными. Примеры.
  5.  Где размещается динамическая область? Как устанавливается размер «кучи»? Единица измерения размера «кучи».
  6.  Работа с динамическими массивами. Дать описание всем вариантам.


 

А также другие работы, которые могут Вас заинтересовать

23713. Задачи для самопроверки (подготовка к контрольной работе) 99 KB
  – Какие свойства чисел используются при упрощении буквенных выражений Переместительное сочетательное распределительное. На доске: – Какие методы работы с моделями мы знаем Нахождение значений выражений решение уравнений используя распределительное свойство метод проб и ошибок метод полного перебора решение уравнений методом весов. 1 16x – 7x – 2x = x16 – 7 – 2 = 7x; Используем распределительное свойство умножения относительно вычитания ac – bc = ca – b 2 x : 5 Количество варенья в одной...
23714. Запись, чтение и составление выражений 40.5 KB
  Цели урока: формировать представление о математических выражениях как о словах математического языка повторить понятия числового и буквенного выражения учить делать перевод текстов с русского языка на математический и наоборот повторить и закрепить приёмы устных вычислений нумерацию натуральных чисел смысл сложения и вычитания взаимосвязь между ними сложение и вычитание многозначных чисел решение задач понятие периметра многоугольника развивать внимание логическое мышление способности к обобщению исследовательские умения...
23715. Запись, чтение и составление выражений 58 KB
  Запишите выражения для ответа на вопрос задачи: а Площадь прямоугольника с см2 а ширина – 7см. – Почему в классе разные ответы а часть ребят совсем не справилась с заданием Что необходимо знать что бы с заданием справились все Для решения первой задачи надо знать как найти ширину прямоугольника по его площади и длине а для решения второй задачи формулу площади прямоугольника. – Поднимите руку те кто не знает формулу нахождения площади прямоугольника К решению этой задачи учащиеся были подготовлены на этапе актуализации по этому...
23716. ХУДОЖНЄ ВИХОВАННЯ В УМОВАХ НОВОЇ ЕСТЕТИЧНОЇ СОЦІАЛЬНОЇ РЕАЛЬНОСТІ В УКРАЇНІ 71 KB
  На основі аналізу феномена „масова культура” з’ясувати проблему його впливу на поведінку людей та необхідність прищеплення естетичного смаку особистості...
23717. Значение выражения, урок рефлексии 59 KB
  Повторить и закрепить понятия буквенного и числового выражения взаимосвязь между арифметическими действиями решение уравнений на сложение и вычитание алгоритмы сложения и вычитания многозначных чисел. Здравствуйте ребята Чему мы учились на прошлых уроках Составлять читать и записывать математические выражения. В каком виде мы записывали ответ В виде числового или буквенного выражения.
23718. Значение выражения 66 KB
  – Какие выражения ещё мы учились составлять и записывать Буквенные выражения. – Сегодня на уроке мы продолжим работать с буквенными выражениями. – Как вы думаете что можно делать с буквенными выражениями Находить их значения.
23719. Метод весов 52.5 KB
  – Решите уравнение: а методом проб и ошибок; б методом перебора: 3. Решите уравнение: 3а 33 = 8а 8 3. – Чем отличается это уравнение от уравнений которые решали раньше В этом уравнении переменная стоит в обеих частях уравнения. – Как же быть Надо найти способ который позволит решить такое уравнение.
23720. Метод перебора 76.5 KB
  – Установите закономерность и продолжите ряд на три числа. – Что вы можете сказать о множителях в произведении Они являются делителями числа 252 252 делится на x и на y. x – 1y 6 = 252 – Что вы можете сказать о втором уравнении Множители во втором уравнении являются делителями числа 252. – Что вы можете сказать о корнях первого и второго уравнения Одни и те же числа.
23721. Метод весов 45.5 KB
  – Что интересного вы можете рассказать о полученном ряде чисел – Назовите самое большое число из данного ряда. 109 – Назовите самое маленькое число из этого ряда. – Замените число 25 суммой разрядных слагаемых разными способами. Вспомните как была построена математическая модель 10х y = xy 52 для задачи 5: Задумано двузначное число которое на 52 больше суммы своих цифр.