|
Статический массив. Структура, его преимущества и недостаткиКурс по структурам данных: https://stepik.org/a/134212 Мы начинаем знакомиться непосредственно со структурами данных. На этом занятии затронем самую простую, но наиболее распространенную – статический массив. Давайте представим, что нам в программе требуется сохранить значения функции косинус в диапазоне от 0 до 2π с шагом 0,1. Как это сделать? Как раз для этого случая очень хорошо подходит статический массив длиной в 64 элемента:
Каждый элемент массива хранит строго определенное значение функции. Или такая задача. Нам нужно хранить состояния игрового поля «Крестики-нолики» размером 3х3 элементов. Опять же удобно воспользоваться статическим массивом длиной в 9 элементов:
Или такая. Нам нужно в программе сохранять фамилии студентов. Опять же, выбираем статический массив, например, длиной в 50 элементов (из предположения максимально длинной фамилии в 50 символов) и посимвольно записываем нужные буквы, получаем строку:
Все это примеры, где целесообразно использовать статические массивы. Давайте теперь поближе познакомимся с этой структурой данных, посмотрим на ее преимущества и недостатки. Структура статического массиваПервый важный момент. Все элементы статического массива должны иметь единый тип данных. Например, только целые числа, или только вещественные числа, или только символы и так далее. Не предполагается в одном и том же массиве сохранять разные типы данных.
Второй важный момент. Длина статического массива (то есть, число его элементов) задается фиксированным значением и не меняется.
Собственно, поэтому данный массив и называется статическим. Третий важный момент: последовательное распределение элементов статического массива в памяти компьютера. То есть, все элементы статического массива располагаются строго друг за другом (без каких-либо пропусков), начиная с некоторого начального адреса (номера ячейки памяти). Давайте предположим, что элементы массива имеют тип int и этот тип занимает 4 байта. Тогда получим следующую структуру статического массива:
Мы здесь полагаем, что массив располагается с 1000-й ячейки в памяти компьютера и занимает: size = n ∙ 4 байт В общем случае, если обозначить через k размер одного элемента в памяти, то выражение примет более общий вид: size = n ∙ k байт Доступ к отдельным элементам статического массиваОтлично, с общей структурой массива, я думаю в целом понятно. Давайте теперь посмотрим, как можно обращаться к отдельным элементам этого массива. Мы всегда знаем, с какого адреса хранятся данные в массиве. Эту информацию нам дает имя массива. Например, если имя массива ar, то в языках программирования, этот ar, как правило, есть не что иное, как ссылка на первый элемент массива. То есть, в данном случае ссылка ar хранит адрес 1000 и через него работает с представленным массивом. Итак, зная начальный адрес массива ar и размер каждого его элемента k, мы легко можем обратиться к первому элементу. Это первые k байт (в нашем примере первые 4 байта), начиная с адреса: ar + 0 ∙ k Для доступа ко второму элементу нам нужно сместиться на k байт, то есть, второй элемент хранится по адресу: ar + 1 ∙ k По аналогии для третьего элемента: ar + 2 ∙ k И так далее для произвольного i-го: ar + (i – 1) ∙ k Обратите внимание на множители перед k. Фактически, это порядковые номера элементов в массиве, только начинаются с нуля, а не с единицы. Эти числа получили названия индексов элементов массива. И если нам нужно получить значение какого-либо элемента с индексом j, то вычисляется адрес элемента: p_j = ar + j ∙ k и берутся k байт, начиная с этого адреса p_j, то есть: p_j, p_j + 1, …, p_j + k -1 Как правило, операция доступа к отдельному элементу массива, в языках программирования записывается по следующему синтаксису: - при считывании значения: value = ar[j] - при записи значения: ar[j] = value То есть, пишется имя массива и затем в квадратных скобках указывается индекс элемента, к которому идет обращение. Очевидно, здесь мы имеем константное время выполнения операций считывания и записи значений, а значит, в терминах О большого их сложность составляет: O(1) И это главное преимущество данной структуры. Она обеспечивает мгновенный доступ к любому элементу. Добавление элементов в массивНо не все так радужно. Помимо чтения и записи данных в определенный элемент массива, коллекции данных должны обеспечивать операции вставки и удаления. Как это работает в случае со статическими массивами? Начнем с операции вставки. Допустим, мы определили массив длиной в 10 элементов, но записали в него только первые шесть значений:
Если нам нужно добавить следующее седьмое значение, то делается это элементарно: ar[6] = 7 Всегда помним, что индекс 7-го элемента равен 6, т.к. отсчет идет с нуля. Но, если вставить нужно не в конец, а, например, в начало этого массива, то придется сначала сдвинуть все элементы вправо:
А, затем, первому элементу присвоить новое значение: ar[0] = 0
Какова вычислительная сложность такого алгоритма с точки зрения О большого? В общем случае примем длину массива n элементов. Тогда в наихудшем случае нужно будет сдвинуть все n элементов этого массива для вставки нового. То есть, сложность составляет: O(n) Удаление элементов из массиваПо аналогии выполняется операция удаления элементов из массива. Опять же, если нам нужно избавиться от какого-либо последнего элемента, то это можно сделать очень быстро, достаточно уменьшить счетчик его актуальных значений:
Счетчик k мы вводим в программе сами и он работает совместно, но независимо от массива. То есть, при удалении одного значения мы его уменьшаем на 1, а при добавлении одного элемента – увеличиваем на 1. В результате знаем, сколько в массиве актуальных значений, которые содержат информационные данные. При этом сами значения всегда должны следовать с самого начала. Но это удаление последнего. А что если удалить нужно самый первый? Тогда придется сдвинуть все остальные элементы влево:
В общем случае объем вычислений с точки зрения О большого также будет составлять: O(n) То есть, операции вставки и удаления элементов в статическом массиве имеют сложность O(n), где n – число элементов в массиве. В итоге получаем следующую таблицу вычислительной сложности для статического массива:
Преимущества и недостатки статического массиваИтак, подводя итог этого занятия по статическим массивам, еще раз отметим преимущества и недостатки этой структуры данных: Достоинства статического массива:
Недостатки статического массива:
На следующем занятии мы продолжим эту тему и увидим, как объявляются статические массивы в разных языках программирования и посмотрим на реализации алгоритмов удаления/вставки элементов. Курс по структурам данных: https://stepik.org/a/134212 Видео по теме |
