Тема 6. Массивы Зачем нужны массивы?
Для представления набора однотипных данных используются массивы, являющиеся наряду с циклами фундаментальным инструментом программирования. Массивы позволяют избегать дублирования кода и разрабатывать компактные, понятные и красивые программы. Для наиболее полного использования возможностей массивов они должны применяться в комбинации с циклами, поэтому для успешного освоения данной темы необходимо уверенно владеть работой с циклами.
Рассмотрим задачу вычисления среднего возраста десяти человек. Вначале объявим 10 переменных, каждая из которых хранит возраст одного человека, затем вычислим их среднее и выведем результат на экран.
//Объявление и инициализации десяти переменных
int age_0 = 30; int age_1 = 21;
int age_2 = 22; int age_3 = 19;
int age_4 = 45; int age_5 = 18;
int age_6 = 15; int age_7 = 61;
int age_8 = 43; int age_9 = 39;
//Вычисление и вывод среднего
int sum = age_0 + age_1 + age_2 +
age_3 + age_4 + age_5 +
age_6 + age_7 + age_8 +
float avg = (float) sum/10;
cout << «Средний возраст равен » << avg << » лет\n»;
Как видно из представленного фрагмента кода, неудобство использования переменных заключается в том, что их пришлось объявить 10 штук и обработать 10 штук. Решить данную проблему при большем количестве переменных, скажем, при 1000, будет еще неудобнее. Кроме того, если в процессе написания программы количество требуемых переменных неизвестно, то придется существенно усложнять код.
Решить эту, а также много других задач эффективно и красиво можно с помощью массивов. Рассмотрим, как это сделать.
Объявление массива
Массив – это набор элементов, которые имеют одинаковый тип и хранятся в памяти строго последовательно. Обращение к элементу массива осуществляется по имени массива и номеру элемента в этом массиве. Номер элемента в массиве называется индексом. В языке Си индекс первого элемента равен 0, а индекс последнего – N-1, где N – это размер массива. При объявлении массива указывается тип его элементов, имя и размер:
В качестве типа элементов массива можно указывать любой существующий в языке Си тип. Имя массива следует выбирать, чтобы оно отражало суть содержимого массива. Например, абстрактный числовой массив можно назвать numbers, массив возрастов – ages, а массив весов – weights. Размер массива должен быть константой, а не переменной, поэтому существуют три способа объявления массива:
const int n = 10;
Поскольку размер массива не может быть переменной, то следующая запись недопустима и вызовет ошибку компиляции:
cout << «Введите размер массива:\n»;
Размер массива указывать необязательно, если при его объявлении выполняется инициализация:
Каждый из элементов массива представляет собой переменную, другими словами, именованную ячейку памяти. Отличие элемента массива от обычной переменной заключается лишь в том, что обращение к обычной переменной происходит по ее имени, а к элементу массива обращаются по имени массива и индексу элемента в этом массива. Таким образом, элементу массива можно присвоить некоторое значение так же, как и переменной:
Кроме того, можно ввести значение элемента массива с клавиатуры при помощи функций ввода
Массивы (Arrays)
Массивы — это структура данных для хранения элементов. Элементами могут быть целые числа, строки, объекты и т.д. Все элементы хранятся непрерывно, т.е. в соседних участках памяти. Если понадобится добавить новый элемент в массив, а места под него рядом не окажется, то придётся запросить другой блок памяти.
Массивы существуют во всех языках программирования и используются в качестве основы для большинства других структур данных.
Создание массива
Количество элементов в массиве определяется разработчиком при его создании. Кроме этого необходимо указать тип элементов, которые будут входить в массив.
Если создать массив, который может содержать 15 элементов, то при получении 16-го нужно будет создавать новый массив. При этом не стоит создавать массив, например, на 1 000 000 элементов, так сказать с запасом. Причина этого в том, что он будет занимать много места в памяти. Ведь память резервируется для хранения 1 000 000 элементов, даже если по факту элементов будет всего 15. И эту память нельзя будет использовать для чего-то другого.
Доступ к элементам массива
Есть две самые примитивные операции с массивами — это запись элементов в массив и чтение — получение значения элемента из массива. Все остальные операции с массивами построены на основе этих двух.
Поместить элемент в массив можно в любое из зарезервированных мест. Каждое из них идентифицируется с помощью индекса — положительного числового значения. Стоит запомнить, что самый первый элемент в массиве имеет индекс 0 , а далее в порядке возрастания. Таким образом, если массив состоит из 15 элементов, то последним индексом будет 14 .
Мы можем обратиться к определённому элементу по его индексу и тогда получим информацию о нём — его значение.
Для помещения большого количества элементов в массив или для получения информации о них используется цикл.
Ёмкость и длина массива
Ёмкость массива — это количество элементов, которое можно поместить в массив. Это то самое значение, которое указывается при создании массива. И это значение нельзя изменить. Если же ёмкость массива исчерпана, но нам нужно записать ещё один элемент, то придётся создать новый массив с большей ёмкостью и переместить в него все существующие элементы вместе с новым.
Длина массива — это количество элементов, непосредственно находящихся в массиве.
Несмотря на то, что ёмкость и длина массива — это разные понятия, а их значения могут отличаться, в различных задачах может встречаться такое, когда методу в качестве параметра передаётся массив без указания этих значений. В этом случае предполагается, что длина == ёмкость.
Вставка элемента в массив
Вставку элементов в массив можно разделить на 3 вида:
- вставка элемента в конец массива
- вставка элемента в начало массива
- вставка элемента по заданному индексу
Для вставки элемента в конец массива нам нужно знать его длину и ёмкость. Любой язык программирования позволяет в любое время узнать эти значения. Если ёмкость массива позволяет добавить новый элемент, то нам достаточно вставить новый элемент по последнему индексу. В противном случае нам потребуется создать новый массив с ёмкостью, достаточной для добавления нового массива, и переместить в него все элементы из старого массива и добавить новый.
При вставке элемента в начало массива, потребуется сдвинуть все другие элементы в массиве вправо на один индекс, чтобы освободить место для нового элемента.
Аналогично работает и вставка по заданному индексу — сначала потребуется сдвинуть все элементы, начиная с заданного, на одну позицию вправо. По сути вставка элемента в начало массива — это частный случай вставки элемента по заданному индексу, так как в этом случае заданный индекс был равен 0 .
Удаление элемента из массива
Также как и вставку, удаление элемента из массива можно разделить на 3 вида:
- удаление последнего элемента массива
- удаление первого элемента массива
- удаление элемента по заданному индексу
Удаление последнего элемента массива занимает меньше всего времени, так как мы в любой момент можем узнать последний индекс элемента и удалить его. Это никак не повлияет на остальные элементы.
Удаление первого элемента массива означает, что появится свободное место по индексу 0 . Чтобы заполнить это место, все элементы потребуется сдвинуть на один индекс влево.
Также и с удалением элемента по заданному индексу — потребуется заполнить свободное место, созданное удалённым элементом. Для этого все элементы справа от удалённого необходимо передвинуть на один индекс влево.
Поиск элементов
Поиск элемента в массиве означает, что необходимо найти определённый элемент в массиве и вернуть его позицию. Это может потребоваться для того, чтобы узнать присутствует ли элемент в массиве или, например, чтобы определить, в какой индекс вставить новый элемент.
Линейный поиск
Если индекс неизвестен, то можно проверять каждый элемент в массиве до тех пор пока не найдём искомый или пока не дойдём до конца массива. Такой алгоритм поиск элемента путём проверки всех элементов один за другим известен как линейный поиск.
В худшем случае линейный поиск заканчивается проверкой всего массива. Следовательно, его временная сложность равна O(n).
Бинарный поиск
При бинарном поиске мы всегда ориентируемся на элемент, который находится в центре массива и сравниваем его с искомым элементом. Если искомый элемент меньше центрального элемента, то массив можно сократить вдвое, удалив его правую часть. В оставшейся части снова берём центральный элемент и сравниваем его с искомым.
Бинарный поиск намного быстрее линейного, но может быть использован только для отсортированного массива. Поэтому если массив неотсортирован, а нам требуется выполнить поиск элемента один раз, то лучше воспользоваться линейным поиском, так как сортировка занимает больше времени. Если же поиск будет выполняться многократно, то полезнее сначала отсортировать массив и использовать бинарный поиск.
Массивы – что это и как с ними работать?
Занимаясь программированием, мы достаточно часто сталкиваемся с использованием массивов. У многих эта тема вызывает достаточно много трудностей из-за непонимания того: что из себя представляют массивы и как с ними работать. Однако, их использование было, есть и будет одной из наиболее важный частей написания программного кода. Именно поэтому, сегодня хотелось бы поговорить о массивах.
Как я уже сказала, массивы очень распространенная вещь. Наиболее часто, если говорить о разработке веб-сайтов, мы сталкиваемся с ними в php и JavaScript кодах. Конечно же, различия при работе с массивами в php и JavaScript имеются, но поняв, как работать с массивами в одном из языков программирования, разобраться, как работать в другом, не составит практически никакого труда.
В этой статье я буду говорить о массивах относительно языка php.
Что же такое массивы?
По определению, Массив – это нумерованный набор переменных.
Переменные в массиве – это элементы массива. Их позиция в массиве задается индексом.
Если понять это не очень просто, то представьте себе «волшебную» коробку. В ней Вы можете создавать сколько угодно отделов и складывать что-то в эти отделы. При необходимости, Вы можете: удалять отделы; создавать новые; вытаскивать и использовать содержимое, которое в них находится; заменять содержимое отдельных отсеков чем-то другим; Вы можете даже хранить в одном из отсеков другой массив, который также содержит разные отделы.
Таким образом, Массив – это тип данных, который содержит в себе набор элементов. Сразу хочется сказать, что элементы эти, если мы говорим о языке php, не обязательно должны являться однотипными!
Для чего нужны массивы?
Возможно, Вам не совсем понятно, для чего нужно использовать массивы.
Давайте представим один несложный пример.
Скажем, Вам нужно написать программу, которая будет считать среднее арифметическое число продаж за месяц (или за год). Для этого нам нужно знать число продаж за каждый день месяца и, соответственно, где-то эти данные хранить. Мы можем объявить 30 переменных (или 356, если речь идет о годе). Вы уже подсчитали сколько строк кода нужно будет написать?
Далее нам нужно написать формулу, которая будет считать среднее арифметическое. Для этого нужно сложить все переменные и поделить сумму на число дней. Не кажется ли Вам, что формула может получиться «слегка» громоздкой?
При всем при этом, объявляя такое большое число переменных, а потом подставляя все это в формулу немудрено допустить ошибку и наш результат будет некорректным. А что, если в один прекрасный момент нам понадобится узнать среднее арифметическое не за 30 дней, а, например, за полтора месяца? Нужно менять весь код!
Используя массив в этой ситуации, мы значительно облегчим себе жизнь. Ведь используя соответствующие функции, мы может узнать: число элементов массива, сумму элементов массива, мы можем хранить все данные о продажах в одном типе данных – массиве, и при этом нам не нужно будет создавать огромное количество переменных.
Это лишь один небольшой пример, который может помочь Вам понять – зачем же нужны массивы. На практике же, подобные задачи возникают постоянно. И если знать, как работать с массивами, то их решение становится гораздо более легким.
Чтобы научиться работать с массивами нужна практика и определенные знания. Я планирую написать серию статей, в которых и попытаюсь рассказать о разнообразных тонкостях, функциях и примерах. Так что эта статья – лишь начало знакомства с массивами.
Это следует помнить, работая с массивами!
Мы привыкли, что начало чего-либо отсчитывается с «1». Во многих ситуациях так оно и есть, но только не в ситуации с массивами.
Я уже говорила, что позиция элемента в массиве задается ее индексом. Так вот нумерация элементов массива начинается не с 1, а с 0. Это нужно всегда помнить, чтобы не допустить ошибок!
Также следует отметить, что Размером массива называют общее количество элементов в массиве.
Как объявить массив
Объявить (или инициализировать) массив можно несколькими способами.
Можно инициализировать массив поэлементно, указывая индекс.
Для этого сначала придумайте имя для Вашего массива. Например, дадим массиву имя «$Mass1». Теперь мы можем инициализировать массив и занести туда какие-то переменные.
Как Вы видите, сначала идет имя нашего массива (при объявлении не забываем знак «$»), далее квадратные скобки, в которых указывается индекс элемента, далее знак присваивания «=» и само значение элемента. В данном примере значения представляют собой целые числа, в конце точка с запятой.
Можно сделать тоже самое, но не указывая индексы. При этом php автоматически присвоит индекс для каждого следующего элемента на единицу больше последнего. Другими словами, добавит элемент в конец массива.
Но, как Вы заметили, квадратные скобки все же нужны. Php должен знать, что имеет дело с массивом.
Есть и другой способ, в котором не потребуются квадратные скобки и можно указать все элементы массива сразу в одну строку. Однако, вместо квадратных скобок потребуется специальное слово «array», которое и расскажет php о том, что мы имеем дело с массивом.
Делается это так:
Вот так мы можем создавать массивы и заполнять их различными элементами.
На самом деле это не все способы, так как существуют еще и ассоциативные и многомерные массивы, но о ним мы поговорим в следующей статье. Все по-порядку.
Мы научились создавать массивы. Давайте теперь поговорим о том, как можно получить и изменить определенный элемент массива.
Как получить и изменить элемент массива
Итак, чтобы обратиться к какому-либо элементу массива, мы будет использовать его индекс, который указывается также в квадратных скобках.
При этом следует помнить, что индексация начинается с нуля.
Допустим у нас есть такой массив:
Чтобы, например, получить первый элемент массива и вывести его на экран, мы можем использовать следующий код:
В итоге, на экране мы увидим значение первого элемента массива – «Маша».
При этом не забудьте, что для того, чтобы тестировать php-код на локальном компьютере, Вам нужно будет установить и запустить Денвер .
А также не забудьте, что весь php-код нужно писать между специальных символов объявления php. Таким образом полный код этого примера будет таким:
Соответственно, чтобы получить второй элемент, вместо нуля в квадратных скобках указываем единицу и т.д.
Также мы можем добавить элемент в массив или изменить уже существующий.
Чтобы добавить элемент в конец массива, достаточно прописать следующее:
А чтобы изменить существующий элемент, нужно в квадратных скобках указать индекс того элемента, который хотим изменить и присвоить ему новое значение. Вот так:
И на последок давайте поговорим о размере массива.
Как узнать размер массива
Довольно часто для различных вычислений необходимо знать размер массива, другими словами, количество его элементов.
В php сделать это можно при помощи функции «count»:
Или при помощи функции «sizeof»:
Оба варианта выведут на экран значение – «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 либо более дочерних узлов и т. п.; — префиксное дерево. Своеобразное дерево поиска. Данные хранятся в шагах, каждый шаг — узел дерева. Часто применяется для хранения слов; — двоичная куча. В каждом узле не больше двух детей. Все уровни заполнены полностью; — графы. Совокупности узлов (их называют вершинами) и связей (их называют ребрами) между этими вершинами. Сами графы еще называют сетями.