冒泡排序双向链表

Question

我浏览了一堆线程，试图了解链表和冒泡排序到底发生了什么，我想我了解了其中的大部分内容。

现在，当我进入排序功能时，我的程序只是崩溃了，我不确定为什么。希望另一双眼睛能看到我看不到的东西。

非常感谢任何帮助。

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

首先，您需要在排序函数中初始化 current，

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;
}

}

Answer 2

到目前为止我能找到的错误是：

您的默认 ListNode() 构造函数不会使 next 和 prev 指针为空。
在 void DoublyList<T>::sortList() 中你没有初始化 dummy，所以它只是指向任何地方。其实根本没有必要使用节点列表，直接使用T.
您没有在同一个函数中初始化 current，您实际上应该将 current 重置为例如front 在每个外循环的开头。
您根本不使用 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 的观点，交换指针是您实际应该使用的方法。

冒泡排序双向链表

Bubble sort a doubly linked list

c++

linked-list

bubble-sort