Для большего удобства вы можете прочитать эту статью на 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. }
Свойства массива
Из определения массива мы можем вывести следующие свойства массива:
- Данные, хранящиеся в массиве, относятся к одному типу, т. е. занимают одинаковый объем памяти.
- Все элементы массива хранятся один за другим, т. е. непрерывно.
- Доступ ко всем элементам возможен, если известно только расположение первого элемента этого массива.
- Имя массива на самом деле является указателем на расположение первого элемента в массиве.
Операции над массивом
Теперь, когда я утомил вас теорией массива, давайте поговорим о разных вещах, которые вы можете делать с массивом.
Посмотрите вверх
Поиск — это причудливый способ обращения к элементу в массиве или любой другой структуре данных. В массиве вы можете получить доступ к любому элементу напрямую, если знаете адрес первого элемента этого массива. Рассмотрим этот код 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