数据结构与程序设计(王丽苹)18searching.ppt

5/27/2023,数据结构与程序设计,1,数据结构与程序设计(18),王丽苹,5/27/2023,数据结构与程序设计,2,Chapter 7 SEARCHING,Information retrieval is one of the important applications of computers.We 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)本章讨论顺序存储列表的查找操作，链接存储在第10章讨论。,5/27/2023,数据结构与程序设计,3,Chapter 7 SEARCHING,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.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.,5/27/2023,数据结构与程序设计,4,Chapter 7 SEARCHING,The searching problem falls naturally into two cases.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.,5/27/2023,数据结构与程序设计,5,Implementation of Key Class,class Key int key;public:Key(int x=0);int the_key()const;bool operator=(const Key,5/27/2023,数据结构与程序设计,6,Implementation of Key Class,Key:Key(int x)key=x;int Key:the_key()constreturn key;bool operator=(const Key,5/27/2023,数据结构与程序设计,7,Implementation of Record Class,class Recordpublic:operator Key();/implicit conversion from Record to Key.Record(int x=0,int y=0);private:int key;int other;,5/27/2023,数据结构与程序设计,8,Implementation of Record Class,Record:Record(int x,int y)key=x;other=y;Record:operator Key()Key tmp(key);return tmp；,5/27/2023,数据结构与程序设计,9,Test Main,void main()Key target(5);Record myrecord(5,9);if(target=myrecord)coutyesendl;else coutnoendl;调用operator Key()构造临时Key tmp,采用void operator=(const Key&x,const Key&y)操作符比较。Output:yes,5/27/2023,数据结构与程序设计,10,Implementation of Search,目录SeqSearch下例程,5/27/2023,数据结构与程序设计,11,Another Method,Recorder中的成员operator Key();主要完成从Recorder对象到Key对象的自动转换。可以用其他方法完成该功能。Use constructor to conversion from Record to Key.,5/27/2023,数据结构与程序设计,12,Implementation of Key Class,class Key int key;public:Key(int x=0);Key(const Record,5/27/2023,数据结构与程序设计,13,Implementation of Key Class,Key:Key(int x)key=x;Key:Key(const Record,5/27/2023,数据结构与程序设计,14,Implementation of Record Class,class Recordpublic:Record(int x=0,int y=0);int the_key()const;private:int key;int other;,5/27/2023,数据结构与程序设计,15,Implementation of Record Class,Record:Record(int x,int y)key=x;other=y;int Record:the_key()constreturn key;,5/27/2023,数据结构与程序设计,16,Test Main,void main()Key target(5);Record myrecord(5,9);if(target=myrecord)coutyesendl;else coutnoendl;调用Key(const Record&r)构造临时Key tmp,采用void operator=(const Key&x,const Key&y)操作符比较后，调用析构函数释放tmp。Output:yes,5/27/2023,数据结构与程序设计,17,Implementation of Search,目录SeqSearch2下例程,5/27/2023,数据结构与程序设计,18,Sequential Search 顺序查找 P272,Error_code sequential_search(const List,5/27/2023,数据结构与程序设计,19,Analysis,BOOK P273The 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.,5/27/2023,数据结构与程序设计,20,Binary Search,Sequential search is easy to write and efficient for short lists,but a disaster for long ones.One of the best methods for a list with keys in order is binary search.首先讨论如何构建一个有序的列表。然后讨论针对顺序列表的二分查找。,5/27/2023,数据结构与程序设计,21,Ordered Lists,有序列表的定义：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.,5/27/2023,数据结构与程序设计,22,Ordered Lists,class Ordered_list:public Listpublic:Error_code insert(const Record,5/27/2023,数据结构与程序设计,23,Ordered Lists,Error_code Ordered_list:insert(const Record&data)/*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 position if no list element has a lesser key).Else:the function fails with the diagnostic Error_code overflow.*/,5/27/2023,数据结构与程序设计,24,Ordered Lists,Error_code Ordered_list:insert(const Record/调用父类的方法。,5/27/2023,数据结构与程序设计,25,Ordered Lists,Error_code Ordered_list:insert(int position,const Record&data)/*Post:If the Ordered list is not full,0=position=n,where n is the number of entries in the list,and the Record data can be inserted at position in the list,without disturbing the list order,then the functionsucceeds:Any entry formerly in position and all later entries have their position numbers increased by 1 and data is inserted atposition of theList.Else:the function fails with a diagnostic Error_code.*/,5/27/2023,数据结构与程序设计,26,Ordered Lists,Error_code Ordered_list:insert(int position,const Record,5/27/2023,数据结构与程序设计,27,Ordered Lists,Error_code Ordered_list:replace(int position,const Record,5/27/2023,数据结构与程序设计,28,Ordered Lists,class Recordpublic:Record();Record(int x,int y=0);int the_key()const;private:int key;int other;bool operator(const Record,5/27/2023,数据结构与程序设计,29,Ordered Lists,Record:Record()key=0;other=0;Record:Record(int x,int y)key=x;other=y;int Record:the_key()constreturn key;,5/27/2023,数据结构与程序设计,30,Ordered Lists,bool operator(const Record,5/27/2023,数据结构与程序设计,31,Ordered Lists-Main,template void print(List_entry,5/27/2023,数据结构与程序设计,32,Result,Your list have 6 elements:023468,5/27/2023,数据结构与程序设计,33,Ordered Lists-Main,mylist.remove(0,Record(i);coutAfter remove(0):endl;mylist.traverse(print);,5/27/2023,数据结构与程序设计,34,Result,After remove(0):23468,5/27/2023,数据结构与程序设计,35,Ordered Lists-Main,mylist.replace(0,Record(-1);coutAfter replace(0,Record(-1):endl;mylist.traverse(print);,5/27/2023,数据结构与程序设计,36,Result,After replace(0,Record(-1):-13468,5/27/2023,数据结构与程序设计,37,Ordered Lists-Main,目录Ordered_list下例程,5/27/2023,数据结构与程序设计,38,课后阅读,关于顺序查找的效率测试。课后阅读P274 3.testing理解函数test_search/统计查找成功和查找不成功时的比较次数。,