数据结构与程序设计 Chapter 7 SEARCHING

1、11/23/2021数据结构与程序设计 1Chapter 7 SEARCHINGnInformation retrieval is one of the important applications of computers.nWe are given a list of records, where each record is associated with one piece of information, which we shall call a key(关键字). (BOOK P269 FIGURE 7.1)n本章讨论顺序存储列表的查找操作，链接存储在第10章讨论。11/23/20

2、21数据结构与程序设计 2Chapter 7 SEARCHINGnWe 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.nWe often ask how times one key is compared with another during a search. This gives us a good measure of the total amount of

3、work that the algorithm will do.11/23/2021数据结构与程序设计 3Chapter 7 SEARCHINGnThe searching problem falls naturally into two cases.nInternal searching（内部查找）（内部查找） means that all the records are kept in high-speed memory. nIn external searching（外部查找）（外部查找）, most of the records are kept in disk files. nWe

4、study only internal searching.11/23/2021数据结构与程序设计 4Implementation of Key Classnclass Key nint key;npublic:nKey (int x = 0);nint the_key( ) const;n;nbool operator = (const Key &x, const Key &y);11/23/2021数据结构与程序设计 5Implementation of Key ClassnKey:Key(int x)nkey=x;nnint Key:the_key() constnret

5、urn key;nnbool operator = (const Key &x, const Key &y)nnreturn x.the_key( ) = y.the_key( );n11/23/2021数据结构与程序设计 6Implementation of Record Classnclass Recordnpublic:noperator Key( ); / implicit conversion from Record to Key .nRecord(int x=0, int y=0);nprivate:nint key;nint other;n;11/23/2021数

6、据结构与程序设计 7Implementation of Record ClassnRecord:Record(int x, int y)nkey=x;nother=y;nnRecord:operator Key( )nKey tmp(key);n return tmp；n11/23/2021数据结构与程序设计 8Test Mainnvoid main()nKey target(5);nRecord myrecord(5,9);nif (target=myrecord) coutyesendl;nelse coutnoendl;nn调用调用operator Key( )构造临时构造临时Key t

7、mp,采用采用void operator = (const Key &x, const Key &y)操作符比较。操作符比较。nOutput:nyes11/23/2021数据结构与程序设计 9Implementation of Search目录目录SeqSearch下例程下例程11/23/2021数据结构与程序设计 10Another MethodnRecorder中的成员中的成员operator Key( );主要主要完成从完成从Recorder对象到对象到Key对象的自动转对象的自动转换。可以用其他方法完成该功能。换。可以用其他方法完成该功能。nUse constructo

8、r to conversion from Record to Key .11/23/2021数据结构与程序设计 11Implementation of Key Classnclass Key nint key;npublic:nKey (int x = 0);nKey (const Record &r);nint the_key( ) const;n;nbool operator = (const Key &x, const Key &y);11/23/2021数据结构与程序设计 12Implementation of Key ClassnKey:Key(int x)n

9、key=x;nnKey:Key(const Record &r)nkey=r.the_key();nnint Key:the_key() constnreturn key;nnbool operator = (const Key &x, const Key &y)nnreturn x.the_key( ) = y.the_key( );n11/23/2021数据结构与程序设计 13Implementation of Record Classnclass Recordnpublic:nRecord(int x=0, int y=0);nint the_key() cons

10、t;nprivate:nint key;nint other;n;11/23/2021数据结构与程序设计 14Implementation of Record ClassnRecord:Record(int x, int y)nkey=x;nother=y;nnint Record:the_key() constnreturn key;n11/23/2021数据结构与程序设计 15Test Mainnvoid main()nKey target(5);nRecord myrecord(5,9);nif (target=myrecord) coutyesendl;nelse coutnoendl

