Skip to main content

Упражнения: C++ Списъци, Итератори и Управление на Паметта

Напредък

0%
✅ Завършени: 0 / 0📊 Напредък: 0%

💡 Напредъкът се записва локално в браузъра

Лесни Упражнения (Основни Концепции)​

10 minЛЕСНО

Задача 1: Разлики между еднопосочен и двусвързан списък​

Какви са основните разлики между еднопосочен списък (singly linked list) и двусвързан списък (doubly linked list)?

Отговор:

  • Еднопосочен списък: Всеки възел има само един указател next към следващия елемент. Може да се обхожда само в една посока (напред).
  • Двусвързан списък: Всеки възел има два указателя - prev към предишния и next към следващия елемент. Може да се обхожда в двете посоки.
  • Памет: Двусвързаният списък заема повече памет заради допълнителния указател.
  • Операции: Двусвързаният списък позволява по-ефективно изтриване на елемент при известен указател.
10 minЛЕСНО

Задача 2: Оператори за динамична памет в C++​

В C++, кои оператори се използват за заделяне и освобождаване на динамична памет?

a) malloc и free b) new и delete c) alloc и dealloc d) create и destroy

Отговор: b) new и delete

В C++ използваме new за заделяне на динамична памет и delete за освобождаването ѝ. За масиви използваме new[] и delete[].

10 minЛЕСНО

Задача 3: Изтичане на памет (Memory Leak)​

Какво е изтичане на памет (memory leak)? Опишете с едно изречение.

Отговор: Изтичане на памет е ситуация, при която програмата заделя динамична памет, но не я освобождава след използването ѝ, което води до натрупване на неизползвана памет.

10 minЛЕСНО

Задача 4: Съдържание на възел в двусвързан списък​

Какво съдържа всеки възел в двусвързан списък?

Отговор: Всеки възел съдържа:

  • Данни (стойността, която се съхранява)
  • Указател prev към предишния възел
  • Указател next към следващия възел
10 minЛЕСНО

Задача 5: Добра практика след delete​

Какво винаги трябва да правите след извикване на delete на указател като добра практика?

int* ptr = new int(10);
delete ptr;
// Какво трябва да следва?

Отговор:

ptr = nullptr;

След delete винаги задавайте указателя на nullptr. Това предотвратява използването на "висящ" указател (dangling pointer) и прави грешките по-лесни за откриване.

10 minЛЕСНО

Задача 6: Каква е времевата сложност O() за добавяне на елемент в края...​

Каква е времевата сложност O() за добавяне на елемент в края на двусвързан списък, когато имате указател към tail?

Отговор: O(1) - константно време.

Когато имаме указател към tail, можем директно да добавим новия елемент и да актуализираме само няколко указателя, независимо от размера на списъка.

10 minЛЕСНО

Задача 7: Кое от следните ще причини изтичане на памет?​

Кое от следните ще причини изтичане на памет?

// Опция A:
int* ptr = new int(5);
delete ptr;

// Опция B:
int* ptr = new int(5);
ptr = new int(10);
delete ptr;

// Опция C:
int* ptr = new int(5);
ptr = nullptr;

Отговор: Опция B и Опция C причиняват изтичане на памет.

  • Опция A: Правилна - паметта се освобождава.
  • Опция B: Грешна - първата заделена памет (5) изтича, защото указателят се презаписва преди да бъде освободена.
  • Опция C: Грешна - заделената памет изтича, защото губим указателя без да освободим паметта.
10 minЛЕСНО

Задача 8: Каква е основната роля на итератор в C++?​

Каква е основната роля на итератор в C++?

Отговор: Итераторът предоставя унифициран начин за обхождане на елементите на различни контейнери, скривайки детайлите на вътрешната им структура. Това позволява писането на общ код, който работи с масиви, списъци, вектори и др., без да се налага промяна при смяна на типа контейнер.

Средни Упражнения​

10 minЛЕСНО

