Быстрый поиск по дважды связанному списку

Question

Привет, ребята, я пытаюсь построить quicksort в свой код планировщика, используя alghoritm, найденный в Интернете. Моя проблема заключается в том, что в какой-то момент кода я получаю нарушение доступа к getPrev, возможно, это указывает на нуль, но я застрял и понятия не имею, как заставить его работать. Будем благодарны за любую небольшую помощь или, по крайней мере, за советы, в каком направлении мне идти. Я уже потратил на это часы, и это не действует.

#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

Вы должны использовать quicksort (не список "friendly")? Если нет, используйте сортировку слияния снизу вверх с массивом указателей на первые узлы списка. Это старый алгоритм, но по какой-то причине он не очень хорошо известен. Он использует только указатели вперед (далее) и типичный MergeLists(), который объединяет два уже отсортированных списка, поэтому он является списком «дружественный».

Пример шаблона, первый узел хранится в массиве [0]. второй узел объединяется с массивом [0] для создания списка размера 2 и сохраняется в массиве [1] (массив [0] очищается). Через два узла список размера 2 объединяется с массивом [1] для создания списка размера 4 и сохраняется в массиве [2] (массив [0], массив [1] очищен). массив [30] содержит список размером 1 миллиард (2^30). массив [31] размер списка неограничен, в него одновременно объединяется 1 миллиард узлов. Таким образом, размер массива 32 составляет избыток, но занимает настолько мало места, что вы могли бы его использовать.

Wiki статьи:

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Answer 2

В NodeDequeue, я думаю, что вы звоните getPrev на первом Node. Узел перед первым узлом всегда должен быть null. Если вы удаляете первый узел, вы должны установить first, равный first->next, а затем установить first->prev на null.