SAKOD_lab4.py

#!/usr/bin/env python3
# \author: Артюхин Матфей
# \date_start: 2025-03-22
# \date_end: 2025-03-27

# Класс Node - элемент двунаправленного списка
class Node:
    """
    \brief Класс Node представляет элемент двунаправленного списка.

    \param data [in]       - данные элемента (числовые, строковые, даты и т.п.)
    \param p_next [in/out] - ссылка на следующий элемент списка
    \param p_prev [in/out] - ссылка на предыдущий элемент списка
    """
    def __init__(self, data):
        # Инициализация данных элемента
        self.data = data  # данные элемента
        self.p_next = None  # указатель на следующий элемент
        self.p_prev = None  # указатель на предыдущий элемент

# Класс DoublyLinkedList - реализация двунаправленного списка
class DoublyLinkedList:
    """
    \brief Класс DoublyLinkedList реализует двунаправленный список с операциями добавления,
           удаления, печати, сортировки и дихатомического(бинарного) поиска.

    \param p_first [in/out] - указатель на первый элемент списка
    \param p_cur [in/out]   - указатель на текущий элемент списка (для удобства добавления)
    """
    def __init__(self):
        # Инициализация указателей списка
        self.p_first = None  # указатель на первый элемент списка
        self.p_cur = None    # указатель на текущий элемент списка

    def add(self, item):
        """
        \brief Функция добавления элемента в список.

        \param item [in] - значение добавляемого элемента.
        \retval None
        """
        # Создаем новый элемент списка с заданным значением
        p_tmp = Node(item)
        # Если список пуст, новый элемент становится первым
        if self.p_first is None:
            self.p_first = p_tmp
            self.p_cur = p_tmp
            # Организуем циклическую связь
            p_tmp.p_next = p_tmp
            p_tmp.p_prev = p_tmp
        else:
            # Добавление после текущего элемента
            p_tmp.p_next = self.p_cur.p_next
            p_tmp.p_prev = self.p_cur
            self.p_cur.p_next.p_prev = p_tmp
            self.p_cur.p_next = p_tmp
            self.p_cur = p_tmp

    def remove(self, item):
        """
        \brief Функция удаления элемента из списка по значению.

        \param item [in] - значение удаляемого элемента.
        \retval None
        """
        if self.p_first is None:
            return

        p_tmp = self.p_first
        while True:
            if p_tmp.data == item:
                if p_tmp.p_next == p_tmp:
                    self.p_first = None
                    self.p_cur = None
                else:
                    if p_tmp == self.p_first:
                        self.p_first = p_tmp.p_next
                    p_tmp.p_prev.p_next = p_tmp.p_next
                    p_tmp.p_next.p_prev = p_tmp.p_prev
                    if p_tmp == self.p_cur:
                        self.p_cur = p_tmp.p_prev
                return
            p_tmp = p_tmp.p_next
            if p_tmp == self.p_first:
                break

    def print_list(self):
        """
        \brief Печать элементов списка.

        \retval None
        """
        if self.p_first is None:
            print("Список пуст")
            return
        print("Элементы списка:", end=" ")
        p_tmp = self.p_first
        print(p_tmp.data, end=" ")
        p_tmp = p_tmp.p_next
        while p_tmp != self.p_first:
            print(p_tmp.data, end=" ")
            p_tmp = p_tmp.p_next
        print()

    def sort(self):
        """
        \brief Сортировка списка методом пузырька.

        \retval None
        """
        if self.p_first is None or self.p_first.p_next == self.p_first:
            return

        swapped = True
        while swapped:
            swapped = False
            current = self.p_first
            while True:
                next_node = current.p_next
                if next_node == self.p_first:
                    break
                if current.data > next_node.data:
                    current.data, next_node.data = next_node.data, current.data
                    swapped = True
                current = next_node

    def is_sorted(self):
        """
        \brief Проверка отсортированности списка по возрастанию.

        \retval bool - True, если список отсортирован
        """
        if self.p_first is None:
            return True
        current = self.p_first
        while True:
            next_node = current.p_next
            if next_node == self.p_first:
                break
            if current.data > next_node.data:
                return False
            current = next_node
        return True

    def get_list_as_array(self):
        """
        \brief Преобразование списка в массив.

        \retval list - массив данных списка
        """
        arr = []
        if self.p_first is None:
            return arr
        p_tmp = self.p_first
        arr.append(p_tmp.data)
        p_tmp = p_tmp.p_next
        while p_tmp != self.p_first:
            arr.append(p_tmp.data)
            p_tmp = p_tmp.p_next
        return arr

    def binary_search(self, value):
        """
        \brief Бинарный поиск значения в отсортированном списке.

        \param value [in] - искомое значение
        \retval tuple - (значение, индекс) или (None, -1) при ошибке
        """
        if not self.is_sorted():
            return None, -1
        arr = self.get_list_as_array()
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == value:
                return arr[mid], mid
            elif arr[mid] < value:
                left = mid + 1
            else:
                right = mid - 1
        return None, -1

def main():
    """
    \brief Основная функция с меню управления.

    \retval None
    """
    pList = DoublyLinkedList()
    while True:
        print("\nПожалуйста, введите номер команды:")
        print("0 - Выход")
        print("1 - Добавить элемент")
        print("2 - Удалить элемент")
        print("3 - Напечатать список")
        print("4 - Отсортировать список")
        print("5 - Бинарный поиск")
        try:
            menuPos = int(input("Введите команду: "))
        except ValueError:
            print("Некорректный ввод.")
            continue

        if menuPos == 0:
            print("... Завершение работы ...")
            break
        elif menuPos == 1:
            data = input("-- Введите значение элемента: ")
            try:
                data = int(data)
            except ValueError:
                pass
            pList.add(data)
        elif menuPos == 2:
            data = input("-- Введите значение элемента: ")
            try:
                data = int(data)
            except ValueError:
                pass
            pList.remove(data)
        elif menuPos == 3:
            pList.print_list()
        elif menuPos == 4:
            pList.sort()
            print("Список отсортирован.")
        elif menuPos == 5:
            if pList.is_sorted():
                data = input("-- Введите искомое значение: ")
                try:
                    data = int(data)
                except ValueError:
                    print("Ошибка ввода!")
                    continue
                result, index = pList.binary_search(data)
                if result is not None:
                    print(f"Найдено: {result} (индекс {index})")
                else:
                    print("Элемент не найден.")
            else:
                print("Список не отсортирован!")
        else:
            print("Неверная команда!")

if __name__ == "__main__":
    main()