I am making a priorityQueue with a linkedList, I understand everything except for my extractMin(), I basically made a copy of the original pQueue and traversed through the copy to find the smallest data field and placed a pointer on that node and compared to the rest of the nodes, then once found, return the smallest data
this it the pritorityQueueLL.h
#include <iostream>
#include <cmath>
using namespace std;
class priorityQueueLL
{
private:
class node
{
public:
//put what you need here..
node *prev, *next;
int data;
node(int x)
{
data = x;
prev = NULL;
next = NULL;
}
};
node * top;
node * bottom;
public:
priorityQueueLL()
{
top = NULL;
bottom = NULL;
}
~priorityQueueLL()
{}
//return true if empty, false if not
bool empty()
{
if(top == NULL)
{
return true;
}
else
{
return false;
}
}
//add item
void insert(int x)
{
node * ai = new node(x);
if(top == NULL)
{
top = ai;
bottom = ai;
}
else
{
bottom -> next = ai;
ai -> prev = bottom;
bottom = ai;
}
}
//remove and return smallest item
int extractMin()
{
node * copy = top;
node * end = bottom;
int val;
//if there is one node in the pq
if(top -> next == NULL)
{
node * tmp = top;
top = NULL;
return tmp -> data;
delete tmp;
}
//if it is empty, return out
if( empty() )
{
return 0;
}
else //if it has at least two nodes in the pq
{
node * smallest = copy;
node * tmp = copy;
while(tmp != NULL)
{
val = smallest -> data;
tmp = tmp -> next;
if(tmp -> data < val)
{
val = tmp -> data;
smallest = tmp;
return val;
tmp -> prev -> next = tmp -> next;
tmp -> next -> prev = tmp -> prev;
delete tmp;
}
}
}
}
};
this is main.cpp
#include <iostream>
#include "stackLL.h"
#include "queueLL.h"
#include "priorityQueueLL.h"
using namespace std;
int main()
{
/////////////Test code for stack ///////////////
stackLL stk;
stk.push(5);
stk.push(13);
stk.push(7);
stk.push(3);
stk.push(2);
stk.push(11);
cout << "Popping: " << stk.pop() << endl;
cout << "Popping: " << stk.pop() << endl;
stk.push(17);
stk.push(19);
stk.push(23);
while( ! stk.empty() )
{
cout << "Popping: " << stk.pop() << endl;
}
// output order: 11,2,23,19,17,3,7,13,5
///////////////////////////////////////
////////////Test code for queue ///////////
queueLL Q;
Q.enqueue(1);
Q.enqueue(2);
Q.enqueue(3);
cout << "Dequeuing: " << Q.dequeue() << endl;
cout << "Dequeuing: " << Q.dequeue() << endl;
Q.enqueue(4);
Q.enqueue(5);
while( ! Q.empty() )
{
cout << "Dequeuing: " << Q.dequeue() << endl;
}
///////////////////////////////////////////
////////////Test code for priority queue/////
priorityQueueLL pQueue;
const int SIZE = 20;
//insert a bunch of random numbers
for(int i=0; i<SIZE; i++)
{
pQueue.insert( rand() );
}
//pull them back out..
while( ! pQueue.empty() )
{
cout << pQueue.extractMin() << endl;
}
///////////////////////////////////////////
system("pause");
return 0;
}
any ideas on what I could be doing wrong?
Aucun commentaire:
Enregistrer un commentaire