cs1010s lec8實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)

CS1010SLecture8:

ImplementingDataStructures15Oct2014SayingoftheWise"IhearandIforget.IseeandIremember.IdoandIunderstand."

--

Confucius

SomePhilosophyPythonislikechessEasytolearn,hardtomasterLevelsoflearningKnowledgeUnderstandingApplicationSecretRecipeforSuccessinCS1010FCDOINGIT(Gettinghandsdirtyandwritingcode)!LectureTrainingsRecitationTutorialMissionsLotsofOptional

TrainingsPythonyoushouldknowPythonStatements:defreturnlambdaif,elif,elsefor,while,

break,continueimportDataabstractionprimitives:tuplelistBelieveitornot:youalreadyknowmostofthePythonthatyouneedtoknowforCS1010S!!Re-Midtermon

17Oct2014(Fri)

@7pm

I3AuditoriumMake-UpLectureon18Oct2014(Sat)@10am

LT19,SoCToday’sAgendaTheGameofNimMoreWishfulThinkingUnderstandingSchemecodeSimpledatastructuresDesigningDataStructuresMultipleRepresentationsTheGameofNimTwoplayersGameboardconsistsofpilesofcoinsPlayerstaketurnsremovinganynumberofcoinsfromasinglepilePlayerwhotakesthelastcoinwinsLet’sPlay!!HowtoWriteThisGame?KeeptrackofthegamestateSpecifygamerulesFigureoutstrategyGluethemalltogetherLet’sstartwithasimplegamewithtwopilesStartwithGameStateWhatdoweneedtokeeptrackof?Numberofcoinsineachpile!GameStateWishfulthinking:

Assumewehave: defmake_game_state(n,m):

...wherenandmarethenumberofcoinsineachpile.WhatElseDoWeNeed? defsize_of_pile(game_state,p):... wherepisthenumberofthepile defremove_coins_from_pile(game_state,n,p):

... wherepisthenumberofthepileandnisthe

numberofcoinstoremovefrompilep.Let’sstartwiththegame

defplay(game_state,player):display_game_state(game_state)ifis_game_over(game_state):announce_winner(player)elifplayer=="human":play(human_move(game_state),"computer")elifplayer=="computer":play(computer_move(game_state),"human")Whathappensifweevaluate:

play(make_game_state(5,8),"mickey-mouse")TakeCareofErrorCondition

defplay(game_state,player):display_game_state(game_state)ifis_game_over(game_state):announce_winner(player)elifplayer=="human":play(human_move(game_state),"computer")elifplayer=="computer":play(computer_move(game_state),"human")

else:print("playerwasn'thumanorcomputer:",player)

DisplayingGameState

defdisplay_game_state(game_state):print("")print("Pile1:"+str(size_of_pile(game_state,1)))print("Pile2:"+str(size_of_pile(game_state,2)))print("")GameOverCheckingforgameover:

defis_game_over(game_state):returntotal_size(game_state)==0deftotal_size(game_state):returnsize_of_pile(game_state,1)+size_of_pile(game_state,2)Announcingwinner/loser:

defannounce_winner(player):ifplayer=="human":print("Youlose.Betterlucknexttime.")else:print("Youwin.Congratulations.")GettingHumanPlayer’sMovedefhuman_move(game_state):p=prompt("Whichpilewillyouremovefrom?")n=prompt("Howmanycoinsdoyouwanttoremove?")returnremove_coins_from_pile(game_state,int(n),int(p))defprompt(prompt_string):returninput(prompt_string)ArtificialIntelligencedefcomputer_move(game_state):pile=1ifsize_of_pile(game_state,1)>0else2print("Computerremoves1coinfrompile"+str(pile))returnremove_coins_from_pile(game_state,1,pile)Isthisagoodstrategy?GameStatedefmake_game_state(n,m): return(10*n)+mdefsize_of_pile(game_state,pile_number): ifpile_number==1: returngame_state//10 else: returngame_state%10defremove_coins_from_pile(game_state, num_coins,pile_number): ifpile_number==1: returngame_state–10*num_coins else: returngame_state-num_coinsWhatisthelimitationofthisrepresentation?AnotherImplementationdefmake_game_state(n,m):return(n,m)defsize_of_pile(game_state,p):returngame_state[p-1]AnotherImplementationdefremove_coins_from_pile(game_state,num_coins,pile_number):ifpile_number==1:returnmake_game_state(size_of_pile(game_state,1) -num_coins,size_of_pile(game_state,2))else:returnmake_game_state(size_of_pile(game_state,1),size_of_pile(game_state,2)-num_coins)ImprovingNimLetsmodifyourNimgamebyallowing“undo”O(jiān)nlyHumanplayercanundo,notComputerRemoveseffectofthemostrecentmovei.e.undomostrecentcomputerandhumanmoveHuman’sturnagainafterundoHumanenters”0”toindicateundoKeyInsightWeneedadatastructuretorememberthehistoryofgamestatesHistoryofgamestatesBeforeeachhumanmove,addthecurrentgamestatetothehistory.Whenundoing,RemovemostrecentgamestatefromhistoryMakethisthecurrentgamestateDatastructure:StackAstackisadatastructurewiththeLIFOproperty.LastIn,FirstOutItemsareremovedinthereverseorderinwhichtheywereadded.WishfulthinkingagainAssumewehavethefollowing:make_stack():returnsanew,emptystackpush(s,item):addsitemtostackspop(s):removesthemostrecentlyaddeditemfromstacks,andreturnsitis_empty(s):returns#tifsisempty,#fotherwiseStackoperationss=make-stack()pop(s)None:emptystack,nothingtopoppush(s,5)push(s,3)pop(s)3pop(s)5is_empty(s)TrueImplementastackashomeworkChangestoNimgame_stack=make_stack()defhuman_move(game_state):p=prompt("Whichpilewillyouremovefrom?")n=prompt("Howmanycoinsdoyouwanttoremove?")

