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

2019-05-25 09:00

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

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

Чтобы реализовать очередь в Python, нужно создать класс и инициализировать его пустым списком. Одним из свойств очереди является то, что первые элементы в очереди выходят первыми (FIFO – first-in, first-out). Снова вернемся к нашему примеру с баром: клиенты, попавшие в очередь раньше, будут обслужены раньше.

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

classQueue:

def __init__(self):

self.people=[]

def add(self,person):

self.people.insert(0,person)

Для удаления элемента из очереди используется метод pop():

classQueue:

def __init__(self):

self.people=[]

def add(self,person):

self.people.insert(0,person)

def remove(self):

returnself.people.pop()

Чтобы узнать размер нашей очереди, можно воспользоваться встроенным в Python методом len():

classQueue:

def __init__(self):

self.people=[]

def add(self,person):

self.people.insert(0,person)

def remove(self):

returnself.people.pop()

def size(self):

returnlen(self.people)

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

Основным отличием стека от очереди, является способ организации и манипулирования данными. В стеке используется алгоритм LIFO (last-in, first-out) – последний добавленный элемент извлекается первым.

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

classStack:

def __init__(self):

self.elements=[]

def push(self,element):

self.elements.append(element)

def pop(self):

returnself.elements.pop()

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

Список абстрактных типов данных в Python продолжает связный список.

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

В качестве реализации связного списка, создается класс Node.

classNode:

def __init__(self,data):

self.data=data

self.next=None

def getData(self):

returnself.data

def getNext(self):

returnself.next

def setNext(self,next):

self.next=next

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

getData() – проверка значения данных;
getNext() – получение ссылки на следующую ноду;
setNext() – установка ссылки на следующий узел.

classLinkedList:

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

whilecurrent!=None:

count+=1

current=current.getNext()

returncount

По умолчанию связный список пустой, поэтому свойство head инициализировано как «None». Когда создается новый узел, ему назначается ссылка на ноду head, а следующему – на предыдущий и последующий и т. д. В примере ниже рассматривается поиск элемента.

classLinkedList:

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

whilecurrent!=None:

count+=1

current=current.getNext()

returncount

def search(self,value):

current=self.head

found=False

whilecurrent!=None andnotfound:

ifcurrent.getData()==value:

found=True

else:

current=current.getNext()

returnfound

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

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

classLinkedList:

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

whilecurrent!=None:

count+=1

current=current.getNext()

returncount

def search(self,value):

current=self.head

found=False

whilecurrent!=None andnotfound:

ifcurrent.getData()==value:

found=True

else:

current=current.getNext()

returnfound

def remove(self,value):

current=self.head

previous=None

found=False

whilenotfound:

ifcurrent.getData()==value:

found=True

else:

previous=current

current=current.getNext()

ifprevious==None:

self.head=current.getNext()

else:

previous.setNext(current.getNext())

Здесь просматривается связный список так же, как и при поиске, за исключением того, что известен предыдущий узел. После нахождения искомого элемента, свойство «next» предыдущего узла устанавливается в качестве свойства «next» текущего узла, чтобы не потерялись следующие ссылки.

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

Источник: medium.com

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

Комментарии: