"From a theoretical point of view, a list is a homogeneous collection
of elements, with a linear relationship between elements.
Linear means that, at the logical level, each element in the list except
the first one has a unique predecessor, and each element except the last one
has a unique successor."
(C++ Plus Data Structures, page 196)
To summarize, a list has one element before it, and one element after it. With the exception of the first and last elements.
There are two different kinds of list:
This lab focuses on the unsorted list, based on an array implementation.
A list whether sorted or unsorted should have a set of general purpose operations. These operations are listed in Section 1.2.
Note: The last five functions (gotoBeginning(), gotoEnd(), gotoNext(), gotoPrior(), and getCursor()) are relevant to the cursor. They allow you to iterate through the entire list--processing it item by item. This gives the user access to each item in sequence.
operations | representation | comments |
---|---|---|
testList.insert('a'); testList.insert('b'); testList.insert('r'); testList.insert('p'); |
Notice, the cursor is positioned at the last item added, and the list is not in alphabetical order (it is unsorted). | |
testList.replace('c'); | Notice that the cursor is at 3 and the 'p' (previously at index 3) has been replaced by 'c'. | |
testList.insert('u'); | The 'u' is added to the end. The size and cursor are incremented. | |
|
The cursor has been moved to the beginning (with gotoBeginning). Now, notice that since the cursor is at 0, the 'a' is removed. All the other elements are shifted "up" the array. | |
testList.gotoNext(); testList.insert('y'); | With gotoNext(), the cursor moves to position 1 ('r'), Then the insert occurs after the cursor position. The cursor then points at 'y'. |
To cycle through the list and print each item, we can make use of the cursor as an iterator. To do this we use a while statement and use the getCursor() function to get the data at the present cursor position. The code will look like this:
testList.gotoBeginning(); cout << testList.getCursor() << endl; while (testList.gotoNext()) { cout << testList.getCursor() << endl; }
In Section 1.3, we demonstrated the use of the insert, replace, remove and a few of the cursor operations (getCursor(), gotoNext(), gotoBeginning()).
Another function that we might need is a find function. This operation searches a list for a specified data item. The search begins with the data item marked by the cursor (not at the beginning of the list). This is an advantage because find can be applied iteratively to locate all of the occurences of a specified data item.
The prototype will look something like this:bool find ( const DataType &searchDataItem ) throw ( logic_error )The function will search through a list for searchDataItem. It begins the search with the data item marked by the cursor. It moves the cursor through the list until either searchDataItem is found (returns true) or the end of the list is reached without finding searchDataItem (returns false).
Note: It leaves the cursor at the last data item visited during the search.
First, let's describe some of details of the program. You won't need to change any of these components (unless we specify that you do), but they are good things to know for comprehending this and future code.
if ( size >= maxSize ) throw logic_error("list is full\n");Don't worry too much about it right now, it will be discussed in a later lab. Recognize for now, that this is part of an exception handling mechanism. For instance, in the above code segment (from the insert function), it checks to make sure that you are not going over the bounds of your array size. If you try to go over the maximum size, this statement will "throw an exception" indicating that your list is full. In the main program (test3.cpp), there are some try and catch statements to deal with this thrown exception.
typedef char DataTypeThis makes DataType a type that is synonymous with char, and can be used in declarations just as other types are used. For instance,
DataType mychar;Declares a variable, called mychar, of type DataType (really char).
DataType mylist[100]This sets the array to have a length of 100. This means that for the entire program, our array (or list) will always have 100 elements. What if we want some lists to have 100 and some lists to have 50? Then, we can dynamically-allocate memory. We can do this using List's constructor, and the new operator. The constructor is invoked whenever a list declaration is encountered during the execution of a program. For instance let's look at a segment of List's constructor:
List:: List ( int maxNumber ) { . . . dataItems = new DataType[maxSize]; }This allocates an array of maxSize data items and assigns the address of the array to the pointer dataItems, where dataItems is of type DataType *. Whenever you allocate memory, you must ensure that it is deallocated when it is no longer needed. You can use the destructor to deallocate memory stored in the array. The destructor is automatically invoked whenever a list is destroyed. The destructor outlined below frees the memory used by the array that you allocated above.
List:: ~List () { delete [] dataItems; }Now, when you declare a list, you can specify the size in parenthesis. For instance, a list of eight elements would be declared in the following way:
List testList(8);
cout << endl <<"Not finished yet but..."; system("pause");When you try the program, you will notice that it prints:
Not finished yet but...Press any key to continue . . .The Press any key to continue . . . is generated through the call to pause. Without getting into details, it "pauses" the main routine at the current location and waits for keyboard input. After it gets keyboard input, it will continue executing the remaining code in "main". If you have time, you can try commenting these lines out or add additional ones to see what happens.
Click here To get the zipped files for this exercise
Your primary tasks for this exercise are to edit the listarr.cpp
and test3.cpp files to add in lines so that it does the following:
Steps include:
*****Printing List to Start with***** Empty list *****Trying 4 insert statements****** size = 4 cursor = 3 0 1 2 3 4 5 6 7 a b r p *****Replacing 'b' with 'c'***** size = 4 cursor = 1 0 1 2 3 4 5 6 7 a c r p *****Adding a 'u' to the end***** size = 5 cursor = 4 0 1 2 3 4 5 6 7 a c r p u Not finished yet but...Press any key to continue . . . *****Removing the second last character***** size = 4 cursor = 3 0 1 2 3 4 5 6 7 a c r u *****Inserting 'y' after the second character***** size = 5 cursor = 2 0 1 2 3 4 5 6 7 a c y r u *****Printing using cursor***** acyru *****Clearing the list***** Empty list *****Testing the find***** Press any key to continue
The output might look something like this:
*****Testing the find***** found a at position 0 found a at position 4 found b at position 1 didn't find b the cursor is 4 found c at position 2 found c at position 3 Press any key to continue
Test plan:
Test Case | Commands | Expected Result | Checked |
---|---|---|---|
Set up list |
testList.insert('a'); testList.insert('b'); testList.insert('c'); testList.insert('c'); testList.insert('a'); |
a b c c a | |
Successful Search |
testList.gotoBeginning(); testList.find('a'); |
returns true; a b c c a |
|
Search for duplicate |
testList.gotoNext(); testList.find('a'); |
returns true; a b c c a |
|
Successful Search |
testList.gotoBeginning(); testList.find('b'); |
returns true; a b c c a |
|
Search for duplicate |
testList.gotoNext(); testList.find('b'); |
returns false; a b c c a |
|
Successful Search |
testList.gotoBeginning(); testList.find('c'); |
returns true; a b c c a |
|
Search for duplicate |
testList.gotoNext(); testList.find('c'); |
returns true; a b c c a |
Friday, 21-Aug-2020 15:22:17 CST |
|
|
|
|