Презентация на тему: «Динамические структуры данных»


Чтобы посмотреть презентацию с оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов:

Новиков Алексей КонстантиновичПреподаватель СПК МГППУПрограммирование на Delphi Занятие 5 Динамические структуры данных Указатель Обычно переменная хранит некоторые данные. Однако существуют переменные, которые ссылаются на другие переменные. Такие переменные называются указатели.Указатель – это переменная, значением которой является адрес другой переменной или структуры данных. Более точно определить указатель как адрес 1-го байта области памяти, которую занимает переменная. Типизированный указатель – это указатель на переменную определенного типа, например, целого, строкового или типа массива. Нетипизированный – это адрес первого байта области памяти, в которой может размещаться любая информация вне зависимости от ее типа.Var Имя:^Тип; Где имя – это имя переменной – указателя; тип – это тип переменной, на которую указывает переменная – указатель, значок ^ показывает, что объявляемая переменная является указателем. Var Имя:^Тип; Где имя – это имя переменной–указателя; тип – это тип переменной, на которую указывает переменная–указатель;значок ^ показывает, что объявляемая переменная является указателем. Примеры объявления указателей Var P1:^integer; {указатель на переменную целого типа} P2:^real; {указатель на переменную вещественного типа} P3:^string; {указатель на строку} P4:pointer; {нетипизированный указатель} Тип pointer совместим со всеми типами указателей.Тип переменной, на которую ссылается указатель, называют типом указателя. P1:^integer, то говорят «P1 – указатель целого типа».В начале работы программы переменная – указатель «ни на что не указывает». В этом случае говорят, что значение указателя равно nil. Идентификатор nil можно использовать в инструкциях присваивания и в условиях. Например, если переменные P1 и P2 объявлены как указатели, то инструкция P1:=nil; устанавливает значение переменной, а инструкция if P2=nil then ShowMessage (‘указатель P2 не инициализирован!’);проверяет, инициализирован ли указатель P2. Указателю можно присвоить значение другого указателя при условии, что они являются указателями на переменную одного типа.Указатель можно использовать для доступа к переменной, адрес которой содержит указатель. Пример Например, если P указывает на переменную i, то в результате выполнения инструкции P^:=5; значение переменной i будет равно 5. В приведенном примере значок ^ показывает, что значение 5 присваивается переменной, на которую указывает переменная – указатель. Динамическая переменная Динамической переменной называется переменная, память для которой выделяется во время работы программы. Так как бывают два разных типа указателей, то в соответствии с ними бывают две разные процедуры создания динамических переменныхдля типизированных указателей – new (p);для нетипизированных указателей – getmem (p, size).Размер size не может превышать 54 килобайта. При выполнении процедуры new в динамической памяти выделяется столько байтов сколько требуется для хранения переменной заданного типа. Для нетипизированных указателей в памяти выделяется size байтов, а указатель получает значение адреса первого байта выделенной области.Обратите внимание – динамические переменные не имеют собственного имени, в процедурах выделения памяти задается не имя переменной, а имя указателя. При выделении динамической памяти полезными являются следующие функции:memavail – возвращает общий размер свободной памяти в байтах;maxavail – возвращает размер наибольшего непрерывного участка свободной памяти. Процедуры «уничтожения динамических переменных» Для типизированных указателей можно использовать:dispose (p) – освобождает память, на которую указывал p;mark (p) и release (p) – эти две процедуры используются только вместе и позволяют сразу очистить целую область памяти.При этом процедура mark (p) запоминает в указателе p адрес начала области динамической памяти, а процедура release (p) очищает всю память, начиная с адреса p. Процедура mark обычно помещается в начало программы, release, наоборот, в конец. Процедуры «уничтожения динамических переменных» В случае нетипизированных указателей можно использовать только одну процедуру: freemen (p, size), которая освобождает size байтов, начиная с адреса p. После освобождения памяти указатели автоматически не обнуляются и, фактически, указывают на несуществующую переменную. Поэтому рекомендуется присвоить всем высвободившимся указателям значения nil. Динамические переменные используются 1) для работы с массивными больших размеров;2) для работы с особыми структурами переменных размеров, которые получили название динамические структуры данных (динамический список данных - ДСД). (Именно они представляют наибольший интерес для программистов). Особенности ДСД Динамические списки данных были предложены для быстрой обработки больших объёмов данных. Они характеризуются следующими особенностями:Для отдельных элементов структуры памяти выделяется в тот момент, когда в них появляется необходимость (а не сразу и не одним блоком, как для массивов);Число элементов динамической структуры заранее не объявляется и может изменятся от нуля до некоторого значения, определяемого задачей; Память, занимаемая структурой, не представляет собой непрерывную область, т.е. элементы могут быть разбросаны в памяти хаотическим образом;Логическая последовательность элементов задаётся в явном виде с помощью одного или нескольких указателей, хранящихся в самих элементах. Как правило, каждый элемент, хранит своё значение и указатель на следующий элемент или на два соседних с ним элемента. Связанный список Самый распространенный ДСД – связанный список. Каждый элемент списка (узел) представляет собой запись, состоящую из двух частей. Первая часть – информационная, в ней хранятся данные, ради которых и создается список, вторая – указатель. Он отвечает за связь со следующим и, возможно, с предыдущим элементом списка. Список, в котором обеспечивается связь только со следующим элементом, называется односвязным или линейным. Типовые действия со списками: добавить новый узел непосредственно перед заданным узлом;удалить заданный узел;объединить два (или более) линейных списка в один список;разбить линейный список на два (или более) списка;сделать копию списка;выполнить сортировку узлов списка в возрастающем порядке по некоторым полям в узлах;найти в списке узел с заданным значением в некотором поле. Стек, очередь, дек Очень часто встречаются линейные списки, в которых добавления и удаления производится только в первом или последнем узлах. Это:Стек – линейный список, в котором все добавления и удаления делают в одном конце списка;Очередь – линейный список, в котором все добавления производятся на одном конце списка, а все удаления делаются на другом конце;Дек – линейный список, в котором все добавления и удаления делаются на обоих концах списка.

Приложенные файлы

  • ppt file109
    Размер файла: 63 kB Загрузок: 2