ifint(p)==0:returnhandle_undo(game_state)else: push(game_stack,game_state)returnremove_coins_from_pile(game_state,int(n),int(p))ChangestoNimdefhandle_undo(game_state):old_state=pop(game_stack)ifold_state:display_game_state(old_state)returnhuman_move(old_state)else:print("Nomorepreviousmoves!")returnhuman_move(game_state)DataStructures:DesignPrinciplesWhendesigningadatastructure,needtospellout:SpecificationImplementationSpecification(contract)Whatdoesitdo?Allowsotherstouseit.ImplementationHowisitrealized?Usersdonotneedtoknowthis.Choiceofimplementation.Nim:Gamestatepiles,coinsineachpilesize,remove-coinMultiplerepresentations possibleSpecificationConceptualdescriptionofdatastructure.Overviewofdatastructure.Stateassumptions,contracts,guarantees.Giveexamples.SpecificationOperations:ConstructorsSelectors(Accessors)PredicatesPrintersExample:ListsSpecs:Alistisacollectionofobjects,inagivenorder.e.g.[],[3,4,1]Example:ListsSpecs:Constructors:Selectors:Predicates:Printer:list(),[][]type,inprintSets:SpecsAsetisanunorderedcollectionofobjects(numbers,inourexample)without

duplicates.e.g.{3,1,2},{1,2,3}arethesamee.g.empty_set

isemptysete.g.{3,3,1,2}isnotvalid!Sets:SpecsConstructors:make_set,adjoin_set,union_set,intersection_setSelectors:Predicates:is_element_of_set,is_empty_setPrinters:print_setSets:ContractForanysetsS,T,andanyobjectx>>>is_element_of_set(x,adjoin_set(x,S))TrueAdjoininganobjecttoasetproducesasetthatcontainstheobject.Sets:Contract>>>is_element_of_set(x,union_set(S,T))

isequalto

>>>is_element_of_set(x,S)oris_element_of_set(x,T)Theelementsof(unionST)aretheelementsthatareinSorinT.>>>is_element_of_set(x,empty_set)Noobjectisanelementoftheemptyset.etc…ImplementationChoosearepresentationUsuallytherearechoices,e.g.lists,treesDifferentchoicesaffecttime/spacecomplexity.Theremaybecertainconstraintsontherepresentation.Theseshouldexplicitlystated.e.g.inrationalnumberpackage,denom≠0ImplementationImplementconstructors,selectors,predicates,printers,usingyourselectedrepresentation.Makesureyousatisfyallcontractsstatedinspecification!Sets:Implementation#1Representation:unorderedlistEmptysetrepresentedbyemptylist.Setrepresentedbyalistoftheobjects.MusttakecaretoavoidduplicatesSets:Implementation#1Constructors:defmake_set():

’’’returnsanew,emptyset’’’

return[]Predicates:defis_empty_set(s):returnnotsSets:Implementation#1Predicates:defis_element_of_set(x,s):ifis_empty_set(s):returnFalseforeins:ife==x:returnTruereturnFalseTimecomplexity:O(n

),nissizeofsetSets:Implementation#1Constructors:defadjoin_set(x,s): ifnotis_element_of_set(x,s): s.append(x)#don’taddifalreadyin returnsTimecomplexity:O(n)Sets:Implementation#1Constructors:defintersection_set(s1,s2): <...........> return<.....>

leftasanexercise (Questionoftheday!)

Sets:Implementation#2Representation:orderedlistEmptysetrepresentedbyemptylist.Musttakecaretoavoidduplicates.Butnowobjectsaresorted.WHYWOULDWEWANTTODOTHIS?Sets:Implementation#2Note:specsdoesnotrequirethis,butwecanimposeadditionalconstraintsinimplementation.Butthisisonlypossibleiftheobjectsarecomparable,i.e.conceptof“greater_than”or“l(fā)ess_than”.e.g.numbers:<e.g.strings,symbols:lexicographicalorder(alphabetical)Notcolors:red,blue,greenSets:Implementation#2Constructors:defmake_set(): return[]#asbeforePredicates:defis_empty_set(s):returnnots#asbeforeSets:Implementation#2Predicates:defis_element_of_set(x,s):ifis_empty_set(s):returnFalseforeins:ife==x:returnTrueelife>x:returnFalsereturnFalseTimecomplexity:O(n),butfasterthanprevious!IntersectionSet1:(1348)Set2:(145689)

