1 Глава 6 Использование динамической памяти 6.1 Адресация оперативной памяти. Указатели и операции над ними Минимальная адресуемая единица памяти – байт. Физический адрес А ф – номер байта оперативной памяти. Адресация по схеме «база+смещение»: А ф = А б + А см, где А б – адрес базы – адрес, относительно которого считают остальные адреса; А см – смещение – расстояние от базового адреса до физического. Указатель – тип данных, используемый для хранения смещений. В памяти занимает 4 байта, адресует сегмент размером V = 2 32 = 4 Гб. Базовый адрес = адрес сегмента AбAб A см Аф Аф

2 Типизированные и нетипизированные указатели Различают указатели: типизированные – адресующие данные конкретного типа; нетипизированные – не связанные с данными определенного типа. Объявление типизированного указателя: Объявление нетипизированного указателя: pointer Примеры: а) Type tpi=^integer; Var pi:tpi; или Var pi: ^integer; б) Var p:pointer; в) Type pp = ^percon; percon = record name: string: next: pp; end ; г) Var r:^integer = nil;

3 Операции над указателями 1. Присваивание. Допускается присваивать указателю только значение того же или неопределенного типа. Пример: Var p1,p2: ^integer; p3: ^real; p: pointer;... {допустимые операции} p1:=p2; p:=p3; p1:=p; p1:=nil; p:=nil;... {недопустимые операции} p3:=p2; p1:=p3; 2. Получение адреса. Результат операции – указатель типа pointer – может присвоен любому указателю. Пример: Var i:integer; pi: ^integer;... pi i

4 Операции над указателями (2) 3. Доступ к данным по указателю (операция разыменования). Полученное значение имеет тип, совпадающий с базовым типом данных указателя. Нетипизированные указатели разыменовывать нельзя. Примеры: j:=pi^; pi^:= pi^+2; 4. Операции отношения: проверка равенства (=) и неравенства ( ). Примеры: sign := p1 = p2; if p1<>nil then...

5 Процедуры и функции, работающие с указателями 1. Функция ADDR(x): pointer – возвращает адрес объекта x, в качестве которого может быть указано имя переменной, функции, процедуры. Пример: Data:=Addr(NodeNumber); NodeNumber; 2. Функция Assigned(const P): Boolean – проверяет присвоено ли значение указателю (true – если присвоено). Пример: if Assigned (P) then Writeln ('You won''t see this'); 3. Функция Ptr(Address: Integer): Pointer – преобразует число в указатель. Пример: p:=Ptr(a);

6 6.2 Динамическое распределение памяти Управление выделением и освобождением памяти осуществляется посредством специальных процедур и функций: 1. Процедура New(var P: ^ ) – выделяет память для размещения переменной, размер определяется типом указателя. 2. Процедура Dispose(var P: ^ ) – освобождает выделенную память. Пример: Var pi:^integer;... if Assigned(pi) then... {false} New(pi); pi^:=5; Dispose(pi); if Assigned(pi) then... {true}... pi 5

7 Процедуры и функции динамического распределения (2) 3. Процедура GetMem(var P: Pointer; Size: Integer) – выделяет указанное количество памяти и помещает ее адрес в указатель. 4. Процедура FreeMem(var P: Pointer[; Size: Integer]) – освобождает выделенную память. 5. Функция SizeOf(X): Integer – возвращает размер переменной в байтах. Пример: Var Buffer: ^array[1..100] of byte;... GetMem(Buffer,SizeOf(Buffer)); Buffer^[1]:=125;... FreeMem(Buffer,sizeof(Buffer));

8 Динамическая матрица Разместить в памяти матрицу размерностью N*M.

9 Программа Program Ex6_1; {$APPTYPE CONSOLE} Uses SysUtils; Var i,j,n,m:word; s:real; ptrstr:array[ ] of pointer; Type tpsingle=^single; {Функция вычисления адреса} Function AddrR(i,j:word):tpsingle; begin AddrR:=Ptr(Integer(ptrstr[i])+(j-1)*SizeOf(single)); end;

