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

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

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

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

Если элементы списка одной длины, структура называется вектором данных, разделители не требуются. При длине одного элемента — d, зная номер элемента — n, его начало определяется соотношением d (n -1).

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

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

Поиск, аналогично линейной структуре, осуществляется по разделителям. Если элементы таблицы одной длины, структура называется матрицей данных, разделители в ней не требуются. При длине одного элемента — d, зная номер строки — m и номер столбца n, a также строк и столбцов М, N, найдем адрес его начала:

d [N(m – 1) + (n – 1)].

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

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

Иерархическую структуру образуют, например, почтовые адреса.

Адрес одного из домов, расположенных, к примеру, на улице Большая Садовая, может выглядеть следующим образом:

Россия\Ростовская область\Ростов\ул. Большая Садовая\д. 1.

Линейная и табличная структуры более просты, чем иерархические, но если в линейной структуре появляется новый элемент, то упорядоченность сбивается. Например, если в списке студентов появляется новый человек, то расположенный по алфавиту список нарушается.

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