Введение в структуры данных и алгоритмы на Python.

Это моя вторая статья после «Введения в современный Python 101», целью которой является обсуждение структур данных в Python, таких как списки, кортежи, множества, стек, словари, очереди, связанные списки и другие. Данные играют очень важную роль в различных областях, таких как машинное обучение, искусственный интеллект и веб-разработка, что означает, что данные должны быть упорядочены, правильно храниться и быть доступными в любое удобное время.
В этой статье вы познакомитесь со структурами данных Python: узнаете больше о структуре данных, типах структур данных в Python — встроенных структурах данных, а также структурах данных, определяемых пользователем, включая List, Dictionary, Tuple, Sets, Stack, Queue и др.

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

Структуры данных — это способ организации и хранения данных таким образом, чтобы к ним можно было получить доступ и эффективно работать с ними.
Структурированные данные приводят к появлению структурированных переменных, которые дают четкое определение взаимосвязи между данными и операциями, которые могут быть выполнены над этими данными.
Структурирование данных важно в python, так как оно облегчает программисту, специалисту по работе с данными или компьютерному инженеру задачу решения критических и больших проблем путем определения наилучшего способа эффективного прохождения программы и внесения точных изменений.

Типы структур данных в Python

В python есть встроенные типы данных, которые поддерживают структуры данных, позволяющие хранить коллекцию данных и иметь к ним одновременный доступ. К ним относятся List, Dictionary, Tuple и Set.
Следовательно, Python также позволяет многим программистам писать и разрабатывать свои собственные функции, что дает возможность управлять данными. Такие структуры данных, как стек, очередь, дерево, связанный список и другие, легко доступны и в других языках программирования, поэтому вы можете создавать различные функции данных, которые могут влиять на всю структуру данных.

Списки

Список — это способ дать одно имя коллекции значений. Эти значения или элементы могут иметь любой тип данных; int, float и т.д., а также более продвинутые типы Python, даже другие списки.
Списки используются для последовательного хранения данных различных типов. Каждому элементу списка присваивается адрес, который называется индексом.
Значение индекса начинается с 0 и продолжается до последнего элемента, называемого положительным индексом.
Существует также отрицательная индексация, которая начинается с -1, позволяющая обращаться к элементам от последнего к первому в списке.

Создание списка в Python

Вы используете квадратные скобки и добавляете в него элементы, соответственно разделенные запятыми.
Если вы не передадите ни одного элемента внутри квадратных скобок, на выходе вы получите пустой список.

thislist = [1, 3, 5, 'Hello', 9.91] #creating list with data
print(thislist)

thislist = [] #create empty list
print(thislist)
Вход в полноэкранный режим Выход из полноэкранного режима

Добавление и изменение элементов

Добавление элементов в список осуществляется с помощью функций append(), extend() и insert(), тогда как изменение элементов достигается путем определения списка с новыми значениями и последующего обращения к диапазону номеров индексов, в который необходимо вставить новые значения:

Функция append() добавляет все переданные ей элементы как один элемент.
Функция extend() добавляет элементы по одному в список.
Функция insert() добавляет элемент, переданный в индексном значении, и также увеличивает размер списка.
Список является мутабельным, что означает, что вы можете изменять и добавлять элементы без изменения их идентичности в списке после его создания.

thislist = [a, b, c]
print(thislist)

thislist.append([1, 2, 3]) #add as a single element
print(thislist)

thislist.extend([4, "Welcome", 2022]) #add as different elements
print(thislist)

thislist.insert(1, "adabracadabra") #add element i
print(thislist)
Вход в полноэкранный режим Выход из полноэкранного режима

Удаление элементов

Для удаления элементов используйте ключевое слово del, которое встроено в Python, но оно не возвращает никакого результата, поскольку удаляет список.
Если вы хотите вернуть элемент обратно, используйте функцию pop(), которая принимает значение индекса.
Для удаления элемента по его значению используется функция remove().

mylist = ["Maths", "English", "CRE", "Biology", "Physics"]
del mylist[5] #delete element at index 2
print(mylist)

mylist.remove("CRE") #remove element with value
print(mylist)

z = mylist.pop(1) #pop element from list
print('Popped Element: ', z, ' List remaining: ', mylist)

mylist.clear() #empty the list
print(mylist)
Вход в полноэкранный режим Выход из полноэкранного режима

