Структуры данных

Перед рассмотрением структур данных рассмотрим следующие понятия.

Изменяемость объектов

Изменяемость объекта (любого объекта, не только структуры данных) определяет, можно ли изменить значение объекта в той же ячейке памяти, где оно хранится:

• изменяемые (mutable) объекты допускают изменение значения объекта.

  изменяемые структуры допускают модификацию их элементов (добавление, удаление, изменение элементов).

  Примеры: списки (list), словари (dict), множества (set)

• неизменяемые (immutable) структуры нельзя изменить после создания.

  При “изменении” такой структуры создаётся новый объект и на него даётся та же ссылка, что на предыдущий. Предыдущий объект при этом удаляется.

  Примеры: кортежи (tuple), строки (str), числа (int, float)

Ссылки на объекты

Особенностью языка Python является то, что все данные в нём является объектами (их тип - object). В том числе объекты, которые обычно называют переменными (например, x=2.4, is_valid=True, some_string='test). Однако такой объект, в отличие от классической переменной, является неизменяемым.

Рассмотрим вариант “изменения” значения “переменной”:

>>>x=5
>>>id(x)
139968856327592
>>>x=x+1
>>>x
6
>>>id(x)
139968856327624

Функция id() показывает адрес памяти, где хранится объект.

Как видно, после выполнения операции x=x+1 ссылка x ведёт на другой адрес. Таким образом, то, что принято называть переменной, в Python является ссылкой на объект или именем переменной.

Упорядоченность

Упорядоченность структуры данных определяет, существует ли чёткий порядок элементов в структуре данных

• упорядоченные структуры имеют фиксированный порядок, например, список [2, 4, 6] всегда сохраняет эту последовательность, т.е. на нулевой позиции всегда будет 2, на первой - 4, на второй - 6. И к этим элементам можно обратиться по номеру позиции.

  Примеры: списки (list), кортежи (tuple), строки (str)

• неупорядоченные структуры содержат элементы, порядок которых явным образом не определён.

  например множество {1, 2, 3} в множестве может выводиться как {2, 1, 3}.

  Примеры: множества (set), словари (dict)

Списки

Список (list) - упорядоченная изменяемая коллекция объектов произвольных типов.

Объектами списка могут быть целые числа, вещественные числа, строки, списки (и другие структуры данных) и другие объекты.

Задача со списком (математика)

Рассмотрим задачу

Задача: Построить график функции для интервала .

Используемые инструменты:

• Пакет Matplotlib
• Объекты - списки

import matplotlib.pyplot as plt

x = [0, 1, 2, 3, 4, 5]
y = [0, 1, 4, 9, 16, 25]

plt.plot(x, y) # нарисовать график
plt.grid() # включить сетку
plt.show() # показать рисунок

Результат работы программы:

Способы создания списка

Создание пустого списка

>>>lst = []
>>>lst
[]

Другой вариант:

>>>lst = list()
>>>lst
[]

Создание списка с элементами

>>>lst = [1, 2, 3, 'a', 'b', True]  # Может содержать разные типы
>>>lst
[1, 2, 3, 'a', 'b', True]

Создание списка с помощью конструктора list()

>>>list('hello')  
['h', 'e', 'l', 'l', 'o']
>>>list(range(5))
[0, 1, 2, 3, 4]
>>>list((1, 2, 3))  # Конвертация кортежа
[1, 2, 3]

list() может конвертировать любую итерируемую коллекцию

Создание списка с помощью генератора списков (list comprehension)

>>>[x for x in range(10)]  
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

>>>[x**2 for x in range(5)]
[0, 1, 4, 9, 16]

>>>[c.upper() for c in 'hello']
['H', 'E', 'L', 'L', 'O']

>>>x = [0, 1, 2, 3, 4, 5]
>>>y = [a**2 for a in x] # одновременное создание и заполнение
>>>y
[0, 1, 4, 9, 16, 25]
>>>z = [a**2 for a in x if a > 2] 
>>>z
[9, 16, 25]

Генераторы списков - самый мощный и Python-образный способ создавать списки

Создание списка с помощью split() (из строки)

lst = "apple banana cherry".split()  # ['apple', 'banana', 'cherry']
lst = "1,2,3,4".split(',')  # ['1', '2', '3', '4']

Сложение списков

lst = [1, 2] + [3, 4]  # [1, 2, 3, 4]

Копирование списка

original = [1, 2, 3]
lst = original.copy()  # [1, 2, 3]
lst = list(original)  # Альтернативный вариант
lst = original[:]  # Срез от начала до конца

Создание списка с помощью оператора *

lst = [0] * 5  # [0, 0, 0, 0, 0]
lst = ['hello'] * 3  # ['hello', 'hello', 'hello']

* оператор удобен для создания однородных списков

Вложенные списки

matrix = [[1, 2], [3, 4], [5, 6]]

Создание списка с помощью функции map()

lst = list(map(str, range(3)))  # ['0', '1', '2']

Создание списка с помощью функции фильтрации filter()

lst = list(filter(lambda x: x > 0, [-2, -1, 0, 1, 2]))  # [1, 2]

Создание списка с помощью других коллекций

lst = list({'a': 1, 'b': 2})  # ['a', 'b'] (ключи словаря)
lst = list({1, 2, 3})  # [1, 2, 3] (из множества)

Для копирования лучше использовать методы .copy() или list()

Методы списка

Методы с объектом списка:

Кортежи

Кортеж (tuple) - упорядоченная неизменяемая коллекция объектов произвольных типов.

• Используются для защиты данных, которые не должны быть изменены.
• Удобен для передачи данных фиксированной длины и содержания между функциями/методами.
• Работает быстрее, чем список.

a = (1, 2, 3, 4, 5, 6)
a = ("John", 45, True)
a = (1,)

Множества

Множество (set) - неупорядоченная изменяемая коллекция неповторяющихся объектов произвольных типов. Удобны для удаления неповторяющихся значений.

a = set()
a = set('hello') # {'h', 'o', 'l', 'e'}
a = {'a', 'b', 'c', 'd'}
a = {i ** 2 for i in range(7)} # {0, 1, 4, 9, 16, 25}
a = {'a', 'b', 'c', 'a'} # {'a', 'b', 'c'}

words = ['break', 'file', 'break', 'one']
>>>set(words)
{'file', 'break', 'one'}

Методы множеств:

• in

  >>>a = {'a', 'b', 'c', 'd'}
  >>>'a' in a
  True  
  

• issubset(other) - истина, если все элементы set принадлежат other:

  >>>a = {'a', 'b', 'c', 'd'}
  >>>a.issubset({'a', 'b', 'c', 'd', 'f', 'e'})
  True
  

• union(other, …) - возвращает объединение нескольких множеств:

  >>>a = {'a', 'b', 'c', 'd'}
  >>>a.union({'f', 'd'})  
  {'b', 'a', 'c', 'f', 'd'}
  

Срезы (slices)

Срез - это механизм, позволяющий извлекать часть последовательности (например, списка, кортежа, строки) по начальному и(или) конечному индексам, а также с возможностью указания шага

Синтаксис среза

sequence[start:stop:step]

• start — начальный индекс (включительно, по умолчанию 0).
• stop — конечный индекс (не включается, по умолчанию до конца).
• step — шаг (по умолчанию 1, может быть отрицательным для обратного порядка).

Примеры срезов

Базовые срезы

nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

print(nums[2:5])    # [2, 3, 4] (элементы с индексами 2, 3, 4)
print(nums[:3])     # [0, 1, 2] (первые 3 элемента)
print(nums[5:])     # [5, 6, 7, 8, 9] (с 5-го до конца)
print(nums[::2])    # [0, 2, 4, 6, 8] (каждый второй элемент)
print(nums[::-1])   # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] (разворот списка)

Отрицательные индексы

Отрицательные значения отсчитываются с конца:

print(nums[-3:])    # [7, 8, 9] (последние 3 элемента)
print(nums[:-2])    # [0, 1, 2, 3, 4, 5, 6, 7] (все, кроме последних 2)

Особенности срезов

• Если индекс выходит за границы, Python не вызывает ошибку, а возвращает доступную часть.

  print(nums[100:200])  # [] (пустой список)
  

• Создание копии списка:

  copy = nums[:]  # полная копия списка
  

• Изменение списка через срезы:

  nums[2:5] = [10, 20, 30]  # замена элементов
  print(nums)  # [0, 1, 10, 20, 30, 5, 6, 7, 8, 9]
  

Словари

Словари - неупорядоченные изменяемые коллекции произвольных объектов с доступом по ключу.

• Данные в словарях хранятся в парах: ключ : значение.
• Словарь является реализацией ассоциативного массива в Python.
• В словаре не может быть двух элементов с одинаковыми ключами. Однако могут быть одинаковые значения у разных ключей.

Рассмотрим задачу, при решении которой удобно использовать словарь.

Задача: Написать программу, которая по введённому пользователем дню недели выводит заранее известное количество шагов, которое ему нужно пройти.

Код программы решения задачи:

steps = {'понедельник': 3500, 'вторник': 5000, 'среда': 6000, 'четверг': 8000, 'пятница': 10000, 'суббота': 4000, 'воскресенье': 0}

while True:
    print(steps[input('Введите день недели: ')])

Запустите программу с различными входными условиями.

Варианты создания и заполнения словаря

Создание словаря с помощью функции dict:

>>>d = dict(short='dict', long='dictionary')
>>>d
{'short': 'dict', 'long': 'dictionary'}

Создание словаря с помощью функции dict на основе списка кортежей

>>>d = dict([(1, 1), (2, 4)])
>>>d
{1: 1, 2: 4}

Получение значений словаря по ключу

>>>d = {'a': 2, 'b': 4, 'g': 9}
>>>d 
{'a': 2, 'b': 4, 'g': 9}
>>>d['b']
4
>>>d['g']
9

Создание пустого словаря и добавление к нему значений

>>>d = {}
>>>d['key1'] = 'value1'
>>>d
{'key1': 'value1'}

Добавление нескольких элементов с помощью метода update()

>>>d = {'a': 1}
>>>d.update({'b': 2, 'c': 3})
>>>d
{'a': 1, 'b': 2, 'c': 3}

Добавление элементов с проверкой с помощью метода setdefault()

>>>d = {'name': 'Alice'}
>>>d.setdefault('age', 25)  # Добавит, если ключа нет
25
>>>d.setdefault('name', 'Bob')  # Не добавит, т.к. ключ существует
'Alice'
>>>d
{'name': 'Alice', 'age': 25}
>>>d.update({'name': 'Bob'})  # Обновит существующее значение
>>>d
{'name': 'Bob', 'age': 25}

Объединение словарей с помощью оператора |=

>>>d = {'x': 10}
>>>d |= {'y': 20, 'z': 30}  # Объединение словарей
>>>d
{'x': 10, 'y': 20, 'z': 30}

Метод fromkeys() (инициализация с одним значением)

>>>keys = ['a', 'b', 'c']
>>>d = dict.fromkeys(keys, 0)  # Все значения 0
>>>d
{'a': 0, 'b': 0, 'c': 0}

Добавление через распаковку

>>>d = {'a': 1}
>>>new_items = {'b': 2, 'c': 3}
>>>d = {**d, **new_items}  # Распаковка словарей
>>>d
{'a': 1, 'b': 2, 'c': 3}

Добавление с проверкой через if

d = {}
key, value = 'color', 'blue'
if key not in d:
    d[key] = value
print(d)

Результат работы кода:

{'color': 'blue'}

Методы словарей

Задачи для самостоятельного решения

Зачада №1

Создайте список, состоящий из первых простых чисел.

Задача №2

Постройте график любой функции на диапазоне, границы которого заданы пользователем.

Задача №3

Напишите функцию, которая возвращает список общих элементов двух списков.

Задача №4

Реализуйте алгоритм пузырьковой сортировки для списка.

Задача №5

Дан словарь sales, где ключ — название товара, а значение — список продаж за последние 5 дней, например:

sales = {
    "Ноутбук": [12000, 15000, 9000, 11000, 13000],
    "Смартфон": [8000, 9500, 7000, 8500, 10000],
    "Планшет": [5000, 6000, 4000, 5500, 4500],
    "Наушники": [2000, 1500, 3000, 2500, 1800]
}

Напишите программу, которая строит подобный словарь по введённым пользователем значениям.

Выведите список товаров по убыванию суммарной выручки.