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

Существует три основных типа структур данных: линейная, иерархическая и табличная.

Линейные структуры (списки данных, векторы данных)

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

Табличные структуры (таблицы данных, матрицы данных)

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

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

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

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

Его суть понятна из примера, представленного на рисунке.

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

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

1.2. Файлы и файловая структура

Единицы представления данных

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

Во многих случаях целесообразно использовать не восьмиразрядное кодирование, а 16-разрядное, 24-разрядное, 32-разрядное и более. Группа из 16 взаимосвязанных бит (двух взаимосвязанных байтов) в информатике называется словом. Соответственно, группы из четырех взаимосвязанных байтов (32 разряда) называются удвоенным словом, а группы из восьми байтов (64 разряда) —учетверенным словом.

Единицы измерения данных

Наименьшей единицей измерения является байт. Более крупная единица измерения — килобайт (Кбайт). Условно можно считать, что 1 Кбайт примерно равен 1000 байт. Условность связана с тем, что более удобно представление чисел в виде степени двойки и потому на самом деле 1 Кбайт равен 1024 байт. Однако всюду, где это не принципиально, с инженерной погрешностью (до 3 %) «забывают» о «лишних» байтах.

Более крупные единицы измерения данных образуются добавлением префиксов мега-, гига- тера~; в более крупных единицах пока нет практической надобности.

1 Мбайт - 1024 Кбайт = 1020 байт

1 Гбайт = 1024 Мбайт = 1030 байт

1 'Гбайт = 1024 Гбайт =1040 байт