10 Программа (2) Begin Randomize; WriteLn('Input n,m'); ReadLn(n,m); for i:=1 to n do begin GetMem(ptrstr[i],m*sizeof(single)); for j:=1 to m do AddrR(i,j)^:=Random; end; s:=0; for i:=1 to n do for j:=1 to m do s:=s+AddrR(i,j)^; WriteLn('Summa =',s:15:10); WriteLn('Middle value =',s/(n*m):15:10); for i:=1 to n do FreeMem(ptrstr[i],m*SizeOf(real)); ReadLn; End.

Динамические структуры данных Структуры данных Последовательности ДеревьяСети Вектор Стек Дек Бинарные Сортированные бинарные Динамические линейные структуры 1. Очередь – структура данных, реализующая: добавление – в конец, а удаление – из начала. 2. Стек – структура данных, реализующая: добавление и удаление с одной стороны. 3. Дек – структура данных, реализующая: добавление и удаление с двух сторон. Очередь Строка Запись Матрица

12 Списки Список – способ организации данных, предполагающий использование указателей для определения следующего элемента. Элемент списка состоит из двух частей: информационной и адресной. Информационная часть содержит поля данных. Адресная – включает от одного до n указателей, содержащих адреса следующих элементов. Количество связей, между соседними элементами списка определяет его связность: односвязные, двусвязные, n-связные. Списки Линейные ДревовидныеN-связные Кольцевые

13 Виды списков Линейный односвязный Кольцевой односвязный Линейный двусвязный Кольцевой двусвязный Сетевой n-связный

14 Примеры описания элементов списка Односвяный список: Type pe = ^element; {тип указателя} element = record name: string[16]; {информационное поле 1} telefon:string[7]; {информационное поле 2} p: pe; {адресное поле} end; Двусвяный список: Type pe = ^element; {тип указателя} element = record name: string[16]; {информационное поле 1} telefon:string[7]; {информационное поле 2} prev: pe; {адресное поле «предыдущий»} next: pe; {адресное поле «следующий»} end;

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

16 Основные приемы работы Описание типа элемента: Type tpel=^element; {тип «указатель на элемент»} element=record num:integer; {число} p:tpel; {указатель на следующий элемент} end; Описание переменной – указателя списка и несколько переменных- указателей в статической памяти: Var first, {адрес первого элемента} n,f,q:tpel; {вспомогательные указатели} Исходное состояние – «список пуст»: first:=nil; first n fq

17 Основные приемы работы (2) 1 Добавление элемента к пустому списку: new(first); first ^.num:=5; first ^.p:=nil; 2 Добавление элемента перед первым (по типу стека): new(q); q^.num:=4; q^.p:=first; first:=q; 3 Добавление элемента после первого (по типу очереди): new(q); q^.num:=4; q^.p:=nil; first^.p:=q; first 5 first 5 q 4 first 5 q 4

18 «Стек» записей Program Ex6_2; {$APPTYPE CONSOLE} Uses SysUtils; Type point=^zap; zap=record det:string[10]; diam:real; p:point; end; Var r,q,f:point; a:zap; c:integer; Begin new(r); r^.p:=nil; Writeln('Input name, diam'); Readln(r^.det,r^.diam); det diam p zap det diam p a rqrf r Гайка 10

19 Создание списка по типу стека ReadLn(a.det); while a.det<>'end' do begin Readln(a.diam); q:=r; new(r); r^.det:=a.det; r^.diam:=a.diam; r^.p:=q; ReadLn(a.det); end; r det diam p a Гайка 10 r det diam p q Шайба 3Болт

20 Варианты удаления элементов first 5 q 48 first f 8 q qf

21 Удаление записей q:=r; c:=0; repeat if q^.diam<1 then if c=0 then begin r:=r^.p; dispose(q); q:=r end else begin q:=q^.p; dispose(f^.p); f^.p:=q end else begin f:=q; q:=q^.p; c:=1 end; until q=nil; r q r q f

22 Вывод результата q:=r; if q=nil then WriteLn('No records') else while q<>nil do begin WriteLn(q^.det:11,q^.diam:5:1); q:=q^.p; end; ReadLn; End.