Доступ к элементам

Элементы списка индексируются, и вы можете получить к ним доступ, передавая значения индексов и, следовательно, получая значения по мере необходимости.

mylist = ["Maths", "English", "CRE", "Biology", "Physics", 90]
for element in my_list: #access elements one by one
     print(element)

print(mylist) #access all elements
print(mylist[4]) #access index 3 element
print(mylist[0:4]) #access elements from 0 to 3 and exclude 4
print(mylist[-1]) #access elements in reverse
Вход в полноэкранный режим Выход из полноэкранного режима

Другие важные функции при работе со списками

Функция len() возвращает нам длину списка.
Функция index() находит значение индекса переданного значения, где оно встречается в первый раз.
Функция count() находит счетчик переданного ей значения.
Функции sorted() и sort() делают одно и то же, то есть сортируют значения списка. Функция sorted() имеет возвращаемый тип, а sort() изменяет исходный список.

my_list = [10, 20, 30, 40, 50, 60, 70, 80, 90, 40]
print(len(my_list)) #find length of list
print(my_list.index(40)) #find index of element that occurs first
print(my_list.count(40)) #find count of the element
print(sorted(my_list)) #print sorted list but not change original

my_list.sort(reverse=True) #sort original list
print(my_list)
Вход в полноэкранный режим Выход из полноэкранного режима

Кортеж

Кортежи похожи на списки, где несколько элементов хранятся в одной переменной, за исключением того, что после ввода данных в кортеж они остаются неизменными (неизменяемость).

Создание кортежа

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

tuple1 = (1, 2, 3, 4, 5, 6) #create tuple
tuple2 = ("Hello", 2019 , "Hi", [10, 20, 30]);
tuple3 = False, "a", "b", True #create tuple without parenthesis
print(tuple1)
print(tuple2)
print(tuple3)
Вход в полноэкранный режим Выход из полноэкранного режима

Доступ к элементам кортежа

Вы можете получить доступ к элементам кортежа, обращаясь к номеру индекса внутри квадратных скобок.
Доступ к элементам в кортеже аналогичен доступу к значениям в списках.

mytuple = (a, b, c, 'Hello world', 3.142, 9) #access elements
for x in mytuple:
    print(x)
print(mytuple)
print(mytuple[0])
print(mytuple[:])
print(mytuple[3][4])
Вход в полноэкранный режим Выход из полноэкранного режима

Добавление элементов в кортеж

Для добавления значений используется оператор ‘+’, который принимает другой кортеж для добавления к нему.

thistuple = (100, 200, 300)
thistuple = thistuple + (400, 500, 600) #add elements
print(thistuple)
Войти в полноэкранный режим Выход из полноэкранного режима

Другие функции в кортеже

Эти функции такие же, как и для списков.

my_tuple = (a, b, c, ['Java', 'python', 'CSS', 'C++'])
my_tuple[3][0] = 'HTML' 

print(my_tuple)
print(my_tuple.count(2))
print(my_tuple.index(['Java', 'python', 'CSS', 'C++']))
Войти в полноэкранный режим Выйти из полноэкранного режима

Словарь

Словарь — это коллекция элементов, где каждый элемент словаря имеет пару ключ/значение, которая хранит значения данных в этих парах ключ:значение.
Словари состоят из пар ключ-значение. Ключ используется для идентификации элемента, а значение элемента.
Ключи уникальны в пределах словаря, в то время как значения могут быть не уникальны. Значения словаря могут быть любого типа, но ключи должны быть неизменяемыми типами данных, такими как строки, числа или кортежи.
Элементы словаря представлены в виде пар ключ:значение, и на них можно ссылаться, используя имя ключа.

Создание словаря

Словари можно создавать с помощью фигурных скобок {} или с помощью функции dict(). При работе со словарями необходимо добавлять пары ключ-значение.

my_dict = {} #empty dictionary
print(my_dict)

my_dict = {1: 'apple', 2: 'banana'} #dictionary with elements
print(my_dict)
Вход в полноэкранный режим Выход из полноэкранного режима

Изменение и добавление пар ключ-значение

Чтобы изменить значения словаря, необходимо сделать это с помощью ключей. То есть сначала вы обращаетесь к ключу, а затем изменяете значение соответственно. Чтобы добавить значения, просто добавьте еще одну пару ключ-значение, как показано ниже.

