Свързани списъци втора част

Малко за представянията

Миналия семинар работихме с един класически начин за представяне на свързан списък, а именно просто чрез указател към първия му елемент. Днес ще разгледаме представянето на свързания списък като клас. Разбира се, какво може да е толкова трудното на това да представим свързания списък като клас? Правим подходящи конструктори, вместо функция freeLinkedList ще имаме деструктор, всички нужни функции ще ги направим като член-функции на новосъздадения ни клас и готово.

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

void map(LinkedListNode<int>* ll, void (*func)(int&)) {
    while(ll) {
        func(ll->data);
        ll = ll->next;
    }
}

Можем да направим нещо подобно:

LinkedListNode* getHead();

Да вземем началото и да обхождаме отново с while цикъл. Когато представяме свързания списък като клас е желателно да държим логиката по представянето на елемента private. Потребителя работи с интерфейса на свързания списък. Това, че елементът на свързания списък е структура LinkedListNode която има указател към следващ елемент и тн остава скрито.

Итератори

Тук на помощ идват итераторите. Итераторите са обекти, които са отговорни за обхождане на контейнери (динамичен масив, свързан списък и тн). В C++ голяма част от STL използва итератори за постигане на целите си. Примерната реализация, с която ще работим, се намира във файла LinkedList.hpp. Представяме свързания списък с два указателя, където * head сочи към първия (най-левия) елемент

• tail сочи към последния (най-десния) елемент

• Също така пазим още една допълнителна променлива от тип size_t за дължината на списъка.

Разгледайте реализацията, особено алгоритмите за добавяне и премахване в началото и в края. Забележете, че всеки път разглеждаме три случая: * Дали листа е празен * Дали листа има един елемент * Дали листа има повече от един елемент

Вече имаме някаква примерна реализация на свързан списък. Хайде да си направим итератор и да видим колко точно сложно ще е. Ще направим итератора вътрешен и публичен клас за класа LinkedList.

// ...
public:
class Iterator {
    private:

    public:

};
// ...

Сега, какво трябва да имаме в този клас? Той е отговорен за предвижване по възлите на свързания списък. Когато се придвижваме във всеки момент имаме някой текущ елемент. Следователно ще ни трябва текущ елемент. Също така, ще ни трябва начин да създадем итератор към някой елемент. След курса по ООП това е лесна задача:

class Iterator {
    private:
        // Текущия възел в обхождането
        LinkedListNode* currentNode;

        Iterator(LinkedListNode* arg) : currentNode { arg } {} 
    public:
};

Искаме да обхождаме, значи ни трябва някакъв начин да се придвижим напред. Конвенцията е тази задача да се изпълнява от operator++. Това става по следния начин:

// Забележете, че връщаме итератор!
Iterator& operator++() {
    // Ако сме стигнали края не правим нищо
    if(currentNode == nullptr)
        return *this;

    // Преместваме се една позиция надясно
    currentNode = currentNode->next;

    return *this;
}

Супер, вече имаме ++it. Но ще е добре и да си направим it++, не знаем за какво ще ни потрябва.

// Защо този път връщаме Iterator а не Iterator&?
// Защото този път връщаме temporary object наречен temp. Той е заделен статично и ще се унищожи когато стигнем края на скоупа

Iterator operator++(int) {
    Iterator temp = *this;
    ++(*this);
    return temp;
}

Напомняме, че разликата между префиксния и постфиксния operator++ е просто един "служебен" int като аргумент на постфиксния.

Супер, вече можем да се движим, но това движение става безполезно ако нямаме начин да видим каква информация имаме в currentNode. Тази задача по конвенция се изпълнява от operator*. Супер, нека го предефинираме:

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

Също ни трябва начин да разберем дали два итератора са равни или не. Тази задача се изпълнява от operator== и operator!=

bool operator==(const Iterator& other) const {
    // Сравняваме ги по адреси!
    return other.currentNode == currentNode;
}

bool operator!=(const Iterator& other) const {
    return !(*this == other);
}

Повечето контейнери в STL имате методи begin() и end(), които връщат итератори към началото и края. Нека последваме примера им:

Iterator begin() {
    return Iterator(head);
}

Iterator end() {
    return Iterator(nullptr);
}

Ние направихме конструктора на итератора private. За да извикаме Iterator(head) обаче трябва някак да имаме достъп до private конструктора на Iterator. Това ще направим като декларираме класа LinkedList като приятелски за Iterator!

/// ...
bool operator!=(const Iterator& other) const {
    return !(*this == other);
}
    friend class LinkedList;
/// ...

Вече сме готови. Нека да проверим дали нашия метод работи:

int main() {
    LinkedList<int> ll;

    for (size_t i = 0; i < 10; i++)
        ll.pushBack(i);
    // Тук има значение дали викаме ++it или it++!
    for(LinkedList<int>::Iterator it = ll.begin(); it != ll.end(); ++it)
        std::cout << *it << " ";
}

Const и итераторите

Нека разгледаме следния код:

int main() {
    const LinkedList<int> ll;
    LinkedList<int>::Iterator beg = ll.begin();
}

В случая имаме грешка, понеже нямаме декларирана константна функция begin(). Нека си напишем константни begin() и end():

const Iterator begin() const {
    return Iterator(head);
}
const Iterator end() const {
    return Iterator(nullptr);
}

Горния фрагмент код се компилира, но вече имаме друг проблем:

