(第1版)数据结构实验指导.docx

《(第1版)数据结构实验指导.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、3Projects3.1Project1:PerformanceMeasurementGivenalistoforderedNintegers,numberedfrom0toN-.checkingtoseethatNisnotinthislistprovidesaworstcaseformanysearchalgorithms.Considertwoalgorithms:oneiscalled"sequentialsearch"whichscansthroughthelistfromlefttoright;andtheotheris"binar

2、ysearch"whichisgivenonpage24(Figure2.9)ofyourtextbook・Yourtasksare:(1)Implementaniterativeversionandarecursiveversionofsequentialsearch;(2)Implementaniterativeversionofbinarysearch;(3)Analyzetheworstcasecomplexitiesoftheabovetwoversionsofsequentialsearchandthatofbinarysearch;

3、(4)MeasureandcomparetheworstcaseperformancesoftheabovethreefunctionsforN=100,500,1000,2000,4000,6000,8000,10000.Tomeasuretheperformanceofafunction,wcmayuseC'sstandardlibrarytime.hasthefollowing:#includeclock_tstart,stop;/*clock_tisabuilt-intypeforprocessortime(ticks)*

4、/doubleduration;/*recordstheruntime(seconds)ofafunctionA/intmain()••••••/*clock()returnstheamountofprocessortime(ticks)thathaselapsedsincetheprogrambeganrunning*/start=clock();rrecordstheticksatthebeginningofthefunctioncall7function();/*runyourfunctionhere*/stop=clock();/*rec

5、ordstheticksattheendofthefunctioncall*/duration=((double)(stop・start))/CLK_TCK;rCLK_TCKisabuilt-inconstant=tickspersecond*/return1;Note:Ifafunctionrunssoquicklythatittakeslessthanaticktofinish,wcmayrepeatthefunctioncallsforKtimestoobtainatotalruntimeC67b/a/Time")、andthendivid

6、ethetotaltimebyKtoobtainamoreaccuratedurationCDuratiorC)forasinglefunofthefunction・Therepetitionfactormustbylargeenoughsothatthenumberofelapsedticksisatleast10ifwewantanaccuracyofatleast1()%・Thetestresultsmustbelistedinthefollowingtabic:N1005001000200040006000800010000Sequent

7、ialSearch(iterativeversion)Iterations(K)TicksTotalTime(sec)Duration(sec)SequennalSearch(reciirsix-eversion)Iterations(&TicksTotalTime(sec)Duration(sec)BinarySearchIterations(&TicksTotalTime(sec)Duration(sec)TheperformancesofthethreefunctionsmustbeplottedinthesameN-run_timecoo

8、rdinatesystemforillustration.3.1Project2:ImplementationofLists,andPo