ADTs Unsorted List and Sorted List

1 3 ADTsUnsorted List and Sorted List2 List DefinitionsLinear relationshipEach element except the first has a unique predecessor, and each element except the last has a unique number of items in a list; the length can vary over DefinitionsUnsorted listA list in which data items are placed in no particular order; the only relationship between data elements is the list predecessor and successor listA list that is Sorted by the value in the key; there is a semantic relationship among the keys of the items in the attributes that are used to determine the logical order of the Data Type (ADT) A data type whose properties (domain and operations)are specified independently of any particular implementation.

2 5 Data from 3 different levels Application (or user) level:modeling real-life data in a specific context. Logical (or ADT) level:abstract view of the domain and operations. WHAT Implementation level:specific representation of the structure to hold the data items, and the coding for operations. HOW4 Basic Kinds of ADT Operations Constructor--creates a new instance (object) of an ADT. Transformer--changes the state of one or more of the data values of an instance. Observer--allows us to observe the state of one or more of the data values of an instance without changing them. Iterator--allows us to process all the components in a data structure and Unsorted ListsUNSORTED LISTE lements are placed into the list in no particular LISTList elements are in an order that is Sorted in some way --either numerically or alphabetically by the elements themselves, or by a component of the element (called aKEY member).

3 ADT Unsorted List OperationsTransformers MakeEmpty InsertItem DeleteItemObservers IsFull LengthIs RetrieveItemIterators ResetList GetNextItemchange stateobserve stateprocess all 89 What is a Generic Data Type?A generic data typeis a type for which the operations are defined but the types of the items being manipulated are not way to simulate such a type for our UnsortedListADT is via a user-defined class ItemTypewith member function ComparedToreturning an enumerated type value LESS, GREATER, or EQUAL. // SPECIFICATION FILE( )#include class UnsortedType// declares a class data type{public : // 8 public member functionsvoid UnsortedType() ;boolIsFull( ) const ; intLengthIs( ) const; // returns length of listvoid RetrieveItem( ItemType&item, bool void InsertItem( ItemTypeitem ) ; void DeleteItem( ItemTypeitem ) ; void ResetList( );void GetNextItem( ItemType private :// 3 private data membersintlength ; ItemTypeinfo[MAX_ITEMS] ; intcurrentPos;}.))

4 1011 Class Constructor A special member function of a class that is implicitly invokedwhen a class object is Constructor Rules1A constructor cannot return a function value, and has no return value type. 2A class may have several constructors. The compiler chooses the appropriate constructor by the number and types of parameters parameters are placed in a parameter list in the declaration of the class parameterlessconstructor is the default constructor. 5If a class has at least one constructor, and an array of class objects is declared, then one of the constructors must be the default constructor, which is invoked for each element in the Interface DiagramUnsortedTypeclassIsFullLengthIs ResetListDeleteItemInsertItemUnsortedTyp eRetrieveItemGetNextItemPrivate data:lengthinfo [ 0 ][ 1 ][ 2 ][MAX_ITEMS-1]currentPos// IMPLEMENTATION FILE ARRAY-BASED LIST ( )#include void UnsortedType::UnsortedType( ) // Pre: Post: List is empty.

5 { length = 0 ;}void UnsortedType::InsertItem( ItemTypeitem )// Pre: List has been initialized. List is not full. // item is not in Post: item is in the list.{info[length] = item ;length++ ;}14 Before Inserting Hsinginto anUnsorted Listlength3info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] ..[MAX_ITEMS-1]The item willbe placed intothe length location,and length will Inserting Hsinginto anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]16intUnsortedType::LengthIs ( ) const// Pre: List has been Post: Function value == ( number of elements in// list ).{ return length ;}boolUnsortedType::IsFull( ) const// Pre: List has been Post: Function value == ( list is full ).

6 {return ( length == MAX_ITEMS ) ;}17void UnsortedType::RetrieveItem( ItemType& item, bool& found ) // Pre: Key member of item is Post: If found, item s key matches an element s key in the list// and a copy of that element has been stored in item; // otherwise, item is unchanged.{ boolmoreToSearch;intlocation = 0 ;found = false ;moreToSearch= ( location < length ) ;while ( moreToSearch&& !found ){ switch ( ( info[location] ) ){ case LESS :case GREATER : location++ ;moreToSearch= ( location < length ) ;case EQUAL : found = true ;item = info[ location ] ;break ;}}}18 Retrieving Ivan from anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]moreToSearch: truefound:falselocation: 0 19 Retrieving Ivan from anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]moreToSearch: truefound:falselocation: 1 20 Retrieving Ivan from anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]moreToSearch: truefound:falselocation: 2 21 Retrieving Ivan from anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]moreToSearch: truefound.