Задача 9: Допълнете следния код за правилно освобождаване на масив:​

Допълнете следния код за правилно освобождаване на масив:

int* arr = new int[10];
// Използвайте масива...
// Напишете правилния код за освобождаване тук:

Отговор:

delete[] arr;
arr = nullptr;

Важно е да използвате delete[] (не просто delete) за масиви, защото той освобождава цялата заделена памет за всички елементи.

15 minСРЕДНО

Задача 10: Какво ще се случи в следния код?​

Какво ще се случи в следния код?

struct Node {
    int data;
    Node* next;
    Node* prev;
};

Node* n = new Node();
n->data = 42;
// Програмата приключва без delete

Отговор: Ще има изтичане на памет. Заделената памет за възела не се освобождава преди приключване на програмата. Правилният код трябва да включва:

delete n;
n = nullptr;
15 minСРЕДНО

Задача 11: Намерете грешката в тази функция за премахване на възел от д...​

Намерете грешката в тази функция за премахване на възел от двусвързан списък:

void removeNode(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    // Какво липсва?
}

Отговор: Липсва delete node;

След актуализиране на указателите, трябва да освободим паметта за премахнатия възел:

void removeNode(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete node; // Освобождаване на паметта
}

Допълнително: Функцията не проверява дали prev или next са nullptr, което може да доведе до грешка при премахване на първия или последния елемент.

15 minСРЕДНО

Задача 12: Имплементирайте метод за добавяне на елемент в началото на д...​

Имплементирайте метод за добавяне на елемент в началото на двусвързан списък:

class DoublyLinkedList {
private:
    Node* head;
    Node* tail;
public:
    void addFront(int value) {
        // Вашата имплементация тук
    }
};

Отговор:

void addFront(int value) {
    Node* newNode = new Node(value);

    if (head) { // Ако списъкът не е празен
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    } else { // Ако списъкът е празен
        head = newNode;
        tail = newNode;
    }
}
15 minСРЕДНО

Задача 13: Какво е RAII и как помага за предотвратяване на изтичане на ...​

Какво е RAII и как помага за предотвратяване на изтичане на памет? Дайте пример.

Отговор: RAII (Resource Acquisition Is Initialization) е идиом в C++, при който ресурсите (като памет) се придобиват в конструктора на обекта и автоматично се освобождават в деструктора му.

Пример:

class SafeArray {
private:
    int* data;
    size_t size;
public:
    SafeArray(size_t n) : size(n) {
        data = new int[n]; // Заделяне в конструктора
    }

    ~SafeArray() {
        delete[] data; // Автоматично освобождаване в деструктора
    }
    // ... други методи ...
};

Когато SafeArray излезе от обхват, деструкторът автоматично освобождава паметта.

15 minСРЕДНО

Задача 14: Допълнете класа итератор за прост масив:​

Допълнете класа итератор за прост масив:

template<typename T>
class ArrayIterator {
private:
    T* current;
public:
    ArrayIterator(T* ptr) : current(ptr) {}

    T& operator*() const {
        // Вашият код тук
    }

    ArrayIterator& operator++() {
        // Вашият код тук
    }

    bool operator!=(const ArrayIterator& other) const {
        // Вашият код тук
    }
};

Отговор:

T& operator*() const {
    return *current; // Връща референция към текущия елемент
}

ArrayIterator& operator++() {
    ++current; // Премества указателя напред
    return *this;
}

bool operator!=(const ArrayIterator& other) const {
    return current != other.current; // Сравнява указателите
}
15 minСРЕДНО

Задача 15: Обяснете защо този код има изтичане на памет и го поправете:​

Обяснете защо този код има изтичане на памет и го поправете:

void processData() {
    int* data = new int[100];
    for (int i = 0; i < 100; i++) {
        data[i] = i * 2;
    }
    if (data[50] > 100) {
        return; // Ранно връщане
    }
    delete[] data;
}

Проблем: При ранно връщане (return), delete[] data никога не се изпълнява, което води до изтичане на памет.