23 Кольцевой список Program Ex6_3; {$APPTYPE CONSOLE} Uses SysUtils; Var y:integer; Function Play(n,m:integer):integer; Type child_ptr=^child; child=record name:integer; p:child_ptr; end; Var First,Next,Pass:child_ptr; j,k:integer; first

24 Создание списка begin { Создание списка } new(First); First^.name:=1; Pass:=First; for k:=2 to N do begin new(Next); Next^.name:=k; Pass^.p:=Next; Pass:=Next; end; Pass^.p:=First; {Замыкание круга} 125 First PassNext 34

25 Проход по кольцу m-1 раз Pass:=First; for k:=n downto 2 do begin for j:=1 to m-1 do begin Next:=Pass; Pass:=Pass^.p; end; 125 First PassNext 34

26 Удаление m-го элемента. Основная программа WriteLn(Pass^.name); Next^.p:=Pass^.p; dispose(Pass); Pass:=Next^.p; end; {Возврат результата} Play:=Pass^.name; end; 125 First PassNext 34 Begin y:=Play(5,7); WriteLn('Result =',y:2); ReadLn; End.

Бинарные сортированные деревья В математике бинарным деревом называют конечное множество вершин, которое либо пусто, либо состоит из корня и не более чем двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Вершины, из которых не выходит ни одной ветви, называют листьями Сортированные бинарные деревья, строятся по правилу: ключевое поле левого поддерева должно содержать значение меньше, чем в корне, а ключевое поле правого поддерева – значение больше или равное значению в корне.

28 Построение бинарного дерева Рассмотрим последовательность целых чисел: {5, 2, 8, 7, 2, 9, 1, 5} Пример. Разработать программу сортировки последовательности чисел с использованием бинарного дерева

29 Описание элемента дерева Program Ex6_4; {$APPTYPE CONSOLE} Uses SysUtils; Const lim=100; Type top_ptr=^top; top=record value:integer; left,right:top_ptr; end; Var next_number:integer; r,pass:top_ptr; Основная программа Add Tree Схема структурная ПО

30 Основная программа Begin WriteLn('Input numbers (End )'); r:=nil; Read(next_number); while next_number<>1000 do begin new(pass); with pass^ do begin value:=next_number; left:=nil; right:=nil; end; Add1(r,pass); Read(next_number) end; ReadLn; WriteLn('Result:'); Tree1(r); ReadLn; End. pass r 5

31 Нерекурсивная процедура построения дерева Procedure Add1(Var r:top_ptr; pass:top_ptr); Var next,succ:top_ptr; Begin if r=nil then r:=pass else begin succ:=r; while succ<>nil do begin next:=succ; if pass^.value<succ^.value then succ:=succ^.left else succ:=succ^.right; end; if pass^.value<next^.value then next^.left:=pass else next^.right:=pass; end; End; 5 r pass 5 r succ 2 pass next

32 Рекурсивная процедура построения дерева Procedure Add2(Var r:top_ptr; pass:top_ptr); begin if r=nil then r:=pass else if (pass^.value<r^.value) then Add2(r^.left,pass) else Add2(r^.right,pass); end;

33 Нерекурсивная процедура обхода дерева Procedure Tree1(r:top_ptr); var pass:top_ptr; mem_top:record nom:0..lim; adres:array[1..lim] of top_ptr; end; begin pass:=r;

34 Нерекурсивная процедура обхода дерева (2) with mem_top do begin nom:=0; while (pass<>nil) or (nom<>0) do if pass<>nil then begin if nom=lim then begin Writeln(Error lim'); exit; end; nom:=nom+1; adres[nom]:=pass; pass:=pass^.left; end else begin pass:=adres[nom]; nom:=nom-1; writeln(pass^.value); pass:=pass^.right; end;

35 Рекурсивная процедура обхода дерева Procedure Tree2(r:top_ptr); begin if r<>nil then begin Tree2(r^.left); Write(r^.value:4); Tree2(r^.right); end;

36