基本数据结构StacksQueuesListsTrees

基本数据结构StacksQueuesListsTreesElementaryDataStructures2TheStackADT(§2.1.1)TheStackADTstoresarbitraryobjectsInsertionsanddeletionsfollowthelast-infirst-outschemeThinkofaspring-loadedplatedispenserMainstackoperations:push(object):insertsanelementobjectpop():removesandreturnsthelastinsertedelementAuxiliarystackoperations:objecttop():returnsthelastinsertedelementwithoutremovingitintegersize():returnsthenumberofelementsstoredbooleanisEmpty():indicateswhethernoelementsarestoredElementaryDataStructures3ApplicationsofStacksDirectapplicationsvisitedhistoryinaWebbrowserUndosequenceinatexteditorChainofmethodcallsintheJavaVirtualMachineorC++runtimeenvironmentIndirectapplicationsAuxiliarydatastructureforalgorithmsComponentofotherdatastructuresElementaryDataStructures4Array-basedStack(§2.1.1)AsimplewayofimplementingtheStackADTusesanarrayWeaddelementsfromlefttorightAvariabletkeepstrackoftheindexofthetopelement(sizeist+1)S012t…Algorithm

pop():

if

isEmpty()

then throwEmptyStackException

else

t

t1 return

S[t+1]Algorithm

push(o)

if

t

=S.length1then throwFullStackException

else

t

t+1

S[t]oElementaryDataStructures5GrowableArray-basedStack(§1.5)Inapushoperation,whenthearrayisfull,insteadofthrowinganexception,wecanreplacethearraywithalargeroneHowlargeshouldthenewarraybe?incrementalstrategy:increasethesizebyaconstantcdoublingstrategy:doublethesizeAlgorithm

push(o)

if

t

=S.length1then

A

newarrayof size…

for

i

0to

tdo

A[i]S[i]

SA

t

t+1

S[t]oElementaryDataStructures6ComparisonoftheStrategiesWecomparetheincrementalstrategyandthedoublingstrategybyanalyzingthetotaltimeT(n)neededtoperformaseriesofnpushoperationsWeassumethatwestartwithanemptystackrepresentedbyanarrayofsize1Wecallamortizedtimeofapushoperationtheaveragetimetakenbyapushovertheseriesofoperations,i.e.,T(n)/nElementaryDataStructures7AnalysisoftheIncrementalStrategyWereplacethearrayk=n/ctimesThetotaltimeT(n)ofaseriesofnpushoperationsisproportionalton+c+2c+3c+4c+…+kc=n+c(1+2+3+…+k)=n+ck(k+1)/2Sincecisaconstant,T(n)isO(n+

k2),

i.e.,O(n2)TheamortizedtimeofapushoperationisO(n)ElementaryDataStructures8DirectAnalysisoftheDoublingStrategyWereplacethearrayk=log2

ntimesThetotaltimeT(n)ofaseriesofnpushoperationsisproportionalton+1+2+4+8+…+2k

=n

+2k+1

-1

