Разделы презентаций

Глава 6 Использование динамически выделяемой памяти

Содержание

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

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

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

и системы управления
Кафедра Компьютерные системы и сети
Лектор: д.т.н., проф.

Иванова Галина Сергеевна

2016

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

Слайд 26.1 Адресация оперативной памяти. Указатели и операции над ними
Минимальная адресуемая

единица памяти – байт.



Физический адрес Аф – номер байта оперативной

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

0

1

2

3

4

Aб

Aсм

Аф

6.1 Адресация оперативной памяти. Указатели и операции над ними Минимальная адресуемая единица памяти – байт.Физический адрес Аф

Слайд 3Типизированные и нетипизированные указатели
Различают указатели:
типизированные – адресующие данные конкретного

типа;
нетипизированные – не связанные с данными определенного типа.
Объявление типизированного указателя:




Объявление

нетипизированного указателя: 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;

Типизированные и нетипизированные указателиРазличают указатели: типизированные – адресующие данные конкретного типа;нетипизированные – не связанные с данными определенного

Слайд 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;

pi

i

Операции присваивания и получения адреса1. Присваивание. Допускается присваивать указателю только значение того же или неопределенного типа. Пример:Var

Слайд 5Операции доступа и отношения
3. Доступ к данным по указателю (операция

разыменования). Полученное значение имеет тип, совпадающий с базовым типом данных

указателя. Нетипизированные указатели разыменовывать нельзя.
Примеры:
j:=pi^;
pi^:= pi^+2;

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

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

Слайд 76.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

6.2 Динамическое распределение памятиУправление выделением и освобождением памяти осуществляется посредством специальных процедур и функций:1. Процедура New(var P:

Слайд 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));…
Подпрограммы динамического распределения (2)3. Процедура GetMem(var P: Pointer; Size: Integer) – выделяет указанное количество памяти и помещает

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

Динамическая матрицаРазместить в памяти матрицу размерностью 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

Слайд 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.
Программа (2)Begin Randomize; WriteLn('Input n,m'); ReadLn(n,m); for i:=1 to n do

Слайд 126.3 Динамические структуры данных
Структуры данных
Последовательные
Древовидные
Сетевые
Вектор
Стек
Дек
Бинарные деревья
Сортированные
Бинарные деревья
Динамические линейные структуры
1.

Очередь – структура данных, реализующая: добавление – в конец, а

удаление – из начала.
2. Стек – структура данных, реализующая: добав-ление и удаление с одной стороны.
3. Дек – структура данных, реализующая: добав-ление и удаление с двух сторон.

Очередь

Строка

Запись

Матрица

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

Слайд 13Списки
Список – способ организации данных, предполагающий использова-ние указателей для определения

следующего элемента.
Элемент списка состоит из двух частей: информационной и адресной.
Информационная

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

Списки

Линейные

Древовидные

N-связные

Кольцевые

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

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

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

Слайд 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

Слайд 166.4 Односвязные списки
Аналогично одномерным массивам реализуют последовательность элементов. Однако в

отличие от одномерных массивов позволяют:
работать с произвольным количеством элементов, добавляя

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

Слайд 17Объявление типа элемента и переменных
Описание типа элемента:
Type tpel=^element; {тип

«указатель на элемент»}
element=record

num:integer; {число}
p:tpel; {указатель на следующий элемент}
end;

Описание переменной – указателя списка и несколько переменных-указателей в статической памяти:
Var first, {адрес первого элемента}
n,f,q:tpel; {вспомогательные указатели}

Исходное состояние – «список пуст»:
first:=nil;

first


n

f

q

Объявление типа элемента и переменныхОписание типа элемента:Type tpel=^element; {тип «указатель на элемент»} element=record

Слайд 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;

first


5


first

5


q

4

first

5


q

4


Добавление элементов к списку1 Добавление элемента к пустому списку: new(first); first

Слайд 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);

det diam p

zap

det diam p

a

r

q

r

f

r

det diam p


Гайка

10

«Стек» записейProgram Ex6_2;{$APPTYPE CONSOLE}Uses SysUtils;Type point=^zap; zap=record det:string[10];

Слайд 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;

r

det diam p

det diam p

a

Гайка

10

r

det diam p

q


Шайба

3

Болт

Создание списка по типу стека ReadLn(a.det); while a.det'end' do begin Readln(a.diam);

Слайд 21Варианты удаления элементов
first
5
q
4
8

first
5
4
8
first
5
4
8

f
8

q
q
f

Варианты удаления элементовfirst5q48first548first548f8qqf

Слайд 22Удаление записей
q:=r;
c:=0;
repeat
if q^.diam

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

Удаление записейq:=r;c:=0;repeat if q^.diam

Слайд 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.
Вывод результата q:=r; if q=nil then WriteLn('No records') else

Слайд 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

3

2

4

5

first

Кольцевой список 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

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

1

2

5

First

Pass

Next

3

4

Создание спискаbegin { Создание списка } new(First); First^.name:=1; Pass:=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;

1

2

5

First

Pass

Next

3

4

Проход по кольцу n-1 раз Pass:=First; for k:=n downto 2 do begin

Слайд 27Удаление m-го элемента. Основная программа
WriteLn(Pass^.name);
Next^.p:=Pass^.p;

dispose(Pass);
Pass:=Next^.p;
end;
{Возврат результата}
Play:=Pass^.name;
end;

1
2
5
First
Pass
Next
3
4
Begin
y:=Play(5,7);

WriteLn('Result =',y:2);
ReadLn;
End.

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

Слайд 286.5 Бинарные сортированные деревья
В математике бинарным деревом называют конечное множество

вершин, которое либо пусто, либо состоит из корня и не

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

Вершины, из которых не выходит ни одной ветви, называют листьями

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

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

Слайд 29Построение бинарного дерева
Рассмотрим последовательность целых чисел: {5, 2, 8, 7,

2, 9, 1, 5}








Пример. Разработать программу сортировки последовательности чисел с

использованием бинарного дерева.

5

2

8

7

2

9

1

5

Построение бинарного дереваРассмотрим последовательность целых чисел: {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;

Основная
программа

Add

Tree

Схема структурная ПО

Описание элемента дереваProgram Ex6_4;{$APPTYPE CONSOLE}Uses SysUtils;Const lim=100;Type top_ptr=^top; top=record value:integer;

Слайд 31Основная программа
Begin WriteLn('Input numbers (End - 1000)');
r:=nil;

Read(next_number);
while next_number1000 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

Основная программаBegin WriteLn('Input numbers (End - 1000)'); r:=nil; Read(next_number); while next_number1000

Слайд 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:=succ^.left
else succ:=succ^.right;
end;
if pass^.value next^.left:=pass
else next^.right:=pass;
end;
End;

5


r

pass



5

r

succ



2

pass



next


Нерекурсивная процедура построения дереваProcedure Add1(Var r:top_ptr; pass:top_ptr);Var next,succ:top_ptr;Begin if r=nil then r:=pass else

Слайд 33Рекурсивная процедура построения дерева
Procedure Add2(Var r:top_ptr; pass:top_ptr);
begin
if r=nil

then r:=pass
else
if (pass^.value

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

Слайд 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;
Нерекурсивная процедура обхода дереваProcedure Tree1(r:top_ptr);var pass:top_ptr; mem_top:record nom:0..lim;

Слайд 35Нерекурсивная процедура обхода дерева (2)
with mem_top do
begin nom:=0;

while (passnil) or (nom0) 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;

5

2

8

7

2

9

1

5

Нерекурсивная процедура обхода дерева (2) with mem_top do begin nom:=0; while (passnil)

Слайд 36Рекурсивная процедура обхода дерева
Procedure Tree2(r:top_ptr);
begin
if rnil then

begin
Tree2(r^.left);

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

Похожие презентации

dad, Peter, dark, brown, kind, dentist son, Sam, fair, grey, funny, pupil mum, dad, Peter, dark, brown, kind, dentist son, Sam, fair, grey, funny, pupil mum, 189
Мотивация Мотивация 314
Закон О взятках Великобритания Закон О взятках Великобритания 233
Гортензии Гортензии 215
НЕФРОТИЧЕСКИЙ СИНДРОМ (НС) НЕФРОТИЧЕСКИЙ СИНДРОМ (НС) 230
Система требований к предпринимательской деятельности Система требований к предпринимательской деятельности 285
Я - ГРАЖДАНИН РОССИИ Я - ГРАЖДАНИН РОССИИ 446
4 класс Раздел 8 УРОК 5 T he 20 th of April Р аботаем с текстом Тема 4 класс Раздел 8 УРОК 5 T he 20 th of April Р аботаем с текстом Тема 204
Витамин РР Витамин РР 194
Эстетическое Воспитание Иванова А.Е Эстетическое Воспитание Иванова А.Е 253
Как сделать так, чтобы ваш аргумент / кейс не повторил судьбу Титаника? Как сделать так, чтобы ваш аргумент / кейс не повторил судьбу Титаника? 219
Методы исследования потоков и аппаратов Методы исследования потоков и аппаратов 167
Сущность Подготовки детей к обучению грамоте Сущность Подготовки детей к обучению грамоте 432
Технологии приема ТВ сигнала Технологии приема ТВ сигнала 265
Сыры от Новой Волны Сыры от Новой Волны 227
ВИРТУАЛЬНАЯ ЭКСКУРСИЯ Беловежье Добровольского края ВИРТУАЛЬНАЯ ЭКСКУРСИЯ Беловежье Добровольского края 191
Начиная со времен неолитической революции, то есть с той поры, когда было Начиная со времен неолитической революции, то есть с той поры, когда было 194
Сочинение по картине Сочинение по картине 180
гигиена войск гигиена войск 235
Моделирование и оптимизация процессов и систем сервиса: понятия процесс и Моделирование и оптимизация процессов и систем сервиса: понятия процесс и 195

Обратная связь

Если не удалось найти и скачать доклад-презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика