Использование динамически выделяемой памяти (Delphi / Pascal, глава 6)

Нажмите для полного просмотра!

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №2

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №3

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №4

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №5

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №6

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №7

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №8

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №9

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №10

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №11

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №12

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №13

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №14

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №15

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №16

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №17

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №18

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №19

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №20

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №21

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №22

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №23

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №24

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №25

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №26

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №27

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №28

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №29

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №30

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №31

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №32

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №33

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №34

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №35

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №36

Использование динамически выделяемой памяти (Delphi / Pascal, глава 6), слайд №37

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Использование динамически выделяемой памяти (Delphi / Pascal, глава 6). Доклад-сообщение содержит 37 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Глава 6 Использование динамически выделяемой памяти МГТУ им. Н.Э. Баумана Факультет Информатика и системы управления Кафедра Компьютерные системы и сети Лектор: д.т.н., проф. Иванова Галина Сергеевна

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

$Операции присваивания и получения адреса 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;$

Описание слайда:

Операции присваивания и получения адреса 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;

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Подпрограммы, работающие с указателями 1. Функция ADDR(x): pointer – возвращает адрес объекта x, в качестве которого может быть указано имя переменной, функции, процедуры. Пример: Data:=Addr(NodeNumber);  Data:= @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);

Слайд 7

$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} ...$

Описание слайда:

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} ...

Слайд 8

Описание слайда:

Подпрограммы динамического распределения (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));…

Слайд 9

Описание слайда:

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

Слайд 10

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

Описание слайда:

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

Слайд 11

Описание слайда:

Программа (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(single)); ReadLn; End.

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Виды списков

Слайд 15

$Примеры описания элементов списка Односвязный список: 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;$

Описание слайда:

Примеры описания элементов списка Односвязный список: 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

Описание слайда:

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

Слайд 17

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

Описание слайда:

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

Слайд 18

Описание слайда:

Добавление элементов к списку 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;

Слайд 19

$«Стек» записей 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);$

Описание слайда:

«Стек» записей 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);

Слайд 20

Описание слайда:

Создание списка по типу стека 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;

Слайд 21

Описание слайда:

Варианты удаления элементов

Слайд 22

Описание слайда:

Удаление записей 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;

Слайд 23

Описание слайда:

Вывод результата 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.

Слайд 24

$Кольцевой список 1 2 3 4 5 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;$

Описание слайда:

Кольцевой список 1 2 3 4 5 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;

Слайд 25

$Создание списка 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; {Замыкание круга}$

Описание слайда:

Создание списка 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; {Замыкание круга}

Слайд 26

Описание слайда:

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

Слайд 27

$Удаление m-го элемента. Основная программа WriteLn(Pass^.name); Next^.p:=Pass^.p; dispose(Pass); Pass:=Next^.p; end; {Возврат результата} Play:=Pass^.name; end;$

Описание слайда:

Удаление m-го элемента. Основная программа WriteLn(Pass^.name); Next^.p:=Pass^.p; dispose(Pass); Pass:=Next^.p; end; {Возврат результата} Play:=Pass^.name; end;

Слайд 28

Описание слайда:

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

Слайд 29

Описание слайда:

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

Слайд 30

$Описание элемента дерева 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;$

Описание слайда:

Описание элемента дерева 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;

Слайд 31

Описание слайда:

Основная программа Begin WriteLn('Input numbers (End - 1000)'); 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.

Слайд 32

Описание слайда:

Нерекурсивная процедура построения дерева 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;

Слайд 33

Описание слайда:

Рекурсивная процедура построения дерева 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;

Слайд 34

Описание слайда:

Нерекурсивная процедура обхода дерева 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;

Слайд 35

Описание слайда:

Нерекурсивная процедура обхода дерева (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; end; end;

Слайд 36

Описание слайда:

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