mydict = {'First': 'Python', 'Second': 'Java', 'Third': 'CSS'}
print(mydict)

mydict['Second'] = 'HTML' #changing element
print(mydict)

mydict['Forth'] = 'C++' #adding key-value pair
print(mydict)
Войти в полноэкранный режим Выход из полноэкранного режима

Удаление пар ключ-значение

Для удаления значений используется функция pop(), которая возвращает удаленное значение.
Для извлечения пары ключ-значение используется функция popitem(), которая возвращает кортеж из ключа и значения.
Чтобы очистить весь словарь, используйте функцию clear().

thisdict = {'First': 'HTML', 'Second': 'CSS', 'Third': 'Java'}
a = thisdict.pop('Second') #pop element
print('Value:', a)
print('Dictionary:', thisdict)
b = thisdict.popitem() #pop the key-value pair
print('Key, value pair:', b)
print('Dictionary', thisdict)

thisdict.clear() #empty dictionary
print('n', thisdict)
Вход в полноэкранный режим Выход из полноэкранного режима

Доступ к элементам

Доступ к элементам можно получить только с помощью клавиш. Вы можете использовать либо функцию get(), либо просто передать значения клавиш, и вы будете извлекать значения.

my_dict = {'First': 'Javascript', 'Second': 'Python'}
print(my_dict['First']) #access elements using keys
print(my_dict.get('Second'))
Вход в полноэкранный режим Выход из полноэкранного режима

Другие функции

У вас есть различные функции, которые возвращают нам ключи или значения пары ключ-значение в соответствии с функциями keys(), values(), items() соответственно.

my_dict = {'First': 'Java', 'Second': 'Python', 'Third': 'HTML'}
print(my_dict.keys()) #get keys
print(my_dict.values()) #get values
print(my_dict.items()) #get key-value pairs
print(my_dict.get('First'))
Вход в полноэкранный режим Выход из полноэкранного режима

Наборы

Наборы — это коллекция неупорядоченных элементов, которые являются уникальными. Это означает, что даже если данные повторяются несколько раз, они будут внесены в набор только один раз.
Наборы также можно использовать для выполнения математических операций с наборами, таких как объединение, пересечение, симметричная разность и т.д.
Отличие множеств от списков и кортежей заключается в том, что множества не могут иметь несколько вхождений одного и того же элемента (дубликаты или повторяющиеся элементы) и могут хранить неупорядоченные значения.

Создание множества в Python

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

my_set = {1, 2, 3, 4, 5, 5, 5, 6} #create set
print(my_set)
Вход в полноэкранный режим Выход из полноэкранного режима

Добавление элементов в набор

Чтобы добавить элементы, вы используете функцию add() и передаете ей значение.

myset = {11, 12, 13}
myset.add(14) #add element to set
print(my_set)
Вход в полноэкранный режим Выход из полноэкранного режима

Операции в наборах

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

myset_1 = {1, 2, 3, 4}
myset_2 = {3, 4, 5, 6}
print(myset_1.union(myset_2), '----------', myset_1 | myset_2)
print(myset_1.intersection(myset_2), '----------', myset_1 & myset_2)
print(myset_1.difference(myset_2), '----------', myset_1 - myset_2)
print(myset_1.symmetric_difference(myset_2), '----------', myset_1 ^ myset_2)
myset_1.clear()
print(myset_1)
Вход в полноэкранный режим Выход из полноэкранного режима

В приведенной выше программе вы видите следующее:

  • Функция union() объединяет данные, присутствующие в обоих наборах.
  • Функция intersection() находит данные, присутствующие только в обоих наборах.
  • Функция difference() удаляет данные, присутствующие в обоих наборах, и выводит данные, присутствующие только в переданном наборе.
  • Функция symmetric_difference() выполняет то же самое, что и функция difference(), но выводит данные, оставшиеся в обоих наборах.

Определяемые пользователем структуры данных

Массивы Python

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

fruits = ["apple", "grapes", "mango", "plums"]  
print (fruits)
Войти в полноэкранный режим Выйти из полноэкранного режима

Массивы позволяют обращаться к элементам массива с помощью индекса, который обычно начинается с нуля.

fruits = ["apple", "grapes", "mango", "plums"]  
x = fruits[1]  
print (x) 
Войти в полноэкранный режим Выйти из полноэкранного режима

