c++ - 双向链表上的快速排序

Question

大家好，我正在尝试使用在互联网上找到的算法将快速排序构建到我的调度程序代码中。我的问题是，在代码的某些点上，我得到了关于 getPrev 的访问冲突，它可能指向 null，但我被卡住了，不知道如何让它工作。如果能提供一点帮助或至少建议我应该朝哪个方向前进，我将不胜感激。我已经花了几个小时在上面，但没有任何效果。

#include <iostream>
using namespace std;
class Node
{
public:

Node(int value, Node* nextptr = nullptr, Node* prevptr = nullptr, int     currentpriority = 0)
{
    this->value = value;
    next = nextptr;
    prev = prevptr;
    priority = currentpriority;

}

int getVal(void)
{
    return value;
}

Node* getNext(void)
{
    return next;
}

Node* getPrev(void)
{
    return prev;
}

void setVal(int value)
{
    this->value = value;
}

void setPrev(Node* prevptr)
{
    prev = prevptr;
};

void setNext(Node* nextptr)
{
    next = nextptr;
}

int getPriority(void)
{
    return priority;
}

void setPriority(int priority)
{
    this->priority = priority;
}

private:
Node* next;
Node* prev;
int priority;
int value;
};

class Stack
{
public:
Stack(void)
{
    top = nullptr;
}


~Stack(void)
{
    while (NodePop() != nullptr);
}

void Push(int value)
{
    Node* tmp = new Node(value, top);
    top = tmp;
}

Node* NodePop(void)
{
    Node* tmp = top;
    if (top != nullptr) top = top->getNext();
    return tmp;
}

int Pop(void)
{
    Node* tmp = NodePop();
    int ret = 0;
    if (tmp != nullptr)
    {
        ret = tmp->getVal();
    }

    else
    {
        throw "Stack Empty";
    }
    delete tmp;
    return ret;
}

private:

Node* top;
};

class Queue
{
public:
Queue(void)
{
    back = front = nullptr;
}

~Queue(void)
{
    while (NodeDequeue() != nullptr);
}

void Enqueue(int i, int priority = 0)
{
    Node* tmp = new Node(i, back, nullptr, priority);
    back = tmp;
    if (front == nullptr) front = back;
    else
    {
        tmp = back->getNext();
        tmp->setPrev(back);
    }
}

int Dequeue(void)
{
    Node* tmp = NodeDequeue();
    int ret = 0;
    if (tmp != nullptr)
    {
        ret = tmp->getVal();
    }
    else
    {
        throw "Queue Empty";
    }
    if (front == nullptr) back = front; // queue now empty
    delete tmp;
    return ret;
}

protected:

Node* back;
Node* front;

private:

virtual Node* NodeDequeue(void)
{
    Node* tmp = front;
    if (front != nullptr)
    {
        front = front->getPrev();
        if (front != nullptr) front->setNext(nullptr);
    }
    return tmp;
}
};


class Scheduler : public Queue
{

public:
Node*getTail_Dll(Node*Head)
{
    if (Head != NULL)
    {
        while (Head->getNext() != NULL)
            Head = Head->getNext();
    }

    return Head;
}




 void partition_QuickSort_Dll(Node*Head, Node*Tail)
{
Node* NewTail=NULL,*Curr = Head, *Pivot = Tail;

    while (Curr != Pivot)
    {
        if ((Curr->getVal()) > (Pivot->getVal()))
        {
            if (Curr->getPrev() != NULL)
                Curr->getPrev()->setNext(Curr->getNext());
            if (Curr->getNext() != NULL)
                Curr->getNext()->setPrev(Curr->getPrev());

            NewTail = Curr;
            Curr = Curr->getNext();
            if (Curr->getPrev() == NULL)
                Head = Curr;

            NewTail->setPrev(Tail);
            NewTail->setNext(NULL);
            Tail->setNext(  NewTail);
        }
        else
            Curr = Curr->getNext();
    }

    if (Pivot->getPrev() != NULL)
        Pivot->getPrev()->setNext(NULL);

    if (Pivot->getNext() != NULL)
        Pivot->getNext()->setPrev(NULL);
}

 void quickSortList_Recur_Dll(Node*Head, Node*Tail)
{
    Node*Pivot = Tail;

    if ((Head != NULL) && (Tail != NULL) && (Head != Tail))
    {
        /* partition */
        partition_QuickSort_Dll(Head, Tail);
        /* sort left part */
        quickSortList_Recur_Dll(Head, (Pivot->getPrev()));
        /* sort right part */
            quickSortList_Recur_Dll(Pivot->getNext(), Tail);

        /* connect pivot to left & right parts */
        if (Pivot->getPrev() != NULL)
            Pivot->getPrev()->setNext(Pivot);

        if (Pivot->getNext() != NULL)
            Pivot->getNext()->setPrev( Pivot);  
    }
}

void quickSortList_Dll(Node*Head)
{
    Node*Tail = getTail_Dll(Head);

    if (Head != NULL)
        quickSortList_Recur_Dll(Head, Tail);
}
/*Node* split()
{

    Node *singleJump = back, *doubleJump = back;
    while (singleJump->getNext() && doubleJump->getNext()->getNext())
    {
        doubleJump = doubleJump->getNext()->getNext();
        singleJump = singleJump->getNext();
    }
    Node *temp = singleJump->getNext();
    singleJump->getNext()->setNext(nullptr);
    return temp;
}
*/


/*void antiBlock()
{
    cycle++;
    if (cycle == 5)
    {
        Node* temp = split();
        while (temp != front)
        {
            if (temp->getPriority() < 10)

                temp->setPriority(temp->getPriority() + 1);

        }
        cycle = 0;
    }
}*/
Node* NodeDequeue(void)
{
    Node* tmp = front;

    //antiBlock();
    quickSortList_Dll(back);
    if (front != nullptr)
    {
        front = front->getPrev();
        if (front != nullptr) front->setNext(nullptr);
    }
    return tmp;
}

};



int main()
{

Scheduler* s = new Scheduler;
s->Enqueue(11, 5);
s->Enqueue(2, 6);
s->Enqueue(3, 1);
s->Enqueue(40, 8);
s->Enqueue(15, 9);
s->Enqueue(6, 10);
//s->Enqueue(67, 6);
//s->Enqueue(78, 3);
//s->Enqueue(529, 2);
//s->Enqueue(110, 7);
//s->Enqueue(211, 4);
//s->Enqueue(312, 8);
//s->Enqueue(413, 3);
//s->Enqueue(154, 6);
//s->Enqueue(135, 2);
//s->Enqueue(116, 7);

    for (int i = 0; i < 6; i++)
    cout << s->Dequeue() << endl;


return 0;


};

Answer 1

在 NodeDequeue 中，我认为您是在第一个 Node 上调用 getPrev。第一个节点之前的节点应始终为 null。如果要删除第一个节点，则应将 first 设置为 first->next 然后将 first->prev 设置为 空。