CMIS 240 DE Week 3 Study the first half of chapter 3, about unsorted and sorted lists classes and binary search. A list is an abstract data type that is a sequence of items. Sequence implies that each list item has an item before it and after it in the list (except for the first and last elements). The number of items in the list is the list's length or size. A partially filled array (i.e. filled from the beginning) is a kind of list, but a list is not an array. A list can be implemented with an array (it could also be implemented with a linked data structure [chapter 5]). The list classes in this chapter are generic lists, meaning that the item type is generic and could be any actual type. You could have a list of ints as easily as a list of some complicated struct type, only a few changes need to be made in the ItemType class. In Chapter 4 we'll learn how templates can completely genericize a class, so that without any change to the class definition, you can declare a list of ints just as easily as a list of some struct type. Having the ItemType class confuses the issue but it's to start us on the road to "generic" data structures, classes whose instances can be used to hold values of different types. If you have a completely generic class (we won't see this until we learn about templates), then different objects of that class can be different types of data. For example, from a single (templated) SortedType class, you could declare a sorted list of ints object, another SortedType object of strings, another of DateTypes; the SortedType class is generic. It seems like a lot of unneccesary work to convert an int to an ItemType. But UnsortedType and SortedType have been partially genericized by being a list of ItemType, since ItemType can easily be changed to any type. Templates will allow us to eliminate the "ItemType" kind of class and directly have SortedType objects of any type. I've taken the online code and made a main driver for the UnsortedType list. It's the 5 files: unsorteddr.cpp UnsortedType.cpp UnsortedType.h ItemType.cpp ItemType.h all in Chapter3/ directory, along with a Makefile. Download and get it working. Read the code along with the textbook's explanation of how the member functions work. A list that's not in any order can not be efficiently searched. Basically you have to look at all the items until either you find what you're looking for or you get to the end of the list. With small lists the time it takes is irrelevant, but many applications have huge lists. Say you've got one million items, and they need to be searched one thousand times every second. The searching is going to take up a lot of CPU time, whatever the mega/giga hertz. However, if the list is in order, and it's stored in an array (i.e. the list is implemented with an array), you can take advantage of the power of array indexing to search very efficiently. Because arrays are laid out sequentially in memory, element access via an index is just a simple memory address calculation, as we saw in chapter 2. Thus any element of an array can be accessed in the same time as any other. You're not limited to sequential access, you can access the elements in any order or pattern. The binary search repeatedly ("recursively" as we'll see in chapter 7) accesses the middle element of subarrays that are half the size of the subarray just previously looked at. This allows searching in essentially no time at all. Next week we'll look at the topic of algorithmic efficiency; for now, just learn how binary search works. The homework has you implement it. -------------------------------------------------- What's with the #ifndef ITEMTYPE in Itemtype.h? "multiple definition" error can be caused by a header file being incorporated more than once in a program. If f1.cpp includes h1.h and f2.cpp includes h1.h, then the stuff in h1.h will be multiply defined, causing error. To prevent this, you use these preprocessor directives: #ifndef XXXX #define XXXX at the top of each header file. . conventionally, XXXX will be the name of the header . file in all caps. . #endif at the bottom of the file. Example: in ItemType.h: #ifndef ITEMTYPE #define ITEMTYPE ... #endif in UnsortedType.h: #ifndef UNSORTEDTYPE #define UNSORTEDTYPE ... #endif Compiler compiles each source .cpp file separately. Linker resolves external references and links the pieces together. Any global thing can only be declared once. It's the linking that discovers multiple definitions. The files being linked don't have to be in the same directory. They don't have to be compiled at the same time (e.g. every program you run uses the iostream code that was compiled a long time ago). Linker would have no idea what .h files were included in those compilations. ----------------------------------------------------------------------- Homework Due: 23 Feb. Using the unsorted list class files as your base, implement the SortedType list class. Basically, you just have to implement the DeleteItem, InsertItem, and RetrieveItem member functions of SortedType class. These functions are defined in the book. Use binary search for the RetrieveItem function. Allow multiple duplicate values to be in the list. Allow the delete operation to not require that the item to be deleted be in the list. Itemtype.h and Itemtype.cpp don't need any changes. The only changes in the driver program is to include "SortedType.h" instead of "UnsortedType.h" and to declare list1 to be of type SortedType instead of UnsortedType. The file's name should be sorteddr.cpp. The only change in the sorted list class's specification file (the .h file) is that the name of the class should be SortedType instead of UnsortedType. The file's name should be SortedType.h. So you only have to make significant changes to one file: the list class implementation file. Change its name to SortedType.cpp Post the SortedType.cpp to Tycho. I will use my copies of Itemtype.h, ItempType.cpp, SortedType.h, and sorteddr.cpp. They will be as just described.