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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构与程序设计,*,数据结构与程序设计(18),王丽苹,11/26/2024,1,数据结构与程序设计,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章讨论。,11/26/2024,2,数据结构与程序设计,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.,11/26/2024,3,数据结构与程序设计,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.,11/26/2024,4,数据结构与程序设计,Implementation of Key Class,class Key,int key;,public:,Key(int x=0);,int the_key()const;,;,bool operator=(const Key,11/26/2024,5,数据结构与程序设计,Implementation of Key Class,Key:Key(int x),key=x;,int Key:the_key()const,return key;,bool operator=(const Key&x,const Key&y),return x.the_key()=y.the_key();,11/26/2024,6,数据结构与程序设计,Implementation of Record Class,class Record,public:,operator Key,();/,implicit conversion from Record to Key.,Record(int x=0,int y=0);,private:,int key;,int other;,;,11/26/2024,7,数据结构与程序设计,Implementation of Record Class,Record:Record(int x,int y),key=x;,other=y;,Record:operator Key(),Key tmp(key);,return tmp；,11/26/2024,8,数据结构与程序设计,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,11/26/2024,9,数据结构与程序设计,Implementation of Search,目录,SeqSearch,下例程,11/26/2024,10,数据结构与程序设计,Another Method,Recorder中的成员operator Key,();主要完成从Recorder对象到Key对象的自动转换。可以用其他方法完成该功能。,Use constructor to conversion from,Record to Key.,11/26/2024,11,数据结构与程序设计,Implementation of Key Class,class Key,int key;,public:,Key(int x=0);,Key(const Record,int the_key()const;,;,bool operator=(const Key,11/26/2024,12,数据结构与程序设计,Implementation of Key Class,Key:Key(int x),key=x;,Key:Key(const Record&r),key=r.the_key();,int Key:the_key()const,return key;,bool operator=(const Key&x,const Key&y),return x.the_key()=y.the_key();,11/26/2024,13,数据结构与程序设计,Implementation of Record Class,class Record,public:,Record(int x=0,int y=0);,int the_key()const;,private:,int key;,int other;,;,11/26/2024,14,数据结构与程序设计,Implementation of Record Class,Record:Record(int x,int y),key=x;,other=y;,int Record:the_key()const,return key;,11/26/2024,15,数据结构与程序设计,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,11/26/2024,16,数据结构与程序设计,Implementation of Search,目录,SeqSearch2,下例程,11/26/2024,17,数据结构与程序设计,Sequential Search 顺序查找 P272,Error_code sequential_search(const List&the_list,const Key&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.*,/,int s=the_list.size();,for(position=0;position s;position+),Record data;,the_list.retrieve(position,data);,if(,target=data,)return success;,return not_present;,11/26/2024,18,数据结构与程序设计,Analysis,BOOK P273,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.,11/26/2024,19,数据结构与程序设计,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.,首先讨论如何构建一个有序的列表。,然后讨论针对顺序列表的二分查找。,11/26/2024,20,数据结构与程序设计,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,.,11/26/2024,21,数据结构与程序设计,Ordered Lists,class Ordered_list:public List,public:,Error_code insert(const Record,Error_code insert(int position,const Record,Error_code replace(int position,const Record,;,11/26/2024,22,数据结构与程序设计,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.*/,11/26/2024,23,数据结构与程序设计,Orde