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

Структурированные типы данных.

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

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

Если все элементы, образующие структуру, однотипны, то структура называется однородной, если элементы не однотипны – неоднородной.

Структура упорядочена, если между ее элементами определен порядок следования.

При прямом доступе каждый элемент структуры доступен пользователю в любой момент.

Если у структуры размер (длина, количество элементов) не может быть изменен, а фиксирован заранее, то ее называют статической.

Данные могут иметь следующие структуры:

Массивы, записи, списки, очереди, стеки, деревья.

Массив – упорядоченный набор однотипных элементов, число которых фиксировано.

Запись – обобщение массива, которая является неоднородной упорядоченной статической структурой прямого доступа.

Списки – некоторая ограниченная последовательность элементов.

Очередь – это последовательный список, в котором все дополнения вносятся в один конец, а доступ для выборки осуществляется к другому концу списка.

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

Деревья – любая древовидная структура данных, т.е. это множество узлов (вершин) вместе с множеством ребер (дуг), соединяющих пары различных вершин.

Хотя динамика и не является отличительной чертой языка Паскаль, все же существует возможность создавать динамические объекты и оперировать с ними. Динамический объект представляет собой область памяти без идентификатора. Для обращения к этой области заводится специальная ссылочная переменная, которая описывается в программе. Элементами множества значений ссылочного типа являются значения адресов оперативной памяти. Чаще всего динамические структуры состоят из объектов, являющихся записями из нескольких полей, одна или несколько из которых являются ссылками на такой же объект. Таким образом можно составлять цепочки или более сложные структуры ссылающихся друг на друга объектов. Размер таких структур ограничивается только объемом свободной памяти и может легко меняться при удалении и создании объектов, что и определило основную область их применения – моделирование нелинейных последовательных структур данных (например, деревьев). Однако, несмотря на кажущееся отсутствие недостатков, динамические структуры тоже имеют свои минусы. Главный из них – отсутствие наглядности программы – вызывает трудности при создании особо крупных структур.

Представление абстрактных типов данных (АТД) в Паскале

Моделирование абстрактных типов данных на конкретных структурах данных Паскаля не является однозначным. Практически любой АТД может быть эффективным образом представлен как на массиве, так и на файле или на динамической структуре, но чаще всего конкретное представление диктуется особенностью доступа к элементам рассматриваемого абстрактного типа.

Стек

Стек – структура данных, представляющая собой последовательность элементов. Добавление и удаление элементов происходит только с одного конца последовательности, т.е. при изменении структуры предыдущая последовательность остается неизменной. Это значит, что по идее идеальной структурой представления для стека должен быть файл. Действительно, добавление элементов происходит только в конец файла, однако при удалении последнего элемента придется два раза переписывать весь файл, причем с подсчетом элементов. Это главный недостаток файла – для удаления компоненты требуется слишком много действий. С другой стороны время удаления элементов из файла не зависит ни от положения этого элемента в файле, ни от количества удаляемых элементов – это плюс! Стек на массиве позволяет уравнять время выполнения действий по добавлению и удалению элемента. Нужно всего лишь хранить в отдельной переменной длину последовательности и увеличивать ее или уменьшать соответственно при добавлении и удалении. Единственный недостаток такого представления – недостаток самого массива в Паскале – ограниченный размер, приводящий к переполнению стека. Использование динамических структур полностью решает эту проблему. В этом случае при добавлении и удалении элемента модифицируется только ссылка на начало цепочки динамических объектов, что снижает до минимума количество используемых для действия операторов. При этом размер стека почти неограничен.

Очередь, дек

Очередь – структура данных, как и стек представляющая собой последовательность элементов. Добавление элементов происходит с одной стороны последовательности, удаление – с другой. Дек – двусторонняя очередь, т.е. и добавление и удаление осуществляется с обеих сторон. Представление на файле этих АТД имеет такой же характер и «преимущества» как и у стека, т.е. переписывание файла происходит во всех случаях кроме добавления компоненты в его конец. Представление очередей и деков на массиве отличается тем, что последовательность элементов может «перемещаться» по массиву, следовательно, чтобы последовательность не выскочила за границы, нужно границы соединить вместе (зациклить). При этом индекс элементов (и первого и последнего) вычисляется как (x mod n), где n – размер массива. Проблемы все те же – возможность переполнения. Реализация на динамике использует ту же особенность (цикличность) и лучше всего представляется в виде кольцевого двунаправленного списка, о котором речь пойдет ниже.

