Презентация, доклад на тему Динамические структуры данных

размер заранее известен (задается при написании программы)
память выделяется при объявлении
размер нельзя увеличить во время работы программы

var x, y: integer;
z: real;
A: array[1..10] of real;
str: string;

время работы программы
нет имени?

Проблема:
как обращаться к данным, если нет имени?
Решение:
использовать адрес в памяти
Следующая проблема:
в каких переменных могут храниться адреса?
как работать с адресами?

(или блока памяти).
Объявление:



Как записать адрес:

var pC: ^char; // адрес символа
pI: ^integer; // адрес целой переменной
pR: ^real; // адрес вещ. переменной

var m: integer; // целая переменная
pI: ^integer; // указатель
A: array[1..2] of integer; // массив
...
pI:= @ m; // адрес переменной m
pI:= @ A[1]; // адрес элемента массива A[1]
pI:= nil; // нулевой адрес

@

^

nil

указатель

адрес ячейки

^integer;
begin
m := 4;
pI := @m;
writeln('Адрес m = ', pI); // вывод адреса
writeln('m = ', pI^); // вывод значения
n := 4*(7 - pI^); // n = 4*(7 - 4) = 12
pI^ := 4*(n - m); // m = 4*(12 – 4) = 32
end.

^

«вытащить» значение по адресу

integer;
pI: ^integer;
begin
for i:=1 to 4 do A[i] := i;
pI := @A[1]; // адрес A[1]
while ( pI^ <= 4 ) // while( A[i] <= 4 )
do begin
pI^ := pI^ * 2; // A[i] := A[i]*2;
pI := pI + 1; // к следующему элементу
end;
end.

переместиться к следующему элементу = изменить адрес на sizeof(integer)

хранить адрес другой переменной;
при объявлении указателя надо указать тип переменных, на которых он будет указывать, а перед типом поставить знак ^ ;
знак @ перед именем переменной обозначает ее адрес;
запись p^ обозначает значение ячейки, на которую указывает указатель p;
nil – это нулевой указатель, он никуда не указывает
при изменении значения указателя на n он в самом деле сдвигается к n-ому следующему числу данного типа (для указателей на целые числа – на n*sizeof(integer) байт).

Отсортировать массив и вывести на экран.
Проблема:
размер массива заранее неизвестен.
Пути решения:
выделить память «с запасом»;
выделять память тогда, когда размер стал известен.
Алгоритм:
ввести размер массива;
выделить память ;
ввести элементы массива;
отсортировать и вывести на экран;
удалить массив.

выделить память

удалить массив

i, N: integer;
begin
writeln('Размер массива>');
readln(N);
GetMem(pointer(A), N*sizeof(integer));
for i := 1 to N do
readln(A[i]);
... { сортировка }
for i := 1 to N do
writeln(A[i]);
FreeMem(pointer(A));
end.

выделить память

освободить память

работаем так же, как с обычным массивом!

какой-то массив целых чисел

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

выделена, а массив используется.
Что делать: так не делать.
Выход за границы массива:
обращение к элементу массива с неправильным номером, при
записи портятся данные в «чужой» памяти.
Что делать: если позволяет транслятор, включать проверку выхода за границы массива.
Указатель удаляется второй раз:
структура памяти нарушена, может быть все, что угодно.
Что делать : в удаленный указатель лучше записывать nil, ошибка выявится быстрее.
Утечка памяти:
ненужная память не освобождается.
Что делать : убирайте «мусор» (в среде .NET есть сборщик мусора!)

writeln('Размер массива>');
readln(N);
SetLength ( A, N );
for i := 0 to N-1 do
readln(A[i]);
... { сортировка }
for i := 0 to N-1 do
writeln(A[i]);
SetLength( A, 0 );
end.

выделить память

освободить память

какой-то массив целых чисел

нумерация с НУЛЯ!

выделяется:
var A: array of integer;
для выделения памяти используют процедуру SetLength (установить длину)
SetLength ( массив, размер );
номера элементов начинаются с НУЛЯ!
для освобождения блока памяти нужно установить нулевую длину через процедуру SetLength:
SetLength ( массив, 0 );

в памяти во время работы программы.
Проблема:
размеры матрицы заранее неизвестны
Решение:

var A: array of array of integer;
N, M: integer;
begin
writeln('Число строк и столбцов>');
readln(N, M);
SetLength ( A, N, M );
... // работаем, как с обычной матрицей
SetLength( A, 0, 0 );
end.

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

Свойства:
автор (строка)
название (строка)
год издания (целое число)
количество страниц (целое число)

Задача: объединить эти данные в единое целое

Размещение в памяти

Book.pages > 200 then // сравнение
writeln(Book.author, '.', Book.title); // вывод

Объявление (выделение памяти):

var Book: record
author: string[40]; // автор, строка
title: string[80]; // название, строка
year: integer; // год издания, целое
pages: integer; // кол-во страниц, целое
end;

название

запись

поля

Обращение к полям:

author: string[40];
title: string[80];
year: integer;
pages: integer;
end;

Books[1] ... Books[10]

...
end;
for i:=1 to N do
if aBooks[i].pages > 200 then
writeln(aBooks[i].author, '.',
aBooks[i].title);

Обращение к полям:

одна запись
aBooks: array[1..N] of TBook; // массив

Объявление типа:

type TBook = record
author: string[40]; // автор, строка
title: string[80]; // название, строка
year: integer; // год издания, целое
pages : integer; // кол-во страниц, целое
end;

Объявление переменных и массивов:

TBook – Type Book («тип книга») – удобно!