Bubble сортировать двойной список

Question

Я прошел через кучу нитей, пытаясь понять, что происходит именно со связанными списками и bubblesort, и я думаю, что получаю основную часть.

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

Любая помощь очень ценится.

DoublyList.h:

#include "listNode.h" 

#ifndef DOUBLYLIST_H 
#define DOUBLYLIST_H 

template <typename T> 
class DoublyList 
{ 
    public: 
     DoublyList(); 
     ~DoublyList(); 
     void addFront(T d); 
     void addBack(T d); 
     T removeFront(); 
     T removeBack(); 
     T peak(); 
     bool isEmpty(); 
     int getSize(); 
     void printList(); 
     void sortList(); 

    private: 
     ListNode<T> *front; 
     ListNode<T> *back; 
     int numOfElements; 
}; 

template <typename T> 
DoublyList<T>::DoublyList(){ 
    front = NULL; 
    back = NULL; 
    numOfElements = 0; 
} 
template <typename T> 
DoublyList<T>::~DoublyList(){ 
    if(numOfElements!=0){ 

     ListNode<T> *current; 
     current = front; 
     while (current != back) 
     { 
      ListNode<T> *temp = current; 
      current = current->next; 
      temp->next = NULL; 
      temp->prev = NULL; 
      delete temp; 
      numOfElements--; 
     } 
     //at this point current = back, now delete it 
     current->next = NULL; 
     current->prev = NULL; 
     delete current; 
     numOfElements--; 
    } 
    //this is a safeguard if you create a LL and then delete it without doing anything to it 
    else{ 
     cout<<"deleted empty LL"<<endl; 
     delete front; 
     delete back; 
    } 
} 
template <typename T> 
void DoublyList<T>::addFront(T d) 
{ 
    ListNode<T> *node = new ListNode<T>(); 
    node->data = d; 
    if (isEmpty()){ 
     back = node; 
    } 
    else{ 
     front->prev = node; 
    } 
    node->next = front; 
    front = node; 
    ++numOfElements; 
} 
template <typename T> 
T DoublyList<T>::removeFront() 
{ 
    if (isEmpty()){ 
     return T(); 
    } 
    else 
    { 
     ListNode<T>* temp = front; 
     if (front->next == 0){ 
      back = 0; 
     } 
     else 
     { 
      front->next->prev = 0; 
     } 
     front = front->next; 
     temp->next = 0; 
     T theData = temp->data; 
     delete temp; 
     --numOfElements; 
     return theData; 
    } 
} 
template <typename T> 
void DoublyList<T>::addBack(T d) 
{ 
    ListNode<T> *node = new ListNode<T>(); 
    node->data = d; 
    if (isEmpty()){ 
     front = node; 
    } 
    else{ 
     back->next = node; 
    } 
    node->prev = back; 
    back = node; 
    ++numOfElements; 
} 
template <typename T> 
T DoublyList<T>::removeBack() 
{ 
    if (isEmpty()) { 
     return T(); 
    } 
    else 
    { 
     ListNode<T>* temp; 
     temp = back; 
     if (back->prev == 0){ 
      front = 0; 
     } 
     else{ 
      back->prev->next = 0; 
     } 
     back = back->prev; 
     temp->prev = 0;  
     T theData = temp->data; 
     delete temp; 
     --numOfElements; 
     return theData; 
    } 
} 
template <typename T> 
T DoublyList<T>::peak() 
{ 
    if (isEmpty()) { 
     return T(); 
    } 
    return front->data; 
} 
template <typename T> 
int DoublyList<T>::getSize(){ 
    return numOfElements; 
} 
template <typename T> 
bool DoublyList<T>::isEmpty(){ 
    if(numOfElements == 0){ 
     return true; 
    } 
    else{ 
     return false; 
    } 
} 
template <typename T> 
void DoublyList<T>::printList(){ 
    if(numOfElements!=0){ 
     ListNode<T> *current = front; 
     while(current!=back) 
     { 
      cout<<current->data<<endl; 
      current = current->next; 
     } 
     cout<<back->data<<endl; 
    } 
    else{ 
     cout<<"list is empty"<<endl; 
    } 
} 


