優先順位の高いリンクをリストの先頭に移動するアルゴリズム

Question

リンクリストを使用してプライオリティキューを作成する必要がありますが、分割エラーを残しておきます。私はまず、優先度なし（優先度= 0）のキューを生成します。私のアルゴリズムは、エンキューのためのようである：メインで

1. Create a new Link, pointer for second link, and pointer for swap 
2. If queue is empty, set new Link = front & back 
3. If not, check if new Link has any priority, if priority = 0, move new link 
to the back of`queue 
4. If new link has any priority, move it to the front 
5. Check to see if the front is less than 
6. if 2nd link has no priority or if 1st link has less priority, perform no swap 
7. if 2nd link's priority is <= front link; swap 

私はその後、私は固体のアルゴリズムを持っていることを確認するために、ループの外に優先順位なしとのリンクをエンキュー、優先順位なしで5リンクキューを生成します。私は別のになど、実際の優先順位、とのリンクをエンキュー

main.cppに

//System Libraries 
#include "PriorityQueue.h" 

using namespace std; 

int main(int argc, char** argv) { 
//Creating a new queue 
    PriorityQueue queue; 
    int MAX_VALUES = 5, num; 

    //Enqueueing each link one by one and displaying queue alongside 
    cout<<"\n"<<MAX_VALUES<< " values enqueued"; 
    for(int x = 0; x < MAX_VALUES; x++){ 
     cout<<"\nEnqueueing..."<<x<<": "; 
     queue.enqueue(x, 0); 
     queue.printQueue(); 
    } 

    //displaying results of enqueueing with priority 
    cout<<"\n------------"<<endl; 
    cout<<"Enqueueing links with priority"<<endl; 
    cout<<"\nEnqueueing w/ lvl. 1 priority...10: "; 
    queue.enqueue(10, 0); //newcomer with top priority 
    queue.printQueue(); 
    cout<<"\nEnqueueing w/ lvl. 2 priority... 9: "; 
    queue.enqueue(9, 2); //newcomer with lower priority than front 
    queue.printQueue(); 
      cout<<"\nDequeueing..."<<queue.returnFront()<<": "; //first two in queue get dequeued first 
      queue.dequeue(num); 
      queue.printQueue(); 
      cout<<"\nDequeueing..."<<queue.returnFront()<<": "; 
      queue.dequeue(num); 
      queue.printQueue(); 
    cout<<"\nEnqueueing w/ lvl. 1 priority...11: "; 
    queue.enqueue(11, 1); //newcomer to queue with same as top priority 
    queue.printQueue(); 

    //Dequeueing each link one by one and displaying it alongside 
    while(!queue.isEmpty()){ 
     cout<<"\nDequeueing..."<<queue.returnFront()<<": "; 
     queue.dequeue(num); 
     queue.printQueue(); 
    } 

    //Attempting one more dequeue to display isEmpty message 
    cout<<"\nDequeueing..."; 
    queue.dequeue(num); 

    cout<<endl; 
    return 0; 
} 

PriorityQueue.cpp

（あなたは私がメインでやったことを見ることができます）

//プリプロセッサディレクティブ

#ifndef PRIORITYQUEUE_H 
#define PRIORITYQUEUE_H 

//System Libraries 
#include <iostream> 

using namespace std; 

class PriorityQueue{ 
private: struct Link{ 
      int data; 
      int priority; 
      Link *next; 
     }; 
     Link *front, *back; 
     int listLength; 
public: PriorityQueue(){front = nullptr; back = nullptr;}; 
     ~PriorityQueue(){destroyList();}; 
     int returnFront(); 
     void printQueue(); 
     void destroyList(); 
     void enqueue(int, int); 
     void dequeue(int &); 
     bool isEmpty() const; 
}; 

void PriorityQueue::destroyList(){ 
    int value; // Dummy variable for dequeue 

    while(!isEmpty()) 
     dequeue(value); 
} 

void PriorityQueue::enqueue(int val, int priority){ 
    Link *newLink = new Link;//pointer for new link 
    Link *linkPtr = nullptr; //pointer for second link 
    Link *temp = nullptr; //pointer for swap of links 

    //allocating new link to pointer and storing number 
    newLink->data = val; 
    newLink->next = nullptr; 
    newLink->priority = priority; 

    //If stack is empty, make the new link the top of stack 
    if(isEmpty()){ 
     front = newLink; 
     back = newLink; 
    } 
    else{ 
     /* 1. move newLink to the front, if priority exists 
     * 2. make newLink point to the front 
     * 3. make the newLink the new front of the list 
     * 4. if 2nd link has no priority or if 1st link has 
     * less priority,perform no swap 
     * 5. if 2nd link's priority is <= front link; swap 
     */ 
     if(newLink->priority == 0){ 
     back->next = newLink; 
     back = newLink; 
     } 
     else if(newLink->priority >= 1){ 
      newLink->next= front;  //1. 
      linkPtr = newLink->next;  //2. 
      front = newLink;    //3. 

      if(front->priority < linkPtr->priority ||linkPtr->priority == 0){} //4. 
      else if(front->priority >= linkPtr->priority){ //5. 
       temp->data = linkPtr->data; 
       temp->priority = linkPtr->priority; 

       linkPtr->data = front->data; 
       linkPtr->priority = front->priority; 

       front->data = temp->data; 
       front->priority = temp-> priority; 
      } 
     } 
    } 

    //track list length 
    listLength++; 
} 

//removing links from front 
void PriorityQueue::dequeue(int& topVal){ 
    Link *temp = nullptr; 

    //If Queue is empty, message is displayed after dequeue attempt 
    if(isEmpty()){ 
     cout<<"Queue is empty."<<endl; 
    } 
    else{ 
     //save the top value into num 
     topVal = front->data; 

     //delete the front node 
     temp = front; 
     front = front->next; 
     delete temp; 

     //update list length 
     listLength--; 
    } 
} 

//returns whether the list is empty or not 
bool PriorityQueue::isEmpty() const{ 
    bool status; 

    if(listLength > 0) 
     status = false; 
    else 
     status = true; 

    return status;  
} 

//returns the value at the top of the queue 
int PriorityQueue::returnFront(){ 
    return front->data; 
} 

//Displays all values in queue 
void PriorityQueue::printQueue(){ 
    Link *newLink = front; 

    while(newLink != nullptr){ 
     cout<<" "<<newLink->data; 
     newLink = newLink->next; 
    } 
} 

#endif /* PRIORITYQUEUE_H */ 

Answer 1

PriotityQueue::enqueue関数では、temp=nullptrと宣言しています。 したがって、temp->dataとtemp->priorityを使用して2つのリンクを交換しようとすると、セグメンテーション違反が発生します。

交換はtempなしで行うことができます。

void PriorityQueue::enqueue(int val, int priority){ 
... 
else if(front->priority >= linkPtr->priority){ //5. 
      front->next=linkPtr.next; 
      linkPtr->next=front; 
      front=linkPtr; 
} 
... 
}