Операции над базовыми структурами данных

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

Содержание

Основные операции
Добавление элементов
1Удаление элементов
Поиск элементов
Сортировка
Сложность алгоритмов
Практическое задание
Задание:
Пример структуры задания:
Пример решения задачи
Функции для массивов (на основе списков)
Реализация связного списка и операций
Тесты (используем unittest)
Как запустить:

Основные операции

Добавление элементов

Добавление в массивы:
При добавлении элемента в массив необходимо учитывать, что массив имеет фиксированный размер. Если массив заполнен, потребуется создать новый массив большего размера и скопировать в него элементы старого массива

Пример кода для добавления в массив:

def add_to_array(arr, element):
    arr.append(element)  # Добавляем элемент в конец массива
    return arr

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

Пример кода для добавления в связный список:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add_to_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

1Удаление элементов

Удаление из массивов:
При удалении элемента из массива необходимо сдвинуть все последующие элементы на одну позицию влево, чтобы заполнить образовавшуюся пустую ячейку

Пример кода для удаления из массива:

def remove_from_array(arr, element):
    if element in arr:
        arr.remove(element)  # Удаляем элемент из массива
    return arr

Удаление из связного списка:
В связном списке удаление элемента также проще: нужно лишь изменить указатели

Пример кода для удаления из связного списка:

def remove_node(self, key):
    current_node = self.head
    if current_node and current_node.data == key:
        self.head = current_node.next
        current_node = None
        return
    prev_node = None
    while current_node and current_node.data != key:
        prev_node = current_node
        current_node = current_node.next
    if current_node is None:
        return
    prev_node.next = current_node.next
    current_node = None

Поиск элементов

Поиск в массивах:
Поиск элемента в массиве можно выполнить линейным или бинарным методом. Линейный поиск проходит по всем элементам, а бинарный требует предварительной сортировки массива

Пример кода для линейного поиска:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

Поиск в связном списке:
Поиск в связном списке также выполняется линейным методом

Пример кода для поиска в связном списке:

def search_node(self, key):
    current_node = self.head
    while current_node:
        if current_node.data == key:
            return current_node
        current_node = current_node.next
    return None

Сортировка

Сортировка массивов:
Существует множество алгоритмов сортировки. Рассмотрим пузырьковую сортировку как один из простейших вариантов.

Пример кода для пузырьковой сортировки:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  # Меняем местами
    return arr

Сортировка связных списков:
Сортировка связного списка может быть реализована с помощью алгоритма сортировки слиянием

Пример кода для сортировки связного списка:

def merge_sort(head):
    if not head or not head.next:
        return head
    middle = get_middle(head)
    next_to_middle = middle.next
    middle.next = None
    left = merge_sort(head)
    right = merge_sort(next_to_middle)
    sorted_list = sorted_merge(left, right)
    return sorted_list

Сложность алгоритмов

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

Добавление:
В массиве: O(n) в худшем случае (при необходимости увеличения размера)
В связном списке: O(1) при добавлении в начало, O(n) при добавлении в конец
Удаление:
В массиве: O(n) (сдвиг элементов)
В связном списке: O(n) (поиск элемента)
Поиск:
В массиве: O(n) для линейного поиска, O(log n) для бинарного поиска
В связном списке: O(n)
Сортировка:
Пузырьковая сортировка: O(n^2)
Сортировка слиянием: O(n log n)

Практическое задание

Теперь, когда мы изучили основные операции, давайте применим полученные знания на практике. Ваша задача — реализовать функции для выполнения операций над массивами и связными списками.

Задание:

Реализуйте функции для добавления, удаления, поиска и сортировки для массивов
Реализуйте аналогичные функции для связных списков
Напишите тесты для проверки корректности работы ваших функций

Пример структуры задания:

# Пример функции добавления для массива
def add_to_array(arr, element):
    # Ваш код здесь

# Пример функции поиска для связного списка
def search_node(self, key):
    # Ваш код здесь

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

Пример решения задачи

Давайте реализуем требуемые функции для массивов и связных списков на Python, а затем напишем тесты

Функции для массивов (на основе списков)

def array_add(arr, element):
    """Добавление элемента в конец массива"""
    return arr + [element]

def array_remove(arr, element):
    """Удаление первого вхождения элемента"""
    if element in arr:
        arr.remove(element)
    return arr

def array_search(arr, element):
    """Поиск элемента в массиве"""
    try:
        return arr.index(element)
    except ValueError:
        return -1

def array_sort(arr, reverse=False):
    """Сортировка массива"""
    return sorted(arr, reverse=reverse)

Реализация связного списка и операций

class Node:
    """Узел связного списка"""
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    """Связный список"""
    def __init__(self):
        self.head = None
    
    def add(self, data):
        """Добавление в конец"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
    
    def remove(self, data):
        """Удаление первого вхождения"""
        current = self.head
        prev = None
        while current:
            if current.data == data:
                if prev:
                    prev.next = current.next
                else:
                    self.head = current.next
                return True
            prev = current
            current = current.next
        return False
    
    def search(self, data):
        """Поиск элемента"""
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1
    
    def sort(self):
        """Сортировка пузырьком"""
        if not self.head:
            return
        swapped = True
        while swapped:
            swapped = False
            current = self.head
            while current.next:
                if current.data > current.next.data:
                    current.data, current.next.data = current.next.data, current.data
                    swapped = True
                current = current.next
    
    def to_list(self):
        """Конвертация в обычный список"""
        result = []
        current = self.head
        while current:
            result.append(current.data)
            current = current.next
        return result

Тесты (используем unittest)

import unittest

class TestDataStructures(unittest.TestCase):
    def test_array_operations(self):
        # Тестирование массива
        arr = [3, 1, 4]
        
        # Добавление
        arr = array_add(arr, 2)
        self.assertEqual(arr, [3, 1, 4, 2])
        
        # Удаление
        arr = array_remove(arr, 1)
        self.assertEqual(arr, [3, 4, 2])
        
        # Поиск
        self.assertEqual(array_search(arr, 4), 1)
        self.assertEqual(array_search(arr, 5), -1)
        
        # Сортировка
        self.assertEqual(array_sort(arr), [2, 3, 4])
        self.assertEqual(array_sort(arr, reverse=True), [4, 3, 2])

    def test_linked_list_operations(self):
        # Тестирование связного списка
        ll = LinkedList()
        
        # Добавление
        ll.add(3)
        ll.add(1)
        ll.add(4)
        self.assertEqual(ll.to_list(), [3, 1, 4])
        
        # Поиск
        self.assertEqual(ll.search(1), 1)
        self.assertEqual(ll.search(5), -1)
        
        # Удаление
        self.assertTrue(ll.remove(1))
        self.assertEqual(ll.to_list(), [3, 4])
        self.assertFalse(ll.remove(5))
        
        # Сортировка
        ll.add(2)
        ll.sort()
        self.assertEqual(ll.to_list(), [2, 3, 4])

if __name__ == '__main__':
    unittest.main()

Как запустить:

Сохраните код в файл data_structures.py
Запустите тесты:

python -m unittest data_structures.py
python -m unittest data_structures.py