Programming in c++ Applied Arrays: Lists and Strings Dale/eems/Headington
1 Applied Arrays: Lists and Strings
Programming in C++ Chapter 13 Topics Meaning of a List Insertion and Deletion of List Elements Selection Sort of List Elements Insertion and Deletion using a Sorted List Binary Search in a Sorted List Order of Magnitude of a Function o Declaring and Using C Strings s Using typedef with Arrays
2 Chapter 13 Topics ❖Meaning of a List ❖Insertion and Deletion of List Elements ❖Selection Sort of List Elements ❖Insertion and Deletion using a Sorted List ❖Binary Search in a Sorted List ❖Order of Magnitude of a Function ❖Declaring and Using C Strings ❖Using typedef with Arrays
Programming in C++ What is a List? A list is a variable-length, linear collection of homogeneous elements linear means each list element(except the first) has a unique predecessor, and each element(except the last) has a unique successor
3 What is a List? ❖A list is a variable-length, linear collection of homogeneous elements. ❖linear means each list element (except the first) has a unique predecessor, and each element (except the last) has a unique successor
Programming in C++ 3 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 8 Observer - allows us to observe the state of one or more of the data values of an instance without changing them
4 3 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
Programming in C++ ADT List Operations Transformers Insert change state Delete Selsort Observers Is Empty IsFull observe state Length .Is Present . Print 5
5 ADT List Operations Transformers • Insert • Delete • SelSort Observers • IsEmpty • IsFull • Length • IsPresent • Print change state observe state
Programming in C++ ADT Unsorted List Data Components lengt number of elements in list data[ 0.. MAX_ LENGTH-11 array of list elements 6
6 ADT Unsorted List Data Components length data[ 0 . . MAX_LENGTH -1 ] number of elements in list array of list elements
Programming in C++ Array-based class List Is Empty Is Full Private data: length Length data Insert Delete Is Present [ MAX_ LENGTH-11 Selsort Print
7 Array-based class List IsFull Length SelSort IsPresent Delete IsEmpty Insert Print Private data: length data [ 0 ] [ 1 ] [ 2 ] [MAX_LENGTH-1]
Programming in C++ SPECIFICATION FILE ARRAY-BASED LIST (list. h const int MAX LENGTH= 50 typedef int Item Type class List // declares a class data type public: public member functions List( ∥ constructor bool IsEmpty( const boo sfUll const int Length(const l/returns length of list void Insert( Item Type item); void Delete( Item Type item); boo IsPresent( Item Type item)const; void SelSort(: void Print() private: ∥ private data members length //number of values currently stored Item Type data[MAX LENGTH; 8
8 // SPECIFICATION FILE ARRAY-BASED LIST ( list.h ) const int MAX_LENGTH = 50 ; typedef int ItemType ; class List // declares a class data type { public : // public member functions List ( ) ; // constructor bool IsEmpty ( ) const ; bool IsFull ( ) const ; int Length ( ) const ; // returns length of list void Insert ( ItemType item ) ; void Delete ( ItemType item ) ; bool IsPresent( ItemType item ) const ; void SelSort ( ); void Print ( ) ; private : // private data members int length ; // number of values currently stored ItemType data[MAX_LENGTH] ; } ;
Programming in C++ IIMPLEMENTATION FILE ARRAY-BASED LIST (list. cpp) include list. h include using namespace std; int List: Length(const //Post: Function value = length return length bool List: IsFull( const l/ Post: Function value = true. if list = MAX LENGTH false. otherwise return( length = MAX LENGTH) 9
9 // IMPLEMENTATION FILE ARRAY-BASED LIST ( list.cpp ) #include “list.h” #include using namespace std; int List :: Length ( ) const // Post: Function value == length { return length ; } bool List :: IsFull ( ) const // Post: Function value == true, if list == MAX_LENGTH // == false, otherwise { return ( length == MAX_LENGTH ) ; }
Programming in C++ List :: List() ∥ Constructor ∥Post: length==0 length =0; void List: Insert(/*in */Item Type item / Pre: length MAX LENGTH & item is assigned //Post: datallength @entry== item & length ==length @entry 1 data length1= item length++; 10
10 List :: List ( ) // Constructor // Post: length == 0 { length = 0 ; } void List :: Insert ( /* in */ ItemType item ) // Pre: length < MAX_LENGTH && item is assigned // Post: data[length@entry] == item && length == length@entry + 1 { data [ length ] = item ; length++ ; }