Список с дескриптором обеспечивает через дескриптор списка доступ, как к первому, так и к последнему элементу односвязного списка. Кроме того, в дескрипторе постоянно хранится текущий размер списка. Однако в некоторых операциях (приводящих в результате своей работы к изменению размера списка), определённых на таком списке необходимо предусмотреть постоянное обновление полей дескриптора списка
Древовидная структура используется во многих структурах данных. Существуют деревья с двумя ветвями (бинарное дерево) и деревья с большим количеством ветвей. В основном применяют деревья с большим количеством ветвей, но для однородности структуры узлов памяти деревья с большим количеством ветвей представляются форме бинарных деревьев. Пример такой структуры представлен на рисунке.
Дерево.
Структура
указателей
Структура
узла
Рассмотренный выше двумерный массив при необходимости можно представить в виде древовидной структуры, показанной на рисунке.
В языке программирования Lisp, как программы, так и данные представляются в виде древовидных структур, и в этом смысле между ними нет существенных различий.
Графовая структура представляет собой структуру наиболее общего вида. Рассмотренные выше списочные и древовидные структуры можно рассматривать как частный случай графовой структуры. Графовая структура, представленная на рисунке ниже содержит циклы, поэтому при обработке такой структуры данных, если не быть в достаточной степени внимательным, существует опасность попасть в бесконечный цикл.
Рис. 1. Графовая структура. Рис. 2. Граф сети авиалиний (1 Мм = 1000 км).
Рис. 3. Структура представления узлов и дуг графа.
Рис. 4. Пример представления графа сети авиалиний.
Существуют различные способы представления графовой структуры в памяти ЭВМ. Например, в узлах и дугах графа, показанного на рисунке 1, указаны конкретные значения данных. Один из способов представления узлов и дуг этого графа в памяти ЭВМ показан на рис. 2. На рис. 4 приведен пример представления графа сети авиалиний, изображенного на рис. 2.
Рассмотренные выше структуры данных могут быть представлены в ЭВМ различными способами. Однако усложнение структур представления данных в памяти вызывает усложнение программ обработки данных. Особенно усложняются программы, реализующие операции дополнения и изменения структуры данных. В этом случае целесообразнее использовать по возможности более простую структуру представления даже в ущерб объему памяти. Именно такой принцип используют реляционные базы данных.
Абстракция данных - средство описания процессов обработки данных, в котором существенным являются объекты и определённые на них операции.
Абстракции данных обеспечивают возможность расширения языка программирования новыми типами данных. Новые типы данных должны включать в себя абстракции как через параметризацию так и через спецификацию. Абстракция через параметризацию может быть осуществлена точно так же, как и для процедур, - использованием параметров там, где это имеет смысл. Абстракция через спецификацию достигается за счет того, что мы представляем операции как часть типа. Абстракции данных - наиболее важный метод в проектировании программ они позволяют отложить окончательный выбор структур данных до момента, когда эти структуры станут нам достаточно ясны.
Список - это последовательность элементов, принадлежащих одному множеству элементов, называемому алфавитом. Вид алфавита определяется особенностями решаемой задачи. Он может состоять из символов, строк, целых чисел, структур данных или подсписков переменной длины.
Имя списка будем обозначать строчной латинской буквой, имена элементов списка - прописными латинскими буквами.
Например: t = (A B K J U). Здесь t - список, содержащий элементы A, B, K, J, U.
Список - это структура непоименованных данных. Он имеет имя, однако отдельные элементы списка имен не имеют.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.