312-174

Lab 6

Spring 2000

Due (PreLab, bridge): Monday, 28 Feb 2000, beginning of class.

Due (In-Lab/PostLab): Monday, 28 Feb, beginning of class.

Goals:

1. Create an dynamic implementation of queues.

2. Review pointers.

Requirements.

1. Complete prelab 6 and the bridge exercise from the Data Structures in C++ lab manual by Roberge. You only have to do steps 3 and 4. This means that you only have to implement a queue using pointers. You do not have to implement it using arrays. You may work in pairs for the PreLab and bridge.

   Turn in your completed pages 112 and 113 in class on Monday. Place all the files that I need to run your solution into a folder labeled with your last name(s) and drag it into the appropriate prelab folder in the Turn-In folder on Nova. If I cannot open your folder, double click on your project file, and run your solution (or at least look at it in C++ builder if you haven't completed it), you will not get credit for handing it in.

2. You must next complete in-lab exercise 1 from the lab book. This part must be done individually.

3. Finally, complete postlab exercise 1 . This must be done individually.

   Turn in pages 114-117, and 120 in class Monday. Place all of the files that I need to run your in-lab solution into a folder labeled with your last name and drag it into the appropriate lab folder in the Turn-In folder on Nova.

Late prelabs, bridges, and postlabs will be penalized as described in the study guide.

All results must be put into the appropriate lab folder on the cs174jb nova account.

All prelabs must have a heading identifying the people who worked on the project. Programs must also contain appropriate comments and headings. Make sure that your code is commented and formatted appropriately. See the style sheets.

Additional requirements:

1. Note: the code I provide you in queueLinkV2.h is different than the code provided in the book. I'm doing this because of the problem with forward references with templates in Builder. Basically, the Queue class is no longer a "friend" class to the QueueNode. Instead, QueueNode provides two public functions, getEle() and getPtr() which return the value of the element and pointer stored in the node. Notice that the data remains private. You must use this implementation.

2. You must include pre and post conditions in every member function that you write (both preLab and Lab). These must be as specific as possible.

3. Your code must be commented and appropriately formatted. Code in any block (ie in any set of braces) must be indented at least 3 spaces.

4. Your member functions must check for any requirements (preconditions) that are part of the ADT structure. If the requirements are not met by the parameters, the member functions must provide a proper response.

5. Place only your last names on the folder that you turn in. Make sure that the prelab is placed in the prelab folder on Nova and the lab is placed in the lab folder on Nova.

6. Written answers must be legible. If I can't read an answer, I will mark it wrong. Print or type if you must.

Hints:

• Important Note!!! The Queue and QueueNode classes reference each other (a Queue contains a QueueNode and a QueueNode names a Queue as a friend). A compiler will have problems with this circular reference. The correct way to get around this problem is to prototype the Queue class before the QueueNode class is declared. Unfortunately, both classes are templated and Builder C++ does not allow forward references of templated classes. This is not a C++ problem, it's a Builder problem.

  There are several ways to resolve this problem. We will take the easiest way out (rather than the more secure way). We will change the definition of the QueueNode class so that all of its variables are Public instead of private. We can then eliminate the friend line. The result is:

  template 
  class QueueNode
  {
  	public:
  		
  			// Constructor
  			QueueNode ( const SE &elem, QueueNode *nextPtr );
  			
  			// Data Members
  			SE element;			// Queue element
  			QueueNode *next;	// Pointer to the next element
  			
  };
  

• To create a random number, use the function call rand(). This function is defined in the stdlib.h library. To use it in your code you must include the following line in your main function:

  #include <stdlib.h>

  rand() returns a random integer between 0 and RAND_MAX where RAND_MAX is a constant defined in stdlib.h. To convert this to a random number between 0 and 3, you should mod the random number with 3:

  randomInt = rand();
  myRand = randomInt % 3;
  

  For more information, see page 245 of the Dale book.

• Remember that you must allocate storage explicitly (by using new) before you can reference a value using a pointer variable.

• Remember that a enqueue operation will require the dynamic creation of a new QueueNode element.

• Remember to delete an element if you dequeue it or when you run clear(). You will lose points for memory leaks!

Return to Student Pages

Return to John Barr's Home Page

Last Modified: 17 February 2000

THIS PAGE MAINTAINED BY:
John Barr, Ithaca College