Аналогично доступу к элементу, вы можете изменять элемент с помощью индекса.

fruits = ["apple", "grapes", "mango", "plums"]  
fruits[2] = "melon"  
print (fruits)
Войти в полноэкранный режим Выход из полноэкранного режима

Узнать количество элементов в массиве можно с помощью метода len().

fruits = ["apple", "grapes", "mango", "plums"]  
print (len(fruits))  # prints 4  
Вход в полноэкранный режим Выход из полноэкранного режима

Оператор for используется для перебора элементов массива. Вы обрабатываете отдельные элементы внутри цикла.

fruits = ["mango", "apple", "grapes"]  

for i in fruits:  
     print(i)
Войти в полноэкранный режим Выход из полноэкранного режима

Метод append() добавляет новый элемент в конец массива так же, как и в список, поскольку массивы являются изменяемыми.

fruits = ["apple", "grapes", "mango", "plums"]  

fruits.append("guava")  
print(fruits)
Вход в полноэкранный режим Выход из полноэкранного режима

Для удаления элементов из массива полезны два метода. Метод pop() принимает индекс массива и удаляет элемент в определенной позиции. remove() принимает значение элемента и удаляет его. Например:

fruits = ["apple", "grapes", "mango", "plums"]  

fruits.pop(2)  
print(fruits)  

fruits.remove("mango")  
print(fruits)  
Войти в полноэкранный режим Выйти из полноэкранного режима

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

Стек — это контейнер объектов, которые вставляются и удаляются в соответствии с концепцией LIFO (Last-In-First-Out).
Стеки — это линейные структуры данных, которые основаны на принципе Last-In-First-Out (LIFO), где данные, которые были введены последними, будут доступны первыми. Он строится с использованием структуры массива и имеет операции, а именно, операции push (добавление элементов), pop (удаление, снятие или доступ к элементам) только из одной точки стека, называемой TOP. Этот TOP является указателем на текущую позицию стека.

Основные операции со стеком

Существует несколько основных операций, которые позволяют выполнять различные действия над стеком. К ним относятся:

Push: Добавить элемент на вершину стека.
Pop: Удалить элемент с вершины стека
IsEmpty: Проверить, пуст ли стек
IsFull: Проверяет, заполнен ли стек.
Peek: Получение значения верхнего элемента без его удаления

   # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 (Top)
stack = [1,2,3,4,5] 
stack.append(6) # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 (Top)
print(stack)

stack.pop() # Bottom -> 1 -> 2 -> 3 -> 4 -> 5 (Top)
stack.pop() # Bottom -> 1 -> 2 -> 3 -> 4 (Top)
print(stack)
Вход в полноэкранный режим Выход из полноэкранного режима

Операции вставки и выгрузки стека

Операции выполняются следующим образом:

  • Указатель TOP используется для отслеживания верхнего элемента в стеке.
  • При инициализации стека мы устанавливаем его значение равным -1, чтобы можно было проверить, пуст ли стек, сравнив TOP == -1.
  • При выталкивании элемента мы увеличиваем значение TOP и помещаем новый элемент в позицию, на которую указывает TOP.
  • При выталкивании элемента мы возвращаем элемент, на который указывает TOP, и уменьшаем его значение.
  • Перед выталкиванием мы проверяем, не заполнен ли стек.
  • Перед выталкиванием мы проверяем, не пуст ли стек.


На рисунке выше, хотя элемент 3 был сохранен последним, он был удален первым. Это принцип LIFO (Last In First Out).
Мы можем реализовать стек на любом языке программирования, например, C, C++, Java, Python или C#, но спецификация практически одинакова.

Применение структуры данных Stack

Структуры данных стека используются :

Чтобы перевернуть слово — поместите все буквы в стек и выньте их оттуда. Благодаря принципу LIFO стека, вы получите буквы в обратном порядке.
В компиляторах — Компиляторы используют стек для вычисления значения выражений типа 2 + 4 / 5 * (7 — 9) путем преобразования выражения в префиксную или постфиксную форму.
В браузерах — Кнопка «назад» в браузере сохраняет в стеке все URL-адреса, которые вы посещали ранее. Каждый раз, когда вы посещаете новую страницу, она добавляется на вершину стопки. Когда вы нажимаете кнопку «назад», текущий URL удаляется из стопки, и открывается доступ к предыдущему URL.

Структура данных очереди

