Реализация элементарных абстрактных типов данных в Python
Существует множество типов данных в Python, применяемых в различных задачах. В этой статье пойдет речь об абстрактных типах данных.
Очереди
Очереди – это способ более эффективной организации данных. Пример очереди из реальной жизни – вереница людей в баре. Если бы каждый самостоятельно привлекал внимание бармена, это привело бы к сплошному хаосу. Выход из ситуации – выстроить всех в один ряд.
Чтобы реализовать очередь в Python, нужно создать класс и инициализировать его пустым списком. Одним из свойств очереди является то, что первые элементы в очереди выходят первыми (FIFO – first-in, first-out). Снова вернемся к нашему примеру с баром: клиенты, попавшие в очередь раньше, будут обслужены раньше.
Метод "add", используемый для представления очереди, добавляет элемент в конец строки. Чтобы добавить элемент в начало строки, используется метод insert() с нулевым индексом.
class Queue:
def __init__(self):
self.people = []
def add(self, person):
self.people.insert(0, person)
Для удаления элемента из очереди используется метод pop():
class Queue:
def __init__(self):
self.people = []
def add(self, person):
self.people.insert(0, person)
def remove(self):
return self.people.pop()
Чтобы узнать размер нашей очереди, можно воспользоваться встроенным в Python методом len():
class Queue:
def __init__(self):
self.people = []
def add(self, person):
self.people.insert(0, person)
def remove(self):
return self.people.pop()
def size(self):
return len(self.people)
Следующим из абстрактных типов данных Python, который часто используется, является стек.
Стек
Основным отличием стека от очереди, является способ организации и манипулирования данными. В стеке используется алгоритм LIFO (last-in, first-out) – последний добавленный элемент извлекается первым.
В Python создать класс стека довольно просто: инициализируется пустой список и создаются методы, позволяющие добавлять и удалять элементы с одной стороны.
class Stack:
def __init__(self):
self.elements = []
def push(self, element):
self.elements.append(element)
def pop(self):
return self.elements.pop()
Реализация стека может показаться тривиальной, но с его помощью можно решить массу интересных задач, например, преобразование десятичных дробей в двоичные числа.
Список абстрактных типов данных в Python продолжает связный список.
Связный список
Связный список представляет собой коллекцию узлов, где каждый узел (за исключением последнего) указывает на следующий. Cвязные списки используются редко, но знать о них полезно, т. к. это облегчит понимание других структур данных.
В качестве реализации связного списка, создается класс Node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
def getData(self):
return self.data
def getNext(self):
return self.next
def setNext(self, next):
self.next = next
По умолчанию нода не будет иметь никакой ссылки на следующий узел. Связный список будет реализован при помощи трех методов:
- getData() – проверка значения данных;
- getNext() – получение ссылки на следующую ноду;
- setNext() – установка ссылки на следующий узел.
class LinkedList:
def __init__(self):
self.head = None
def add(self, value):
temp = Node(value)
temp.setNext(self.head)
self.head = temp
def length(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
По умолчанию связный список пустой, поэтому свойство head инициализировано как "None". Когда создается новый узел, ему назначается ссылка на ноду head, а следующему – на предыдущий и последующий и т. д. В примере ниже рассматривается поиск элемента.
class LinkedList:
def __init__(self):
self.head = None
def add(self, value):
temp = Node(value)
temp.setNext(self.head)
self.head = temp
def length(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
def search(self, value):
current = self.head
found = False
while current != None and not found:
if current.getData() == value:
found = True
else :
current = current.getNext()
return found
Для поиска по связному списку или вычисления его длины, в цикле перебираются ссылки на ноды, пока не будет найден искомый элемент, или пока цикл не достигнет конца (свойство узла "None"). Каждая итерация цикла будет проходить по списку, используя ссылку на следующий узел.
В то время как добавление или поиск элемента в списке кажется простым, удаление узла выглядит немного сложнее. Если удалить ссылку на следующий узел, то удалится не только следующий узел, но и ссылки на узлы, идущие дальше по цепочке. Чтобы избежать этой проблемы, можно сохранить ссылку на предыдущий узел во временную переменную, для манипуляций со ссылками на соседние узлы.
class LinkedList:
def __init__(self):
self.head = None
def add(self, value):
temp = Node(value)
temp.setNext(self.head)
self.head = temp
def length(self):
current = self.head
count = 0
while current != None:
count += 1
current = current.getNext()
return count
def search(self, value):
current = self.head
found = False
while current != None and not found:
if current.getData() == value:
found = True
else :
current = current.getNext()
return found
def remove(self, value):
current = self.head
previous = None
found = False
while not found:
if current.getData() == value:
found = True
else :
previous = current
current = current.getNext()
if previous == None:
self.head = current.getNext()
else:
previous.setNext(current.getNext())
Здесь просматривается связный список так же, как и при поиске, за исключением того, что известен предыдущий узел. После нахождения искомого элемента, свойство "next" предыдущего узла устанавливается в качестве свойства "next" текущего узла, чтобы не потерялись следующие ссылки.