CSCI 262 Data Structures--Spring 2004
Assignment 6
Due at the beginning of class, Friday, March 26, 2004
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:
~csci262/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.
In this problem you will use the public functions of the list class to write
new functions. In the file, list_functions.cc (which you copied from the
assign6 folder in the ~csci262/assignments directory) you will find 5 function
stubs that you should fill in using the List class functions. You may not change
any other code other than the code for these 5 function stubs. The 5 functions
you should write are as follows:
- 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 that they fullfil the given post conditions. You may 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 (which is
provided for you) will be as follows:
Sample output:
mathcs% 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
mathcs%
When you are done, submit the softcopies of your files 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:
Make sure you include a
file prologue with your name, class, lecture section, 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).
- Submit the soft copy of your program using the command:
~csci262/bin/submit csci262 assign6
Home | | Syllabus | |
Assignments | |
Lecture Notes
Constance Royden--croyden@mathcs.holycross.edu
Computer Science 262--Data Structures
Date Created: March 22, 2002
Last Modified: March 8, 2004
Page Expires: January 14, 2005