Решение 1 - добавяне на delete преди return:

void processData() {
    int* data = new int[100];
    for (int i = 0; i < 100; i++) {
        data[i] = i * 2;
    }
    if (data[50] > 100) {
        delete[] data; // Освобождаване преди връщане
        return;
    }
    delete[] data;
}

Решение 2 - използване на RAII (по-добро):

void processData() {
    std::unique_ptr<int[]> data = std::make_unique<int[]>(100);
    for (int i = 0; i < 100; i++) {
        data[i] = i * 2;
    }
    if (data[50] > 100) {
        return; // Паметта се освобождава автоматично
    }
    // Паметта се освобождава автоматично и тук
}
15 minСРЕДНО

Задача 16: Какви са трите основни типа smart pointers в C++ и кога бихт...​

Какви са трите основни типа smart pointers в C++ и кога бихте използвали всеки?

Отговор:

  • std::unique_ptr: Ексклузивна собственост. Използвайте когато само един обект трябва да притежава ресурса. Не може да се копира, само да се премести с std::move.
  • std::shared_ptr: Споделена собственост чрез reference counting. Използвайте когато множество обекти трябва да споделят ресурса. Паметта се освобождава, когато последният shared_ptr бъде унищожен.
  • std::weak_ptr: "Слаба" референция към shared_ptr, която не увеличава reference count. Използвайте за прекъсване на циклични зависимости между shared_ptr обекти.
15 minСРЕДНО

Задача 17: Имплементирайте функция за броене на елементите в двусвързан...​

Имплементирайте функция за броене на елементите в двусвързан списък:

int countElements(Node* head) {
    // Вашата имплементация тук
}

Отговор:

int countElements(Node* head) {
    int count = 0;
    Node* current = head;

    while (current != nullptr) {
        count++;
        current = current->next;
    }

    return count;
}

Времева сложност: O(n), където n е броят елементи в списъка.

15 minСРЕДНО

Задача 18: Напишете деструктор за двусвързан списък, който правилно осв...​

Напишете деструктор за двусвързан списък, който правилно освобождава всички възли:

class DoublyLinkedList {
private:
    Node* head;
    Node* tail;
public:
    ~DoublyLinkedList() {
        // Вашата имплементация тук
    }
};

Отговор:

~DoublyLinkedList() {
    Node* current = head;
    while (current != nullptr) {
        Node* next_node = current->next;
        delete current;
        current = next_node;
    }
    head = nullptr;
    tail = nullptr;
}

Обхождаме целия списък и изтриваме всеки възел. Важно е да запазим next указателя преди да изтрием текущия възел.

Трудни Упражнения​

20 minТРУДНО

Задача 19: Имплементирайте метод insert, който добавя нов елемент сле...​

Имплементирайте метод insert, който добавя нов елемент след дадена итераторна позиция:

template<typename T>
class DoublyLinkedList {
public:
    class Iterator {
        Node* current;
        // ... iterator methods ...
    };

    void insertAfter(Iterator position, T value) {
        // Вашата имплементация тук
    }
};

Отговор:

void insertAfter(Iterator position, T value) {
    if (!position.current) return; // Проверка за валидност

    Node* newNode = new Node(value);
    Node* next = position.current->next;

    // Свързване на новия възел
    newNode->prev = position.current;
    newNode->next = next;

    // Актуализиране на съседните възли
    position.current->next = newNode;

    if (next) {
        next->prev = newNode;
    } else {
        // Ако вмъкваме след последния елемент
        tail = newNode;
    }
}

Забележка: Необходим е достъп до current от итератора, което изисква или friend декларация, или публичен getter.

20 minТРУДНО

Задача 20: Анализирайте следния код и идентифицирайте всички проблеми, ...​

Анализирайте следния код и идентифицирайте всички проблеми, свързани с паметта:

class DataManager {
    int* buffer;
    int size;
public:
    DataManager(int n) {
        size = n;
        buffer = new int[size];
    }

