Основные структуры данных

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

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

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

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

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

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

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

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

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