Указатели Динамические структуры данных

2 Статические данные переменная (массив) имеет имя, по которому к ней можно обращаться размер заранее известен (задается при написании программы) память выделяется при объявлении размер нельзя увеличить во время работы программы var x, y: integer; z: real; A: array[1..10] of real; str: string; var x, y: integer; z: real; A: array[1..10] of real; str: string;

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

4 Указатели Указатель – это переменная, в которую можно записывать адрес другой переменной (или блока памяти). Объявление: Как записать адрес: var pC: ^char; // адрес символа pI: ^integer; // адрес целой переменной pR: ^real; // адрес вещ. переменной var pC: ^char; // адрес символа pI: ^integer; // адрес целой переменной pR: ^real; // адрес вещ. переменной var m: integer; // целая переменная pI: ^integer; // указатель A: array[1..2] of integer; // массив... m; // адрес переменной m A[1]; // адрес элемента массива A[1] pI:= nil; // нулевой адрес var m: integer; // целая переменная pI: ^integer; // указатель A: array[1..2] of integer; // массив... m; // адрес переменной m A[1]; // адрес элемента массива A[1] pI:= nil; // нулевой ^ nil указатель адрес ячейки

5 Обращение к данным через указатель... var m, n: integer; pI: ^integer; begin m := 4; pI 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.... var m, n: integer; pI: ^integer; begin m := 4; pI 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. ^ «вытащить» значение по адресу

6 Обращение к данным (массивы) var i: integer; A: array[1..4] of integer; pI: ^integer;... begin for i:=1 to 4 do A[i] := i; pI // адрес A[1] while ( pI^

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

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

9 Где нужны динамические массивы? Задача. Ввести размер массива, затем – элементы массива. Отсортировать массив и вывести на экран. Проблема: размер массива заранее неизвестен. Пути решения: 1)выделить память «с запасом»; 2)выделять память тогда, когда размер стал известен. Алгоритм: 1)ввести размер массива; 2)выделить память ; 3)ввести элементы массива; 4)отсортировать и вывести на экран; 5)удалить массив. выделить память удалить массив

10 Динамические массивы(Delphi) procedure TForm1.Button1Click(Sender: TObject); var A: array of integer; i, n: integer; begin n:=StrToInt(Edit2.Text); SetLength ( A, n ); for i := 0 to N-1 do A[i]:=random(20);... { сортировка } for i := 0 to N-1 do Edit1.Text:=Edit1.Text + IntToStr(A[i])+' '; SetLength( A, 0 ); end. выделить память освободить память какой-то массив целых чисел нумерация с НУЛЯ!

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

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

13 Динамические матрицы (Delphi) Задача. Ввести размеры матрицы и выделить для нее место в памяти во время работы программы. Проблема: размеры матрицы заранее неизвестны Решение:... var A: array of array of integer; N, M: integer; begin N:=StrToInt(Edit1.Text);// число строк M:=StrToInt(Edit2.Text);// число столбцов SetLength ( A, N, M );... // работаем, как с обычной матрицей SetLength( A, 0, 0 ); end.... var A: array of array of integer; N, M: integer; begin N:=StrToInt(Edit1.Text);// число строк M:=StrToInt(Edit2.Text);// число столбцов SetLength ( A, N, M );... // работаем, как с обычной матрицей SetLength( A, 0, 0 ); end.

Динамические переменные Динамические структуры (записи) Динамические структуры данных

15 Динамические переменные procedure TForm1.Button1Click(Sender: TObject); var p1,p2,p3:^integer; //указатели на переменную integer begin // создаем динамические переменные типа integer // выделяем память для динамических переменных New(p1); // выделение памяти под переменную p1 New(p2); New(p3); р1^ := 5; р2^ := 3; р3^ := р1^ + р2^; ShowMessage('Сумма чисел равна' + IntToStr(р3^)); // уничтожаем динамические переменные // выделяем память, занимаемую этими переменными Dispose(p1); Dispose(р2); Dispose(р3); end; procedure TForm1.Button1Click(Sender: TObject); var p1,p2,p3:^integer; //указатели на переменную integer begin // создаем динамические переменные типа integer // выделяем память для динамических переменных New(p1); // выделение памяти под переменную p1 New(p2); New(p3); р1^ := 5; р2^ := 3; р3^ := р1^ + р2^; ShowMessage('Сумма чисел равна' + IntToStr(р3^)); // уничтожаем динамические переменные // выделяем память, занимаемую этими переменными Dispose(p1); Dispose(р2); Dispose(р3); end;

16 Структуры (в Паскале – записи) Структура (запись) – это тип данных, который может включать в себя несколько полей – элементов разных типов (в том числе и другие структуры). Свойства: автор (строка) название (строка) год издания (целое число) количество страниц (целое число) Задача: объединить эти данные в единое целое Размещение в памяти авторназвание год издания количество страниц 40 символов80 символовцелое

