数据结构与程序设计（王丽苹）18 searching

数据结构与程序设计(18)王丽苹lipingwang@4/29/20261数据结构与程序设计Chapter7SEARCHING

Informationretrievalisoneoftheimportantapplicationsofcomputers.Wearegivenalistofrecords,whereeachrecordisassociatedwithonepieceofinformation,whichweshallcallakey(关键字).(BOOKP269FIGURE7.1)本章讨论顺序存储列表的查找操作，链接存储在第10章讨论。4/29/20262数据结构与程序设计Chapter7SEARCHINGWearegivenonekey,calledthetarget,andareaskedtosearchthelisttofindtherecord(s)(ifany)whosekeyisthesameasthetarget.Weoftenaskhowtimesonekeyiscomparedwithanotherduringasearch.Thisgivesusagoodmeasureofthetotalamountofworkthatthealgorithmwilldo.4/29/20263数据结构与程序设计Chapter7SEARCHING

Thesearchingproblemfallsnaturallyintotwocases.Internalsearching（内部查找）meansthatalltherecordsarekeptinhigh-speedmemory.Inexternalsearching（外部查找）,mostoftherecordsarekeptindiskfiles.Westudyonlyinternalsearching.4/29/20264数据结构与程序设计ImplementationofKeyClassclassKey{

intkey;public: Key(intx=0);

int

the_key()const;};booloperator==(constKey&x,constKey&y);4/29/20265数据结构与程序设计ImplementationofKeyClassKey::Key(intx){ key=x;}int

Key::the_key()const{ returnkey;}booloperator==(constKey&x,constKey&y){ returnx.the_key()==y.the_key();}4/29/20266数据结构与程序设计ImplementationofRecordClassclassRecord{public:

operatorKey();//implicitconversionfrom RecordtoKey.

Record(intx=0,inty=0);private:

intkey;

intother;};4/29/20267数据结构与程序设计ImplementationofRecordClassRecord::Record(intx,inty){ key=x; other=y;}Record::operatorKey(){ Keytmp(key);

returntmp；}4/29/20268数据结构与程序设计TestMainvoidmain(){ Keytarget(5); Recordmyrecord(5,9);

if(target==myrecord)

cout<<"yes"<<endl; elsecout<<"no"<<endl;}调用operatorKey()构造临时Keytmp,采用voidoperator==(constKey&x,constKey&y)操作符比较。Output:yes4/29/20269数据结构与程序设计ImplementationofSearch目录SeqSearch下例程4/29/202610数据结构与程序设计AnotherMethodRecorder中的成员operatorKey();主要完成从Recorder对象到Key对象的自动转换。可以用其他方法完成该功能。Useconstructortoconversionfrom

RecordtoKey.4/29/202611数据结构与程序设计ImplementationofKeyClassclassKey{

intkey;public: Key(intx=0);

Key(constRecord&r);

int

the_key()const;};booloperator==(constKey&x,constKey&y);4/29/202612数据结构与程序设计ImplementationofKeyClassKey::Key(intx){ key=x;}Key::Key(constRecord&r){ key=r.the_key();}int

Key::the_key()const{ returnkey;}booloperator==(constKey&x,constKey&y){ returnx.the_key()==y.the_key();}4/29/202613数据结构与程序设计ImplementationofRecordClassclassRecord{public:

Record(intx=0,inty=0);

int

the_key()const;private:

intkey;

intother;};4/29/202614数据结构与程序设计ImplementationofRecordClassRecord::Record(intx,inty){ key=x; other=y;}int

Record::the_key()const{ returnkey;}4/29/202615数据结构与程序设计TestMainvoidmain(){ Keytarget(5); Recordmyrecord(5,9);

if(target==myrecord)

cout<<"yes"<<endl; elsecout<<"no"<<endl;}调用Key(constRecord&r)构造临时Keytmp,采用voidoperator==(constKey&x,constKey&y)操作符比较后，调用析构函数释放tmp。Output:yes4/29/202616数据结构与程序设计ImplementationofSearch目录SeqSearch2下例程4/29/202617数据结构与程序设计SequentialSearch顺序查找P272Error_code

