Data Structures and Algorithms I Lab 4

Data Structures and Algorithms I - Lab 4 - Completing A List ADT

Name _____________________________________ Section ________ Score ______________

Objectives

To practice implementing and using a simple ADT.

Background

Abstract Data Types are often implemented in C++ using classes. This allows the use of private and public member access specifiers to be used to control access to the members of the class. It also promotes information hiding through the use of a public interface. Classes allow operations to be grouped; encapsulation is achieved by placing the implementation in a separate file from the class definition.

Experimental Procedure/Analysis

Task 1

Open the Win32 Console Application called Lab03 created in the previous lab. We will be completing the implementation of the List ADT. Last time we finished the first three methods.

constructor - create an empty list
destructor - destroy a list
insert - add an item to a list at the current position
remove - delete the current item from the list
setPos - set the current position
next and prev - change the current position
currValue - the current item of the list
length - number of items in the list

Task 1a

Implement the length function in List.cpp. This is to return the number of items stored in the list (the current length of the list). For example, if the list is empty, it would return 0. This method is a type of "get method"; it returns an attribute of the list object.

Add std::cout statements to main that display the messages: "The length of localList is n" and "The length of globalList is n" (n should be the current length of each list). Do this immediately after localList is declared, and again just before main's final cout statement. Test your program. What are the list lengths at these two locations?

At start of main: localList's length is _________, globalList's length is ___________.

At end of main: localList's length is _________, globalList's length is ___________.

Can the length of the innerList be displayed at these same places in main? (Try it) If not, why. If so, what length is displayed each time?

Next, implement the setPos function. This is supposed to set currentPos to the value of the argument. Of course, you must not allow the current position to become illegal. current always represents an ordinal position (1 means first, 2 means second, etc.). In addition, if a list has 2 items, current must be 'first', second', or 'third'. The last case indicates that the 'end of the list' is the current position. If setPos is given an illegal argument, it is to ignore the request (do nothing). Build the project to be sure you have no syntax errors.

Run the program and record the list contents that are displayed after the list has been filled - this is the output from the call to the print method:

Add a statement to the body of the loop (in main), immediately after the call to insert, to set the position of List localList to the list's current length. Use the public method to determine the list's length. Write the statement you added here:

________________________________________________
Run the program and record the list contents that are displayed after the list has been filled. Give an explanation of why the results differ from what was displayed previously:

To examine the contents of a list from a client application, we need to implement the currValue function. Do so now. This function returns a copy of the current item in the list. The numItems and currentPos attributes should not be changed by this method. Of course, if the current position is at the 'end of list' position, there is nothing to return. This presents a serious problem to the programmer as the function requires a return value. Suggest a solution and incorporate it into your function.

My solution is:______________________________________________________________

_________________________________________________________________________

You should also implement the next and prev member functions. These are relatively straightforward and change only currentPos. Be sure to ignore requests that would make current illegal. A quick solution can be had by calling the setPos member function with the appropriate argument as it already does the range checking. Note that calling setPos will cause the upper and lower bounds of the position to be checked, whereas in next, only the upper limit needs to be validated (and in prev, the lower). This extra comparison and the overhead of an extra function call would mean that calling setPos would be a less efficient solution. Your solution should not call setPos.

We will be testing these methods in the next task.

Task 1b

To view a list's contents, we added a public method called print. Change its declaration in List.h to make it a private method. What compile error occurs after you make this change and attempt to rebuild the project?

When a container class (like List) has no public method to display the contents of the container, the client application may have to perform this task on its own. Add a function to the Driver.cpp module that will print the items in a list. The prototype is:

//display list contents as '[first, second, ..., last]'
void print(List & L);

Could you simply copy the statements from List::print() to define this function? After all, it does the same thing! Explain why this would not work.

Define the print function below main in driver.cpp. Start with this as the first statement in the function's body: L.setPos();

What is the current position after this statement is executed?_______(1, 2, 3, ...?)

You will need a loop and you should make use of the next member function inside the loop to move forward through the list. Loop control will depend on the length of the list. You must use the currValue function to access each item of the list. Print brackets around the list [...] and advance to a new line after the closing bracket.

Replace the uses of the print method by the function call: print(localList);
Test your program and record the list output:

___________________________________________________________________________

Add a statement to main to display the contents of globalList.

What statement did you add? ___________________________

Record the output from that statement here:

Task 1c

Implement the remove function. This will remove the current item (if there is one) from the list. Return a true if successful, otherwise return false. Under what condition will the remove operation fail? (your answer should be the C++ if statement used to check for this situation)

___________________________________________________________________________

Remember that the List's current location must remain valid at all times. Are there any situations where current would have to change to ensure it remains valid when an item is removed from a list? (This can be a descriptive answer)

___________________________________________________________________________

Add the statement localList.remove();immediately after localList is printed (after the loop that inserts 10 items into localList). Print localList again after the call to remove. Record the two outputs:

___________________________________________________________________________

If the list is unchanged, explain why. If they are different, tell which item was deleted (first, second, etc) and explain how this item became the current item.

Write a pair of statements that would remove the middle item of a list, localList. The middle item of a list with n items would be at position (n+1)/2.

_________________________________________________

Feel free to test this in your program - be sure to check it for lists of even and odd length.

Comment out irrelevant statements in main. We want to test the following code:

for (int i=1; i<=9; i++){
        globalList.insert(i);
        globalList.setPos(i/2);
}
print(globalList);

Run the program and record the output:

Move the print statement inside the loop; place it after the setPos call. Run the program and record the first three lists displayed and the last list displayed:

You should notice that the final list is different from the one recorded in the previous test, explain why the difference occurs!

Task 1d

In List.h, change the definition of ITEM_TYPE. We want to create a List of character strings, so the appropriate typedef is:

typedef char * ITEM_TYPE

In Driver.cpp, comment out main and replace it with this function:

main(){
        char * members[]={"Harold", "Fred", "Sally", 
                        "Gloria", "Paul", "Eve"};
        int pos[]={3, 1, 5, 2, 0, 6};
        List club;
        for (int i=0; i<sizeof(pos)/sizeof(int); i++){
                club.setPos(pos[i]);
                club.insert(members[i]);
        }
        print(club);
        return 0;
}

Correct any syntax errors, run the program, and record the list of names printed by the program.

___________________________________________________________________________

You're all done. Hand in this lab and your three printed files (stapled). Be sure your name appears in each file. Remember to clean up local hard disk storage.