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

3
6527
Добавить в избранное

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

Очереди

queues

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

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

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

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

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

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

Стек

Стек

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

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

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

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

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

Изучение типов данных в Python

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

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

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

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

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

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

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

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

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

Оригинал

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

Интересуетесь программированием на Python?

Подпишитесь на нашу рассылку, чтобы получать больше интересных материалов:

И не беспокойтесь, мы тоже не любим спам. Отписаться можно в любое время.




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

  1. спасибо, хорошо написано

  2. Простите, но это не НЕ АБСТРАКТНЫЕ ТИПЫ данных.
    Это вполне ПРАКТИЧЕСКИЕ РЕАЛИЗАЦИИ СТРУКТУР данных.
    Совсем хреново у автора с терминологией.

  3. Вместо такого вот вычисления размера связанного списка почему бы не увеличивать self.count при добавлении нового элемента и уменьшать при…?

Добавить комментарий