close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Динамические
структуры данных
Два подхода к распределению памяти на стадии
компиляции
Статический (традиционный)
Динамический
На основании информации из раздела
описаний и длины кода самой программы
операционная система во время работы
программы выделяет определённый объём
оперативной памяти, который закрепляется
за программой на всё время её выполнения
В процессе работы программы специальной процедурой
программист может запросить у системы некоторый
объём памяти, а после использования (также
специальной процедурой) возвратить её системе, т.е.
динамическое управление памятью – это выделение
памяти во время выполнения программы.
Например, пусть в
программе имеется
описание:
Преимущества:
разумное использование динамических структур
данных приводит к сокращению объёма памяти,
необходимого для работы программы;
динамические данные не требуют объявлений их как
данных фиксированного размера;
ряд алгоритмов более эффективен при реализации
их с использованием динамических структур.
Например, вставка элемента в массив на
определенное место требует перемещения части
элементов массива. При вставке в середину списка
достаточно несколько операторов присваивания.
Const
a:real=25.369;
Var
MAS:array[1..20
0] of integer;
I,j:byte;
s:string
На основании этого
описания будет
зарезервировано
следующее количество
оперативной памяти:
под константу типа real –
6 байтов; под массив –
400 байтов (200
элементов по 2 байта);
под переменные i и j – по
2 байта; под переменную
s – 256 байтов. Всего –
6+400+2+2+256=666
байт.
Такой подход снижает
эффективность использования
оперативной памяти.
Примеры:
1) большой массив данных, к-ый
Статический
существует
очень(традиционный)
малую часть общего
времени работы программы, т.е.
статически выделенная память
использоваться практически не будет;
2)ситуации, при которых требуется
объём памяти, больший того, который
может быть доступен программе в
статическом режиме;
3)ищется слово в тексте, длина которого
заранее неизвестна.
Недостатки:
•алгоритмы для динамических структур
обычно более сложны, трудны для
отладки по сравнению с аналогичными
для статических данных;
•использование динамических структур
требует затрат на память для ссылок. В
некоторых задачах объём памяти,
отводимой для ссылок, превосходит
объём памяти, выделяемой
непосредственно для данных;
•существуют алгоритмы, реализация
которых более эффективна на обычных
данных.
Основные сведения о ссылочном типе данных (указателях)
Организация динамического управления памятью (выделение памяти во
время выполнения программы) возможно при использовании нового типа
данных, которые называются указатели.
Указатель — это переменная, которая в качестве своего значения содержит
адрес первого байта памяти, начиная с которого записаны данные.
Переменной, на которую указывает указатель, не обязательно присваивать
какое-либо имя. К ней можно обращаться через имя указателя, потому она
называется ссылочной переменной.
Все ссылочные переменные имеют одинаковый размер, равный 4 байтам.
Для хранения динамических переменных выделяется специальная область
памяти, называемая «кучей». Работая с указателями, мы работаем с
адресами величин, а не с их именами.
Место для данных в «куче» отводится и высвобождается только во время
работы программ, и потому мы говорим о динамических данных
Объявление переменных ссылочного типа
Типизированные указатели
Всегда привязаны к конкретному типу данных. Для
объявления используется специальный символ ”^”, после
которого записывается базовый тип динамической
переменной.
TYPE <имя_типа>=^<базовый_тип>;
VAR <имя_переменной>:<имя_типа>;
или
VAR <имя_переменной>:^<базовый_тип>;
Например,
TYPE ss=^Integer;
VAR x,y: ss;{Указатели на переменные целого типа}
a:^Real; {Указатель на переменную вещественного типа}
Можно передавать значения одних указателей другим, однако при этом они должны
быть одного типа.
Например,
можно записать x:=y; но нельзя записать x:=a;
Если x — это указатель, значением которого является адрес переменной типа
Integer, то x^ — это обращение к самой переменной, расположенной по этому
адресу.
Среди возможных указателей в Турбо Паскале выделяется один специальный
указатель, который «никуда не указывает». Для его обозначения используется
зарезервированное слово Nil. Указатель Nil считается константой, совместимой с
любым ссылочным типом.
При составлении программ часто создают новый тип, использующий указатели,
например:
TYPE MAS:array[1..50] of real;
Тогда можно указать тип указателя на такой объект:
TYPE PMAS:^MAS;
Операции при работе с ссылочными переменными
Основной операцией при работе со ссылочными переменными является операция
разыменования — переход от ссылочной переменной к значению, на которое она
указывает.
Например, P^:=15 означает, что по адресу, который является значением указателя P,
записывается значение 15.
При использовании типизированных указателей запрос на выделение
динамической памяти осуществляется процедурой
NEW(P), где P — типизированный указатель.
Процедура NEW отводит место для хранения динамической переменной P^ и
присваивает её адрес ссылке P.
Освобождение же памяти, запрошенной с помощью NEW, осуществляется
процедурой DISPOSE(P), которая освобождает память, занимаемую динамической
переменной. После выполнени процедуры значение указателя P становится
неопределённым:
x
X^
x:=Nil
Nil
New(x)
15
X^:=15
Dispose(x)
Механизм выделения и освобождения динамической
памяти
Вся динамическая память представляет собой сплошную область, которая физически
располагается в старших адресах ОЗУ непосредственно за памятью, занимаемой самой
программой.
Системная
область
программа
Занятая часть кучи
HEARPORG
Системная область
КУЧА
HEAPPTR
HEAPEND
Область оперативной памяти, из которых происходит её динамическое выделение,
называется кучей.
Адрес начала кучи хранится в стандартной переменной HEAPORG,
конечный адрес — в переменной HEAPEND,
а адрес начала невыделенной части памяти кучи хранит переменная HEAPPTR:
Характерно, что в момент выделения динамической памяти
указатель P, являющийся параметром в процедуре NEW(P),
получает то значение, которое на этот момент имел указатель
кучи PTR(HEAPPTR), после чего он смещается на величину
объёма выделенной памяти.
Чередование процедур NEW и DISPOSE приводит к
формированию «ячеистой» структуры памяти.
Все операции с кучей выполняются под руководством
специальной программы — «администратора кучи».
При очередной процедуре «администратор» разыскивает
наименьший свободный фрагмент, где может разместиться
объект, под который запрашивается память, и адрес начала
найденного фрагмента становится значением указателя,
а сам фрагмент помечается как занятая часть кучи
Примеры задач, демонстрирующие возможности
использования динамической памяти
1. Сформируйте массив случайных чисел, находящихся в диапазоне от 1 до 255,
состоящий из 1000 элементов. Отобразите квадрат наибольшего числа. Массив
расположите в динамической памяти.
PROGRAM din_mas;
Uses crt;
TYPE TARR=array[1..1000] of
byte;
VAR
P:^TARR;MX:byte;i,kv:Integer;
BEGIN
clrscr;
randomize;
NEW(P);
MX:=0;
For i:=1 To 1000 do
Begin
P^[i]:=random(256);
If P^[i]> MX Then
Mx:=P^[i];
End;
DISPOSE(P);
kv:=sqr(MX);
WriteLn(kv);
Readkey;
END.
2. Составьте программу нахождения корней квадратного уравнения, расположив его
коэффициенты в динамической памяти.
PROGRAM din_kvur;
If D<0 Then
Uses crt;
begin
VAR a,b,c:^real;d,x1,x2:real; WriteLn('Дискриминант трицателен');
BEGIN
Halt;
clrscr;
end;
randomize;
x1:=((-b^)+sqrt(D))/(2*a^);
NEW(a);NEW(b); NEW(c); x2:=((-b^)-sqrt(D))/(2*a^);
{Запрос динамической
DISPOSE(a);DISPOSE(b);DISPOSE(c) ;
памяти}
{Высвобождение динамической памяти
WriteLn('Введите
WriteLn('x1=',x1:4,' ',‘x2=',X2:4);
Readkey;
коэффициенты:');
END.
ReadLn(a^,b^,c^);
D:=sqr(b^)-4*a^*c^;
3.
В текстовом файле находится матрица a целых чисел
a[1,1] … a[1,n]
…
a[m,1] … a[m,n]
причём каждая строка матрицы занимает отдельную строку файла
(разделитель между числами – пробел). Числа m и n заранее неизвестны.
Загрузив a в динамическую память, найти такое число, которое является
максимальным в своей строке и в то же время минимальным в своём
столбце, или выдать сообщение, что таких чисел нет. Можно доказать, что
если все элементы в матрице различны и подобное число существует, то
оно единственное. Такое число называется седловой точкой матрицы.
Р е ш е н и е :
Рассмотрим решение данной задачи для матрицы, все элементы которой
различны.
Докажем единственность решения в случае его существования.
Пусть существуют две седловые точки — a[i1,j1] и a[i2,j2], причём i1≠i2 и j1≠j2 в
силу определения седловой точки и отсутствия в матрице одинаковых
элементов. Рассмотрим элемент матрицы a[i1,j2]. Так как a[i1,j1] максимален в
своей строке, а a[i2,j2] минимален в своём столбце, получаем
a[i2,j2] < a[i1,j2] < a[i1,j1]
С другой стороны —
a[i2,j2] > a[i2,j1] > a[i1,j1]
Полученное противоречие доказывает, что предположение о существовании
двух седловых точек неверно.
Документ
Категория
Презентации по информатике
Просмотров
98
Размер файла
694 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа