Структуры хранения данных в оперативной памяти

Для размещения логических записей в оперативной памяти исполь­зуются линейные и нелинейные структуры хранения данных.

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

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

В массивах отсутствуют операции добавления и удаления элементов; они могут лишь модифицироваться. Одномерный массив называется вектором, двухмерный - матрицей (каждый элемент в произвольной матрице определен двумя индексами). В принципе массив может иметь любую размерность.

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

Очередь, как и стек, является линейной структурой переменного размера, причем исключение элементов допускается лишь с ее начала. Напротив, включение элементов производится только с ее конца. Это значит, что информация в очередях обрабатывается по принципу «первым пришел - первым ушел» (first input, first output, FIFO). Очередь также относится к структурам с ограниченным доступом.

Таблица представляет собой линейную структуру переменного раз­мера; ее элементами являются строки (записи), включающие набор атрибутов (полей). В таблице имеется возможность непосредственного обращения к любой из ее строк по значению так называемого ключа (ключевого поля).

Отношения между объектами во многих реальных задачах носят не­линейный характер, поэтому невозможно обойтись только линейными структурами хранения. Это могут быть отношения, определяемые ло­гическими условиями, а также отношения типа «один ко многим» или «многие ко многим». К нелинейным структурам принадлежат деревья, графы и списковые структуры.

Древовидные структуры используются для описания отношения «один ко многим»; особенно часто они возникают при создании всякого рода справочников, ускоряющих доступ к данным (рис. 28). Деревья относятся к разряду структур, которые удобно строить в динамической памяти с использованием указателей.

Отношения «многие ко многим» носят более универсальный характер и описываются структурами графов. Граф в общем виде состоит из ряда вершин и ребер, связывающих пары вершин (рис. 29). Вершины графов описывают определенные объекты, а ребра соответствуют отношениям между ними. Модель данных, имеющую вид графа, называют сетью.

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

Для отображения древовидных структур в памяти ЭВМ используют связные списки. Каждый элемент такого списка состоит из поля и одного или нескольких указателей; поле описывает один из узлов дерева, а указатели - связи данного узла.

Рис. 30. Пример списковой структуры

При организации списков используют структуры, относящиеся к ти­пу записей. Они состоят из двух частей: информационной (содержащей собственно данные) и ссылочной (содержащей указатель на следующий элемент списка). Так, на рис. 30 Dl, D2 и т.д. - это данные; чтобы по­лучить к ним доступ, достаточно хранить в памяти адрес начала списка «nach».

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

Рис. 31. Двоичное дерево и его представление с помощью списковых структур памяти

Рис. 32. Пример группировки элементов данных

Структура данных, любой элемент которой сам может являться спи­ском, называется списковой. При организации таких структур выделяют объекты, записи о которых становятся элементами основного списка. Все остальные объекты группируются в подсписки второго уровня, ответвляющиеся от тех элементов основного списка, с которыми они находятся в определенной логической связи. От каждого элемента под­списка второго уровня может ответвляться подсписок третьего уровня и т.д. (рис. 31, 32).

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