=2n-1T(n)isO(n)TheamortizedtimeofapushoperationisO(1)geometricseries12148ElementaryDataStructures9TheaccountingmethoddeterminestheamortizedrunningtimewithasystemofcreditsanddebitsWeviewacomputerasacoin-operateddevicerequiring1cyber-dollarforaconstantamountofcomputing.AccountingMethodAnalysisoftheDoublingStrategyWesetupaschemeforchargingoperations.Thisisknownasanamortizationscheme.Theschememustgiveusalwaysenoughmoneytopayfortheactualcostoftheoperation.Thetotalcostoftheseriesofoperationsisnomorethanthetotalamountcharged.(amortizedtime)(total$charged)/(#operations)ElementaryDataStructures10AmortizationSchemefortheDoublingStrategyConsideragainthekphases,whereeachphaseconsistingoftwiceasmanypushesastheonebefore.Attheendofaphasewemusthavesavedenoughtopayforthearray-growingpushofthenextphase.Attheendofphaseiwewanttohavesavedicyber-dollars,topayforthearraygrowthforthebeginningofthenextphase.02456731$$$$$$$$0245678911310121314151$$Wecharge$3forapush.The$2savedforaregularpushare“stored”inthesecondhalfofthearray.Thus,wewillhave2(i/2)=icyber-dollarssavedatthenendofphasei.Therefore,eachpushrunsinO(1)amortizedtime;npushesruninO(n)time.ElementaryDataStructures11TheQueueADT(§2.1.2)TheQueueADTstoresarbitraryobjectsInsertionsanddeletionsfollowthefirst-infirst-outschemeInsertionsareattherearofthequeueandremovalsareatthefrontofthequeueMainqueueoperations:enqueue(object):insertsanelementattheendofthequeueobjectdequeue():removesandreturnstheelementatthefrontofthequeueAuxiliaryqueueoperations:objectfront():returnstheelementatthefrontwithoutremovingitintegersize():returnsthenumberofelementsstoredbooleanisEmpty():indicateswhethernoelementsarestoredExceptionsAttemptingtheexecutionofdequeueorfrontonanemptyqueuethrowsanEmptyQueueExceptionElementaryDataStructures12ApplicationsofQueuesDirectapplicationsWaitinglinesAccesstosharedresources(e.g.,printer)MultiprogrammingIndirectapplicationsAuxiliarydatastructureforalgorithmsComponentofotherdatastructuresElementaryDataStructures13SinglyLinkedListAsinglylinkedlistisaconcretedatastructureconsistingofasequenceofnodesEachnodestoreselementlinktothenextnodenextelemnodeABCDElementaryDataStructures14QueuewithaSinglyLinkedListWecanimplementaqueuewithasinglylinkedlistThefrontelementisstoredatthefirstnodeTherearelementisstoredatthelastnodeThespaceusedisO(n)andeachoperationoftheQueueADTtakesO(1)timefrnodeselementsElementaryDataStructures15ListADT(§2.2.2)TheListADTmodelsasequenceofpositionsstoringarbitraryobjectsItallowsforinsertionandremovalinthe“middle”Querymethods:isFirst(p),isLast(p)Accessormethods:first(),last()before(p),after(p)Updatemethods:replaceElement(p,o),s(p,q)insertBefore(p,o),insertAfter(p,o),insertFirst(o),insertLast(o)remove(p)ElementaryDataStructures16DoublyLinkedListAdoublylinkedlistprovidesanaturalimplementationoftheListADTNodesimplementPositionandstore:elementlinktothepreviousnodelinktothenextnodeSpecialtrailerandheadernodesprevnextelemtrailerheadernodes/positionselementsnodeElementaryDataStructures17Trees(§2.3)Incomputerscience,atreeisanabstractmodelofahierarchicalstructureAtreeconsistsofnodeswithaparent-childrelationApplications:OrganizationchartsProgrammingenvironmentsComputers”R”UsSalesR&DManufacturingLaptopsDesktopsUSInternationalEuropeAsiaCanadaElementaryDataStructures18TreeADT(§2.3.1)WeusepositionstoabstractnodesGenericmethods:integersize()booleanisEmpty()objectIteratorelements()positionIteratorpositions()Accessormethods:positionroot()positionparent(p)positionIteratorchildren(p)Querymethods:booleanisInternal(p)booleanisExternal(p)booleanisRoot(p)Updatemethods:s(p,q)objectreplaceElement(p,o)AdditionalupdatemethodsmaybedefinedbydatastructuresimplementingtheTreeADTElementaryDataStructures19PreorderTraversal(§2.3.2)AtraversalvisitsthenodesofatreeinasystematicmannerInapreordertraversal,anodeisvisitedbeforeitsdescendantsApplication:printastructureddocumentMakeMoneyFast!1.MotivationsReferences2.Methods2.1Stock

Fraud2.2Ponzi

Scheme1.1Greed1.2Avidity2.3Bank

Robbery123546789Algorithm

preOrder(v)visit(v)for

eachchildwofv preorder(w)ElementaryDataStructures20PostorderTraversal(§2.3.2)Inapostordertraversal,anodeisvisitedafteritsdescendantsApplication:computespaceusedbyfilesinadirectoryanditssubdirectoriesAlgorithm

postOrder(v)for

eachchildwofv postOrder(w)visit(v)cs16/homeworks/todo.txt

1Kprograms/DDR.java

10KStocks.java

25Kh1c.doc

3Kh1nc.doc

2KRobot.java

20K931724568ElementaryDataStructures21BinaryTrees(§2.3.3)Abinarytreeisatreewiththefollowingproperties:EachinternalnodehastwochildrenThechildrenofanodeareanorderedpairWecallthechildrenofaninternalnodeleftchildandrightchildAlternativerecursivedefinition:abinarytreeiseitheratreeconsistingofasinglenode,oratreewhoseroothasanorderedpairofchildren,eachofwhichisabinarytreeApplications:arithmeticexpressionsdecisionprocessessearchingABCFGDEHIElementaryDataStructures22ArithmeticExpressionTreeBinarytreeassociatedwithanarithmeticexpressioninternalnodes:operatorsexternalnodes:operandsExample:arithmeticexpressiontreefortheexpression(2(a-1)+(3b))+-2a13bElementaryDataStructures23DecisionTreeBinarytreeassociatedwithadecisionprocessinternalnodes:questionswithyes/noanswerexternalnodes:decisionsExample:diningdecisionWantafastmeal?Howaboutcoffee?Onexpenseaccount?StarbucksIn‘NOutAntoine'sDenny’sYesNoYesNoYesNoElementaryDataStructures24PropertiesofBinaryTreesNotationn numberofnodese numberofexternalnodesi numberofinternalnodesh heightProperties:e=i+

1n=

2e-

1hih(n-

1)/2e

2hh

log2

eh

log2(n+

1)

-

1ElementaryDataStructures25InorderTraversalInaninordertraversalanodeisvisitedafteritsleftsubtreeandbeforeitsrightsubtreeApplication:drawabinarytreex(v)=inorderrankofvy(v)=depthofvAlgorithm

inOrder(v)if

isInternal(v)inOrder(leftChild(v))visit(