Create the ADT priority queue by implementing attached PriorityQueueInterface in

Question

Create the ADT priority queue by implementing attached PriorityQueueInterface interface .

Use a chain of linked nodes for your implementation and call the class LinkedPriorityQueue

Your implementation must use generics and be able to work with any object Type that is Comparable.

You are free to use circular or regular chain for your implementation but not array based implementation.

Use attached Driver class to test your implementation.

The Driver class uses attached  Entry class (which is Comparable) as data type.

The driver creates different instances of Entry with different values and store them in your priority queue implementation.

and the retrieve from the queue. your implementation priorities items based on their value.

You are not supposed to modify any of the attached file. But once you put your implementation of  LinkedPriorityQueue in the same folder as the other 3 files, the Driver class should compile and run.

Explanation / Answer

Answer:

typedef struct list_item
{
input_object *data;
struct list_item *later;
} list_item;

typedef list_item input;

input *create_input(void)
{
input *p;

p = (input *) malloc(sizeof(input));
if(p==NULL)  
    {
      printf("out of bound memory ");
      exit(1);
    }

p->later=NULL;
return p;
}

boolean input_is_empty(input *p)
{
return( (p->later==NULL) ? TRUE : FALSE );
}

input_object *find_min(input *p)
{
list_item *first, *second;

if(input_is_empty(p)==TRUE)
    {
      printf("Attempt to find minimum object in empty queue ");
      exit(1);
    }

first=p->later;
for(second=p->later->later; second; second=second->later)
    {
      if(second->data->input_cost < first->data->input_cost)
        first=second;
    }
return first->data;
}

void input_insert(input *p, input_object *object, cost object_cost)
{
list_item *new_item;

new_item = (list_item *) malloc(sizeof(list_item));
if(new_item==NULL)
    {
      printf("OUT OF MEMORY! ");
      exit(1);
    }

object->input_cost=object_cost;
new_item->data=object;

new_item->later=p->later;
p->later=new_item;
}

void delete_min(input *p)
{
list_item *first, *second, *before;

if(input_is_empty(p)==TRUE)
    {
      printf("Attempt to find minimum object in empty queue ");
      exit(1);
    }

first=p->later;
for(second=p->later->later; second; second=second->later)
    {
      if(second->data->input_cost < first->data->input_cost)
   first=second;
    }
for(before=p; before->later != first; before=before->later);

before->later=first->later;
free(first);
}

void less_price(input *p, input_object *object, cost smaller_cost)
{
object->input_cost=smaller_cost;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.