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. 274
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 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
2008级计算机 据结构课堂教学笔记 内部资料,仅供课堂教学使用 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: P. 275 Static data members must be defined and initialized outside of a class definition. Accordingly, the follow statement is included in the Key implementation file key. c: int Key comparisons =0 e Use the class Timer from Appendix C to provide CPU timing information Most later searching methods require the data to be ordered, so use a list with integer keys in increasing 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 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 Random . random integer from Appendix Edom To make the test more realistic, use pseudo-random numbers to choose the target, by employing the method 17.3| Binary Search 7.3.1 Ordered Lists P. 278 DEFINITION: An ordered list is a list in which each entry contains a key, such that the keys are in order. That is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j. P. 278 All List operations except insert and replace apply without modification to an ordered list Methods insert and replace must fail when they would otherwise disturb the order of a list. We implement an ordered list as a class derived from a contiguous List. In this derived class, we shall override the methods insert and replace with new implementations. P. 279 Overloaded insertion: P. 279 Overridden insertion P 280 7.3.2 Binary Search P. 280 Idea: In searching an ordered list, first compare the target to the key in the center of the list. If it is smaller, restrict the search to the left half; otherwise restrict the search to the right half, and repeat. In this way,at each step we reduce the length of the list to be searched by half. Keep two indices, top and bottom, that will bracket the part of the list still to be searched The target key, provided it is present, will be found between the indices bottom and top, inclusive Initialization: Set bottom =0; top= the list size( )-1 Compare target with the Record at the midpoint, mid =(bottom+top)/2 Change the appropriate index top or bottom to restrict the search appropriate half of the list Loop terminates when topsbottom, if it has not terminated earlier by finding the target Make progress toward termination by ensuring that the number of items remaining to be searched top-bottom+l, strictly decreases at each iteration of the process 7.3.3 The Forgetful Version of Binary Search P. 281 Algorithm verification P 282 Nonrecursive Binary Search P. 283 7.3.4 Recognizing Equality in Binary Search P 284 Nonrecursive Version P 285 Algorithm Verification P. 285 7.4 Asy mptotics: The Big-O and Other Notations P 302 7.6.2 Orders of Magnitude P. 304 Assumptions P 305 Orders of Magnitude of Common Functions Polynomials P. 306 ogarithms P 307 L HOpital's Rule P 307 Exponential functions P. 308 The function n log n: The function n log n has strictly greater order of magnitude than n but strictly smaller order of magnitude than any power n' for any r>l Growth Rates of Common Orders P 309-310 7.6.3 The Big-O and Related Notations P. 310 Examples: P. 311 Algorithm Analyses P. 311 7.6.4 Keeping the dominant term: P 311 We define f (n)=g(n)+O(h(n)) to mean that f (n)-g(n) is O(h(n)) More precise form: P 312
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ 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:P. 275 ⚫ 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. Test Data for Searching P. 275 ⚫ 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. ⚫ To make the test more realistic, use pseudo-random numbers to choose the target, by employing the method Random :: random integer from Appendix B. [7.3] Binary Search 7.3.1 Ordered Lists P. 278 DEFINITION: An ordered list is a list in which each entry contains a key, such that the keys are in order. That is, if entry i comes before entry j in the list, then the key of entry i is less than or equal to the key of entry j . P. 278 ⚫ All List operations except insert and replace apply without modification to an ordered list. ⚫ Methods insert and replace must fail when they would otherwise disturb the order of a list. ⚫ We implement an ordered list as a class derived from a contiguous List. In this derived class, we shall override the methods insert and replace with new implementations. P. 279 Overloaded insertion: P. 279 Overridden insertion: P. 280 7.3.2 Binary Search P. 280 ⚫ Idea: In searching an ordered list, first compare the target to the key in the center of the list. If it is smaller, restrict the search to the left half; otherwise restrict the search to the right half, and repeat. In this way, at each step we reduce the length of the list to be searched by half. ⚫ Keep two indices, top and bottom, that will bracket the part of the list still to be searched. The target key, provided it is present, will be found between the indices bottom and top, inclusive. ⚫ Initialization: Set bottom = 0; top = the_list.size( ) − 1; ⚫ Compare target with the Record at the midpoint, ⚫ mid = (bottom+top)/2; ⚫ Change the appropriate index top or bottom to restrict the search to the appropriate half of the list. ⚫ Loop terminates when top≤bottom, if it has not terminated earlier by finding the target. ⚫ Make progress toward termination by ensuring that the number of items remaining to be searched, top−bottom+1, strictly decreases at each iteration of the process. 7.3.3 The Forgetful Version of Binary Search P. 281 Algorithm Verification P. 282 Nonrecursive Binary Search P. 283 7.3.4 Recognizing Equality in Binary Search P. 284 Nonrecursive Version P. 285 Algorithm Verification P. 285 [7.4] Asymptotics: The Big-O and Other Notations P. 302 7.6.2 Orders of Magnitude P. 304 Assumptions P. 305 Orders of Magnitude of Common Functions Polynomials P. 306 Logarithms P. 307 L’Hôpital’s Rule P. 307 Exponential functions P. 308 The function n log n: The function n log n has strictly greater order of magnitude than n but strictly smaller order of magnitude than any power nr for any r>1. Growth Rates of Common Orders P. 309-310 7.6.3 The Big-O and Related Notations P. 310 Examples: P. 311 Algorithm Analyses P. 311 7.6.4 Keeping the dominant term: P. 311 We define f (n) = g (n) + O(h (n)) to mean that f (n) − g(n) is O(h(n)) . More precise form: P.312
2008级计算机 据结构课堂教学笔记 供课堂教学使用 Pointers and Pitfalls 10 items P.314-315 Er rata p. 275, line 4 of test search: Change " funtion"to"function p. 313, El2, line 2: Change"O(f(n)"to"Theta( f(n))". line 3: Change "transitive"to"symmetric p. 313, E13, line 2: Change"transitive"to"reflexive p. 314, E16, displayed limit: Change","to
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Pointers and Pitfalls 10 items P.314-315 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 275, line 4 of test_search: Change "funtion" to "function". p. 313, E12, line 2: Change "O(f(n))" to "Theta(f(n))". line 3: Change "transitive" to "symmetric". p. 313, E13, line 2: Change "transitive" to "reflexive". p. 314, E16, displayed limit: Change ";" to ",". ----------------------------------------------------------------------------------------------------------------------------- --