sequential_search(constList<Record>&the_list,constKey&target,int&position)/*Post:Ifanentryinthelisthaskeyequaltotarget,thenreturnsuccessandtheoutputparameterpositionlocatessuchanentrywithinthelist.Otherwisereturnnot_presentandpositionbecomesinvalid.*/{ints=the_list.size();for(position=0;position<s;position++){Recorddata;

the_list.retrieve(position,data);if(target==data)returnsuccess;}returnnot_present;}4/29/202618数据结构与程序设计AnalysisBOOKP273Thenumberofcomparisonsofkeysdoneinsequentialsearchofalistoflengthnis:Unsuccessfulsearch:ncomparisons.Successfulsearch,bestcase:1comparison.Successfulsearch,worstcase:ncomparisons.Successfulsearch,averagecase:(n+1)/2comparisons.4/29/202619数据结构与程序设计BinarySearchSequentialsearchiseasytowriteandefficientforshortlists,butadisasterforlongones.Oneofthebestmethodsforalistwithkeysinorderisbinarysearch.首先讨论如何构建一个有序的列表。然后讨论针对顺序列表的二分查找。4/29/202620数据结构与程序设计OrderedLists有序列表的定义：DEFINITIONAnorderedlistisalistinwhicheachentrycontainsakey,suchthatthekeysareinorder.Thatis,ifentryicomesbeforeentryjinthelist,thenthekeyofentryiislessthanorequaltothekeyofentryj.4/29/202621数据结构与程序设计OrderedListsclassOrdered_list:publicList<Record>{public:

Error_code

insert(constRecord&data);

Error_code

insert(intposition,constRecord&data);

Error_code

replace(intposition,constRecord&data);};4/29/202622数据结构与程序设计OrderedListsError_code

Ordered_list::insert(constRecord&data)/*Post:IftheOrdered_listisnotfull,thefunctionsucceeds:TheRecorddataisinsertedintothelist,followingthelastentryofthelistwithastrictlylesserkey(orinthefirstlistpositionifnolistelementhasalesserkey).Else:thefunctionfailswiththediagnosticError_codeoverflow.*/4/29/202623数据结构与程序设计OrderedListsError_code

Ordered_list::insert(constRecord&data)/*Post:IftheOrdered_listisnotfull,thefunctionsucceeds:TheRecorddataisinsertedintothelist,followingthelastentryofthelistwithastrictlylesserkey(orinthefirstlistpositionifnolistelementhasalesserkey).Else:thefunctionfailswiththediagnosticError_codeoverflow.*/{

ints=size();

intposition; for(position=0;position<s;position++){ Recordlist_data;

retrieve(position,list_data);

if(data<list_data)break;//bookp279wrong } returnList<Record>::insert(position,data);//调用父类的方法。}4/29/202624数据结构与程序设计OrderedListsError_code

Ordered_list::insert(intposition,constRecord&data)/*Post:IftheOrderedlistisnotfull,0<=position<=n,wherenisthenumberofentriesinthelist,andtheRecorddatacanbeinsertedatpositioninthelist,withoutdisturbingthelistorder,thenthefunctionsucceeds:Anyentryformerlyinpositionandalllaterentrieshavetheirpositionnumbersincreasedby1anddataisinsertedatpositionoftheList.Else:thefunctionfailswithadiagnosticError_code.*/4/29/202625数据结构与程序设计OrderedListsError_code

Ordered_list::insert(intposition,constRecord&data)/*Post:succeeds:AnyentryformerlyinpositionandalllaterentrieshavetheirElse:thefunctionfailswithadiagnosticError_code.*/{ Recordlist_data; if(position>0){

retrieve(position-1,list_data); if(data<list_data) returnfail; } if(position<size()){

retrieve(position,list_data); if(data>list_data) returnfail; } returnList<Record>::insert(position,data);}4/29/202626数据结构与程序设计OrderedListsError_code

Ordered_list::replace(intposition,constRecord&data){ if(position<0||position>=count)return

range_error; Recordlist_data; if(position>0){

retrieve(position-1,list_data); if(data<list_data) returnfail; } if(position<size()-1){

retrieve(position+1,list_data); if(data>list_data) returnfail; }

entry[position]=data; returnsuccess;}4/29/202627数据结构与程序设计OrderedListsclassRecord{public: Record();

Record(intx,inty=0);

int

the_key()const;private:

intkey;

intother;};booloperator>(constRecord&x,constRecord&y);booloperator<(constRecord&x,constRecord&y);ostream&operator<<(ostream&output,Record&x);4/29/202628数据结构与程序设计OrderedListsRecord::Record(){ key=0; other=0;}Record::Record(intx,inty){ key=x; other=y;}int

Record::the_key()const{ returnkey;}4/29/202629数据结构与程序设计OrderedListsbooloperator>(constRecord&x,constRecord&y){ returnx.the_key()>y.the_key();}booloperator<(constRecord&x,constRecord&y){ returnx.the_key()<y.the_key();}ostream&operator<<(ostream&output,Record&x){ output<<x.the_key(); output<<endl; returnoutput;}4/29/202630数据结构与程序设计OrderedLists--Maintemplate<classList_entry>void