template <typename T> 
void DoublyList<T>::sortList(){ 
    int size = getSize(); 
    ListNode<T> *current; 
    ListNode<T> *dummy; 
    ListNode<T> *next; 

    if(current == NULL) return; 
    if(current -> next == NULL) return; 

    int swapped = 1; 
    while(swapped){ 
     swapped = 0; //last pass unless there is a swap 
     while(current -> next != NULL){ 
      if(current-> data < current -> next -> data){ 
       swapped = 1; //swap, will need to re-enter while loop 
       //actual number swap 
       dummy -> data = current -> data; 
       current -> data = current -> next -> data; 
       current -> next -> data = dummy -> data; 
      } 
      current = current -> next; 
     } 
    } 

} 

#endif 

listNode.h:

#include <iostream> 
#ifndef LISTNODE_H 
#define LISTNODE_H 

using namespace std; 
template <typename T> 
class ListNode 
{ 
    public: 
     T data;//the data that we will store 
     ListNode(); 
     ListNode(int d); 
     ~ListNode(); 
     ListNode *next;//int and ptr and the member variables 
     ListNode *prev; 
}; 
template <typename T> 
ListNode<T>::ListNode(int d){ 
    data = d; 
    next = NULL; 
    prev = NULL; 
} 
template <typename T> 
ListNode<T>::ListNode(){} 
template <typename T> 
ListNode<T>::~ListNode(){ 
    delete next; 
    delete prev; 
    cout<<"deleted Node"<<endl; 
} 
#endif 

testList.cpp

#include <iostream> 
#include "doublyList.h" 
#include "genericQueue.h" 




int main(){ 
    DoublyList<int> testQueue; 
    testQueue.addBack(3); 
    testQueue.addBack(5); 
    testQueue.addBack(2); 
    testQueue.addBack(10); 
    testQueue.addBack(1); 

    cout << "Before Sort: " << endl; 
    testQueue.printList(); 

    cout << "After Sort: " << endl; 
    testQueue.sortList(); 
    testQueue.printList(); 

} 

Answer 1

В erors я мог найти до сих пор является:

1. Вашего ListNode() по умолчанию конструктор не обнулить next и prev указателей.
2. В void DoublyList<T>::sortList() вы не инициализируете dummy, поэтому он просто указывает в никуда. На самом деле нет оснований использовать список узлов вообще, вы можете просто использовать переменную типа T.
3. Вы не инициализируете current в той же функции, и вы действительно должны сбросить current, например. front в начале каждого внешнего контура.
4. Вы вообще не используете next (и не нужно), поэтому просто удалите его.

Подводя итог, это то, что void DoublyList<T>::sortList() может выглядеть следующим образом:

template <typename T> 
void DoublyList<T>::sortList(){ 
    int size = getSize(); 
    ListNode<T> *current=front; 
    T dummy; 

    if (current == NULL) return; 
    if (current->next == NULL) return; 

    int swapped = 1; 
    while (swapped){ 
     current = front; 
     swapped = 0; //last pass unless there is a swap 
     while (current->next != NULL){ 
      if (current->data < current->next->data){ 
       swapped = 1; //swap, will need to re-enter while loop 
       //actual number swap 
       dummy = current->data; 
       current->data = current->next->data; 
       current->next->data = dummy; 
      } 
      current = current->next; 
     } 
    } 
} 

и это мое предложение для конструктора ListNode.

template <typename T> 
ListNode<T>::ListNode() : 
    next(nullptr), 
    prev(nullptr), 
    data{} 
{} 

Кроме того, я также согласен с DaveB в том, что подмены указателей - это подход, который вы должны использовать.

Answer 2

Для начала вам необходимо инициализировать тока в функции сортировки,

current = first; 


template <typename T> 
void DoublyList<T>::sortList(){ 

ListNode<T> *current; 
ListNode<T> *next; 

T tmp; 
current = front; 
if(current == NULL) return; 
if(current -> next == NULL) return; 

int swapped = 1; 
while(swapped){ 
    swapped = 0; //last pass unless there is a swap 
    while(current->next != nullptr){ 
     if(current->data < current->next->data){ 
      swapped = 1; //swap, will need to re-enter while loop 
      //actual number swap 
      tmp = current->data; 
      current->data = current->next->data; 
      current->next->data = tmp; 
     } 
     current = current -> next; 
    } 
    if (swapped)   // go back to start of list for next pass 
     current = front; 
} 

}