Упорядочение структур данных

Иерархические структуры данных

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

В иерархической структуре адрес каждого элемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу. Вот, например, как выглядит путь доступа к команде, запускающей программу Калькулятор (стандартная программа операционной системы семейства Windows): Пуск / Программы / Стандартные / Калькулятор.

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

Списочные и табличные структуры являются простыми. Ими легко пользоваться, поскольку адрес каждого элемента задается числом (для списка), двумя числами (для двумерной таблицы) или несколькими числами для многомерной таблицы. Они также легко упорядочиваются. Основным методом упорядочения является сортировка. Данные можно сортировать по любому избранному критерию: алфавиту, возрастанию порядкового номера или какого-либо иного параметра.

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

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

Адресные данные. Если данные хранятся в организованной структуре, то каждый элемент данных приобретает новое свойство (параметр), который можно назвать адресом. Работать с упорядоченными данными удобнее, но при этом их объём увеличивается, поскольку адреса элементов данных – тоже данные, и их тоже надо хранить и обрабатывать.

Дата добавления: 2014-12-16