Lab Assignment #1

Due Wednesday, July 8 at the beginning of class

The assignment tests your knowledge of searching, sorting, and manipulating lists (implemented as arrays) in C++. You will implement several functions as specified below.

   Function 	               Description

void ReadData(...)        Reads integers from a text file.
void LinearSearch(...)    Searches sequentially for an item in an unsorted list.
void Sort(...)            Sorts a list of items using the selection sort.
void LinearSearchOrd(...) Searches sequentially for an item in a sorted list.
void BinarySearch(...)    Uses a binary search method to find an item in a sorted list.
void DeleteOne(...)       Deletes one occurrence of an item from an unsorted list.
void DeleteAll(...)       Deletes all occurrences of an item from an unsorted list.

The exact specifications for these functions are in a file called search.h, which you can get from my home directory on PCC's AIX system. (/home/inst/mmead/) It is posted on the class web pages as well. It is very important that you implement these functions exactly as they are specified. There is also a driver module called driver1.cpp that you may use to help you test your program. (You may want to get numbers.dat and numbers2.dat if you don't want to create your own.) This driver does not test every possible case, but it is a starting point. You are responsible for making sure that your program works in all cases. I will be using a modified version of this driver to test your functions. The driver code is also in my home directory and posted on the web page. The page is at www.pacifier.com/~mmead/cs162/outline.html

Details

Name your implementation file search.cpp. Any other name will cause the test programs to fail. You will have to include "search.h" in this file.
Do not put a main() function in search.cpp; it is implemented in driver1.cpp
Don't sort the numbers as you read them from the file, just store them in the array in the order that they are read in.
Your implementation of Sort(. . .) must use the selection sort algorithm that we discussed in class.
The functions DeleteOne(. . .) and DeleteAll(. . .) must not create a separate array. In other words, you must remove the appropriate item and then "collapse" the array to fill in the space created by removing the item(s).
You must test your functions thoroughly. The driver program that is available is not exhaustive. I will be using a different version of the driver that will test your functions more thoroughly. Many students lose points because they didn't test their programs well enough. The only compiler I will use to test these is the compiler on PCC's AIX system. If you don't test your programs on that system, you may not find the same mistakes that I do.
Submit only the search.cpp file.

To compile the files on the AIX system into an executable called lab1 you can use this on the command line:

xlC -o lab1 driver1.cpp search.cpp

If you are not using the Unix system at PCC, you will have to find out how to compile your programs on the machine you are using. As in all programs you write, you should use meaningful identifier names, and the code must be well commented and consistently formatted. Your functions must have appropriate declarations and detailed header comments must explain the purpose of the function, and describe any inputs and/or outputs. Variables should be declared local to the function they are used in. No global variables are allowed, although global constants are permitted.

How to submit your programs

Back to Outline