数据结构与程序设计18 searching

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

Informationretrievalisoneoftheimportantapplicationsofcomputers.Wearegivenalistofrecords,whereeachrecordisassociatedwithonepieceofinformation,whichweshallcallakey(关键字).(BOOKP269FIGURE7.1)本章讨论顺序存储列表的查找操作，链接存储在第10章讨论。4/21/20232.Chapter7SEARCHINGWearegivenonekey,calledthetarget,andareaskedtosearchthelisttofindtherecord(s)(ifany)whosekeyisthesameasthetarget.Weoftenaskhowtimesonekeyiscomparedwithanotherduringasearch.Thisgivesusagoodmeasureofthetotalamountofworkthatthealgorithmwilldo.4/21/20233.Chapter7SEARCHING

Thesearchingproblemfallsnaturallyintotwocases.Internalsearching（内部查找）meansthatalltherecordsarekeptinhigh-speedmemory.Inexternalsearching（外部查找）,mostoftherecordsarekeptindiskfiles.Westudyonlyinternalsearching.4/21/20234.ImplementationofKeyClassclassKey{ intkey;public: Key(intx=0); intthe_key()const;};booloperator==(constKey&x,constKey&y);4/21/20235.ImplementationofKeyClassKey::Key(intx){ key=x;}intKey::the_key()const{ returnkey;}booloperator==(constKey&x,constKey&y){ returnx.the_key()==y.the_key();}4/21/20236.ImplementationofRecordClassclassRecord{public:

operatorKey();//implicitconversionfrom RecordtoKey. Record(intx=0,inty=0);private: intkey; intother;};4/21/20237.ImplementationofRecordClassRecord::Record(intx,inty){ key=x; other=y;}Record::operatorKey(){ Keytmp(key);returntmp；}4/21/20238.TestMainvoidmain(){ Keytarget(5); Recordmyrecord(5,9);

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

RecordtoKey.4/21/202311.ImplementationofKeyClassclassKey{ intkey;public: Key(intx=0);

Key(constRecord&r); intthe_key()const;};booloperator==(constKey&x,constKey&y);4/21/202312.ImplementationofKeyClassKey::Key(intx){ key=x;}Key::Key(constRecord&r){ key=r.the_key();}intKey::the_key()const{ returnkey;}booloperator==(constKey&x,constKey&y){ returnx.the_key()==y.the_key();}4/21/202313.ImplementationofRecordClassclassRecord{public: Record(intx=0,inty=0);

intthe_key()const;private: intkey; intother;};4/21/202314.ImplementationofRecordClassRecord::Record(intx,inty){ key=x; other=y;}intRecord::the_key()const{ returnkey;}4/21/202315.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/21/202316.ImplementationofSearch目录SeqSearch2下例程4/21/202317.SequentialSearch顺序查找P272Error_codesequential_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/21/202318.AnalysisBOOKP273Thenumberofcomparisonsofkeysdoneinsequentialsearchofalistoflengthnis:Unsuccessfulsearch:ncomparisons.Successfulsearch,bestcase:1comparison.Successfulsearch,worstcase:ncomparisons.Successfulsearch,averagecase:(n+1)/2comparisons.4/21/202319.BinarySearchSequentialsearchiseasytowriteandefficientforshortlists,butadisasterforlongones.Oneofthebestmethodsforalistwithkeysinorderisbinarysearch.首先讨论如何构建一个有序的列表。然后讨论针对顺序列表的二分查找。4/21/202320.OrderedLists有序列表的定义：DEFINITIONAnorderedlistisalistinwhicheachentrycontainsakey,suchthatthekeysareinorder.Thatis,ifentryicomesbeforeentryjinthelist,thenthekeyofentryiislessthanorequaltothekeyofentryj.4/21/202321.OrderedListsclassOrdered_list:publicList<Record>{public: Error_codeinsert(constRecord&data); Error_codeinsert(intposition,constRecord&data); Error_codereplace(intposition,constRecord&data);};4/21/202322.OrderedListsError_codeOrdered_list::insert(constRecord&data)/*Post:IftheOrdered_listisnotfull,thefunctionsucceeds:TheRecorddataisinsertedintothelist,followingthelastentryofthelistwithastrictlylesserkey(orinthefirstlistpositionifnolistelementhasalesserkey).Else:thefunctionfailswiththediagnosticError_codeoverflow.*/4/21/202323.OrderedListsError_codeOrdered_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/21/202324.OrderedListsError_codeOrdered_list::insert(intposition,constRecord&data)/*Post:IftheOrderedlistisnotfull,0<=position<=n,wherenisthenumberofentriesinthelist,andtheRecorddatacanbeinsertedatpositioninthelist,withoutdisturbingthelistorder,thenthefunctionsucceeds:Anyentryformerlyinpositionandalllaterentrieshavetheirpositionnumbersincreasedby1anddataisinsertedatpositionoftheList.Else:thefunctionfailswithadiagnosticError_code.*/4/21/202325.OrderedListsError_codeOrdered_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/21/202326.OrderedListsError_codeOrdered_list::replace(intposition,constRecord&data){ if(position<0||position>=count)returnrange_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/21/202327.OrderedListsclassRecord{public: Record(); Record(intx,inty=0); intthe_key()const;private: intkey; intother;};booloperator>(constRecord&x,constRecord&y);booloperator<(constRecord&x,constRecord&y);ostream&operator<<(ostream&output,Record&x);4/21/202328.OrderedListsRecord::Record(){ key=0; other=0;}Record::Record(intx,inty){ key=x; other=y;}intRecord::the_key()const{ returnkey;}4/21/202329.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/21/202330.Ordered