    void resize(int newSize) {
        buffer = new int[newSize];
        size = newSize;
    }

    DataManager(const DataManager& other) {
        size = other.size;
        buffer = other.buffer;
    }
};

Проблеми:

  1. Липсва деструктор: Няма ~DataManager() за освобождаване на buffer.
  2. Memory leak в resize(): Старата памет не се освобождава преди заделянето на нова.
  3. Shallow copy в copy constructor: buffer = other.buffer просто копира указателя, не прави deep copy на данните.
  4. Липсва copy assignment operator: Няма operator= за правилно копиране.
  5. Липсва move constructor и move assignment: За ефективно преместване на ресурси.

Правилна имплементация:

class DataManager {
    int* buffer;
    int size;
public:
    DataManager(int n) : size(n), buffer(new int[n]) {}

    ~DataManager() { delete[] buffer; }

    void resize(int newSize) {
        int* newBuffer = new int[newSize];
        int copySize = std::min(size, newSize);
        for (int i = 0; i < copySize; i++) {
            newBuffer[i] = buffer[i];
        }
        delete[] buffer;
        buffer = newBuffer;
        size = newSize;
    }

    DataManager(const DataManager& other) : size(other.size) {
        buffer = new int[size];
        for (int i = 0; i < size; i++) {
            buffer[i] = other.buffer[i];
        }
    }

    DataManager& operator=(const DataManager& other) {
        if (this != &other) {
            delete[] buffer;
            size = other.size;
            buffer = new int[size];
            for (int i = 0; i < size; i++) {
                buffer[i] = other.buffer[i];
            }
        }
        return *this;
    }
};
20 minТРУДНО

Задача 21: Имплементирайте двупосочен итератор за двусвързан списък с `...​

Имплементирайте двупосочен итератор за двусвързан списък с operator++ и operator--:

template<typename T>
class DoublyLinkedList {
    struct Node {
        T data;
        Node* prev;
        Node* next;
    };

    class Iterator {
    private:
        Node* current;
    public:
        // Имплементирайте всички необходими оператори
    };
};

Отговор:

class Iterator {
private:
    Node* current;
public:
    Iterator(Node* node) : current(node) {}

    // Достъп до стойността
    T& operator*() const {
        return current->data;
    }

    // Преместване напред (префикс)
    Iterator& operator++() {
        if (current) current = current->next;
        return *this;
    }

    // Преместване назад (префикс)
    Iterator& operator--() {
        if (current) current = current->prev;
        return *this;
    }

    // Преместване напред (постфикс)
    Iterator operator++(int) {
        Iterator temp = *this;
        ++(*this);
        return temp;
    }

    // Преместване назад (постфикс)
    Iterator operator--(int) {
        Iterator temp = *this;
        --(*this);
        return temp;
    }

    // Сравнение
    bool operator==(const Iterator& other) const {
        return current == other.current;
    }

    bool operator!=(const Iterator& other) const {
        return current != other.current;
    }
};
20 minТРУДНО

Задача 22: Имплементирайте пълен двусвързан списък с exception-safe вмъ...​

Имплементирайте пълен двусвързан списък с exception-safe вмъкване. Гарантирайте, че няма изтичане на памет дори при хвърляне на изключения.

Отговор: Ключът е да използваме RAII и да заделим паметта така, че ако възникне изключение, всичко да се освободи автоматично:

template<typename T>
class SafeDoublyLinkedList {
private:
    struct Node {
        T data;
        std::unique_ptr<Node> next; // Автоматично управление
        Node* prev; // Raw pointer назад (не притежава)

        Node(const T& val) : data(val), next(nullptr), prev(nullptr) {}
    };

    std::unique_ptr<Node> head;
    Node* tail;

public:
    SafeDoublyLinkedList() : head(nullptr), tail(nullptr) {}

    void add(const T& value) {
        auto newNode = std::make_unique<Node>(value);

        if (tail) {
            newNode->prev = tail;
            tail->next = std::move(newNode);
            tail = tail->next.get();
        } else {
            tail = newNode.get();
            head = std::move(newNode);
        }
    }
};

Използването на unique_ptr гарантира автоматично освобождаване при изключения.

20 minТРУДНО

Задача 23: Разгледайте сценарий с циклични референции използвайки `std:...​