11、;nn调用调用Key(const Record &r)构造临时构造临时Key tmp,采用采用void operator = (const Key &x, const Key &y)操作符比较后，调用析构函数释放操作符比较后，调用析构函数释放tmp。nOutput:nyes11/23/2021数据结构与程序设计 16Implementation of Search目录目录SeqSearch2下例程下例程11/23/2021数据结构与程序设计 17Sequential Search 顺序查找顺序查找 P272nError_code sequential_search(co

12、nst List &the_list,nconst Key &target, int &position)n/* Post: If an entry in the list has key equal to target , then return success and thenoutput parameter position locates such an entry within the list.nOtherwise return not_present and position becomes invalid. */nnint s = the_list.si

13、ze( );nfor (position = 0; position s; position+) n Record data;n the_list.retrieve(position, data);n if (target = data) return success;nnreturn not_present;n11/23/2021数据结构与程序设计 18AnalysisBOOK P273nThe number of comparisons of keys done in sequential search of a list of length n is:nUnsuccessful sear

14、ch: n comparisons.nSuccessful search, best case: 1 comparison.nSuccessful search, worst case: n comparisons.nSuccessful search, average case: (n + 1)/ 2 comparisons.11/23/2021数据结构与程序设计 19Binary SearchSequential search is easy to write and efficient for short lists, but a disaster for long ones.One o

15、f the best methods for a list with keys in order is binary search.首先讨论如何构建一个有序的列表。然后讨论针对顺序列表的二分查找。11/23/2021数据结构与程序设计 20Ordered Listsn有序列表的定义：nDEFINITION nAn 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 li

16、st, then the key of entry i is less than or equal to the key of entry j .11/23/2021数据结构与程序设计 21Ordered Listsnclass Ordered_list: public Listnpublic:nError_code insert(const Record &data);nError_code insert(int position, const Record &data);nError_code replace(int position, const Record &

17、data);n;11/23/2021数据结构与程序设计 22Ordered ListsnError_code Ordered_list : insert(const Record &data)n/* Post: If the Ordered_list is not full, the function succeeds: The Record data is inserted into the list, following the last entry of the list with a strictly lesser key (or in the first list posit

18、ion if no list element has a lesser key).nElse: the function fails with the diagnostic Error_code overflow. */11/23/2021数据结构与程序设计 23Ordered ListsnError_code Ordered_list : insert(const Record &data)n/* Post: If the Ordered_list is not full, the function succeeds: The Record data is inserted into

19、 the list, following the last entry of the list with a strictly lesser key (or in the first list position if no list element has a lesser key).nElse: the function fails with the diagnostic Error_code overflow. */nnint s = size( );nint position;nfor (position = 0; position s; position+) nRecord list_

20、data;nretrieve(position, list_data);nif (data list_data) break; /book p279 wrongnnreturn List : insert(position, data);n /调用父类的方法。调用父类的方法。n11/23/2021数据结构与程序设计 24Ordered ListsnError_code Ordered_list : insert(int position, const Record &data)n/* Post: If the Ordered list is not full, 0 = position

21、 0) nretrieve(position - 1, list_data);nif (data list_data)nreturn fail;nnif (position list_data)nreturn fail;nnreturn List : insert(position, data);n11/23/2021数据结构与程序设计 26Ordered ListsnError_code Ordered_list : replace(int position, const Record &data)nnif (position = count)return range_error;n

22、Record list_data;nif (position 0) nretrieve(position - 1, list_data);nif (data list_data)nreturn fail;nnif (position list_data)nreturn fail;nnentryposition = data;nreturn success;n11/23/2021数据结构与程序设计 27Ordered Listsnclass Recordnpublic:nRecord();nRecord(int x, int y=0);nint the_key() const;nprivate:

23、nint key;nint other;n;nbool operator (const Record &x, const Record &y);nbool operator (const Record &x, const Record &y);nostream & operator (const Record &x, const Record &y)nnreturn x.the_key( ) y.the_key( );nnbool operator (const Record &x, const Record &y)nnreturn x.the_key( ) y.the_key( );nnostream & operator (ostream &output, Record &x)nnoutputx.the_key();noutputendl;nreturn output;n11/23/2021数据结构与程序设计 30Ordered Lists-Mainntemplate nvoid print(List_entry &x)ncoutx;nnvoid main()nOrdered_list mylist;nfor(int i