Урок №16. Одномерные массивы
В программах, с которыми мы работали раньше, было всего несколько переменных. Каждой из них мы давали своё имя, и никаких сложностей при этом не возникало.
Объёмы данных, которые обрабатывают современные компьютеры, огромны: количество значений измеряется миллионами и миллиардами. Если каждую из этих переменных называть своим именем, очень легко запутаться, и работать с таким набором данных очень неудобно.
Допустим, мы хотим сложить значения 1000 ячеек с именами a1, а2, …, a1000. Для этого нужно будет написать очень длинный оператор присваивания:
sum = a1 + а2 + ... + a1000 Учтите, что компьютер не понимает многоточий, поэтому нам придётся перечислить все 1000 имён переменных.
Серьёзная проблема возникнет при решении этой задачи, если количество данных заранее неизвестно (например, они поступают по компьютерной сети). Мы не знаем, сколько переменных потребуется, а поэтому не можем написать команду суммирования.
Для того чтобы было удобно работать с большим количеством данных, обычно дают общее имя группе ячеек, которая называется массивом.
Массив — это группа данных одного типа, расположенных в памяти друг за другом и имеющих общее имя. К элементу массива можно обращаться по его номеру (индексу).
Перед тем как использовать массив, надо присвоить ему имя, определить тип входящих в массив переменных (элементов массива) и их количество. По этим сведениям компьютер вычислит, сколько места требуется для хранения массива, и выделит в памяти нужное число ячеек.
Для работы с массивами необходимо научиться:
- выделять память нужного размера под массив;
- записывать данные в нужную ячейку;
- читать данные из ячейки массива.
В языке Python нет такой структуры данных, как «массив». Вместо этого для хранения группы однотипных (и не только однотипных!) объектов используют списки — объекты типа list.
В отличие от массивов список — это динамическая структура, его размер можно изменять во время выполнения программы (удалять и добавлять элементы), при этом все операции по управлению памятью берёт на себя транслятор.
Далее, говоря о списках, мы будем использовать слово «массив», потому что чаще всего списки в языке Python используются именно в роли массива, т. е. для хранения однотипных значений.
Массив (список) можно создать перечислением элементов через запятую в квадратных скобках, например так:
А = [1, 3, 4, 23, 5]
print( type(А))
Такая программа выведет:
<class 'list'>Это означает, что массив — объект типа list.
Массив можно составить не только из чисел, но и из данных любых типов, например из символьных строк:
А = ["Вася", "Петя", "Коля", "Маша", "Даша"]Массивы можно «складывать» с помощью знака +, например приведённый выше числовой массив можно было построить сложением нескольких списков:
А = [1, 3] + [4, 23] + [5]Сложение одинаковых массивов заменяется умножением *. Оператор
А = [0]*10создаёт новый массив из 10 элементов (выделяет для них место в памяти) и заполняет их нулями.
Длина массива (количество элементов в нём) определяется с помощью функции lеn:
N = len(А)Таким образом, в любой момент массив «знает» свой размер.
Иногда размер массива хранят в отдельной переменной:
N = 10
А = [0]*N
В этом случае очень просто переделать программу для работы с массивом другого размера: достаточно просто изменить значение N в первой строке программы.
Каждый элемент массива имеет свой номер (индекс). Используя индекс, можно сразу обратиться к любому элементу массива. Поэтому говорят, что массив — это структура данных с произвольным доступом.
Индекс — это значение, которое указывает на конкретный элемент массива.
Нумерация элементов массивов (и элементов символьных строк) в Python всегда начинается с нуля, второй по счёту элемент имеет номер 1 и т. д.
Для того чтобы обратиться к элементу массива (прочитать или изменить его значение), нужно записать имя массива и в квадратных скобках — (рис. 1.7) индекс нужного элемента, например А[2] (рис. 1.7).
Индексом может быть также целое значение переменной или арифметического выражения. Например, для массива на рис. 1.7 программа
i = 1
print(A[i], A[i+1], A[3*i+1], A[A[3*i]])
выведет то же самое, что и программа
print(А[1], А[2] , А[4], А[0])Индексом может быть даже значение элемента массива. Для последнего элемента вывода запись A[A[3*i]] означает, что нужно взять значение A[3*i] при i = 1 и использовать его как индекс нужного элемента. Получаем:
i = 1 => 3*i = 3 => A[3*i] = А[3] = 0 => А [А[3*i] ] = А[0] = 3. Как и для символьных строк, для массивов можно использовать отрицательные индексы элементов, при этом отсчёт ведётся с конца массива. Например, А[-1] — это последний элемент, а А[-2] — предпоследний. Для получения соответствующего положительного индекса к отрицательному нужно прибавить длину массива.
При обращении к элементу массива с несуществующим индексом происходит серьёзная ошибка — выход за границы массива, и программа завершается аварийно. Например, для массива на рис. 1.7 (он имеет длину 5) правильные значения индексов — от -5 до 4.
Далее везде будем считать, что N — это текущий размер массива А, с которым мы работаем, т. е. то значение, которое возвращает вызов функции len( А ).
Перебор элементов состоит в том, что мы в цикле просматриваем все элементы массива и, если нужно, выполняем с каждым из них некоторую операцию. Для этого удобнее всего использовать цикл по переменной, значение которой изменяется от минимального до максимального индекса. Для массива из N элементов цикл выглядит так:
for i in range(N):
... # работаем c A[i]
Здесь вместо многоточия можно добавлять операторы, которые работают с элементом A[i] (в том числе и изменяют его).
Мы видим, что благодаря использованию массива нам достаточно описать, что делать с одним элементом, и поместить эти действия внутрь цикла, перебирающего значения индексов. Если бы мы применяли простые переменные, то нам пришлось бы описывать необходимые действия для каждого элемента (правда, при этом цикл бы не понадобился).
Программа
for i in range(N):
A[i] = i
заполняет массив целыми числами от 0 до N-1 (это как раз та последовательность, которую строит функция range). Здесь мы предполагаем, что память для N элементов массива уже выделена, иначе обращение к несуществующему элементу вызовет ошибку и аварийное завершение программы.
Теперь заполним массив первыми N натуральными числами в обратном порядке: в первый элемент массива должно быть записано число N, во второй — число N-1, а в последний — единица.
Сначала запишем в развёрнутом виде (без цикла) операторы, которые должны быть выполнены:
А [ 0 ] = N
А[1] = N-1
...
A[N-1] = 1
Теперь составим цикл, в котором значение, присваиваемое очередному элементу, пока обозначим через X:
for i in range(N):
A[i] = X
Величина X должна изменяться при переходе к следующему элементу. Её начальное значение равно N, конечное значение равно 1, с каждым повторением цикла оно уменьшается на 1. Можно записать цикл так:
X = N
for i in range(N):
A[i] = X
X -= 1
А можно его значительно упростить, заметив, что при увеличении индекса элемента i на единицу значение X уменьшается, причём тоже на единицу. Поэтому сумма i + X остаётся постоянной!
Для первого элемента мы должны получить i + X = N. Выразив X из этого уравнения, находим, что элемент с номером i принимает значение N — i, поэтому цикл можно записать так:
for i in range(N):
A[i] = N - i
Теперь предположим, что массив заполнен, и попробуем увеличить все его элементы на единицу. Это значит, что нужно заменить значение элемента A[i] на A[i]+1:
for i in range(N):
A[i] += 1
Массив — это набор элементов, поэтому во многих языках программирования нельзя вывести массив одной командой. Однако в языке Python такая возможность есть:
print(А) В этом случае весь массив выводится в квадратных скобках, его элементы разделяются запятыми.
Можно вывести элементы массива на экран по одному, используя цикл перебора:
for i in range(len(A)):
print( A[i], end=" " )
Параметр end определяет, что после ввода каждого элемента добавляется пробел, а не символ перехода на новую строку.
Удобно записывать такой цикл несколько иначе:
for х in А:
print( х, end=" " )
Здесь не используются переменная-индекс i и функция len, а просто перебираются все элементы массива. На каждой итерации цикла в переменную х заносится значение очередного элемента массива (в порядке возрастания индексов). Такой цикл перебора очень удобен, если не нужно изменять значения элементов массива.
В языке Python существует ещё один замечательный способ вывода всех элементов массива через пробел (без скобок):
print( *А )Знак * перед именем массива означает, что нужно преобразовать массив в набор отдельных значений, т. е. для массива
А = [1, 2, 3, 4, 5]эта команда сработает так же, как и
print ( 1, 2, 3, 4, 5 )Иногда небольшие массивы вводятся с клавиатуры. В простейшем случае мы просто строим цикл, который выполняет оператор ввода отдельно для каждого элемента массива:
for i in range(N):
A[i] = int ( input ())
Напомним, что если какую-то из введённых строк не удастся преобразовать в целое число, программа завершится с ошибкой.
Вместо цикла можно использовать генератор, который сразу создаёт массив и заполняет его введёнными числами:
А = [int( input()) for i in range(N)] Здесь при каждом повторении цикла строка, введённая пользователем, преобразуется в целое число с помощью функции int, и это число добавляется к массиву.
При этом пользователь вводит данные «вслепую», т. е. программа не подсказывает ему, значение какого элемента вводится в данный момент.
Значительно удобнее, если перед вводом появляется сообщение с подсказкой:
for i in range(N):
print ( "A[{}]=".format(i), end="" )
A[i] = int ( input () )
В этом примере перед вводом очередного элемента массива на экран выводится подсказка. Например, при вводе элемента с индексом 3 будет выведено: А[3]= и курсор (приглашение к вводу) будет мигать справа от знака =.
Иногда нужно заполнить массив случайными числами (например, определить случайные координаты клеток с призами или препятствиями в игре).
Для работы со случайными (точнее, псевдослучайными) числами нужно подключить (импортировать) модуль random, из которого нам будет нужна одна функция — randint. Эта функция генерирует случайное целое число в заданном диапазоне. Вначале подключим эту функцию:
from random import randintЕсли массив уже создан, используем цикл по переменной:
for i in range(N):
A[i] = randint( 20, 100 )
To же самое можно сделать с помощью генератора:
А = [randint( 20, 100 ) for i in range(N)]Генератор создаёт массив из N элементов и заполняет его случайными числами из отрезка [20, 100].