SAKOD_lab3.py

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

# Класс 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 реализует двунаправленный список с операциями добавления,
           удаления, печати и поиска k-й порядковой статистики.

    \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  # устанавливаем p_first
            self.p_cur = p_tmp    # устанавливаем p_cur
            # Организуем циклическую связь для одиночного элемента
            p_tmp.p_next = p_tmp  # ссылка на самого себя как на следующий элемент
            p_tmp.p_prev = p_tmp  # ссылка на самого себя как на предыдущий элемент
        else:
            # Добавление нового элемента после текущего элемента p_cur
            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                # перемещаем указатель p_cur
        # Конец функции add

    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
        # Конец функции remove

    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()
        # Конец функции print_list

    def get_list_as_array(self):
        """
        \brief Функция преобразования списка в массив для сортировки или поиска.

        \retval list - массив значений элементов списка
        """
        if self.p_first is None:
            return []
        result = []
        p_tmp = self.p_first
        result.append(p_tmp.data)
        p_tmp = p_tmp.p_next
        while p_tmp != self.p_first:
            result.append(p_tmp.data)
            p_tmp = p_tmp.p_next
        return result

    def order_statistic(self, k):
        """
        \brief Функция поиска k-й порядковой статистики с помощью алгоритма QuickSelect.

        \param k [in] - порядковый номер искомого элемента (нумерация с 0).
        \retval tuple - (значение k-й статистики, количество перестановок) или (None, 0), если k некорректен
        """
        # Получаем массив элементов списка
        arr = self.get_list_as_array()
        if not arr or k < 0 or k >= len(arr):
            return None, 0

        # Счетчик перестановок
        swaps = [0]  # Используем список, чтобы изменять значение внутри вложенной функции

        def swap(arr, i, j):
            """Вспомогательная функция для перестановки элементов"""
            arr[i], arr[j] = arr[j], arr[i]
            swaps[0] += 1

        def partition(arr, left, right):
            """
            \brief Разделение массива относительно опорного элемента.

            \param arr [in/out] - массив для разделения
            \param left [in] - левая граница
            \param right [in] - правая граница
            \retval int - позиция опорного элемента после разделения
            """
            pivot = arr[left]  # Опорный элемент - первый в подмассиве
            i = left
            j = right
            while i <= j:
                while arr[i] < pivot:
                    i += 1
                while arr[j] > pivot:
                    j -= 1
                if i <= j:
                    swap(arr, i, j)
                    i += 1
                    j -= 1
            return i - 1

        def quick_select(arr, left, right, k):
            """
            \brief Рекурсивный алгоритм QuickSelect для поиска k-й статистики.

            \param arr [in/out] - массив для поиска
            \param left [in] - левая граница
            \param right [in] - правая граница
            \param k [in] - искомый индекс
            \retval int - значение k-й статистики
            """
            if left == right:
                return arr[left]
            pivot_idx = partition(arr, left, right)
            if k == pivot_idx:
                return arr[k]
            elif k < pivot_idx:
                return quick_select(arr, left, pivot_idx - 1, k)
            else:
                return quick_select(arr, pivot_idx + 1, right, k)

        # Запускаем QuickSelect и возвращаем результат с количеством перестановок
        result = quick_select(arr, 0, len(arr) - 1, k)
        return result, swaps[0]

def main():
    """
    \brief Основная функция программы, реализующая меню для работы со списком.

    \retval None
    """
    pList = DoublyLinkedList()

    while True:
        print("\nПожалуйста, введите номер команды:")
        print("0 - Выход")
        print("1 - Добавить элемент")
        print("2 - Удалить элемент")
        print("3 - Напечатать список")
        print("4 - Найти k-ю порядковую статистику")
        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:
            try:
                k = int(input("-- Введите номер k (нумерация с 0): "))
                result, swaps = pList.order_statistic(k)
                if result is not None:
                    print(f"k-я статистика (k={k}): {result}")
                    print(f"Количество перестановок: {swaps}")
                else:
                    print(f"k={k} некорректен или список пуст")
            except ValueError:
                print("Некорректный ввод k. Введите число.")
        else:
            print("!!! Неверный номер команды !!!")

if __name__ == "__main__":
    main()