資源描述:
《lecture4 Linked Lists》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、ListsCS122AlgorithmsandDataStructuresAlistisavarying-length,linearcollectionofhomogeneouselements.Linearmeanseachlistelement(exceptthefirst)hasauniquepredecessor,andeachelement(exceptthelast)hasauniqueMW11:00am-12:15pm,MSEC101successorInstructor:XiaoQinInalinearstructure,componentscanonlybeacce
2、ssedsequentiallyoneaftertheLecture4:LinkedListsother2Lists(cont.)ListsasADTsDomainItnormallyhastwo"special"named–Acollectionelementsofthesametypeelementscalledheadandtail.They–Animplicitlistcursorintherange1throughn+1wherenisthecurrentlengthofthelist.pointtothefirstandlastelementoftheOperations
3、list.–create():createanewlist.Shouldbedoneusingconstructors–BooleanIsEmpty()&BooleanIsFull():returnstrueifthelistisemptyandfullrespectively–voidInsertBeginning(v)&voidInsertEnd(v):Insertthevalueveitherintheendorthebeginningofthelist–voidDelete():itematlistcursordeleted–print():PrintthewholelistMor
4、eListOperationsArray-basedclassListOperations–insertAfter(v,anotherV):insertthevaluevafterthefirstoccurrenceofanotherV.IsEmpty–insertBefore(v,anotherV):InsertthevaluevIsFullPrivatedata:beforethefirstoccurrenceofanotherV.Lengthlength–search(v):searchforthefirstoccurrenceofvinthelistandreturnitspos
5、ition.CouldbeusedtohelptheInsertdata[0]implementationofseveralotheroperations[1]–deleteAll(v):DeletealloccurrencesofvinthelistDelete[2]–reset():Listcursorisatfrontoflist.IsPresent[MAX_LENGTH-1]Wecanassumethatprivatedatainalistincludesthelistsitself(usinganarrayorlinkedlist),thePrinthead,thetailan
6、dthesizeofthelistSortedList61//ARRAY-BASEDLIST(list.h)constintMAX_LENGTH=50;typedefintItemType;HowtoImplementaListclassSortedList{public://publicmemberfunctionsuseabuilt-inarraystoredincontiguousmemorySortedList();//constructorlocations,implementingoperationsInsertandboolIsEmpty()const;Deletebymo
7、vinglistitemsaroundinthearray,boolIsFull()const;intLength()const;//returnslengthoflistasneededvoidInsert(ItemTypeitem);voidDelete(ItemTypeitem);usealinkedlist(toavoidexcessivedataboolIsPresent(ItemTypeitem)const