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

Goals:

1. Understand the heap sort.

2. Review pointers.

Note: we are not using the Roberge book!

Requirements.

1. The prelab 13 and the bridge exercise from the Data Structures in C++ lab manual by Roberge are already completed and in the software folder. This provides a heap class. You are to add a heapsort function to the class. It may be either iterative or recursive. You must do the following tasks:
   • Add the heapsort function to the heap class.

   • Modify the heap class to make it work as necessary.

   • Change the main program to read in 20 integers, add them to the heap, and then perform a heap sort on them and then print them out using the showStructure function.

2. You may work in pairs for this lab. 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.

3. There is no post-lab this week.

No lab will be accepted after class on Friday.

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

All labs 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. 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.

2. 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.

3. 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.

4. 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.

5. 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 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.

  For this lab, we will resolve this problem by making all of the data public. The result is:

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

• 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: 17 April 2000

THIS PAGE MAINTAINED BY:
John Barr, Ithaca College