17 Новый тип данных – запись const N = 10; var Book: TBook; // одна запись aBooks: array[1..N] of TBook; // массив const N = 10; var Book: TBook; // одна запись aBooks: array[1..N] of TBook; // массив Объявление типа: type TBook = record author: string[40]; // автор, строка title: string[80]; // название, строка year: integer;// год издания, целое pages : integer; // кол-во страниц, целое end; type TBook = record author: string[40]; // автор, строка title: string[80]; // название, строка year: integer;// год издания, целое pages : integer; // кол-во страниц, целое end; Память не выделяется! ! ! Статическое объявление переменных и массивов: TBook – Type Book («тип книга») – удобно!

18 Динамическое выделение памяти под запись var pB: ^TBook; begin New(pB); pB^.author := 'А.С. Пушкин'; pB^.title := 'Полтава'; pB^.year := 1990; pB^.pages := 129; Dispose(pB); end. var pB: ^TBook; begin New(pB); pB^.author := 'А.С. Пушкин'; pB^.title := 'Полтава'; pB^.year := 1990; pB^.pages := 129; Dispose(pB); end. Для обращения к полю записи по адресу используется знак ^ ! ! New(pB); выделить память под запись, записать адрес в pB pB^ Dispose(pB); освободить память pB: ^TBook; переменная- указатель на TBook

19 Динамическое выделение памяти под элементы массива Задача. Создать массив книг. Предусмотреть ввод каждой книги с клавиатуры. Память под каждый новый элемент массива должна выделяться динамически. Предусмотреть вывод массива, а также функции освобождения памяти от занимаемого массива.

20 Реализация в программе type PBook = ^TBook; { новый тип данных } TBook = record author: string[40]; // автор, строка title: string[80]; // название, строка year: integer;// год издания, целое pages : integer; // кол-во страниц, целое end; var Form1: TForm1; p: array[1..100] of PBook; {массив указателей на тип TBook} kol:integer; {текущее количество элементов в массиве}... {процедура создания формы (при запуске программы)} procedure TForm1.FormCreate(Sender: TObject); begin kol:=0;{обнуляем начальное количество элементов массива} end; type PBook = ^TBook; { новый тип данных } TBook = record author: string[40]; // автор, строка title: string[80]; // название, строка year: integer;// год издания, целое pages : integer; // кол-во страниц, целое end; var Form1: TForm1; p: array[1..100] of PBook; {массив указателей на тип TBook} kol:integer; {текущее количество элементов в массиве}... {процедура создания формы (при запуске программы)} procedure TForm1.FormCreate(Sender: TObject); begin kol:=0;{обнуляем начальное количество элементов массива} end;

21 Реализация в программе {процедура нажатия кнопки «Добавить запись»} procedure TForm1.Button1Click(Sender: TObject); var i:integer; begin kol:=kol+1; {количество элементов массива +1} new(p[kol]); {создание элемента массива, адрес в p[kol]} p[kol]^.author:=Edit1.Text; //заполнение элемента p[kol]^.title:=Edit2.Text; // массива p[kol]^.year:=StrToInt(Edit3.Text); // данными p[kol]^.pages:=StrToInt(Edit4.Text); // из формы Memo1.Clear; // очистка Memo1 for i:=1 to kol do //вывод массива в Memo Memo1.Lines.Add(IntToStr(i)+'. '+p[i]^.author+', +p[i]^.title+', '+IntToStr(p[i]^.year)+', +IntToStr(p[i]^.pages)); end; {процедура нажатия кнопки «Добавить запись»} procedure TForm1.Button1Click(Sender: TObject); var i:integer; begin kol:=kol+1; {количество элементов массива +1} new(p[kol]); {создание элемента массива, адрес в p[kol]} p[kol]^.author:=Edit1.Text; //заполнение элемента p[kol]^.title:=Edit2.Text; // массива p[kol]^.year:=StrToInt(Edit3.Text); // данными p[kol]^.pages:=StrToInt(Edit4.Text); // из формы Memo1.Clear; // очистка Memo1 for i:=1 to kol do //вывод массива в Memo Memo1.Lines.Add(IntToStr(i)+'. '+p[i]^.author+', +p[i]^.title+', '+IntToStr(p[i]^.year)+', +IntToStr(p[i]^.pages)); end;

22 Реализация в программе {процедура нажатия кнопки «Удалить массив»} procedure TForm1.Button2Click(Sender: TObject); var i:integer; begin for i:=1 to kol do Dispose(p[i]); {удаление i-го элемента массива} Memo1.Clear; kol:=0; {обнуление кол-ва элементов массива} end; {процедура нажатия кнопки «Удалить массив»} procedure TForm1.Button2Click(Sender: TObject); var i:integer; begin for i:=1 to kol do Dispose(p[i]); {удаление i-го элемента массива} Memo1.Clear; kol:=0; {обнуление кол-ва элементов массива} end;