so1inintersection,moveset1,set2cursorforwardSet1:(348)Set2:(45689)

3<4,3notinintersection,forwardset1cursoronlyIntersectionSet1:(48)Set2:(45689)

so4inintersection,forwardset1,set2cursorSet1:(8)Set2:(5689)

8>5,5notinintersection,forwardset2cursoronlyIntersectionSet1:(8)Set2:(689)

8>6,6notinintersection,forwardset2cursorSet1:(8)Set2:(89)

so8inintersection,forwardset1,set2cursorIntersectionSet1:()Set2:(9)

set1empty,return()appendeverythingtogether:(148)Sets:Implementation#2Constructors:defintersection_set(s1,s2):ifis_empty_set(s1)oris_empty_set(s2):return[]result=[]i,j=0,0whilei<len(s1)andj<len(s2):ifs1[i]==s2[j]: result.append(s1[i])i=i+1 j=j+1 elifx1<x2: i=i+1

Sets:Implementation#2else:j=j+1returnresultTimecomplexity:O(n),fasterthanprevious!Sets:Implementation#3Representation:binarytreeEmptysetrepresentedbyemptytree.Musttakecaretoavoidduplicates.Objectsaresorted.Sets:Implementation#3Eachnodestores1object.Leftsubtreecontainsobjectssmallerthanthis.Rightsubtreecontainsobjectsgreaterthanthis.Sets:Implementation#3Threetreesrepresentingtheset{1,3,5,7,9,11}793511137195115937111Sets:Implementation#3Treeoperators:defmake_tree(entry,left,right): return(entry,left,right)defentry(tree): returntree[0]defleft_branch(tree): returntree[1]defright_branch(tree): returntree[2]Sets:Implementation#3Predicates:defis_element_of_set(x,s): ifis_empty_set(s): returnFalse elifx==entry(s): returnTrue elifx<entry(s): returnis_element_of_set(x,left_branch(s)) else: returnis_element_of_set(x,right_branch(s))Timecomplexity:O(logn)Sets:Implementation#3Adjoin:defadjoin_set(x,s): ifis_empty_set(s): returnmake_tree(x,[],[]) elifx==entry(s): returns elifx<entry(s): returnmake_tree(entry(s), adjoin_set(x,left_branch(s)), right_branch(s)) else: returnmake_tree(entry(s),left_branch(s), adjoin_set(x,right_branch(s))BalancingtreesOperationisO(logn)assumingthattreeisbalanced.Buttheycaneunbalancedafterseveraloperations.Unbalancedtreesbreakthelogncomplexity.Onesolution:defineafunctiontorestorebalance.Calliteverysooften.5791113QuestionoftheDayHowdoweconvertanunbalancedbinarytreeintoabalancedtree?Writeafunctionbalance_tree

thatwilltakeabinarytreeandreturnabalancedtree(orasbalancedasyoucanmakeit)MultiplerepresentationsYouhaveseenthatforcompounddata,multiplerepresentationsarepossible:e.g.setsas:Unorderedlists,w/oduplicatesOrderedlists,w/oduplicatesBinarytrees,w/oduplicatesMultiplerepresentationsEachrepresentationhasitspros/cons:Typically,someoperationsaremoreefficient,somearelessefficient.“Best”representationmaydependonhowtheobjectisused.Typicallyinlargesoftwareprojects,multiplerepresentationsco-exist.Why?ManypossiblereasonsBecauselargeprojectshavelonglifetime,andprojectrequirementschangeovertime.Becausenosinglerepresentationissuitableforeverypurpose.Becauseprogrammersworkindependentlyanddeveloptheirownrepresentationsforthesamething.MultiplerepresentationsTherefore,youmustlearntomanagedifferentco-existingrepresentations.Whataretheissues?Whatstrategiesareavailable?Whatarethepros/cons?Complex-arithmeticpackageRecall:complexnumbers 3+4i,i=√-1 x+iy ,x:realpart,y:imaginarypartTheaboveisrectangularform.Thereisalsopolar

form:z=x+iy=re

iAr:magnitudeA:angleAbstractionbarrierRectangularrepresentationPolarrepresentationComplex-arithmeticpackageProgramsthatusecomplexnumbersplex,plex,plex,plexBenhasprovidedthisAlyssahasprovidedthisYouwanttobuildthisArithmeticpackageSimilartorationalnumberpackage(Lecture7)Addition:z=z1+z2

real_part(z)=real_part(z1)+real_part(z2) imag_