Структуры данных.

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

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

Указатели. Указатель – это ячейка (или блок ячеек), содержащий адрес другой ячейки памяти. Применительно к структурам данных указатели используются для записи адресов элементов данных. Таким образом, элемент данных может храниться в какой-либо ячейки памяти, а адрес этой ячейки – в указателе, при помощи которого можно позже получить эти данные. То есть значение указателя сообщит нам, где искать данные («указатель указывает на данные»).

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

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

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

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

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

Для определения конца связного списка используется пустой указатель (NIL), который является просто определенного вида набором битов и находится в последней записи, указывая, что за ним в списке более нет элементов, пример, если мы условимся никогда не хранить элементы списка по адресу 0; значение 0 никогда не будет являться разрешенным значением указателя, и этому его можно использовать как пустой указатель.

На рис. 3.11 отдельные блоки памяти, в которых хранятся элементы связного списка, представлены в виде прямоугольников. Строение каждого прямоугольника (блока памяти) обозначено надписями над ним. Указатели представлены стрелками, идущими от самого указателя к адресу, на который тот указывает. Для прохождения списка нужно последовать указателю головы — так мы найдем первую запись. Далее необходимо следовать указателям, хранящимся в записях, и по ним переходить от элемента к элементу до достижения пустого (NIL) указателя.

Рис. 3.12. Структура связного списка.

Теперь вернемся к вопросу удаления и добавления элементов в список. Использование указателей устраняет необходимость перемещения имен из одной ячейки памяти в другую, возникающую при хранении списка в одном связном блоке. Удалить имя можно, изменив один указатель. Это означает, что указатель, который ранее указывал на удаленное имя, изменяется и указывает теперь на имя, следующее за удаленным (рис. 3.13). Тогда при обработке списка удаленное имя пропускается.

Рис. 3.13. Удаление записи из связного списка.

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

Рис. 3.14. Добавление записи в связный список.

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

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

Деревья. Эта структура данных отражает принцип организации типичных компаний. В такой структуру президент находится на вершине, от которой отходят линии к вице-президентам, и т.д. Чтобы дать интуитивное определение дерева накладывает ограничение, состоящее в том, что ни один сотрудник компании не подчиняется двум разным начальникам. То есть разные ветви организации не сливаются на нижнем уровне.

Рис. 3.15. Структура дерева.

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

Бинарное дерево – дерево, где у каждого узла может быть максимум два потомка. Бинарные деревья обычно хранятся в памяти при помощи связной структуры, похожей на связные списки. Каждая запись (или узел) дерева состоит из трех компонентов: 1) данные, 2) указатель на первого потомка узла и 3) указатель на второго потомка узла.