7 Falselocation: 3 22 Retrieving Ivan from anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]moreToSearch: falsefound:falselocation: 4 23void UnsortedType::DeleteItem( ItemTypeitem ) // Pre: item s key has been element in the list has a key that matches item Post: No element in the list has a key that matches item s.{ intlocation = 0 ;while ( (info [location] ) != EQUAL )location++;// move last element into position where item was locatedinfo [location] = info [length -1 ] ;length--;}24 Deleting Bradley from anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]location: 0 Key Bradley hasnot been Bradley from anUnsorted Listlength4info [ 0 ] Maxwell[ 1 ] Bradley[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]location: 1 Key Bradley hasbeen Bradley from anUnsorted Listlocation: 1 length4info [ 0 ] Maxwell[ 1 ] Hsing[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]Placed copy oflast list elementinto the position where the key Bradley was Bradley from anUnsorted Listlength3info [ 0 ] Maxwell[ 1 ] Hsing[ 2 ] Asad[ 3 ] [MAX_ITEMS-1]location.

8 1 Decremented UnsortedType::ResetList( ) // Pre: List has been Post: Current position is prior to first element in list.{ currentPos= -1 ;}void UnsortedType::GetNextItem( ItemType& item ) // Pre: List has been initialized. Current position is at current position is not last in Post: Current position is updated to next item is a copy of element at current position.{currentPos++ ;item = info [currentPos] ;}2930 Specifying class ItemType// SPECIFICATION FILE( )const intMAX_ITEM = 5 ;enumRelationType{ LESS, EQUAL, GREATER } ;class ItemType// declares class data type{public : // 3 public member functionsRelationTypeComparedTo( ItemType) const ;voidPrint ( ) const;voidInitialize ( intnumber ) ; private :// 1 private data memberintvalue ; // could be any different type} ;// IMPLEMENTATION FILE( )// Implementation depends on the data type of value.

9 #include #include <iostream>RelationTypeComparedTo( ItemTypeotherItem) const{if ( value < )return LESS ;else if ( value > )return GREATER ;else return EQUAL ;}void Print ( ) const{using namespace std;cout<< value << endl;}void Initialize ( intnumber ){value = number ;} 32 ItemTypeClass Interface DiagramPrivate datavalue ComparedToPrintInitializeclass ItemType33 Sorted Type Class Interface DiagramSortedTypeclassIsFullLengthIs ResetListDeleteItemInsertItemMakeEmptyRe trieveItemPrivate data:lengthinfo [ 0 ][ 1 ][ 2 ][MAX_ITEMS-1]currentPosGetNextItem34 Member functions Which member function specifications and implementations must change to ensure that any instance of the Sorted List ADT remains Sorted at all times?

10 InsertItem DeleteItemInsertItemalgorithm forSortedListADT Find proper location for the new element in the Sorted list. Create space for the new element by moving downall the list elements that will follow it. Put the new element in the list. Increment SortedTypemember function InsertItem// IMPLEMENTATION FILE ( )#include // also must appear in client codevoid SortedType:: InsertItem( ItemType item )// Pre: List has been initialized. List is not full. // item is not in List is Sorted by key member using function Post: item is in the list. List is still Sorted .{..}void SortedType:: InsertItem( ItemTypeitem ){ boolmoreToSearch;intlocation = 0 ;// find proper location for new elementmoreToSearch= ( location < length ) ;while ( moreToSearch){switch ( ( info[location] ) ){ case LESS : moreToSearch= false ;break ;case GREATER : location++ ;moreToSearch= ( location < length ) ;break ;}}// make room for new element in Sorted listfor ( intindex = length ; index > location ; index--)info [ index ] = info [ index -1 ] ;info [ location ] = item ;length++ ;}38 DeleteItemalgorithm for SortedListADT Find the location of the element to be deleted from the Sorted list.