Разгледайте сценарий с циклични референции използвайки std::shared_ptr. Обяснете проблема и предоставете решение с std::weak_ptr:

class Node {
public:
    std::shared_ptr<Node> next;
    std::shared_ptr<Node> prev;
    int data;
};

Проблем: Ако два възела се сочат взаимно чрез shared_ptr, reference count никога не достига нула и паметта никога не се освобождава.

Решение: Използвайте weak_ptr за едната връзка:

class Node {
public:
    std::shared_ptr<Node> next;  // Силна референция напред
    std::weak_ptr<Node> prev;    // Слаба референция назад
    int data;

    Node(int val) : data(val) {}
};

Така next притежава следващия възел, но prev само наблюдава предишния, без да го притежава. Това прекъсва цикличната зависимост.

20 minТРУДНО

Задача 24: Използвайки Valgrind концептуално, анализирайте тази програм...​

Използвайки Valgrind концептуално, анализирайте тази програма:

void complexFunction() {
    int* arr1 = new int[50];
    int* arr2 = new int[100];

    for (int i = 0; i < 50; i++) {
        arr1[i] = i;
    }

    arr1 = arr2; // Презаписване
    delete[] arr2;
}

int main() {
    for (int i = 0; i < 1000; i++) {
        complexFunction();
    }
    return 0;
}

Valgrind би докладвал:

  • Memory leak: 50 * sizeof(int) * 1000 = 200,000 байта изтичат, защото arr1 се презаписва без да се освободи първата заделена памет.
  • Invalid free/delete: arr2 се освобождава два пъти - веднъж чрез delete[] arr2 и втори път когато arr1 (който вече сочи към същата памет) би трябвало да се освободи (но това не се случва в кода).

Поправка:

void fixedFunction() {
    int* arr1 = new int[50];
    int* arr2 = new int[100];

    for (int i = 0; i < 50; i++) {
        arr1[i] = i;
    }

    delete[] arr1; // Освобождаване преди презаписване
    delete[] arr2;
}
20 minТРУДНО

Задача 25: Проектирайте memory-efficient двусвързан списък, който изпол...​

Проектирайте memory-efficient двусвързан списък, който използва sentinel nodes (фиктивни head и tail) за опростяване на граничните условия.

Отговор:

template<typename T>
class SentinelDoublyLinkedList {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node() : prev(nullptr), next(nullptr) {} // Sentinel конструктор
        Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
    };

    Node* sentinel_head; // Фиктивен head (не съдържа данни)
    Node* sentinel_tail; // Фиктивен tail (не съдържа данни)

public:
    SentinelDoublyLinkedList() {
        sentinel_head = new Node();
        sentinel_tail = new Node();
        sentinel_head->next = sentinel_tail;
        sentinel_tail->prev = sentinel_head;
    }

    ~SentinelDoublyLinkedList() {
        Node* current = sentinel_head->next;
        while (current != sentinel_tail) {
            Node* next = current->next;
            delete current;
            current = next;
        }
        delete sentinel_head;
        delete sentinel_tail;
    }

    void add(const T& value) {
        Node* newNode = new Node(value);
        Node* last = sentinel_tail->prev;

        // Вмъкване преди sentinel_tail
        newNode->prev = last;
        newNode->next = sentinel_tail;
        last->next = newNode;
        sentinel_tail->prev = newNode;
    }

    // Предимство: не се налагат проверки за nullptr при add/remove
};

Sentinel nodes опростяват логиката, защото винаги има "предишен" и "следващ" елемент.

20 minТРУДНО

