CSCI 132 Data Structures

    Assignment 6

    Due at the beginning of class, Friday, March 28, 2014

    Home | | Syllabus | | Assignments | | Lecture Notes

    Programming Style: You will be graded not only on whether your programs work correctly, but also on programming style, such as the use of informative names, good comments, easily readable formatting, and a good balance between compactness and clarity (e.g. do not define lots of unnecessary variables, or write multiple statements to perform a task that can be expressed clearly in a single statement.) Create appropriate functions for tasks that can be encapsulated.

    List functions

    In class we learned about the List class and the basic functions that go with it:

    • List( );
      /*Post: The List has been created and is initialized to be empty.*/
    • int size( ) const;
      /* Post: The function returns the number of entries in the List. */
    • bool full( ) const;
      /*Post: The function returns true or false according to whether the List is full or not.*/
    • bool empty( ) const;
      /*Post: The function returns true or false according to whether the List is empty or not.*/
    • void clear( );
      /*Post: All List entries have been removed; the List is empty.*/
    • void traverse(void (*visit)(List_entry &));
      /* Post: The action specied by function (*visit) has been performed on every entry of the List, beginning at position 0and doing each in turn. */
    • Error_code retrieve(int position, List_entry &x) const;
      /*Post: If 0 <= position < n, where n is the number of entries in the List, the function succeeds: The entry at position is copied to x; all List entries remain unchanged. Else: The function fails with a diagnostic error code.*/
    • Error_code replace(int position, const List_entry &x);
      /*Post: If 0 <= position < n, where n is the number of entries in the List, the function succeeds: The entry at position is replaced by x; all other entries remain unchanged. Else: The function fails with a diagnostic error code. */
    • Error_code remove(int position, List_entry &x);
      /*Post: If 0 <= position < n, where n is the number of entries in the List, the function succeeds: The entry at position is removed from the List, and all later entries have their position numbers decreased by 1. The parameter x records a copy of the entry formerly at position. Else: The function fails with a diagnostic error code.*/
    • Error_code insert(int position, const List_entry &x);
      /* Post: If the List is not full and 0 <= position <= n, where n is the number of entries in the List, the function succeeds: Any entry formerly at position and all later entries have their position numbers increased by 1 and x is inserted at position of the List. Else: The function fails with a diagnostic error code. */

    To start this assignment, copy the files for this assignment which can be found in:

      ~csci132/assignments/assign6

    The files that you need for this problem are:

      list.cc
      list.h
      list_functions.cc
    The above functions have all been supplied for you in the file, list.cc. Use the public functions of the list class to write new functions. In the copied file, list_functions.cc you will find five function stubs you need to complete. In doing so you must use the List class member functions. You may not change any other code other than filling in these five function stubs. The five functions are:

    • Error_code interchange(int pos1, int pos2, List &a_list)
      /* Post: Any entries at positions pos1 and pos2 of List a_list are interchanged. If either entry is missing a code of range_error is returned. */
    • void reverse_traverse_list(List &a_list, void (*visit)(List_entry &))
      /* Post: The List a_list is traversed, in reverse order, and the function *visit is applied to all entries. */
    • Error_code join(List &list1, List &list2)
      /* Post: All entries from list1 are copied onto the end of list2. A code of overflow is returned if list2 is filled up before the copying is complete. */
    • Error_code reverse(List &a_list)
      /* Post: Reverses the order of all entries in a_list. A code of fail is returned in case the reversal cannot be completed. */
    • Error_code split(List &source, List &oddlist, List &evenlist)
      /* Post: Copies all entries from source so that those in odd-numbered positions make up oddlist and those in even-numbered positions make up evenlist. Returns an error code of overflow in case either output list fills before the copy is complete. */

    Fill in the function stubs so they fullfil the stated post conditions. You must compile your code using:

      g++ -g -Wall list_functions.cc -o list_functions

    When all the functions are written correctly, the output of the main program (provided for you) will be as follows:
    Sample output: 

      radius% ./list_functions
Creating list. 
0 1 2 3 4 5 6 7 8 9 

Interchanging positions 2 and 3 of list. 
0 1 3 2 4 5 6 7 8 9 

Switching positions 2 and 3 back to original positions. 
0 1 2 3 4 5 6 7 8 9 

Printing list in reverse. 
9 8 7 6 5 4 3 2 1 0 

Splitting list into odds and evens. 
Printing odd list. 
1 3 5 7 9 

Printing even list. 
0 2 4 6 8 

Joining odd and even lists.
0 2 4 6 8 1 3 5 7 9 

Reversing list. 
9 7 5 3 1 8 6 4 2 0 
radius%

    When you are finished, submit electronicly using the submit program. Turn in a hard copy of the list_functions.cc file.

    What to turn in:

    • Turn in a hard copy of the file:
        list_functions.cc

      Make sure you include a file prologue with your name, class, the date, and the assignment number, along with a description of the file contents and their purpose. Also include appropriate comments for each of the functions you implement (with proper pre and post conditions).
    • Turn in discussion log
    • Submit the soft copy of your program using the command:
      ~csci132/bin/submit csci132 assign6

    Home | | Syllabus | | Assignments | | Lecture Notes


    Computer Science 132--Data Structures
    Last Modified: March 21, 2014
    Page Expires: January 14, 2015