Assigned: | Monday, February 29 |
Due: | Wednesday, March 16, 11:59pm |
This assignment gives you experience using linked lists.
For this assignment, you will not write an application, but just a module that can be used in other applications, as you did for assignment 3.
Create a module called pqueue.cpp that implements priority queues, with a header file called pqueue.h that describes what pqueue.cpp exports.
A priority queue is an abstract data type. An instance of a priority queue holds a collection items, each with a priority. You can insert an item, with a given priority into the collection and you can remove the item with the smallest priority from the collection.
Development plan |
---|
1. Items and Priorities: Types PQItemType and PQPriorityTypeIt is not clear right now what types of items or priorities an application will need. For example, should the priorities by integers or real numbers or something else? Should the items be strings or widgets or something else? To handle that, you will define two types, PQItemType and PQPriorityType. Start with default definitions of them. But it must be possible to change what those types are only by changing one line for each type. Here are default definitions that you are required to use for this assignment. Put typedef const char* PQItemType; typedef double PQPriorityType;in pqueue.h to define type PQItemType to be const char* and PQPriorityType to be double. Write the entire implementation of priority queues using PQItemType for the type of an item and PQPriorityType for the type of a priority. Do not assume that PQItemType will be const char* or that PQPriorityType will be double. |
2. Representing Priority Queues: Types PriorityQueue and PQCellYou are required to store the information in a priority queue using a linked list, kept in increasing order by priority. You will need the following types. Provide documentation for each type.
|
3. Testing Whether a Priority Queue Is EmptyDocument and define function isEmpty with the following heading. bool isEmpty(const PriorityQueue& q);It must return true if q is empty, false if q is not empty. Put a prototype for isEmpty into pqueue.h. |
4. Insertion into a Priority QueueDocument and define function insert(item, pri, q) that inserts item item with priority pri into PriorityQueue object q. Put a prototype for this function into pqueue.h. The prototype is just the function's heading followed by a semicolon. For example, void insert(PQItemType item, PQPriorityType pri, PriorityQueue& q);says that there will be a definition of insert with this heading. By putting this prototype in pqueue.h, you are saying that other modules should be allowed to use it. Put the definition of insert into pqueue.cpp. You will find it convenient to write a helper function void insertCell(const PQItemType& item, PQPriorityType pri, PQCell*& p)that inserts a given item into a linked list. The reason is that this function can be recursive. Just make insert call insertCell. Do not put a prototype for insertCell in pqueue.h. It is only to be used in pqueue.cpp. |
5. Removing an ItemDocument and define function remove with the following heading. void remove(PQItemType& item, PQPriorityType& pri, PriorityQueue& q);It must remove the item from q that has the smallest priority. (If two items have the same priority, remove one of them.) It must also store the item that is removed into variable item and stores its priority into pri. Put a prototype for remove into pqueue.h. Be sure to delete the list cell that is removed. |
6. Debugging: Printing the Priority QueueAdd the following type definitions to pqueue.h. typedef void (ItemPrinter)(PQItemType); typedef void (PriorityPrinter)(PQPriorityType); Document and define a function printPriorityQueue with the following heading. void printPriorityQueue(const PriorityQueue& q, ItemPrinter pi, PriorityPrinter pp);It must show a clear and readable representation of priority queue q. Function printPriorityQueue is only intended to be used for debugging. Put a prototype for printPriorityQueue into pqueue.h so that another module can be used to debug pqueue.cpp. Recall that you do not know what types PQItemType and PQPriorityType will be. For now, they have defaults, but those can change. You want to define pqueue.cpp so that it will continue to work, without any modification, when the definitions of PQItemType and PQPriorityType are changed. To handle that, printPriorityQueue needs to be told how to print an item and how to print a priority. It uses pi to print an item and pp to print a priority. In the body of printPriorityQueue, write statement pi(x);to print item x and pp(y);to print priority y. PrintPriorityQueue should assume that pi and pp do not write any spaces or newlines. PrintPriorityQueue should print those. Another module can print a priority queue by defining functions for printing items and priorities. For example, If PQItemType and PQPriorityType have the default definitions, then the following would be suitable. void printString(const char* s) { printf("%s", s); } void printDouble(double x) { printf("%lf", x); }Now printPriorityQueue(q, printString, printDouble);prints priorith queue q. |
7. Summary of the priority queue interfaceA module that uses priority queues can do the following, and nothing more.
|
Keep function definitions short and simple.
As always, you must follow the coding standards for this course, which include the following.
Every function is required to have a clear, concise and precise contract telling what the function accomplishes and returns and how each of its parameters influences what it accomplishes and what it returns. The contract must not be concerned with how the function works.
A function body must not change the value of a call-by-value parameter.
You will need to write a test module that uses priority queues and demonstrates that your implementation is working, at least for the test cases. Call your tester testpq.cpp.
Ensure that your tester tests every function thoroughly. Try creating more than one priority queue. (You will need to use the same types of items and priorities for both.)
Testing is critical. Do not turn in an untested module.
A Makefile is provided for you. If your tester is called testpq.cpp, you can use the following commands with it.
To turn in your work, log into the Linux system, change your
directory for the one for assignment 5,
use the following command.
~abrahamsonk/3300/bin/submit 5 pqueue.cpp pqueue.h testpq.cpp
After submitting, you should receive confirmation that the
submission was successful. If you do not receive confirmation,
assume that the submission did not work.
Command
~abrahamsonk/3300/bin/submit 5
will show you what you have submitted for
assignment 5.
You can do repeated submissions. New submissions will replace old ones.
Late submissions will be accepted for one day after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.