Задача 26: Създайте custom iterator, който автоматично прескача елемент...​

Създайте custom iterator, който автоматично прескача елементи, удовлетворяващи даден предикат.

Отговор:

template<typename T, typename Predicate>
class FilteringIterator {
private:
    Node* current;
    Node* end;
    Predicate pred;

    void advance() {
        while (current != end && pred(current->data)) {
            current = current->next;
        }
    }

public:
    FilteringIterator(Node* start, Node* end_node, Predicate p)
        : current(start), end(end_node), pred(p) {
        advance(); // Прескачаме нежеланите елементи в началото
    }

    T& operator*() const {
        return current->data;
    }

    FilteringIterator& operator++() {
        if (current != end) {
            current = current->next;
            advance(); // Прескачаме нежелани елементи
        }
        return *this;
    }

    bool operator!=(const FilteringIterator& other) const {
        return current != other.current;
    }
};

// Пример: прескачане на отрицателни числа
auto it = FilteringIterator<int, auto>(
    list.begin(), list.end(),
    [](int x) { return x < 0; }
);
20 minТРУДНО

Задача 27: Имплементирайте move constructor и move assignment operator ...​

Имплементирайте move constructor и move assignment operator за двусвързан списък:

template<typename T>
class DoublyLinkedList {
public:
    DoublyLinkedList(DoublyLinkedList&& other) noexcept {
        // Имплементирайте move constructor
    }

    DoublyLinkedList& operator=(DoublyLinkedList&& other) noexcept {
        // Имплементирайте move assignment
    }
};

Отговор:

// Move constructor
DoublyLinkedList(DoublyLinkedList&& other) noexcept
    : head(other.head), tail(other.tail) {
    // "Крадем" ресурсите от other
    other.head = nullptr;
    other.tail = nullptr;
}

// Move assignment
DoublyLinkedList& operator=(DoublyLinkedList&& other) noexcept {
    if (this != &other) {
        // Освобождаваме собствените ресурси
        Node* current = head;
        while (current) {
            Node* next = current->next;
            delete current;
            current = next;
        }

        // "Крадем" ресурсите от other
        head = other.head;
        tail = other.tail;
        other.head = nullptr;
        other.tail = nullptr;
    }
    return *this;
}

Move семантиката позволява ефективно трансфериране на ресурси без копиране.

20 minТРУДНО

Задача 28: Проектирайте memory pool allocator за възли на двусвързан сп...​

Проектирайте memory pool allocator за възли на двусвързан списък за намаляване на overhead и фрагментация.

Отговор:

template<typename T>
class NodePool {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
    };

    struct Chunk {
        Node nodes[64]; // Блок от 64 възела
        bool used[64];
        Chunk* next;

        Chunk() : next(nullptr) {
            for (int i = 0; i < 64; i++) used[i] = false;
        }
    };

    Chunk* chunks;

public:
    NodePool() : chunks(new Chunk()) {}

    ~NodePool() {
        while (chunks) {
            Chunk* next = chunks->next;
            delete chunks;
            chunks = next;
        }
    }

    Node* allocate() {
        Chunk* current = chunks;
        while (current) {
            for (int i = 0; i < 64; i++) {
                if (!current->used[i]) {
                    current->used[i] = true;
                    return &current->nodes[i];
                }
            }
            if (!current->next) {
                current->next = new Chunk();
            }
            current = current->next;
        }
        return nullptr;
    }

    void deallocate(Node* node) {
        Chunk* current = chunks;
        while (current) {
            if (node >= current->nodes &&
                node < current->nodes + 64) {
                int index = node - current->nodes;
                current->used[index] = false;
                return;
            }
            current = current->next;
        }
    }
};

Memory pool намалява броя системни алокации и подобрява cache locality.

Забележка: Тези упражнения преминават от основно разбиране на концепциите до напреднали имплементации, покривайки всички ключови теми от лекцията: двусвързани списъци, итератори, управление на паметта, smart pointers и RAII принципи.