Вы здесь

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

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

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

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

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

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

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

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

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

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

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

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

Казахстан\ВКО\Усть-Каменогорск\ул. Солнечная\д. 10.

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

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

Предмет: