Due (PreLab, bridge): Friday, 14 Apr 2000, end of class.

Due (In-Lab/PostLab): Monday, 17 Apr 2000, end of class.

Goals:

1. Use recursion.

2. Review pointers.

Note: even though this is lab 11, we are using lab 10 from the Roberge book!

Requirements.

1. Complete prelab 10 (parts A, B, and C only) and the bridge exercise (parts A and B) from the Data Structures in C++ lab manual by Roberge. This lab demonstrates the use of recursion. You will have to create an unordered list similar to the one that you created in Lab 7 (dynamic implementation). Most of the code is provided in the software:Lab 11 folder. You must add some of the functions from lab 7 to this code. These functions can be the same as you used in lab 7, they do not have to be recursive.

2. Do only parts A, B, and C of the prelab. Do both part A and part B from the bridge exercises.

   You may use function implementations from lab 7. Note that these are no longer on the web, so you can only use your implementation if you have kept a file backed up on a disk somewhere.

3. You may work in pairs for the PreLab and bridge. Turn in your completed pages 193 - 198 and 203-206 in class on Friday. 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.

4. You must next complete in-lab exercises 1A (not B) and 2 from the lab book. This part must be done individually.

5. Finally, complete postlab exercises 1 and 2. This must be done individually.

   Turn in pages 207-208, 210-211, and 214-215 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. Your test plan need cover only characters. Every test plan given in the in-labs must be filled out appropriately. Part of your grade will be based on the completeness of your test plan.

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:

• The aBeforeb() function is not a normal insert function. Instead, this function will recurse through the list and find every occurrence of the character b in the list (there may be many) and insert the character a before it. For example, if the list contains the following characters before a call to aBeforeb():

  b c d b g b a z f b b

  Then after a call to aBeforeb() it will contain:

  a b c d a b g a b a z f a b a b

  Note that occurrences of a in the original list are not affected.

• Important Note!!! The List and ListNode classes reference each other (a List contains a ListNode and a ListNode names a List as a friend). A compiler will have problems with this circular reference. The correct way to get around this problem is to prototype the List class before the ListNode 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 solve this problem by adding public accessor and transformer functions to the ListNode. getEle() will returns the element stored in the ListNode, getPtr() will return the pointer stored in the node and setEle and setPtr will change the element and pointer values stored in the node. We can then eliminate the friend line. The result is:

  template 
  class ListNode
  {
  	public:
  		
  			// Constructor
  			ListNode ( const LE &elem, ListNode *nextPtr );
  			
  			// Get the element stored
  			LE getEle();
  			
  			// Get the pointer stored
  			ListNode *getPtr();
  			
  			// gives the node a new element
  			void setEle(const LE &elem);  
  	
  			// gives the node a new next pointer
  			void setPtr(ListNode *newPtr);  
  						
  	private:
  			// Data Members
  			LE element;			// List element
  			ListNode *next;	// Pointer to the next element
  			
  };
  

• Unfortunately, when you make this change, you must also change the showStructure() function defined in the code that you were given. You must rewrite this function to work with your list. You can iterate through the List using the iterator member functions of the list and print out the stored value using the member function getCursor( )

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

• Remember that an insert operation will require the dynamic creation of a new ListNode element.

• Remember to delete an element if you remove 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: 6 April 2000

THIS PAGE MAINTAINED BY:
John Barr, Ithaca College