Очередь — это контейнер объектов, которые вставляются и удаляются в соответствии с принципом «первый пришел — первый ушел» (FIFO).
Очередь также является линейной структурой данных, основанной на принципе «первый вошел — первый вышел» (FIFO), когда данные, введенные первыми, будут доступны первыми. Она построена с использованием структуры массива и имеет операции, которые могут выполняться с обоих концов очереди, то есть с головы до хвоста или спереди назад. Такие операции, как добавление и удаление элементов, называются En-Queue и De-Queue, и доступ к элементам может быть осуществлен.

На изображении выше, поскольку 1 был первым в очереди раньше 2, он первым будет удален из очереди. Это и есть правило FIFO.

Операции с очередью

Очередь — это абстрактная структура данных ADT, которая позволяет выполнять следующие операции:

  • Enqueue: Добавить элемент в конец очереди.
  • Dequeue: Удалить элемент из передней части очереди.
  • IsEmpty: Проверить, пуста ли очередь
  • IsFull: Проверяет, заполнена ли очередь.
  • Peek: Получить значение передней части очереди, не удаляя ее.

Операции с очередью работают следующим образом:

  1. два указателя FRONT и REAR
  2. FRONT отслеживает первый элемент очереди
  3. REAR отслеживает последний элемент очереди
  4. первоначально, установите значения FRONT и REAR равными -1

Операция вызова

  • проверить, заполнена ли очередь
  • для первого элемента установите значение FRONT равным 0
  • увеличить индекс REAR на 1
  • добавить новый элемент в позицию, на которую указывает REAR

Операция выгрузки

  • проверить, пуста ли очередь
  • вернуть значение, на которое указывает FRONT
  • увеличить индекс FRONT на 1
  • для последнего элемента сбросьте значения FRONT и REAR на -1


N/B:

  • Вставка и удаление в очереди происходят на разных концах. Поэтому нам необходимо отслеживать передний и задний конец очереди.
  • Хотя очередь имеет возможность увеличивать свой размер, очередь может иметь и максимальный размер. Если мы попытаемся вставить элемент, превышающий максимальный размер, это приведет к переполнению.
  • Если мы попытаемся удалить элемент из пустой очереди, это приведет к переполнению.
  • Операция enqueue вставляет элемент в очередь. Временная сложность операции enqueue() равна O(1).
  • Операция dequeue удаляет элемент из очереди. Временная сложность операции dequeue() также равна O(1).

Применение очередей в Python

  1. Планирование работы процессора, планирование работы диска
  2. Когда данные передаются асинхронно между двумя процессами. Очередь используется для синхронизации. Например: Буферы ввода-вывода, каналы, файловый ввод-вывод и т.д.
  3. Обработка прерываний в системах реального времени.
  4. Телефонные системы Call-центров используют очереди, чтобы держать людей, звонящих им, в порядке очереди.

Связанные списки

Связанные списки — это линейные структуры данных, которые не хранятся последовательно, а связаны друг с другом с помощью указателей. Узел связанного списка состоит из данных и указателя, называемого next.
Вы разрабатываете связанные списки с помощью следующих операций:

  • Создать список с заданными элементами
  • Отобразить элементы в списке
  • Найти количество элементов в списке
  • Извлечь элемент в заданной позиции
  • Добавить или удалить элемент(ы)


Здесь вы видите связный список как набор узлов. Первый узел называется HEAD, и он используется в качестве начальной точки для любой итерации по списку. Последний узел должен иметь следующую ссылку, указывающую на NULL, чтобы определить конец списка.

Типы связных списков

К ним относятся:

  • Односвязные списки
  • Двусвязные списки
  • Циклические связные списки
  • Циклические двусвязные списки

Приложения связанных списков

  • Динамическое распределение памяти
  • Реализовано в стеках и очередях
  • В функциональности отмены в программном обеспечении
  • Хэш-таблицы, графы

Алгоритмы работы с данными в Python

Алгоритмы Python — это набор инструкций, которые выполняются для получения решения поставленной задачи.
Поскольку алгоритмы не зависят от языка, не существует набора языковых правил, как писать алгоритмы, и они обычно реализуются на нескольких языках программирования.
Алгоритмы данных обеспечивают руководство для решения проблемы анализа данных и играют важную роль для компьютерных ученых/программистов для обработки информации, предоставленной в качестве входных данных.

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *