2008级计算机 内部资料,仅供课堂教学使用 Chapter 7 Searching P 268 1. Introduction. Notation 3. Binary Search 2. Sequential Search 4. Asymptotics: The Big-O and Other Notations 17.1 Introduction, Notation Records and Keys P. 269 We are given a list of records, where each record is associated with one piece of information, which we shall call a key We are given one key, called the target, and are asked to search the list to find the record(s)(if any) whose key is the same as the target. There may be more than one record with the same key, or there may be no record with a given key We often ask how times one key is compared with another during a search. This gives us a good measure of the total amount of work that the algorithm will do Internal searching means that all the records are kept in high-speed memory. In external searching, most of the records are kept in disk files. We study only internal searching or now consider only contiguous lists of records. We shall consider linked structures in Chapter 10 Records and Keys in C++ P 270 cong the records(from a class Record) that are stored in the list being searched(generally called the list)must confor m to the following minimal standards Every Record is associated to a key (of a type or class called Key) There is a conversion operation to turn any Record into its associated Aey ,< Key objects can be compared with the standard operators Record objects can be compared to each other or to a Key by first converting the record objects to thei sociated keys Examples of the conversion operation A method of the class Record, with the declaration operator )const If the classes Key and Record are identical, no conversion needs to be defined, since any Record autom atically a Key o We do not assume that a Record has a Key object as a data member, although often it does. We merely assume that the compiler can turn a Record into its corresponding Key Key Definition in C++ P 270-271 Parameters for Search Functions P. 271 Each searching function has two input parameters First is the list to be searched Second is the target key for which we are searching Each searching function will also have an output parameter and a returned value The returned value has type Error code and indicates whether or not the search is successful in finding an entry with the target key o If the search is successful, then the returned value is success, and the output parameter called position will locate the target within the list If the search is unsuccessful, then the value not present is re-turned, and the output parameter may have an undefined value or a value that will differ from one method to another 7.2 Sequential Search Sequential Search and Analysis P 272 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 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: I comparison Successful search, worst case: n comparisons Successful search, average case: (n+ 1)/2 comparisons Testing Pre P.274 e 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 C++, static class members provide data objects that are shared by every instance of the clas member.In is counter must be available to all Key objects: Thus, it should be declared as a static class The definition of the class Key P. 2742008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 7 Searching P.268 ----------------------------------------------------------------------------------------------------------------------------- ----- 1. Introduction, Notation 2. Sequential Search 3. Binary Search 4. Asymptotics: The Big-O and Other Notations [7.1] Introduction, Notation Records and Keys P. 269 ⚫ We are given a list of records, where each record is associated with one piece of information, which we shall call a key. ⚫ We are given one key, called the target, and are asked to search the list to find the record(s) (if any) whose key is the same as the target. ⚫ There may be more than one record with the same key, or there may be no record with a given key. ⚫ We often ask how times one key is compared with another during a search. This gives us a good measure of the total amount of work that the algorithm will do. ⚫ Internal searching means that all the records are kept in high-speed memory. In external searching, most of the records are kept in disk files. We study only internal searching. ⚫ For now, we consider only contiguous lists of records. We shall consider linked structures in Chapter 10. Records and Keys in C++ P. 270 The records (from a class Record) that are stored in the list being searched (generally called the list) must conform to the following minimal standards: ⚫ Every Record is associated to a key (of a type or class called Key). ⚫ Key objects can be compared with the standard operators: == , != , <, >, <= , >= . ⚫ There is a conversion operation to turn any Record into its associated Key. ⚫ Record objects can be compared to each other or to a Key by first converting the Record objects to their associated keys. ⚫ Examples of the conversion operation: ◼ A method of the class Record, with the declaration operator Key( ) const; ◼ A constructor for the class Key, with declaration Key(const Record &); ◼ If the classes Key and Record are identical, no conversion needs to be defined, since any Record is automatically a Key. ⚫ We do not assume that a Record has a Key object as a data member, although often it does. We merely assume that the compiler can turn a Record into its corresponding Key. Key Definition in C++ P. 270-271 Parameters for Search Functions P. 271 Each searching function has two input parameters: ⚫ First is the list to be searched; ⚫ Second is the target key for which we are searching. Each searching function will also have an output parameter and a returned value: ⚫ The returned value has type Error code and indicate s whether or not the search is successful in finding an entry with the target key. ⚫ If the search is successful, then the returned value is success, and the output parameter called position will locate the target within the list. ⚫ If the search is unsucce ssful, then the value not present is re- turned, and the output parameter may have an undefined value or a value that will differ from one method to another. [7.2] Sequential Search Sequential Search and Analysis P. 272 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. 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: (n + 1)/2 comparisons. Testing Program P. 274 ⚫ 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 definition of the class Key P. 274