Purpose of This Assignment This assignment gives you experience implementing an abstract data type using linked lists Follow the design Do not rename the functions or reorder the parameters Initially, this might look like a difficult assignment It isn't Keep it simple Read the entire assignment before you start to work on it You will need to define 2 structure types and 5 functions Background A priority queue is a collection of items each having a priority A priority queue supports three fundamental operations You can ask a priority queue whether it is empty You can insert an item into the priority queue with a given priority You can remove the item from the priority queue that has the smallest priority For example, suppose that you start with an empty priority queue and imagine performing the following steps Insert item one with priority 10 Insert item two with priority 5 Insert item three with priority 15 Remove the item with the smallest priority and call it x Remove the item with the smallest priority and call it y You should find that x is two and y is one The Assignment For this assignment, you will not write an application, but just a module that can be used as part of a larger application, as you did for assignment 4 Create a module called pqueue cpp that implements priority queues, with a header file called pqueue h that describes what pqueue cpp exports The interface includes the following, and nothing else Types ItemType and PriorityType are discussed below under the refinement plan A type, PriorityQueue Creating a PriorityQueue object with line PriorityQueue q makes q be an initially empty priority queue Function isEmpty ( q ) returns true if q is an empty priority queue Its prototype is bool isEmpty(const PriorityQueue q) Function insert ( q , x , p ) inserts item x with priority p into q Its prototype is void insert(PriorityQueue q, ItemType x, PriorityType p) Function remove ( q , x , p ) removes the item that has the smallest priority from q Its prototype is void remove(PriorityQueue q, ItemType x, PriorityType p) Parameters x and p are out parameters 'Remove' sets x to the item that was removed and sets p to the priority associated with that item If q is empty, then remove( q , x , p ) writes a message on the standard output explaining the problem and stops the program Statement exit(1) stops the program and returns exit status 1 to the operating system You will need to include to use exit Function printPriorityQueue ( q , printItem, printPriority) prints the contents of priority queue q in a readable format for debugging Parameters printItem and printPriority are functions PrintPriorityQueue uses printItem( x ) to print item x and uses printPriority( p ) to print priority p Summary of the interface A module that uses priority queues can do the following, and nothing more It can create a variable q of type PriorityQueue, as follows PriorityQueue q The priority queue is initially empty It can use the following functions bool isEmpty(const PriorityQueue q) void insert(PriorityQueue q, ItemType item, PriorityType pri) void remove(PriorityQueue q, ItemType item, PriorityType pri) Strictly for debugging, it can use void printPriorityQueue(const PriorityQueue q, ItemPrinter printItem, PriorityPrinter printPriority) Additional Requirements Your program must follow the design in the section A refinement plan It can have additional functions, but it must have at least the functions indicated in the design Do not add extra responsibilities to the required functions A Refinement Plan Development plan 1 Create a directory for assignment 6 and create files pqueue h and pqueue cpp Use the module template for pqueue cpp and the header template for pqueue h Modify the templates with your name and the separation between tab stops, if you use tabs Get files Makefile, dotest and testpqueue cpp and put them in that directory Add a comment to pqueue cpp telling its purpose It provides priority queues Give a sketch of the interface 2 Items and Priorities Types ItemType and PriorityType Your module is intended to support an application, not to be an application You will use it in assignments 7 and 8 It is not clear right now what types of items or priorities the application will need assignment 7 needs different item and priority types than assignment 8 To handle that, define two types, ItemType and PriorityType , in pqueue h For this assignment, use definitions typedef const char ItemType typedef double PriorityType Later, when you want to change the definitions of ItemType and PriorityType, you should only need to change those two lines Not a single other line should need to be touched (You might need to add one or more include lines to pqueue h to make some types available ) That means you need to write the entire implementation of priority queues using ItemType for the type of an item and PriorityType for the type of a priority Do not assume that ItemType is const char or that PriorityType is double They will need to be changed for later assignments 3 Representing Priority Queues Types PriorityQueue and PQCell You are required to represent the information in a priority queue using a linked list, kept in nondecreasing order by priority That means items with smaller priorities are closer to the beginning of the linked list You will need the following types In pqueue cpp , define a structure type, PQCell , that is used as a cell in a linked list It holds an item, a priority, and a pointer to the next cell in the list Document type PQCell Be sure to say that an object of type PQCell is a cell in a linked list In pqueue h , write a forward declaration of PQCell , as follows struct PQCell That allows your definition of PriorityQueue to use type PQCell In pqueue h , after the forward definition of PQCell , define a structure type, PriorityQueue , that holds only a pointer to a linked list made of PQCells This pointer must be initially set to NULL by a parameterless constructor in the definition of PriorityQueue Document type PriorityQueue in pqueue h What is an object of type PriorityQueue Mention that it is represented by a linked list that is in nondecreasing order by priority 4 Testing Whether a Priority Queue Is Empty In pqueue cpp , document and define function isEmpty( q ) with the following prototype bool isEmpty(const PriorityQueue q) IsEmpty( q ) must return true if q is empty, false if q is not empty Add a prototype for isEmpty pqueue h 5 Insertion into a Priority Queue In pqueue cpp , document and define function insert( q , x , p ), which inserts item x with priority p into PriorityQueue object q Add prototype void insert(PriorityQueue q, ItemType x, PriorityType p) to pqueue h You will find it convenient to write a helper function void insertCell(PQCell L, ItemType x, PriorityType p) that inserts item x with priority p into linked list L (made of PQCells) It assumes that L is in nondescending order by priority, and it inserts the new item into the correct spot so that the list is still in nondescending order by priority The reason for defining 'insertCell' is that it can be recursive, and that makes it easier to write The body of 'insert' should just make a call to 'insertCell' That is, 'insert' should have a one line body Do not put a prototype for 'insertCell' into pqueue h since 'insertCell is not being exported it is only to be used in pqueue cpp 6 Debugging Printing the Priority Queue In pqueue cpp , write a function for debugging that prints the content of the priority queue in a readable format There is an important issue here Remember that the definitions of types ItemType and PriorityType might be changed You cannot assume that ItemType is const char or that PriorityType is double But then how do you know how to print the items and priorities A solution is to require the module that uses priority queues to say how to print items and priorities by providing two functions, one for printing an item and another for printing a priority C allows you to pass a function as a parameter of a function (Think of lending a tool to a friend You don't use the tool, your friend does ) Add the following type definitions to pqueue h typedef void ( ItemPrinter)(ItemType) typedef void ( PriorityPrinter)(PriorityType) They define types ItemPrinter and PriorityPrinter The function to print an item has type ItemPrinter it takes a parameter of type ItemType and has a void return type The function to print a priority has type PriorityPrinter It takes a parameter of type PriorityType and has a void return type In pqueue cpp , document and define a function printPriorityQueue with the following prototype void printPriorityQueue(const PriorityQueue q, ItemPrinter printItem, PriorityPrinter printPriority) It must show a clear and readable representation of what is in priority queue q , including each value and its priority In the body of printPriorityQueue , use statement printItem(x) to print item x and printPriority(y) to print priority y PrintPriorityQueue should assume that printItem and printPriority do not write any spaces or newlines PrintPriorityQueue should print those It is not acceptable to write out the entire priority queue on one line Function printPriorityQueue is only intended to be used for debugging Put a prototype for printPriorityQueue into pqueue h so that other modules can use it for debugging 7 Testing insert Add a stub for 'remove' It does nothing, but it allows you to run the tester to test 'insert' Here is a suitable stub void remove(PriorityQueue q, ItemType x, PriorityType p) x nothing p 0 0 Put a prototype for remove into pqueue h Now use the automated tester to test insert Don't be surprised that errors are reported about 'remove' not working But don't move on to the next step until 'insert' is working 8 Removing an Item In pqueue cpp , replace the stub for 'remove' by a correct definition 'Remove' must remove the item from q that has the smallest priority (If two or more items have the same priority, remove one of them ) Parameters x and p are out parameters 'Remove' must store the item that is removed into variable x and store its priority into p Be sure that 'remove' deletes the list cell that is removed so that you do not have a memory leak 9 Test remove Rerun the automated tester This time, everything should look right If not, fix any errors 10 Proofread pqueue cpp and pqueue h Check contracts for correctness, spelling and grammar Are standards followed Are all parameters described and referred to by name in contracts Are contracts written in complete sentences 11 Submit your work

The Answer is in the image, click to view ...

Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 11, 2024

Purpose of This Assignment This assignment gives you experience implementing an abstract data type using linked lists. Follow the design. Do not rename the functions

Purpose of This Assignment

This assignment gives you experience implementing an abstract data type using linked lists.

Follow the design. Do not rename the functions or reorder the parameters.

Initially, this might look like a difficult assignment. It isn't. Keep it simple. Read the entire assignment before you start to work on it.

You will need to define 2 structure types and 5 functions.

Background

A priority queue is a collection of items each having a priority. A priority queue supports three fundamental operations.

You can ask a priority queue whether it is empty.
You can insert an item into the priority queue with a given priority.
You can remove the item from the priority queue that has the smallest priority.

For example, suppose that you start with an empty priority queue and imagine performing the following steps.

Insert item "one" with priority 10.
Insert item "two" with priority 5.
Insert item "three" with priority 15.
Remove the item with the smallest priority and call it x.
Remove the item with the smallest priority and call it y.

You should find that x is "two" and y is "one".

The Assignment

For this assignment, you will not write an application, but just a module that can be used as part of a larger application, as you did for assignment 4.

Create a module called pqueue.cpp that implements priority queues, with a header file called pqueue.h that describes what pqueue.cpp exports. The interface includes the following, and nothing else. Types ItemType and PriorityType are discussed below under the refinement plan.

A type, PriorityQueue. Creating a PriorityQueue object with line
```
 PriorityQueue q; 
```
makes q be an initially empty priority queue.
Function isEmpty(q) returns true if q is an empty priority queue. Its prototype is
```
 bool isEmpty(const PriorityQueue& q); 
```
Function insert(q, x, p) inserts item x with priority p into q. Its prototype is
```
 void insert(PriorityQueue& q, ItemType x, PriorityType p); 
```
Function remove(q, x, p) removes the item that has the smallest priority from q. Its prototype is
```
 void remove(PriorityQueue& q, ItemType& x, PriorityType& p); 
```
Parameters x and p are out-parameters. 'Remove' sets x to the item that was removed and sets p to the priority associated with that item.

If q is empty, then remove(q, x, p) writes a message on the standard output explaining the problem and stops the program. Statement
```
 exit(1); 
```
stops the program and returns exit status 1 to the operating system. You will need to include to use exit.
Function printPriorityQueue(q, printItem, printPriority) prints the contents of priority queue q in a readable format for debugging. Parameters printItem and printPriority are functions. PrintPriorityQueue uses printItem(x) to print item x and uses printPriority(p) to print priority p.

Summary of the interface

A module that uses priority queues can do the following, and nothing more.

It can create a variable q of type PriorityQueue, as follows.
```
 PriorityQueue q; 
```
The priority queue is initially empty.

It can use the following functions.

 bool isEmpty(const PriorityQueue& q); void insert(PriorityQueue& q, ItemType item, PriorityType pri); void remove(PriorityQueue& q, ItemType& item, PriorityType& pri);

Strictly for debugging, it can use

 void printPriorityQueue(const PriorityQueue& q, ItemPrinter printItem, PriorityPrinter printPriority);

Additional Requirements

Your program must follow the design in the section "A refinement plan." It can have additional functions, but it must have at least the functions indicated in the design. Do not add extra responsibilities to the required functions.

A Refinement Plan

Development plan
1. Create a directory for assignment 6 and create files pqueue.h and pqueue.cpp. Use the module-template for pqueue.cpp and the header-template for pqueue.h. Modify the templates with your name and the separation between tab stops, if you use tabs. Get files Makefile, dotest and testpqueue.cpp and put them in that directory. Add a comment to pqueue.cpp telling its purpose. It provides priority queues. Give a sketch of the interface.

2. Items and Priorities: Types ItemType and PriorityType Your module is intended to support an application, not to be an application. You will use it in assignments 7 and 8. It is not clear right now what types of items or priorities the application will need; assignment 7 needs different item and priority types than assignment 8. To handle that, define two types, ItemType and PriorityType, in pqueue.h. For this assignment, use definitions typedef const char* ItemType; typedef double PriorityType; Later, when you want to change the definitions of ItemType and PriorityType, you should only need to change those two lines. Not a single other line should need to be touched. (You might need to add one or more #include lines to pqueue.h to make some types available.) That means you need to write the entire implementation of priority queues using ItemType for the type of an item and PriorityType for the type of a priority. Do not assume that ItemType is const char* or that PriorityType is double. They will need to be changed for later assignments.

3. Representing Priority Queues: Types PriorityQueue and PQCell You are required to represent the information in a priority queue using a linked list, kept in nondecreasing order by priority. That means items with smaller priorities are closer to the beginning of the linked list. You will need the following types. In pqueue.cpp, define a structure type, PQCell, that is used as a cell in a linked list. It holds an item, a priority, and a pointer to the next cell in the list. Document type PQCell. Be sure to say that an object of type PQCell is a cell in a linked list. In pqueue.h, write a forward declaration of PQCell, as follows. struct PQCell; That allows your definition of PriorityQueue to use type PQCell. In pqueue.h, after the forward definition of PQCell, define a structure type, PriorityQueue, that holds only a pointer to a linked list made of PQCells. This pointer must* be initially set to NULL by a parameterless constructor in the definition of PriorityQueue. Document type PriorityQueue in pqueue.h. What is an object of type PriorityQueue? Mention that it is represented by a linked list that is in nondecreasing order by priority.

4. Testing Whether a Priority Queue Is Empty In pqueue.cpp, document and define function isEmpty(q) with the following prototype. bool isEmpty(const PriorityQueue& q); IsEmpty(q) must return true if q is empty, false if q is not empty. Add a prototype for isEmpty pqueue.h.

5. Insertion into a Priority Queue In pqueue.cpp, document and define function insert(q, x, p), which inserts item x with priority p into PriorityQueue object q. Add prototype void insert(PriorityQueue& q, ItemType x, PriorityType p); to pqueue.h. You will find it convenient to write a helper function void insertCell(PQCell& L, ItemType x, PriorityType p) that inserts item x with priority p into linked list L (made of PQCells). It assumes that L is in nondescending order by priority, and it inserts the new item into the correct spot so that the list is still in nondescending order by priority. The reason for defining 'insertCell' is that it can be recursive, and that makes it easier to write. The body of 'insert' should just make a call to 'insertCell'. That is, 'insert' should have a one-line body. Do not put a prototype for 'insertCell' into pqueue.h* since 'insertCell; is not being exported; it is only to be used in pqueue.cpp.

6. Debugging: Printing the Priority Queue In pqueue.cpp, write a function for debugging that prints the content of the priority queue in a readable format. There is an important issue here. Remember that the definitions of types ItemType and PriorityType might be changed. You cannot assume that ItemType is const char* or that PriorityType is double. But then how do you know how to print the items and priorities? A solution is to require the module that uses priority queues to say how to print items and priorities by providing two functions, one for printing an item and another for printing a priority. C++ allows you to pass a function as a parameter of a function. (Think of lending a tool to a friend. You don't use the tool, your friend does.) Add the following type definitions to pqueue.h. typedef void (ItemPrinter)(ItemType); typedef void (PriorityPrinter)(PriorityType); They define types ItemPrinter and PriorityPrinter. The function to print an item has type ItemPrinter; it takes a parameter of type ItemType and has a void return type. The function to print a priority has type PriorityPrinter. It takes a parameter of type PriorityType and has a void return type. In pqueue.cpp, document and define a function printPriorityQueue with the following prototype. void printPriorityQueue(const PriorityQueue& q, ItemPrinter printItem, PriorityPrinter printPriority); It must show a clear and readable representation of what is in priority queue q, including each value and its priority. In the body of printPriorityQueue, use statement printItem(x); to print item x and printPriority(y); to print priority y. PrintPriorityQueue should assume that printItem and printPriority do not write any spaces or newlines. PrintPriorityQueue should print those. It is not acceptable to write out the entire priority queue on one line. Function printPriorityQueue is only intended to be used for debugging. Put a prototype for printPriorityQueue into pqueue.h so that other modules can use it for debugging.

7. Testing insert Add a stub for 'remove'. It does nothing, but it allows you to run the tester to test 'insert'. Here is a suitable stub. void remove(PriorityQueue& q, ItemType& x, PriorityType& p) { x = "nothing"; p = 0.0; } Put a prototype for remove into pqueue.h. Now use the automated tester to test insert. Don't be surprised that errors are reported about 'remove' not working. But don't move on to the next step until 'insert' is working.

8. Removing an Item In pqueue.cpp, replace the stub for 'remove' by a correct definition. 'Remove' must remove the item from q that has the smallest priority. (If two or more items have the same priority, remove one of them.) Parameters x and p are out-parameters. 'Remove' must store the item that is removed into variable x and store its priority into p. Be sure that 'remove' deletes the list cell that is removed so that you do not have a memory leak.

9. Test remove Rerun the automated tester. This time, everything should look right. If not, fix any errors.

10. Proofread pqueue.cpp and pqueue.h. Check contracts for correctness, spelling and grammar. Are standards followed? Are all parameters described and referred to by name in contracts? Are contracts written in complete sentences?

11. Submit your work.