void hack(const LinkedList<int>& ll) {
    LinkedList<int>::Iterator beg = ll.begin();
    *beg = 10;
}

int main() {
    LinkedList<int> ll;
    ll.pushBack(1);
    hack(ll);
    std::cout << ll.back();
}

В случая, въпреки че ll е const, отново променяме стойността му. Но защо?

В случая beg е константен. Той е съставен от един пойнтър, който обаче не е константен. В някакъв смисъл това, че стойността на паметта към която сочи пойнтъра се променя не чупи константността на итератора. За това ще се наложи да дефинираме още един клас, ConstIterator!

class ConstIterator {
    private:
        // Тук вече е указател към константна памет
        const LinkedListNode* currentNode;

        ConstIterator(LinkedListNode* arg) : currentNode { arg } {}  
    public:

    ConstIterator& operator++() {
        if(currentNode == nullptr)
            return *this;
        currentNode = currentNode->next;
        return *this;
    }

    ConstIterator operator++(int) {
        Iterator temp = *this;
        ++(*this);
        return temp;
    }

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

    bool operator==(const ConstIterator& other) const {
        return other.currentNode == currentNode;
    }

    bool operator!=(const ConstIterator& other) const {
        return !(*this == other);
    }

    friend class LinkedList;
};

Нещата са доста подобни, единствената разлика тук е, че имаме константен указател като тип на текущия елемент.

Реализираме следните:

// Връща константен итератор към началото
ConstIterator cbegin() const {
    return ConstIterator(head);
}

// Връща константен итератор към края
ConstIterator cend() const {
    return ConstIterator(nullptr);
}

Сега, ако искам да имам итератор за константен списък, просто ще създавам ConstIterator. Примерно, искаме да итерираме константен свързан списък:

void iterate(const LinkedList<int>& ll){
    for(LinkedList<int>::ConstIterator it = ll.cbegin(); it != ll.cend(); ++it) {
        std::cout << *it << " ";
    }
}

auto

Най - вероятно вече сте чували за ключовата дума auto. Чрез нея карате компилатора сам да прецени какъв тип да използва за променливата. Тя е удобна когато имате дълги типове. Прави кодът по-четим и разбираем. Като всяко хубаво нещо обаче с auto не е добре да се прекалява.

// Автоматично разбирам типа на it
for(auto it = ll.begin(); it != ll.end(); ++it) {
    //...
}

auto x = 5;         // х е променлива от тип int
const auto y = 10u; // y e променлива от тип const unsigned
auto f = 10.0f;     // f е променлива от тип float
const auto& r = f;  // r е променлива от тип const float&

std::list<int> ll;

auto it = ll.begin(); // it e променлива от тип std::list<int>::iterator
const auto its = ll.end(); // it е променлива от тип ?
auto itss = ll.cend(); // it е променлива от тип ?

range based for loops

От c++11 езикът ни предлага начин, чрез който да пишем подобни for цикли още по - бързо.

int main() {
    LinkedList<int> ll;

    for(const int& elem : ll) {
        std::cout << elem << " ";
    }
}

Този цикъл е еквивалентен на горния, просто е синтактична захар.

За по - любопитните компилатора развива този приятен for цикъл до следното:

{
    LinkedList<int> & __range1 = ll;

    LinkedList<int>::Iterator __begin1 = __range1.begin();

    LinkedList<int>::Iterator __end1 = __range1.end();

    for(; __begin1.operator!=(__end1); __begin1.operator++()) {
      const int & elem = __begin1.operator*();
      std::operator<<(std::cout.operator<<(elem), " ");
    }
}

Задача първа:

Даден е списък l с n елемента.

Да се дефинира функция shuffle(), която получава адреса на първия елемент на списъка.

Функцията да пренарежда възлите на списъка така, че елементите от втората половина на списъка да се преместят в началото на списъка, но в обратен ред (при списъци с нечетен брой елементи считаме средния елемент за принадлежащ към първата половина на списъка). Пример:

Вход: L1 → L2 → L3 → L4 → L5

Изход: L5 → L4 → L1 → L2 → L3

Задача втора:

Даден е списък l с елементи стекове.

Да се дефинира функция equalize(l), която размества елементите на стековете така, че да няма два стека в l с разлика в броя на елементите, по-голяма от 1.

Вход                          Изход

5 -> 4 -> 3 -> 2 -> 1         5 -> 4 -> 3
|                             |
v                             v
7 -> 6                        7 -> 6 -> 1
|                             |
v                             v
11 -> 10 -> 9 -> 8            11 -> 10 -> 9
|                             |
v                             v
12                            12 -> 2 -> 8

Задача трета - Linked List Partition

Да се създаде функция

LinkedListNode<int>* partition(LinkedListNode<int>* head, int x);

която пренарежда списъка така, че всички възли със стойност по-малка от х са преди всички възли със стойност по-голяма или равна от х.

Пример:

Вход: head -> 1 -> 4 -> 3 -> 2 -> 5 -> 2, x = 3

Изход: 1 -> 2 -> 2 -> 4 -> 3 -> 5

Вход: head -> 2 -> 1, x = 2

Изход: 1 -> 2

HINT:

Можете да си направите два указателя, чрез които да строите някакви полезни помощни списъци. После, след като построите тези полезни помощни списъци, можете да пренасочите правилните указатели и да получите коректен отговор.