Презентация, доклад Динамические структуры данных

другие переменные. Такие переменные называются указатели.
Указатель – это переменная, значением которой является адрес другой переменной или структуры данных.
Более точно определить указатель как адрес 1-го байта области памяти, которую занимает переменная.

строкового или типа массива.
Нетипизированный – это адрес первого байта области памяти, в которой может размещаться любая информация вне зависимости от ее типа.
Var Имя:^Тип;
Где имя – это имя переменной – указателя; тип – это тип переменной, на которую указывает переменная – указатель, значок ^ показывает, что объявляемая переменная является указателем.

тип переменной, на которую указывает переменная–указатель;
значок ^ показывает, что объявляемая переменная является указателем.

P2:^real; {указатель на переменную вещественного типа}
P3:^string; {указатель на строку}
P4:pointer; {нетипизированный указатель}

указатель, называют типом указателя.
P1:^integer, то говорят «P1 – указатель целого типа».
В начале работы программы переменная – указатель «ни на что не указывает». В этом случае говорят, что значение указателя равно nil.

переменные P1 и P2 объявлены как указатели, то инструкция P1:=nil; устанавливает значение переменной, а инструкция if P2=nil then ShowMessage (‘указатель P2 не инициализирован!’);
проверяет, инициализирован ли указатель P2.

указателями на переменную одного типа.
Указатель можно использовать для доступа к переменной, адрес которой содержит указатель.

инструкции P^:=5; значение переменной i будет равно 5. В приведенном примере значок ^ показывает, что значение 5 присваивается переменной, на которую указывает переменная – указатель.

работы программы.
Так как бывают два разных типа указателей, то в соответствии с ними бывают две разные процедуры создания динамических переменных
для типизированных указателей – new (p);
для нетипизированных указателей – getmem (p, size).
Размер size не может превышать 54 килобайта.

требуется для хранения переменной заданного типа. Для нетипизированных указателей в памяти выделяется size байтов, а указатель получает значение адреса первого байта выделенной области.
Обратите внимание – динамические переменные не имеют собственного имени, в процедурах выделения памяти задается не имя переменной, а имя указателя.

размер свободной памяти в байтах;
maxavail – возвращает размер наибольшего непрерывного участка свободной памяти.

память, на которую указывал p;
mark (p) и release (p) – эти две процедуры используются только вместе и позволяют сразу очистить целую область памяти.
При этом процедура mark (p) запоминает в указателе p адрес начала области динамической памяти, а процедура release (p) очищает всю память, начиная с адреса p. Процедура mark обычно помещается в начало программы, release, наоборот, в конец.

процедуру: freemen (p, size), которая освобождает size байтов, начиная с адреса p. После освобождения памяти указатели автоматически не обнуляются и, фактически, указывают на несуществующую переменную. Поэтому рекомендуется присвоить всем высвободившимся указателям значения nil.

с особыми структурами переменных размеров, которые получили название динамические структуры данных (динамический список данных - ДСД). (Именно они представляют наибольший интерес для программистов).

объёмов данных. Они характеризуются следующими особенностями:
Для отдельных элементов структуры памяти выделяется в тот момент, когда в них появляется необходимость (а не сразу и не одним блоком, как для массивов);
Число элементов динамической структуры заранее не объявляется и может изменятся от нуля до некоторого значения, определяемого задачей;

быть разбросаны в памяти хаотическим образом;
Логическая последовательность элементов задаётся в явном виде с помощью одного или нескольких указателей, хранящихся в самих элементах. Как правило, каждый элемент, хранит своё значение и указатель на следующий элемент или на два соседних с ним элемента.

представляет собой запись, состоящую из двух частей. Первая часть – информационная, в ней хранятся данные, ради которых и создается список, вторая – указатель. Он отвечает за связь со следующим и, возможно, с предыдущим элементом списка. Список, в котором обеспечивается связь только со следующим элементом, называется односвязным или линейным.

узел;
объединить два (или более) линейных списка в один список;
разбить линейный список на два (или более) списка;
сделать копию списка;
выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах;
найти в списке узел с заданным значением в некотором поле.

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