CSCI 132 Data Structures

    Home | | Syllabus | | Assignments | | Lecture Notes

    Laboratory 7
    Due at the beginning of class, Wednesday, 3/26

    In today's lab you will practice implementing the List class using two different representations discussed in lecture: the contiguous and the linked-list representations

    The code for this lab is available in the directory:

      ~csci132/labs/lab7

    Start the lab as follows:

    • Copy the code for lab7 into your labs folder by typing:
        cp -r ~csci132/labs/lab7 labs/.
    • Verify that the lab7 directory contains the following files:
      • list.h
      • list.cc
      • testList.cc
      • listL.h
      • listL.cc
      • testListL.cc

    1. Writing implementations for a contiguous list

    In the list.cc file, fill in the missing code for the function stubs for remove(), replace() and retrieve() for the implementation of a list that is represented as an array of elements. (See the list.h file for the specification of the class). Pay close attention to the postconditions for each of these. In particular, note that the remove() function stores the value of the removed item in a parameter (&x). Make sure to do the appropriate error checking (i.e. check for range_error and underflow where appropriate).

    To test your code, you should compile the file, testList.cc. This file includes not only the list.h file, but also the list.cc file (this is necessary so that the correct object code can be created for the given List_entry type). Therefore, to compile this code, you can use the command:

      g++ -g -Wall testList.cc -o testList

    Sample output:
    When you run testList, the output should look as follows: 

      Inserted value 222 at position 10.
Removed from position 4, value = 8
Replaced position 6 with value 111.
Retrieved from position 3, value = 6
Removed from position 0, value = 0
2
4
6
10
12
111
16
18
222
20

    2. Writing implementations for a linked list

    In the listL.cc file, fill in the missing code for the same functions as above: remove(), replace() and retrieve(). In this implementation, the list is represented as a linked list. (See the specification in the listL.h file). The functions should have the same postconditions as for the contiguous implementation. You will need to make use of the list function, set_position() to locate the appropriate node. Make sure to do appropriate error checking. Also, in the remove() function, you will need to consider special cases. What happens when you want to remove the first node (at position 0)? Do you need to write special code if you want to remove the last node (at position count -1)? Think these cases through carefully!

    To test your code, you should compile the file, testListL.cc. This file includes not only the listL.h file, but also the listL.cc file (this is necessary so that the correct object code can be created for the given List_entry type). Therefore, to compile this code, you can use the command:

      g++ -g -Wall testListL.cc -o testListL

    Run testListL and you should get the same output as above.

    What To Turn In.

    • A printout of the list.cc file
    • A printout of the listL.cc file
    • Submit your lab with the submit function:
        ~csci132/bin/submit csci132 lab7

    Be sure that the file prologue for each file contains your name, course, lecture section, date and purpose of the program or a description of the contents of the file (e.g. specification of the stack class).

    Reminder.
    Be sure to save a copy of each file in your labs directory. It is your responsibility to keep the copies of all programs written for this course until your graded assignment is returned.

    Home | | Syllabus | | Assignments | | Lecture Notes