Error code sequential search( List< Record>& the list const int &target, int &position) /* Post: If an entry in the list has key equal to target, then return success and the output parameter position locates such an entry within the list. Otherwise return not_present and position becomes invalid. * i for( position=0; position<the list size position++) i Record x the list. retrieve(position x); if(x==target return success return not_ present;//脱离for,则检索不成功
Error_code sequential_search( List<Record> & the_list, const int &target, int &position) /* Post: If an entry in the list has key equal to target, then return success and the output parameter position locates such an entry within the list. Otherwise return not_present and position becomes invalid. */ { for( position=0; position<the_list.size( ); position++) { Record x; the_list.retrieve(position, x); if(x==target) return success; } return not_present; // 脱离for,则检索不成功 }
To analyze the behavior of an algorithm that makes comparisons of keys, we shall use the count of these key comparisons as our measure of the work done 2. Analysis The number of comparisons of keys done in sequential search of a list of length n is Unsuccessful search: n comparisons Successful search best case: 1 comparison Q Successful search, worst case: n comparisons Successful search, average case: n+ comparisons
To analyze the behavior of an algorithm that makes comparisons of keys, we shall use the count of these key comparisons as our measure of the work done. 2. Analysis The number of comparisons of keys done in sequential search of a list of length n is ◆ Unsuccessful search: n comparisons. ◆Successful search, best case: 1 comparison. ◆Successful search, worst case: n comparisons. ◆Successful search, average case: comparisons. 2 n +1
3. Testing Program For test purposes, use integer keys and do not store any data other than a key in a record. accordingly, we define typedef Key record Keep a count of all key comparison operations by modifying the overloaded key comparison operations to increment a counter whenever they are called. This counter must be available to all Key objects Thus, it should be declared as a static class member. In C++, static class members provide data objects that are shared by every instance of the class
3. Testing Program ◆For test purposes, use integer keys, and do not store any data other than a key in a record. Accordingly, we define typedef Key Record; ◆Keep a count of all key comparison operations, by modifying the overloaded key comparison operations to increment a counter whenever they are called. ◆This counter must be available to all Key objects: Thus, it should be declared as a static class member. In C++, static class members provide data objects that are shared by every instance of the class
The method the key inspects a copy of a key s value. The static counter comparisons is incremented by any call to a Key comparison operator For example: bool operator==(const Key &x, const Key &y) i Key: comparisons++ return x. the key ()==y the key(); Static data members must be defined and initialized outside of a class definition. Accordingly, the following statement is included in the Key implementation file key.c: int Key comparisons =0; Use the class Timer from Appendix C to provide CPU timing information
◆The method the key inspects a copy of a key's value. ◆The static counter comparisons is incremented by any call to a Key comparison operator. For example: bool operator== (const Key &x, const Key &y) { Key::comparisons++; return x.the_key( ) == y.the_key( ); } ◆Static data members must be defined and initialized outside of a class definition. Accordingly, the following statement is included in the Key implementation file key.c: int Key :: comparisons = 0; ◆Use the class Timer from Appendix C to provide CPU timing information
Choice of test data Most later searching methods require the data to be ordered so use a list with integer keys in increasing order. To test both successful and unsuccessful searches insert only keys containing odd integers into the list. If n denotes the number of entries in the list, then the targets for successful searches will be 1,3,5,…,2n-1 Q For unsuccessful searches, the targets will be 0,246,…,2n In this way we test all possible failures, including targets less than the smallest key in the list, between each pair, and greater than the largest
Choice of test data ◆Most later searching methods require the data to be ordered, so use a list with integer keys in increasing order. ◆To test both successful and unsuccessful searches, insert only keys containing odd integers into the list. ◆If n denotes the number of entries in the list, then the targets for successful searches will be 1, 3, 5, …, 2n – 1 . ◆For unsuccessful searches, the targets will be 0, 2, 4, 6, …, 2n. ◆In this way we test all possible failures, including targets less than the smallest key in the list, between each pair, and greater than the largest