Массивы (Arrays)
Массивы — это структура данных для хранения элементов. Элементами могут быть целые числа, строки, объекты и т.д. Все элементы хранятся непрерывно, т.е. в соседних участках памяти. Если понадобится добавить новый элемент в массив, а места под него рядом не окажется, то придётся запросить другой блок памяти.
Массивы существуют во всех языках программирования и используются в качестве основы для большинства других структур данных.
Создание массива
Количество элементов в массиве определяется разработчиком при его создании. Кроме этого необходимо указать тип элементов, которые будут входить в массив.
Если создать массив, который может содержать 15 элементов, то при получении 16-го нужно будет создавать новый массив. При этом не стоит создавать массив, например, на 1 000 000 элементов, так сказать с запасом. Причина этого в том, что он будет занимать много места в памяти. Ведь память резервируется для хранения 1 000 000 элементов, даже если по факту элементов будет всего 15. И эту память нельзя будет использовать для чего-то другого.
Доступ к элементам массива
Есть две самые примитивные операции с массивами — это запись элементов в массив и чтение — получение значения элемента из массива. Все остальные операции с массивами построены на основе этих двух.
Поместить элемент в массив можно в любое из зарезервированных мест. Каждое из них идентифицируется с помощью индекса — положительного числового значения. Стоит запомнить, что самый первый элемент в массиве имеет индекс 0 , а далее в порядке возрастания. Таким образом, если массив состоит из 15 элементов, то последним индексом будет 14 .
Мы можем обратиться к определённому элементу по его индексу и тогда получим информацию о нём — его значение.
Для помещения большого количества элементов в массив или для получения информации о них используется цикл.
Ёмкость и длина массива
Ёмкость массива — это количество элементов, которое можно поместить в массив. Это то самое значение, которое указывается при создании массива. И это значение нельзя изменить. Если же ёмкость массива исчерпана, но нам нужно записать ещё один элемент, то придётся создать новый массив с большей ёмкостью и переместить в него все существующие элементы вместе с новым.
Длина массива — это количество элементов, непосредственно находящихся в массиве.
Несмотря на то, что ёмкость и длина массива — это разные понятия, а их значения могут отличаться, в различных задачах может встречаться такое, когда методу в качестве параметра передаётся массив без указания этих значений. В этом случае предполагается, что длина == ёмкость.
Вставка элемента в массив
Вставку элементов в массив можно разделить на 3 вида:
- вставка элемента в конец массива
- вставка элемента в начало массива
- вставка элемента по заданному индексу
Для вставки элемента в конец массива нам нужно знать его длину и ёмкость. Любой язык программирования позволяет в любое время узнать эти значения. Если ёмкость массива позволяет добавить новый элемент, то нам достаточно вставить новый элемент по последнему индексу. В противном случае нам потребуется создать новый массив с ёмкостью, достаточной для добавления нового массива, и переместить в него все элементы из старого массива и добавить новый.
При вставке элемента в начало массива, потребуется сдвинуть все другие элементы в массиве вправо на один индекс, чтобы освободить место для нового элемента.
Аналогично работает и вставка по заданному индексу — сначала потребуется сдвинуть все элементы, начиная с заданного, на одну позицию вправо. По сути вставка элемента в начало массива — это частный случай вставки элемента по заданному индексу, так как в этом случае заданный индекс был равен 0 .
Удаление элемента из массива
Также как и вставку, удаление элемента из массива можно разделить на 3 вида:
- удаление последнего элемента массива
- удаление первого элемента массива
- удаление элемента по заданному индексу
Удаление последнего элемента массива занимает меньше всего времени, так как мы в любой момент можем узнать последний индекс элемента и удалить его. Это никак не повлияет на остальные элементы.
Удаление первого элемента массива означает, что появится свободное место по индексу 0 . Чтобы заполнить это место, все элементы потребуется сдвинуть на один индекс влево.
Также и с удалением элемента по заданному индексу — потребуется заполнить свободное место, созданное удалённым элементом. Для этого все элементы справа от удалённого необходимо передвинуть на один индекс влево.
Поиск элементов
Поиск элемента в массиве означает, что необходимо найти определённый элемент в массиве и вернуть его позицию. Это может потребоваться для того, чтобы узнать присутствует ли элемент в массиве или, например, чтобы определить, в какой индекс вставить новый элемент.
Линейный поиск
Если индекс неизвестен, то можно проверять каждый элемент в массиве до тех пор пока не найдём искомый или пока не дойдём до конца массива. Такой алгоритм поиск элемента путём проверки всех элементов один за другим известен как линейный поиск.
В худшем случае линейный поиск заканчивается проверкой всего массива. Следовательно, его временная сложность равна O(n).
Бинарный поиск
При бинарном поиске мы всегда ориентируемся на элемент, который находится в центре массива и сравниваем его с искомым элементом. Если искомый элемент меньше центрального элемента, то массив можно сократить вдвое, удалив его правую часть. В оставшейся части снова берём центральный элемент и сравниваем его с искомым.
Бинарный поиск намного быстрее линейного, но может быть использован только для отсортированного массива. Поэтому если массив неотсортирован, а нам требуется выполнить поиск элемента один раз, то лучше воспользоваться линейным поиском, так как сортировка занимает больше времени. Если же поиск будет выполняться многократно, то полезнее сначала отсортировать массив и использовать бинарный поиск.
C++ для начинающих
Массив — это упорядоченный набор однотипных данных, объединенных под одним именем. Массивы используются для обработки большого количества однотипных данных.
Отдельное значение в массиве называется элементом массива. Элементами массива могут быть данные любого типа. Количество элементов в массиве называется размером массива.
Каждый элемента массива имеет свой номер, который называется индексом. Индекс ячейки – это целое неотрицательное число, по которому можно обращаться к элементу массива и выполнять какие-либо действия над ним. Первый элемент массива в С++ имеет индекс ноль.
b1[0] = 10; // первому элементу массива b1 присваивается значение 10
d=m3[2] + m3[4]; // переменной d присваивается сумма элементов массива m3 c номерами 2 и 4
Количество индексов для указания элемента массива называется размерностью массива. В зависимости от количества индексов массивы делятся на одномерные (линейные) массивы, двумерные массивы (матрицы), трёхмерные массивы и так далее до n-мерного массива. Чаще всего в программировании используются одномерные и двумерные массивы.
Одномерные массивы в С++
Одномерный массив — массив с одним индексом. Наглядно массив можно представить в виде набора пронумерованных ячеек, в каждой из которых может находиться только одно значение. Иногда эти данные могут совпадать с номером ячейки. На рисунке 1 показана структура целочисленного одномерного массива A. Размер этого массива — 8.
| Индекс ( порядковый номер ячейки) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Элементы массива (содержимое ячейки) | 5 | -12 | 4 | 6 | 6 | -8 | 0 | 15 |
Обратите внимание, что максимальный индекс одномерного массива A равен 7, но размер массива 8, потому что нумерация ячеек массива всегда начинается с 0.
Инициализация массива
Для того чтобы использовать массивы в своих программах, его надо сначала объявить.
Синтаксис объявления одномерного массива в С++:
тип имя_массива [размер_массива];
Сначала указывается тип элементов массива. После имени массива в квадратных скобках задаётся размер одномерного массива.
Пример. Объявление одномерного массива а из 16 целых чисел. Создается пустой массив (обычно, заполненный нулями).
int — целочисленный тип данных;
а — имя одномерного массива;
16 — размер одномерного массива, 16 ячеек.
Пример. Объявление двух одномерных массивов mas и а размерами 10 и 16 соответственно. Оба массива имеют одинаковый тип данных — int .
Массивы могут быть инициализированы при объявлении. Инициализация одномерного массива выполняется в фигурных скобках после знака равно, каждый элемент массива отделяется от предыдущего запятой.
При инициализации размер массива можно не указывать. В этом случае компилятор сам определит размер одномерного массива.
Пример. Инициализация массива без определения его размера.
Обращение к элементам массива
Для обращения к элементу массива необходимо указать имя массива и номер элемента. Например, для присвоения элементу массива значения указываем имя массива и номер элемента и после знака равенства указываем присваиваемое значение.
arr[6] = 7 * 4; // arr[6] равен 28
cout << arr[10] << ", " << arr[11]; // на экран выводится значения одиннадцатого и двенадцатого элементов массива
Всегда следите, чтобы не обращаться к элементам, которые находятся за пределами массива. Если длина равна 5, а вы обратитесь к ячейке под индексом 5, 6, 7 и так далее, то результат может быть непредсказуемым.
Пример. Инициализация и вывод элементов одномерного массива.
В строке 5 объявлен и инициализирован целочисленный одномерный массив с именем m1, размером 10 элемнтов. Обработка массива осуществляется циклом for . Переменную-счётчик i используется для обращения к элементам одномерного массива m1. В условии продолжения цикла for (строка 9) стоит строгий знак неравенства, так как индекса 10 в одномерном массиве m1 нет. В теле цикла for (строка 11) оператор cout выводит элементы одномерного массива.
Рис. 2 — Результат выполнения программы
Ввод элементов массива
Пример. Программа последовательно считывает в массив 6 введённых чисел с клавиатуры. Затем вычисляет и выводит на экран сумму элементов массива.
В переменной sum будет накапливаться сумма элементов одномерного массива. Первый цикл for заполняет одномерный массив числами, введёнными с клавиатуры (строки 9 — 13). Переменная счётчик i используется для последовательного доступа к элементам одномерного массива mas, начиная с индекса 0 и до 5-го включительно. Второй цикл for (строки 15 — 16) последовательно считывает элементы одномерного массива и суммирует их.
Рис. 3 -Результат выполнения программы
Пример. Программа заполняет массив из 12 элементов случайными вещественными числами в диапазоне [-5;5] и выводит элементы массива на экран.
Пример. Программа заполняет массив из 10 элементов числами, которые вычисляются выражением bi=2i+6 . Элементы массива и выводятся на экран.
#include <iostream> using namespace std; int b[10]; int i; int main() < for(i = 0; i < 10; i++) < b[i]=2*i+6; cout << "b[" << i << "] cpp-array1_files/screen-array3.png" width="75" height="127">Рис. 5 — Результат выполнения программы
Массив как способ структурирования данных
Когда данные образованы в структуру, можно их эффективно обрабатывать и успешно ими управлять. В этой статье будет рассмотрена такая структура данных, как массив. Данный способ структурирования хорошо известен в программировании и широко используется для решения различных практических задач.
Что такое массив?
Массив (array) представляет собой структуру данных, содержащую упорядоченный набор однотипных элементов. Тут следует привести несколько коротких терминов: — элементы массива — его составляющие компоненты, которые расположены в смежных местах памяти — соответствующих ячейках памяти; — длина — общее число элементов; — индекс — обозначение (имя, номер) позиции отдельного элемента. Индекс — это ссылка, обеспечивающая доступ к соответствующему элементу; — размерность — количество индексов.
Концепция
Концептуальную схему этой структуры данных можно увидеть на картинке ниже:
Что иллюстрирует диаграмма: 1. Массив можно назвать контейнером элементов. 2. У элементов есть значения, и они имеют определенный тип данных. 3. У каждого элемента есть свой индекс, который, как уже было сказано выше, применяется для выполнения доступа к этому элементу.
На очередной диаграмме можно увидеть, как объявляется массив в таких языках программирования, как Python и C ++. Глядя на синтаксис, можно сделать вывод, что при общей схожести возможны небольшие различия.
Объявление осуществляется тремя блоками данных: • именем массива (его можно в дальнейшем использоваться в качестве ссылки на коллекцию); • типом данных (к примеру, int (Integer), если речь идет о целых числах); • элементами — значениями данных.
Особенности массивов
Есть ряд общих свойств, которыми можно охарактеризовать array: • элементы хранятся в смежных ячейках памяти; • индекс обычно меньше, чем общее число элементов (это потому, что индексация начинается с нуля); • синтаксически, любая переменная, которая объявлена в качестве массива, способна хранить несколько значений; • практически все языки программирования имеют схожее «понимание» массивов, однако объявлять и инициализировать их они могут по-разному; • имя, тип данных и элементы — общие составляющие любых инициализаций.
Основные виды массивов по структуре
Структура данных может быть разной. Чаще всего сегодня используют одномерные и двумерные массивы. В одномерных у элемента есть только один индекс. Представим одномерный массив с именем A. Чтобы получить доступ к i-ому элементу, надо указать имя массива и индекс (номер) необходимого элемента: A[i].
В двумерном массиве (в матрице) структура представлена в виде таблицы. Доступ в матрицу производится также еще и по номерам строки и столбца, на пересечении которых и находится нужный элемент:
A[i, j]
Здесь A — имя массива, i – номер строки, j – номер столбца в матрице.
Хотя в различных языках программирования работа с такими структурами данных может отличаться, однако главные принципы в большинстве случаев неизменны. В известном языке Pascal обращение к 2-мерному массиву будет осуществляться именно так, как в примере выше: A[i, j]. А вот уже в языке C++ обращение будет следующим: A[i][j].
Какие еще бывают массивы?
Выше описывались массивы, которые относят к статическому типу — число элементов фиксировано и постоянно. Но есть и другие массивы, размер которых может меняться в процессе выполнения программы, — динамические. Они характеризуются непостоянностью размера, и это неплохо, ведь работа становится более гибкой. Но следует учесть, что сам процесс обработки таких структур усложняется, что не может не влиять и на быстродействие операции. Правило «За все нужно платить» никто не отменял.
Второй момент, который стоит упомянуть, связан с однородностью массива. Однородность — важный критерий статической структуры данных. Если же однородность отсутствует, такой массив называют гетерогенным. Использование гетерогенных структур оправдано во многих случаях, но имеет недостатки, которые справедливы для структур динамических.
Зачем они вообще нужны?
Для применения существует масса причин, вот 2 основные: • массивы — одна из наиболее подходящих структур для реализации в коде однотипных данных и хранения в одной переменной нескольких значений; • операция поиска в такой структуре данных является более простой и быстрой, то есть один из профитов заключается в том, что экономится время обработки.
Также стоит напомнить, что недостаточно просто выбрать в качестве структуры массив. Дополнительно нужно определиться и со способом его представления, ведь сам по себе массив — это лишь общее обозначение. Разработчику же надо выбирать наиболее подходящий вид массива с учетом поставленной задачи.
Еще не конец: данные других типов
Какие еще структуры данных следует знать: — связные (связанные) списки. Группа узлов, вместе образующих последовательность. Каждый узел включает в себя фактические данные (они хранятся и бывают представлены любым типом данных) и ссылку-указатель на следующий узел последовательности; — стеки. Так называемая «стопка книг». Можно вставлять либо удалять компоненты только из начала (невозможно взять интересующую книгу из середины стопки, предварительно не взяв книги, лежащие сверху); — очереди. Стоящий первым обслуживается первым (принцип FIFO — first in, first out); — множества. Данные хранятся без определенного порядка, причем значение не повторяются; — Map. Данные хранятся в парах ключ-значение, каждый ключ является уникальным; — хэш-таблицы. В данных этого типа реализуется интерфейс map, позволяющий хранить пары ключ-значение. Вычисление индекса происходит с помощью функции, называющейся хэш-функцией; — двоичное дерево поиска. Каждое дерево имеет корневой узел, последний имеет 0 либо более дочерних узлов, каждый дочерний узел имеет 0 либо более дочерних узлов и т. п.; — префиксное дерево. Своеобразное дерево поиска. Данные хранятся в шагах, каждый шаг — узел дерева. Часто применяется для хранения слов; — двоичная куча. В каждом узле не больше двух детей. Все уровни заполнены полностью; — графы. Совокупности узлов (их называют вершинами) и связей (их называют ребрами) между этими вершинами. Сами графы еще называют сетями.
Урок №74. Массивы
На уроке о структурах мы узнали, что с их помощью можно объединять переменные разных типов под одним идентификатором. Это идеально, когда нужно смоделировать объект, который имеет много разных свойств. Однако удобство работы со структурами при наличии большого количества элементов оставляет желать лучшего.
Что такое массив?
К счастью, структуры не являются единственным агрегированным типом данных в языке C++. Есть еще массив — совокупный тип данных, который позволяет получить доступ ко всем переменным одного и того же типа данных через использование одного идентификатора.
Рассмотрим случай, когда нужно записать результаты тестов 30 студентов в классе. Без использования массива нам придется выделить 30 почти одинаковых переменных!
С использованием массива всё гораздо проще. Следующая строка эквивалентна коду, приведенному выше:
В объявлении переменной массива мы используем квадратные скобки [] , чтобы сообщить компилятору, что это переменная массива (а не обычная переменная), а в скобках — количество выделяемых элементов (это называется длиной или размером массива).
В примере, приведенном выше, мы объявили фиксированный массив с именем testResult и длиной 30. Фиксированный массив (или «массив фиксированной длины») представляет собой массив, размер которого известен во время компиляции. При создании testResult , компилятор выделит 30 целочисленных переменных.
Элементы массива
Каждая из переменных в массиве называется элементом. Элементы не имеют своих собственных уникальных имен. Вместо этого для доступа к ним используется имя массива вместе с оператором индекса [] и параметром, который называется индексом, и который сообщает компилятору, какой элемент мы хотим выбрать. Этот процесс называется индексированием массива.
В вышеприведенном примере первым элементом в нашем массиве является testResult[0] , второй — testResult[1] , десятый — testResult[9] , последний — testResult[29] . Хорошо, что уже не нужно отслеживать и помнить кучу разных (хоть и похожих) имен переменных — для доступа к разным элементам нужно изменять только индекс.
Важно: В отличие от повседневной жизни, отсчет в программировании и в языке С++ всегда начинается с 0, а не с 1!
В массиве длиной N элементы массива будут пронумерованы от 0 до N-1 ! Это называется диапазоном массива.