Реверсирование родового двусвязного списка в C++

Question

Я пытаюсь дать свой общий класс списка обратную функцию. По какой-то причине мой алгоритм не работает, когда я его тестирую. Я подумал, что это имеет смысл: поменяйте указатели на первый и последний узлы списка, затем перейдите в список и для каждого узла поменяйте указатели на предыдущий и следующий узлы.

Прогуляйтесь со мной, ребята. Я пытаюсь получить некоторую практику с общим программированием. Научите меня пуристам пустого С ++.

Вот функция подкачки:

template <class T> void swap(T* a, T* b) { 
T* tempPtr = a; 
a = b; 
b = tempPtr; 
} 

Вот обратная функция:

template <class T> void List<T>::reverse() { 
    if (size > 1) { 
     swap(firstNodePtr, lastNodePtr); 
     node* curNodePtr = firstNodePtr; 
     while (curNodePtr != NULL) { 
      swap(curNodePtr->prevNodePtr, curNodePtr->nextNodePtr); 
      curNodePtr = curNodePtr->nextNodePtr; 
     } 
    } 
} 

Вот класс, его членов и прототипов функций:

template <class T> class List { 

public: 
    List(); 
    ~List(); 
    void push_back(T); 
    void push_front(T); 
    T get_at(unsigned); 
    unsigned get_size(); 
    void reverse(); 

private: 
    struct node { 
     T val; 
     node* prevNodePtr; 
     node* nextNodePtr; 
    }; 
    node* firstNodePtr; 
    node* lastNodePtr; 
    unsigned size; 

}; 

Answer 1

Поскольку вы передаете два указателя по значению, изменения на a и b не p ropagate из функции swap(), делая его не-op.

Один из способов исправить это является передача указателей по ссылке:

template <class T> void swap(T*& a, T*& b) { 

Альтернативно (и предпочтительно) просто использовать std::swap() вместо вашей собственной функции.

Answer 2

Функция swap<T> не работает: она обменивает указатели, которые копируются по значению в локальные переменные вашей функции, что не влияет на вызывающего.

Оставьте свой собственный swap и замените его на std::swap, исправив эту проблему.

Answer 3

Если вы выставили свою структуру node (или, по крайней мере, тип двунаправленного итератора для своего списка), вы можете избежать всей проблемы и просто использовать std::reverse.

List<int> someList; 
// fill with data 
std::reverse(someList.begin(), someList.end()); // where begin returns a bidirectional iterator for the head, and end returns a bidirectional iterator for 1 element beyond the tail