Для большего удобства вы можете прочитать эту статью на Idiomatic Programmers, там я размещаю все свои новые статьи.

Что такое массив?

Учебное определение массива — это набор данных, которые имеют одинаковую природу и хранятся в непрерывном порядке. Массив – это систематизированное расположение похожих объектов, обычно в виде строк и столбцов.

Что вообще означают эти слова? Начнем с определения того, что такое структура данных. В компьютерных науках структура данных — это формат организации, управления и хранения данных, обеспечивающий эффективный доступ и модификацию. Точнее, структура данных — это набор значений данных, взаимосвязей между ними и функций или операций, которые можно применять к данным. С точки зрения программирования, класс в языке программирования C++ можно рассматривать как структуру данных. Если вы понятия не имеете, о чем я говорю, не беспокойтесь, в будущем вы узнаете, что большинство наверное в моем блоге xD.

По сути, вы храните данные в структуре данных, а поскольку массив — это структура данных, вы можете хранить данные в массиве. В нашем определении массива это еще одна фраза о данных подобного характера. Это сводится к тому, какие данные хранятся в памяти в вашем случае RAM. И каждый тип данных занимает фиксированный объем памяти, например: в большинстве современных компьютеров целое число занимает 4 байта памяти (или 32 бита), а число с десятичной точкой занимает ровно 8 байтов (или 64 бита). Когда два данных имеют одинаковую природу, это означает, что они относятся к одному типу и, следовательно, занимают одинаковый объем памяти в ОЗУ.

Еще одна особенность массива заключается в том, что данные хранятся непрерывно, это означает, что в памяти или ОЗУ все данные будут храниться один за другим. Чтобы понять эту концепцию, рассмотрите эту диаграмму.

Изображение выше представляет собой представление оперативной памяти и того, как массив хранится в памяти. Учтите, что массив начинается с ячейки памяти 1000 (байт), а также предположим, что в этом массиве хранятся целые числа, что означает, что каждое число будет занимать 4 байта в памяти. Таким образом, первое число будет храниться от 1000 до 1004, как вы можете видеть на диаграмме, то, что хранится в непрерывном порядке, означает, что в массиве следующее число будет храниться от ячейки памяти от 1004 до 1008, а следующее от 1008 до 1012. и так далее. Последний элемент в массиве всегда равен NULL, это специальный символ, используемый компьютером, который сообщает ЦП, что это конец этой структуры данных, вам не нужно смотреть дальше.

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

Ниже приведена инициализация массива C++:

void main(){ int arr[10]; // this will create space // for an array of length 10 in the memory. }

Свойства массива

Из определения массива мы можем вывести следующие свойства массива:

  1. Данные, хранящиеся в массиве, относятся к одному типу, т. е. занимают одинаковый объем памяти.
  2. Все элементы массива хранятся один за другим, т. е. непрерывно.
  3. Доступ ко всем элементам возможен, если известно только расположение первого элемента этого массива.
  4. Имя массива на самом деле является указателем на расположение первого элемента в массиве.

Операции над массивом

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

Посмотрите вверх

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

void main(){ int arr[] = [1,2,3,4,5];
 cout << arr[3]; // This will print the 4th element 
// of the array because array index 
// starts from 0 and ends at n-1 }

Обход

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

void main(){ int arr[] = [1,2,3,4,5];
 int i = 0;
 int size = 5;
 while(i < size){
 cout << arr[i];
 i++;
 }
 }

Searching

Существует два наиболее распространенных способа или алгоритма поиска и элемента в массиве.

Линейный поиск

Этот алгоритм постулирует поиск элемента путем просмотра каждого элемента в этом массиве до тех пор, пока не будет найден требуемый элемент. Рассмотрим этот код C++.

int linearSearch(int arr[], int item){ int i = 0; while (arr[i] != '/0'){ if (arr[i] == item){ return i; } } return -1; }

Условие в цикле while arr[i] != '/0' относится к тому факту, что последним элементом каждого массива является NULL, который при преобразовании в стандарты ASCII становится 0.

Бинарный поиск

В отличие от линейного поиска, двоичный поиск работает путем деления массива пополам на каждой итерации. Рассмотрим этот код.

int binarySearch(int arr[], int l, int h, int item){
 while(l<h){
 int m = (h+l)/2;
 if (arr[m] == item){ return m; }
 else if (arr[m] < item){
 h = m-1; } else {
 l = m+1; }
 return -1; }

В приведенном выше коде вы видите на два параметра больше, чем при линейном поиске. int l и int h, l — самый низкий индекс массива, а h — самый высокий индекс. Бинарный поиск имеет возможность искать элемент в массиве из 1 миллиона всего за 20 шагов или математически записывать 2 (размер), в отличие от линейного поиска, который занял бы 1 миллион шагов (в худшем случае).

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

Спасибо.

Первоначально опубликовано на https://idiomaticprogrammers.com