La mise en œuvre de la priorité de la file d'attente en C++

Je suis en train de mettre en œuvre une file d'attente à l'aide d'un tableau circulaire. Mon code est censé être en mesure de retirer le nombre le plus bas de la file d'attente. J'ai créé test de code de sortie 1 2 3 4 5 les valeurs les plus faibles étant enlevé, mais mon réel de production est de 3 2 1 8 7. Je ne sais pas si mon problème est que mon code pour trouver la valeur la plus faible est incorrect ou il y a un problème avec la façon dont je suis le codage de l'effectif de la file d'attente. Je soupçonne les deux, mais j'apprécierais des suggestions ou des conseils pour trouver le problème dans mon code.

#include <iostream>
using namespace std;
class priorityQueue
{
private:
int front;
int rear;
int size;
int *array;
public:
priorityQueue();
~priorityQueue();
void insert(int x);
//remove and return the smallest item currently in the priority queue
int extractMin();
bool empty();
};
priorityQueue::priorityQueue()
{
front = rear = -1;
size = 10;
array = new int[size];
}
priorityQueue::~priorityQueue()
{
delete[] array;
}
void priorityQueue::insert(int x)
{
//if queue is full
if ( (rear + 1)% size == front ){
return;
}
//else if queue is empty
else if ( empty() ){
rear = front = 0;
}
else
{
rear = (rear + 1) % size;
}
array[rear] = x;
}
//extract and return smallest value in queue
int priorityQueue::extractMin()
{
int minValue = array[front];
if ( empty() ){
return -1;
}
else if (front == rear){
front = rear = -1;
}
else
{
front = (front + 1) % size;
}
//find smallest value
for (int i = front; i <= rear; i++){
if (array[i] < minValue)
minValue = array[i];
}
//return smallest value
return array[front];
}
bool priorityQueue::empty()
{
if ( (front == -1) && (rear == -1) )
return true;
else
return false;
}
int main()
{
priorityQueue myqueue;
myqueue.insert(4);
myqueue.insert(3);
myqueue.insert(2);
myqueue.insert(1);
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
myqueue.insert(8);
myqueue.insert(7);
myqueue.insert(6);
myqueue.insert(5);
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
cout << myqueue.extractMin() << endl;
system("pause");
return 0;
}

est-ce correct que vous return tableau[avant] pas minValue de extractMin()?
oubliée. merci pour l'attraper.
Remarque: votre file d'attente est cassé, si vous essayez de le copier, vous aurez probablement l'expérience d'un crash. Au lieu d'utiliser new, essayez d'utiliser std::vector<int>; vous pouvez alors retirer le destructeur, vous a écrit que ce sera inutile. En général, je vous conseille de ne pas mélanger les responsabilités: une classe pour gérer la mémoire, une classe permettant de gérer la logique, de cette façon, les deux sont simples (et peut être testé de façon indépendante).

OriginalL'auteur JosephK | 2014-02-10

c++dynamic-arrays priority-queue

1

Vous trouvez la plus petite valeur, cependant, il n'est pas la valeur que vous revenez quand vous extrayez min:
```
//find smallest value
for (int i = front; i <= rear; i++){
if (array[i] < minValue)
minValue = array[i];
}
//return smallest value
return array[front]; //Not equal to the smallest value
```
Je pense que ce que vous voulez faire est de trouver le plus petit numéro, puis de le retirer de la pile et de le retourner.

C'est peut-être pas le plus propre solution, mais il permettra de résoudre votre problème:
```
int minIndex = front;
//find smallest value
for (int i = front; i <= rear; i++){
if (array[i] < minValue)
{
minIndex = i;
minValue = array[i];
}
}
array[minIndex] = array[front];
//return smallest value
return minValue;
```
Si je devais mettre en œuvre une file d'attente de priorité, je ferait en sorte de toujours mettre la plus petite valeur à l'avant et assurez-vous que le tableau est trié quand je fais insérer.
```
int index = rear;
for(int i = front ; i <= rear ; i++)
{
if(x < array[i])
{
for(int j = rear ; j >= i ; j--)
{
array[j] = array[j-1];
}
index = i;
break;
}
}
array[index] = x;
```
En ajoutant ceci à votre insert type de travail, cependant la première fois lorsque le fragment de code suivant est exécuté avant sera fixé à un. ce qui signifie que vous passez la première valeur dans la file d'attente.
```
else
{
front = (front+1) % size;
}
```
Je suggère de faire le changement ci-dessus de l'insert et de changer votre extractmin à quelque chose comme ceci:
```
//extract and return smallest value in queue
int priorityQueue::extractMin()
{
//Handle circulation.
//return smallest value
return array[front++];
}
```
je pensais retour[avant] ou le retour[minValue] (que j'avais vu à tort) et j'ai été inconscient de retour minValue. ma nouvelle sortie pour 1 1 1 1 5. Il commence et se termine bien alors que c'est un plus. : ) Je vais garder à elle.
J'ai modifié mon code pour inclure minIndex comme vous l'avez suggéré, mais mon résultat est 1 2 2 3 5. Est qu'une erreur sur ma fin. Avez-vous été en mesure de venir avec le bon de sortie?
Oh, d'accord. Juste vérifier. Merci.

OriginalL'auteur Simon Karlsson
1

en supposant que vous résoudre ce petit problème:
```
//return smallest value
return array[front];
```
où vous êtes de retour à l'avant de la file d'attente, pas le plus petit élément,

vous avez encore un problème dans ton code, parce que c'est comportement étrange (pour une file d'attente): supposons que votre taille de file d'attente est de 4 et que vous avez les éléments 3 1 2 4 int la file d'attente; dans cet ordre. Lors de l'extraction, de vous renvoyer à 1, et maintenant, si vous insérez un nouvel élément, 5, votre attente va contenir 5,1,2,4; on a remplacé le mauvais élément;

Oh, d'accord. Visualiser comme ça aide. Merci.
n'oubliez pas de upvote si vous avez trouvé toutes les réponses utiles 🙂

OriginalL'auteur Pandrei

Vous devez vous connecter pour publier un commentaire.