Массив (Array)

Массив — составная структура данных, состоящая из элементов одного типа данных. Массив располагается в памяти в виде непрерывного участка памяти разделенного на блоки одинакового размера. В каждом блоке находится отдельные элементы, блоки одинакового размера из-за того, что в них хранятся значения одинакового типа с постоянным размером.

Для доступа к элементам массива используется селектор и индекс.

Массив предоставляет произвольный доступ, что означает обращение к любому элементу массива за одинаковое время независимо от длины массива, или, по другому, скорость доступа на чтение и запись к любому элементу массива равна $\mathcal{O}(1)$.

Одинаковая скорость доступа к элементам массива обеспечивается за счёт возможности вычисления позиции элемента в памяти на основе индекса. Для этого каждый элемент массива должен быть одинакового размера. Например, в случае если массив состоит из 4-байтовых чисел и индексация начинается с нуля, то положение элемента относительно начала массива будет равно index * 4. Так как вычисление любого адреса сводится к одному умножению, то сложность вычисления не зависит от длины массива. Формула вычисления адреса элемента массива при индексации от нуля:

$$a_i=a_0+i\ast s$$

• $a_0$ — адрес первого компонента массива
• $i$ — индекс элемента
• $s$ — размер одного элемента

Сравнение массивов и записей.

Ссылки

• Грокаем алгоритмы. Адитья Бхаргава. Питер. 2018. Глава 2. Сортировка выбором. Массивы и связанные списки
• Алгоритмы и структуры данных. Новая версия для Оберона. Никлаус Вирт. ДМК Пресс. 2010. Глава 1. Фундаментальные структуры данных. 1.6. Представление массивов, записей и множеств

Ссылки на эту заметку

• Использование остатка от деления для зацикливания перебора массива
• Линейный поиск (Linear search)
• Отношение между структурами данных и абстрактными типами данных
• Произвольный доступ
• Селектор элементов массив и списков
• Список (АТД)
• Сравнение массивов и записей
• Структуры данных (Data structures)

Эта заметка на GitHub

Обсудить на форуме