Линейный список

Линейный список – одна из тех структур данных, которая если не приравнивается, то хотя бы ассоциируется с динамическими структурами. Он представляет собой упорядоченное множество (возможно пустое), в котором добавление и удаление элементов может происходить на любом месте списка. Элементы списков чаще всего представляют в виде записи, состоящей из поля информационной части и одного или двух полей-ссылок на другие узлы. Списки имеют последовательную структуру, т.е. для того чтобы перейти к какому-либо элементу, нужно пройти все элементы, предшествующие искомому. Причем если каждый элемент имеет ссылку только на следующий за ним элемент, то каждый такой проход нужно начинать с «головы» списка. Этот недостаток устраняется либо зацикливанием списка (ссылка последнего элемента указывает на первый) – в этом случае вообще теряются понятия начала и конца списка – либо использованием второй ссылки (на предыдущий элемент), чтобы можно было перемещаться в обе стороны. Представление списка на массиве является простым моделированием на массиве оперативной памяти. Элементом списка опять будет запись, состоящая из поля информационной части и поля, хранящего индекс следующего элемента в массиве (аналог ссылки). Для того чтобы смоделировать «кучу» свободной памяти, из которой берется память под новые объекты, создается список свободных элементов.

Линейные списки Pascal – курсовая работа

Деревья

Дерево – множество, состоящее из элемента, называемого корнем, и конечного (возможно пустого) множества деревьев, называемых поддеревьями данного дерева. Дерево, так же как и список, реализуется прежде всего на динамических структурах, т.е. узел дерева содержит два поля-ссылки – на левое и правое поддерево для двоичного дерева и на брата и старшего сына для дерева общего вида. Дерево уже не является линейной структурой, поэтому представление деревьев на последовательной памяти (файлах) представляет собой определенную проблему. Однако все данные хранятся во внешней памяти в виде файлов, поэтому решение этой проблемы необходимо. Тем не менее, сразу стоит оговориться, что это представление не будет в полной мере реализацией АТД дерева на структуре данных файле, поскольку требуется лишь создать обратимое отображение дерева в файл – никаких операций с файлом-деревом совершаться не будет. Создадим новый тип узла дерева (он станет компонентом файла) – запись информационного поля и поля, хранящего число поддеревьев данного узла. В файл будем последовательно записывать каждый узел так, чтобы поддеревья записывались после своего корня. Обратная операция производится с использованием рекурсии. Читаем из файла узел дерева, создаем его и ссылки на его поддеревья (столько, сколько указано в соответствующем поле). Затем для всех указанных поддеревьев повторяем ту же процедуру.

Дерево Pascal – лабораторная работа

Множества и деревья

Бинарное дерево называется упорядоченным, если для каждого его узла, имеющего поддеревья, корень больше левого поддерева и меньше правого. Используя упорядоченные бинарные деревья, можно легко реализовать математическое множество данных, для которого существует отношение порядка. При добавлении элемента нужно сохранить свойство упорядоченности, поэтому у добавляемого элемента существует единственное место в дереве (конечно, если такой элемент еще не присутствует в дереве). Проверка наличия элемента в дереве осуществляется тем же способом – переход от узла к узлу происходит по принципу максимального приближения к искомому значению. Если на том месте, где должен находиться искомый элемент, отсутствует поддерево, значит можно утверждать, что такого элемента нет во множестве.

труктурированные типы данных, такие, как массивы, множества, записи, представляют собой статические структуры, так как их размеры неизменны в течение всего времени выполнения программы. Часто требуется, чтобы структуры данных меняли свои размеры. Такие структуры данных называются динамическими. К динамическим структурам относятся списки (однаправленные, двунаправленные, кольцевые однаправленные и кольцевые двунаправленные), стеки, деки, очереди, деревья и другие.

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

Для реализации некоторой динамической структуры на языке программирования Pascal необходимо:

отобразить ее на одну из структур языка программирования Pascal,

написать на Pascal процедуры выполнения типовых операций.

Заметим, что описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задачи.

Каждую компоненту любой динамической структуры можно представить как запись, содержащую, по крайней мере, два поля: одно поле типа указатель на следующую компоненту, а второе поле - для размещения данных - принято называть информационным полем или полем данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной любого простого типа, массивом, множеством или записью.

Дата добавления: 2015-04-24