9126

Реализация элементарных абстрактных типов данных в Python

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

Очереди

queues

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

Чтобы реализовать очередь в 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 продолжает связный список.

Связный список

Изучение типов данных в 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" текущего узла, чтобы не потерялись следующие ссылки.

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

Оригинал

Другие материалы по теме:

РУБРИКИ В СТАТЬЕ

Комментарии

BUG
LIVE