sort queue sort [C++]

Question

У меня есть назначение, и мне нужно добавить метод сортировки в очередь приоритетов, которую я сделал для моего последнего назначения.

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

О, и я действительно получил пункт, отведенный для моего последнего задания, и все, что он оставил для комментария, было «Ошибка сегментации при вызове enqueue()». Я отправил ему электронное письмо, что это значит, он не ответил (вчера раздавал оценки). Я думаю, что ошибка происходит из не вызывая malloc на линии 90.

#include <stdlib.h> //NEEDED TO RUN calloc 
#include <cstdio> // NEEDED TO RUN perror 
#include <iostream> 

using namespace std; 

// c-style struct 
// node used to implement linked list 
typedef struct _node 
{ 
    int value; 
    struct _node *next; 
} 
node; 

/* Standard Stack LIFO ADT */ 
class Priority_Queue 
{ 

    /* tracks number of nodes in Priority_Queue */ 
    int nNodes; 
    /* keeps track of first node in Priority_Queue */ 
    node *head; 
    void  sort(void); //Sort linked list using selection sorting algorithm 

    //anything above public is private 
    public: 

     Priority_Queue(void); //find a constructor everytime the user    extanjiates Priority_Queue object. 

     void enqueue(int); //insert node/ enqueue on an integer. 
     void dequeue(void); //remove node/ dequeue off node from the top. 
     bool empty(void); //test whether Priority_Queue is empty 
     int  size(void); //return size 
     int  top(void); // access top of the Priority_Queue/ next node. 
     int  back(void); 
}; 

/* init head and nNodes */ 
Priority_Queue::Priority_Queue(void) 
{ 
    head = NULL; //everytime a user enstantiates one of the Priority_Queues 
    nNodes = 0; // so we know how many nodes are sitting on our Priority_Queue. 
} 

/* place new node at top of Priority_Queue */ 
void Priority_Queue::enqueue(int value) //enqueue on a value/ user wants  to place a Priority_Queue 
{ 

    if(head == NULL) 
    { 
     if((head = (node*)calloc(1, sizeof(node))) == NULL) 
     { 
      perror("Could not calloc memory"); 
     } 
     else 
     { 
      head->value = value; 
      nNodes++; // increase the number of nodes in link list 
     } 
    } 
    else 
    { 
     node *temp; 

     if((temp = (node*)malloc(sizeof(node))) == NULL) //malloc  because both values for stut will be set immediatly 
     { 
      perror("Could not malloc memory"); 
     } 
     else 
     { 
      temp->value = value; // 
      node* p = head; 

      if (value<head->value) 
      { 
       temp -> next = head; 
       head = temp; 
       temp = NULL; 
      } 
      while (p->next != NULL && p->next->value<value) 
      { 
       p = p-> next; // p is pointintint to the next node 
      } 
      temp->next = p->next; 
      p->next = temp; 
      temp = NULL; 
      nNodes++; // increase the number of nodes in link list 
     } 
     //malloc(sizeof (node)); 
    } 

} 

/* remove the first node from top of Priority_Queue */ 
void Priority_Queue::dequeue(void) 
{ 
    node *temp; 

    if(head != NULL) // allow users to keep calling dequeue even if it is empty 
    { 
     temp = head; 
     head = head->next; // head is now pointing to 3 

     free(temp); 
     temp = NULL; 

     nNodes--; //decrease node count for the Priority_Queue 
    } 

} 

/* return true if Priority_Queue is empty */ 
bool Priority_Queue::empty(void) 
{ 
    return (head == NULL); //valuated as true or false. 
} 

/* return number of nodes in Priority_Queue */ 
int Priority_Queue::size(void) 
{ 
    return nNodes; //PLACING RESPONSIBILITY ON USER TO REMEMBER 28:00 part1 
} 

/* return value of node at top of Priority_Queue */ 
int Priority_Queue::top(void) 
{ 
    return head->value; // PLACING RESPONSIBILITY ON USER TO REMEMBER 28:00 part1 
} 

int Priority_Queue::back(void) 
{ 
    node *p = head; 
    while (p->next != NULL) 
    { 
     p = p->next; 
    } 
    return p->value; // 
} 

void Priority_Queue::sort(void) 
{ 
     node *temp; 
    bool onward = true; //while loop set to true 
    //compare each pair of adjacent elements 
    //switches elements if in wrong order 
    //Continues operations until elements are sorted. 
    while(onward) 
    { 
     // onward set to false so just in case it is sorted, it will loop through the elements. 
     for(temp = head, onward = false; temp->next != NULL; temp = temp->next) 
     { 
      //Check to see if current element is greater than the next 
      if(temp->value > temp->next->value) 
      { 
       //swapping current elements value 
       int a = temp->value; 
       temp->value = temp->next->value; 
       temp->next->value = a; 
       onward = true; // 
      } 
     } 
    } 
} 

int main(void) 
{ 
    /* instantiate new Priority_Queue */ 
    Priority_Queue my_Priority_Queue = Priority_Queue(); 
    int i = 0; 
    /* enqueue some values onto Priority_Queue */ 
    for(i = 0; i < 10; i++) 
     my_Priority_Queue.enqueue(i); 
    /* print values stored in Priority_Queue until Priority_Queue is empty */ 
    while(!my_Priority_Queue.empty()) 
    { 
     cout << "Value: " << my_Priority_Queue.top() << endl; // Give access to the top of the Priority_Queue. 
     my_Priority_Queue.dequeue(); // dequeue the top off so to see a different node at the top in the next line. 
     cout << "Node Count: " << my_Priority_Queue.size() << endl << endl; 
    } 
    my_Priority_Queue.dequeue(); 

    return 0; 
} 

Answer 1

приоритетной очереди, как правило, имеют функцию, чтобы получить наивысший приоритет элемента.

Чтобы отсортировать все элементы, все, что вам нужно сделать, это поместить элементы по одному, и они будут отсортированы в порядке.

Обычно очередь приоритетов реализуется как куча, а алгоритм сортировки с использованием кучи в качестве очереди приоритетов называется heapsort.

Поскольку вы не дали код очереди приоритетов, используя зЬй :: priority_queue в качестве примера, вот как вы бы получить отсортированный список элементов:

template<class T, class Container, class Compare> 
std::vector<T> get_sorted(std::priority_queue<T, Container, Compare> pq) 
{ 
    std::vector<T> sorted; 
    sorted.reserve(pq.size()); 
    while (!pq.empty()) 
    { 
    sorted.push_back(pq.top()); 
    pq.pop(); 
    } 
    return sorted; 
}