№18 Массивы / Уроки по Python для начинающих
Примечание: Python не имеет встроенной поддержки массивов, но вместо этого можно использовать списки (list) Python.
Массивы используются для хранения нескольких значений в одной переменной:
Что такое массив?
Массив — это специальная переменная, которая может содержать более чем одно значение.
Если у вас есть список предметов (например, список марок авто), то хранение автомобилей в отдельных переменных может выглядеть так:
car1 = "Ford"; car2 = "Volvo"; car3 = "BMW"; Однако, что, если вы хотите проскочить через все машины и найти конкретную? А что, если у вас было бы не 3 автомобиля а 300?
Решение представляет собой массив!
Массив может содержать много значений под одним именем, и вы так же можете получить доступ к значениям по индексу.
Доступ к элементам массива
Вы ссылаетесь на элемент массива, ссылаясь на индекс.
Получим значение первого элемента массива:
Изменим значение первого элемента массива:
Длина массива
Используйте метод len() чтобы вернуть длину массива (число элементов массива).
Выведем число элементов в массиве cars :
Примечание: Длина массива всегда больше, чем индекс последнего элемента.
Циклы элементов массива
Вы можете использовать цикл for для прохода по всем элементам массива.
Выведем каждый элемент из цикла cars :
Добавление элементов массива
Вы можете использовать метод append() для добавления элементов в массив.
Добавим еще один элемент в массив cars :
Удаление элементов массива
Используйте метод pop() для того, чтобы удалить элементы из массива.
Удалим второй элемент из массива cars :
Так же вы можете использовать метод remove() для того, чтобы убрать элемент массива.
Удалим элемент со значением “Volvo”:
Примечание: Метод remove() удаляет только первое вхождение указанного значения.
Методы массива
В Python есть набор встроенных методов, которые вы можете использовать при работе с lists/arrays.
| Метод | Значение |
|---|---|
| append() | Добавляет элементы в конец списка |
| clear() | Удаляет все элементы в списке |
| copy() | Возвращает копию списка |
| count() | Возвращает число элементов с определенным значением |
| extend() | Добавляет элементы списка в конец текущего списка |
| index() | Возвращает индекс первого элемента с определенным значением |
| insert() | Добавляет элемент в определенную позицию |
| pop() | Удаляет элемент по индексу |
| remove() | Убирает элементы по значению |
| reverse() | Разворачивает порядок в списке |
| sort() | Сортирует список |
Примечание: В Python нет встроенной поддержки для массивов, вместо этого можно использовать Python List.
Массивы в python лекция
В таких языках, как C и Java, требуется заранее указывать размер массива и тип данных. Структура списка в Python позволяет обойти эти требования, сохраняя данные в виде указателей на местоположение элементов в памяти, автоматически изменяя размер массива, когда место заканчивается. Элементам памяти не обязательно находиться рядом друг с другом.
Реализация
Основные ограничения, с которыми мы сталкиваемся при создании массивов на языке Python:
- После выделения места для массива мы не можем получить больше, не создав новый массив.
- Все значения в массиве должны быть одного типа.
Мы можем реализовать в Python очень простой класс Array, который имитирует основную функциональность массивов в языках более низкого уровня.
Отсутствие ограничений на типы данных и длину делает связанные списки привлекательными. Однако эта гибкость создает некоторые проблемы. Программе доступен только верх списка, а это значит, что для поиска любого другого узла нам придется пройти весь список. Другими словами, мы лишаемся O(1) поиска для любого элемента, кроме первого узла. Если вы запрашиваете 100-й элемент, то для его получения потребуется 100 шагов: схема O(n).
Можно сделать связанные списки более универсальными. Для этого необходимо добавить указатели на предыдущие узлы и раскрыть конец списка, или сделать его кольцевым. В целом, выбор связанных списков вместо массивов является платой за удобство.
Реализация
Чтобы создать связанный список в Python, начнем с определения узла. Необходимы только две части: данные, которые хранит узел и указатель на следующий узел в списке. Добавим метод __repr__ для того, чтобы было легче увидеть содержание узла.
LC 141. Linked List Cycle: Цикл связанного списка – пример использования медленных и быстрых указателей. Наша цель определить, есть ли в списке цикл, который возникает, когда следующий указатель узла показывает на более ранний узел в списке.
Проблема в том, что проход списка через цикл будет бесконечным.
Один из вариантов решения заключается в том, что нам нужно установить ограничение на продолжительность выполнения обхода, или решить проблему повторяющихся паттернов за некоторый период времени.
Более простой подход заключается в использовании двух указателей.
В данном случае невозможно использование while fast и fast.next , так как эти методы имеют значение False только при достижении конца списка. Вместо этого, подставим slow и fast на первый и второй узлы. Будем перемещать их по списку с разной скоростью, пока они не совпадут. В конце списка вернем False . Если два указателя будут показывать на один и тот же узел, вернем True.
def has_cycle(head: ListNode) -> bool: """ Определяем где связанный список имеет цикл """ slow = head fast = head.next while slow != fast: # Находим конец списка if not (fast or fast.next): return False slow = slow.next fast = fast.next.next return True Мы узнали, что такое массивы и связанные списки. Это важная составляющая структур данных, которая используется во всех языках программирования.
В следующей части материала приступим к изучению деревьев и графов.