數(shù)據(jù)結(jié)構(gòu)與算法分析-課件-宋霜-最終完整版

DataStructureandAlgorithmAnalysisinC++

數(shù)據(jù)結(jié)構(gòu)與算法分析（C++）SONGShuang宋霜TableofContentLectrure1:IntroductionLecture9:Graph(2)Lectrure2:OverviewofC++Lecture10:HashingLecture3:AlgorithmAnalysisLecture11:Sorting(1)Lecture4:LinearStructure(1)Lecture12:Sorting(2)Lecture5:LinearStructure(2)Lecture13:GreedyAlgorithmsLecture6:Tree(1)Lecture14:DivideandConquerLecture7:Tree(2)Lecture15:DynamicProgrammingLecture8:Graph(1)Lecture16:BacktrackingAlgorithmsLecture1

IntroductionContentPurposeofthiscourseMainContentsComputerProgramDataStructureAlgorithmPurpose/GoalsThiscoursedescribesdatastructures,methodsoforganizinglargeamountsofdata;AlgorithmHowtoevaluatethealgorithmHowtoimprovetheperformance.TextbookDataStructureandAlgorithmAnalysisinC++,4thedition,MarkAllenWeissIntroductiontoAlgorithms,3rdedition,ThomasH.CormenDataStructuresandAlgorithmAnalysis(C++Version),CliffordA.ShafferC++PrimerScore課堂成績15%作業(yè)15%FinalProject20%FinalExamination50%MainContentsLinearStructureTreeGraphSortingandsearchingAlgorithmdesigntechnologyDataStructureAlgorithmLanguageAlthoughthematerialinthiscourseislargelylanguage-independent,programmingrequirestheuseofaspecificlanguage.Asthetitleimplies,wehavechosenC++forthiscourse.GenericProgramming：class,template,STLHowtosolveaproblemwithcomputerMathematicModelAlgorithmProgrammingTesting&DebuggingRunningModelObjectRelationshipDataStructureWhatisprogramProgram=+DataStructureAlgorithmDataStructureIncomputerscience,adatastructureisaparticularwayoforganizingdata

inacomputersothatitcanbeusedefficiently.DataStructure=(D,S)DataChar‘a(chǎn)’‘9’Short1280Int-62000Float3.1415926Double2.675e-15StructStructStudent{

intNum;

charName[32];

floatScore;}StructNode{

intNum;

floatX;

floatY;}StructureSetLinearStructureTreeGraphSomeexamplesinmechanicalAsetofmechanicalpartsSomeexamplesinmechanicalIfwelistallthesepartsonebyoneinanexcelfile,wecanhavealist(linearstructure)oftheseparts.減速箱明細表SomeexamplesinmechanicalAnassembletreeSomeexamplesinmechanicalAPCBgraphStructureSetLinearStructureTreeGraphLogicalStructure&PhysicalStructureLogicalStructureLogicalrelationshipbetweendataSet,Linear,Tree,GraphPhysicalStructureHowtostorethedataphysicallySequentialstructure,ChainstructureExample8125379158512379158LCRC5LCRC12LCRC7LCRCSequentialstructureChainstructureDataTherelationshipbetweeneachdataHowtooperatethedataAbstractDataTypeAnabstractdatatype(ADT)isasetofobjectstogetherwithasetofoperations.ADT=(D,S,P)ExampleStackpushpoptopAlgorithmInformally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.ExampleSortingproblemInput:Asequenceofnnumbers(a1,a2,…an).Output:Areorderingsequence(a’1,a’2,…a’n)suchthata’1≤a’2,≤…≤a’nInsertionSortPropertiesFinitenessDefinitenessInputOutputEffectivenessHighefficiencyRobustnessEvaluateanalgorithmRunningtimeT(n)=O(f(n))SpacerequirementT(n)=O(f(n))f(n)=3n2+2n+1T(n)=O(3n2+2n+1)=O(n2)O(1)O(n)O(n2)A=a+1;O(1)for(i=0;i<n;i++){A=a+1;}O(n)for(i=1;i<n;i++)for(j=0;j<i;j++)A=a+1;O(n2)O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)DesignofAlgorithmsGreedyAlgorithmDivideandConquerDynamicProgrammingRandomizedAlgorithmBacktrackingAlgorithmMainContentsOverviewofC++AlgorithmAnalysisLinearStructureTreeGraphAlgorithmHashingSortingAlgorithmDesignTechnologyOverviewofC++MainlyreviewtheC++programminglanguage.Tosupportthelearningofthisclass,requiredprogrammingknowledgewillberecalledforthiscourse.AlgorithmAnalysisHowtoanalyseandevaluateanalgorithm.Theconceptofrunningtimewillalsobegiven.LinearStructureShowabasicdatastructure---thelinearstructure.Threetypes,thelist,thestack,andthequeuewillbeintroduced.Theoperationsthatworkontheselinearstructureswillalsobeshown.TreeIntroducethetreestructure.Theoperationsandalgorithms,suchasconstructionandtraversals,willalsobeintroduced.Binarysearchtreeanditsoperationwillalsobeintroduced.GraphAlgorithmThegraphstructure.Theoperationsandalgorithms,suchasconstruction,traversals,shortest-pathalgorithms,minimumspanningtree,willalsobementioned.SomediscussionofNP-Completenesswillalsobecarriedout.HashingConceptandoperationsofhashingtable.SortingShowthecommonsortingalgorithms,whichincludeinsertionsort,bubblesort,selectionsort,mergesort,quicksort,heapsortandradixsort.RunningtimeofthesealgorithmswillbeevaluatedandcomparedAlgorithmDesignTechnologyIntroducesomealgorithmdesigntechniques,suchasgreedyalgorithms,divideandconquer,dynamicprogrammingandbacktrackingalgorithms.Recursionf(x)=kx+bf(n)=f(n-1)+n*nf(0)=0RulesBasecasesf(0)=0Makingprogressf(n)=f(n-1)+n*nDesignrule.Assumethatalltherecursivecallswork.Compoundinterestrule.Neverduplicateworkbysolvingthesameinstanceofaprobleminseparaterecursivecalls.FibonaccisequenceF（0）=0，F(xiàn)（1）=1，F(xiàn)（n）=F(n-1)+F(n-2)（n≥2，n∈N*）HomeworkPleasegiveanexampleofthedatastructureandalgorithmthatusedinyourproject.Lecture2

OverviewofC++HelloWorld#include<stdio.h>intmain(){printf(“HelloWorld!\r\n”);return0;}#include<iostream>usingnamespacestd;intmain(){cout<<“HelloWorld”<<endl;return0;}#include<iostream>intmain(){

std::cout<<“HelloWorld”<<std::endl;return0;}namespace命名空間::scopeoperator作用域操作符CC++stdiovsiostreamprintfinta=10;doubleb=5.5;charc=‘a(chǎn)’;printf(“a=%d,b=%f,c=%c\r\n”,a,b,c);coutinta=10;doubleb=5.5;charc=‘a(chǎn)’;cout<<“a=“<<a<<“,b=“<<b<<“,=“<<c<<endl;scanfinta;floatb;charc;scanf(“%d%f%c”,&a,&b,&c);cininta;doubleb;charc;cin>>a>>b>>c;Comments

（注釋）TherearetwokindsofcommentsinC++:single-lineandpaired.Single-linecomment(單行注釋)Asingle-linecommentstartswithadoubleslash(//)andendswithanewline.Everythingtotherightoftheslashesonthecurrentlineisignoredbythecompiler.Acommentofthiskindcancontainanytext,includingadditionaldoubleslashes.Pairedcomment（成對注釋）Pairedcommentusestwodelimiters(/*and*/)thatareinheritedfromC.Suchcommentsbeginwitha/*andendwiththenext*/.Thesecommentscanincludeanythingthatisnota*/,includingnewlines.Thecompilertreatseverythingthatfallsbetweenthe/*and*/aspartofthecomment.ExerciseIndicatewhich,ifany,ofthefollowingoutputstatementsarelegal:std::cout<<"/*";std::cout<<"*/";std::cout<</*"*/"*/;std::cout<</*"*/"/*"/*"*/;WhyiscommentsimportantForyourselfandforothersIncomputerprogramming,acommentisaprogrammer-readableannotationinthesourcecodeofacomputerprogram.TheyareaddedwiththepurposeofmakingthesourcecodeeasiertounderstandCodeTellsYouHow,CommentsTellYouWhyNamingconvention

（命名規(guī)則）Incomputerprogramming,anamingconventionisasetofrulesforchoosingthecharactersequencetobeusedforidentifierswhichdenotevariables,types,functions,andotherentitiesinsourcecodeanddocumentation.Reducetheeffortneededtoreadandunderstandsourcecode;Toenablecodereviewstofocusonmoreimportantissuesthanarguingoversyntax(語法)

andnamingToenhancesourcecodeappearance(forexample,bydisallowingoverlongnamesorunclearabbreviations).Array

(數(shù)組)Incomputerscience,anarraydatastructure,orsimplyanarray,isadatastructureconsistingofacollectionofelements(valuesorvariables),eachidentifiedbyatleastonearrayindexorkey.inta[10];12345678910a[4]a[8]a[0]Attentioninta[];//errorinta[5];//it’sOK.a={1,2,3,4,5}//errora[3]=4;//rightintb[5]=a;//errorb=a;//errorb[2]=a[1];//rightPointer

(指針)Incomputerscience,apointerisaprogramminglanguageobject,whosevaluerefersto(or"pointsto")anothervaluestoredelsewhereinthecomputermemoryusingitsaddress.inta=10;int*b=&a;int*c;c=&a;int*d;d=c;Var(變量)Address(地址)Contents（內(nèi)容）a0x0114FC4810b0x0114FC3C0x0114FC48c0x0114FC300x0114FC48d0x0114FC240x0114FC48ArrayandPointerinta[10]={1,2,3};int*b=a;a[2],b[2]*(a+2),*(b+2)for(inti=0;i<10;i++){a[i]=i;b[i]=i;*(a+i)=i;*(b+i)=i;}Thesefourhavethesameresult.ArrayandPointerinta[10]={1,2,3};int*b=a;b++;b[0]=?b=b+3;b[0]=?a++;a[0]=?a=a+3;a[0]=?ArrayandPointerint*a1[3]int(*a2)[3]int*b;a1[0]=b;intc[10][3];a2=c;a2[5][2]=4;intc2[3];a2=c2?a2=&c2;Itisanarray,eachelementisapointerItisapointer.Itpointstoanarraywith3elementserrorFlowofControl

(控制流)whiledowhileforifswitchcasegotoExampleCalculate1+2+3+…+100？What’sthedifferencebetweenwhileanddowhileExample2IfandswitchFunction

（函數(shù)）Incomputerprogramming,asubroutine(子程序)isasequenceofprograminstructionsthatperformaspecifictask,packagedasaunit.Afunctiondefinitiontypicallyconsistsofareturntype,aname,alistofzeroormoreparameters,andabody.intadd(inta,intb){returna+b;}ArgumentPassing

(參數(shù)傳遞)Passedbyvalue(按值傳遞)Passedbyreference(引用傳遞)Examplevoidswap(inta,intb){intc;c=a;a=b;b=c;}inta1,a2;a1=10;a2=5;swap(a1,a2);//PassedbyvaluePassedbyvaluePassedbyreferenceCC++ReferenceandPointerReferencePointerinta=10;int&r=a;r=5;inta=10;int*r=&a;*r=5;Areferencemustbeinitializedwhenitiscreated.(Pointerscanbeinitializedatanytime.)Onceareferenceisinitializedtoanobject,itcannotbechangedtorefertoanotherobject.(Pointerscanbepointedtoanotherobjectatanytime.)YoucannothaveNULLreferences.Youmustalwaysbeabletoassumethatareferenceisconnectedtoalegitimatepieceofstorage.BrainStorming

(頭腦風(fēng)暴)inta,b,c;c=a;a=b;b=c;Canyouchangethevaluesofaandbwithoutathirdvaluec?Functionpointerandpointerfunctionint*f(intx,inty){}//pointerfunctionfisafunction,itreturnsapointerint(*f)(intx,inty){}//functionpointerfisapointer,itpointstoafunctionExampleDefineandConstCC++#defineMAX1024constintMAX=1024#definemax(a,b)((a)>(b)?(a):(b))inlineintmax(inta,intb){returna>b?a:b;}Class（類）ClassMembers(類成員)Constructors(構(gòu)造函數(shù))MemberFunctions(成員函數(shù))constructorinitializerlist構(gòu)造函數(shù)初始化列表ConstructorandDestructor

（構(gòu)造函數(shù)與析構(gòu)函數(shù)）Class（類）Mostfundamentally,aclassdefinesanewtypeandanewscope.Thefundamentalideasbehindclassesaredataabstraction（抽象）

andencapsulation（封裝）Abstraction（抽象）Dataabstractionisaprogramming(anddesign)techniquethatreliesontheseparationofinterfaceandimplementation.Theclassdesignermustworryabouthowaclassisimplemented,butprogrammersthatusetheclassneednotknowaboutthesedetails.Instead,programmerswhouseatypeneedtoknowonlythetype'sinterface;theycanthinkabstractlyaboutwhatthetypedoesratherthanconcretelyabouthowthetypeworks.Encapsulation（封裝）Encapsulationisatermthatdescribesthetechniqueofcombininglower-levelelementstoformanew,higher-levelentity.Afunctionisoneformofencapsulation:Thedetailedactionsperformedbythefunctionareencapsulatedinthelargerentitythatisthefunctionitself.Encapsulatedelementshidethedetailsoftheirimplementation.Wemaycallafunctionbuthavenoaccesstothestatementsthatitexecutes.Inthesameway,aclassisanencapsulatedentity:Itrepresentsanaggregationofseveralmembers,andmost(well-designed)classtypeshidethemembersthatimplementthetype.Encapsulation(封裝)Byusingtheprivateword,youcanhidethemembervariable.Userscanonlyaccessthesevaluesthroughmemberfunctions.Inheritance(繼承)Inobject-orientedprogramming,inheritanceiswhenanobjectorclassisbasedonanotherobjectorclass,usingthesameimplementation(inheritingfromanobjectorclass)specifyingimplementationtomaintainthesamebehaviour(realizinganinterface;inheritingbehaviour).Itisamechanismforcodereuseandtoallowindependentextensionsoftheoriginalsoftwareviapublicclassesandinterfaces.Inheritance(繼承)StructureandClass(結(jié)構(gòu)體與類)Structure(C)Class(C++)ExampleStructstu{intnum;charname[20];intage;int(*getScore)();}Classstu{stu();private:intnum;charname[20];intagepublic：intGetScore();}MemberFunction(成員函數(shù))NYAccess(權(quán)限)publicPrivate,publicInheritance(繼承)NYDesign(設(shè)計)SeparateoperationsfromdataData+operationsTemplate(模板)TemplatesareafeatureoftheC++programminglanguagethatallowsfunctionsandclassestooperatewithgenerictypes.Thisallowsafunctionorclasstoworkonmanydifferentdatatypeswithoutbeingrewrittenforeachone.Template(模板)Function:compareintcompare(inta,intb);intcompare(doublea,doubleb);intcompare(chara,charb);{

returna>b?1:0;}Template(模板)Function:compareintcompare(inta,intb);intcompare(doublea,doubleb);intcompare(chara,charb);{

returna>b?1:0;}Overload重載C++FunctionTemplate(函數(shù)模板)Function:comparetemplate<typenameT>intcompare(Ta,Tb);{

returna>b?1:0;}ClassTemplate(類模板)STLTheStandardTemplateLibrary(STL)isasoftwarelibraryfortheC++programminglanguagethatinfluencedmanypartsoftheC++StandardLibrary.Itprovidesfourcomponentscalledalgorithms,containers,functional,anditerators.VectorVectorsaresequencecontainersrepresentingarraysthatcanchangeinsize.SequenceElementsinsequencecontainersareorderedinastrictlinearsequence.Individualelementsareaccessedbytheirpositioninthissequence.DynamicarrayAllowsdirectaccesstoanyelementinthesequence,eventhroughpointerarithmetics,andprovidesrelativelyfastaddition/removalofelementsattheendofthesequence.Allocator-awareThecontainerusesanallocatorobjecttodynamicallyhandleitsstorageneeds./reference/vector/vector/HomeworkWriteafunctiontemplateswap3,for3inputnumbers,a1,a2,a3,afterthisfunction,a1>=a2>=a3.Writeaclasstemplatetorealizea“stack”structure.AnexampleofprogrammingHowitworks?WhatdoIhave?MessageBased,EventDrivenMSGmsg;while(GetMessage(&msg,NULL,NULL,NULL)){TranslateMessage(&msg);DispatchMessage(&msg);}InitializethemapReceiveanddispatchMSGHandleMSGButtonDownButtonUpTimerPaintLeftRightBothFunctionFunctionFunctionMapDataLecture3

AlgorithmAnalysisAlgorithmAnalgorithmisaclearlyspecifiedsetofsimpleinstructionstobefollowedtosolveaproblem.Onceanalgorithmisgivenforaproblemanddecided(somehow)tobecorrect,animportantstepistodeterminehowmuchinthewayofresources,suchastimeorspace,thealgorithmwillrequire.PropertiesFiniteness(有窮性)Definiteness(確定性)Input(輸入)Output(輸出)Effectiveness(可行性)Highefficiency(高效)Robustness(魯棒性)ContentsofthislectureHowtoestimatethetimerequiredforaprogram.Howtoreducetherunningtimeofaprogram.MathematicalBackgroundDefinition1

T(N)=O(f(N)),iftherearepositiveconstantscandn0,suchthatT(N)<=cf(N)whenN>=n0.

T(N)=1000N,f(N)=N^2;c=1,n0=1000,T(N)<=cf(N)whenN>=n0.T(N)=1000Nf(N)=N^2MathematicalBackgroundDefinition2

T(N)=Ω(f(N)),iftherearepositiveconstantscandn0,suchthatT(N)>=cf(N)whenN>=n0.

T(N)=N2,f(N)=1000N;c=1,n0=1000,T(N)>=cf(N)whenN>=n0.MathematicalBackgroundDefinition3

T(N)=Θ(f(N)),ifandonlyifT(N)=O(f(N))andT(N)=Ω(f(N)).

T(N)=2N2,f(N)=N2+2N;c=1,n0=2,T(N)>=cf(N)whenN>=n0.c=2,n0=1,T(N)<=cf(N)whenN>=n0.MathematicalBackgroundDefinition4

T(N)=o(f(N)),ifforallpositiveconstantsc,thereexistsann0suchthatT(N)<cf(N)whenN>n0.T(N)=o(f(N)),ifT(N)=O(f(N)),andT(N)≠Θ(f(N)MathematicalBackgroundRelativeratesofgrowth(相對增長率)WhenwesaythatT(N)=O(f(N)),weareguaranteeingthatthefunctionT(N)

growsataratenofasterthanf(N);thusf(N)isanupperboundonT(N);T(N)isalowerboundonf(N).T(N)=O(f(N))=>f(N)=Ω(T(N))UsingBig-OhnotationTtisverybadstyletoincludeconstantsorlow-ordertermsinsideaBig-Oh.DonotsayT(N)=O(2N2)orT(N)=O(N2+N).Inbothcases,thecorrectformisT(N)=O(N2).ThismeansthatinanyanalysisthatwillrequireaBig-Ohanswer,allsortsofshortcutsarepossible.Lower-ordertermscangenerallybeignored,andconstantscanbethrownaway.Considerablylessprecisionisrequiredinthesecases.SomerulesTypicalGrowthRatesfunctionNamecconstantlogNlogarithmiclog2NLog-squaredNLinearNlogNN2quadraticN3cubic2NexponentialWecanalwaysdeterminetherelativegrowthratesoftwofunctionsf(N)

andg(N)bycomputinglimN→∞f(N)/g(N).Thelimitcanhavefourpossiblevalues:Findtwofunctionsf(N)andg(N)suchthatneitherf(N)=O(g(N))norg(N)=O(f(N)).NlogNvsN1.5f(N)=NlogNg(N)=N1.5NlogNvsN1.5logN

vsN0.5log2N

vsNlog2NisbetterNlogNisbetterGeneralRules1:forloops(for循環(huán))Therunningtimeofaforloopisatmosttherunningtimeofthestatementsinsidetheforloop(includingtests)timesthenumberofiterations.2:nestedloops(嵌套循環(huán))Analyzetheseinsideout.Thetotalrunningtimeofastatementinsideagroupofnestedloopsistherunningtimeofthestatementmultipliedbytheproductofthesizesofalltheloops.GeneralRules3:consecutivestatements(順序語句)Thesejustadd.4:if/elsetherunningtimeofanif/elsestatementisnevermorethantherunningtimeofthetestplusthelargeroftherunningtimesofS1andS2.Example11+2+3+…+Nsum=0;for(i=1;i<=N;i++)sum+=i;O(N)Example2sum=0;for(i=1;i<=N;i++)

for(j=0;j<i;j++)sum+=i*j;O(N2)Example3sum=0;for(i=1;i<=N;i++)sum+=i;for(i=1;i<=N;i++)

for(j=0;j<i;j++)sum+=i*j;O(N2)+O(N)=O(N2)Example4xnO(logN)FibonacciSequence

(斐波那契數(shù)列)F(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2);FibonacciSequence

(斐波那契數(shù)列)F(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2);O(N)T(N)=T(N?1)+T(N?2)+2FibonacciSequence

(斐波那契數(shù)列)Canwefutureimproveouralgorithm?O(logN)MaximumSubsequenceSum

(最大子序列和問題)

O(N3)O(N2)O(NlogN)O(N)ExerciseAnalgorithmtakes0.5msforinputsize100.Howlongwillittakeforinputsize500iftherunningtimeisthefollowing(assumelow-ordertermsarenegligible)?a.linearb.O(NlogN)c.quadraticd.cubicLecture4

LinearStructureIADT(抽象數(shù)據(jù)類型)Anabstractdatatype(ADT)isasetofobjectstogetherwithasetofoperationsDataTherelationshipbetweeneachdataHowtooperatethedataADT=(D,S,P)NotesThereisnoruletellinguswhichoperationsmustbesupportedforeachADT;thisisadesigndecision.Errorhandling(錯誤處理)

andtiebreaking(結(jié)構(gòu)調(diào)整)(whereappropriate)arealsogenerallyuptotheprogramdesignerTheimplementationcanbedoneinseveralways,butiftheyaredonecorrectly,theprogramsthatusethemwillnotnecessarilyneedtoknowwhichimplementationwasused.TheListADTData:A0,A1,A2,…An,datawiththesametype.nisthelistsize.n=0iscalledanemptylistStructureAifollows(orsucceeds)(后繼)Ai-1

(i<N)andthat

Ai?1precedes(前驅(qū))

Ai(i>0).OperationprintList,makeEmpty,insert,remove,findADT=(D,S,P)ImplementationArrayLinkedlistDoublylinkedlistA0A1A2A3A4A5A6ArraybasedListAnarrayimplementationallowsprintListtobecarriedoutinlineartime,andthefindKth

operationtakesconstanttime,whichisasgoodascanbeexpected.However,insertion

anddeletionarepotentiallyexpensive,dependingonwheretheinsertionsanddeletionsoccur.ArraybasedList123456717234561734562ArraybasedListArraybasedListArraybasedList1723456173456LinkedListInordertoavoidthelinearcostofinsertionanddeletion,weneedtoensurethatthelistisnotstoredcontiguously,sinceotherwiseentirepartsofthelistwillneedtobemoved.Thelinkedlistconsistsofaseriesofnodes,whicharenotnecessarilyadjacentinmemory.Eachnodecontainstheelementandalinktoanodecontainingitssuccessor.Wecallthisthenextlink.Thelastcell’snextlinkpointstonullptr.LinkedList12345NULL712345NULL7LinkedList127345NULLDelete(3)P0P1LinkedList127345NULLReverse543721NULLprecurnextcur->next=prepre=curcur=nextnext=next->nextDoublyLinkedList1n234567n8DoublyLinkedList45Insert(7)p1DoublyLinkedListdelete(4)345pp->next->pre=p->prep->pre->next=p->nextdeletep;p=NULL;Notesforusingpointerint*a,b;intd=10;a=&d;b=&d;Notesforusingpointertypedefint*int_p;int*a,b;intd=10;a=&d;b=&d;Notesforusingpointerint*a=NULL;a=newint[10];a[0]=1;int*b=NULL;voidf(int*c){

c=newint[10];}f(b);b[0]=1;NotesforusingpointerNotesforusingpointerMemoryDistributionStack(棧區(qū))Heap(堆區(qū))Static(全局區(qū)/靜態(tài)區(qū))文字常量區(qū)程序代碼區(qū)Lecture5

LinearStructureIIStackADTAstackisalistwiththerestrictionthatinsertionsanddeletionscanbeperformedinonlyoneposition,namely,theendofthelist,calledthetop.Thefundamentaloperationsonastackarepush,whichisequivalenttoaninsert,andpop,whichdeletesthemostrecentlyinsertedelement.LIFO(Lastin,Firstout)NoteApoportoponanemptystackisgenerallyconsideredanerrorinthestackADT.RunningoutofspacewhenperformingapushisanimplementationlimitbutnotanADTerror.ImplementationSinceastackisalist,anylistimplementationwilldo.LinkedListImplementationofStacksArrayImplementationofStacksNoticethattheseoperationsareperformedinnotonlyconstanttimebutveryfastconstanttime.Onsomemachines,pushesandpops(ofintegers)canbewritteninonemachineinstruction,operatingonaregisterwithauto-incrementandauto-decrementaddressing.Thefactthatmostmodernmachineshavestackoperationsaspartoftheinstructionsetenforcestheideathatthestackisprobablythemostfundamentaldatastructureincomputerscience,afterthearray.QueueADTLikestacks,queuesarelists.Withaqueue,however,insertionisdoneatoneendwhereasdeletionisperformedattheotherend.QueueModelenqueueinsertsanelementattheendofthelist(calledtherear)Dequeuewhichdeletes(andreturns)theelementatthestartofthelist(knownasthefront)FIFO(Firstin,Firstout)frontback1frontbackenqueue(1)1234frontbackenqueue(2),

enqueue(3),

enqueue(4),dequeuesize=back-frontisEmpty:Size==0?Back==front?q1[back++]=1;intq1[10];Returnq1[front++];Bewareofsizea=?7preferredMayleadtoseriousbug

anditishardtobefound.frontback1frontbackenqueue(1)1234frontbackenqueue(2),

enqueue(3),

enqueue(4),dequeuesize=back-frontisEmpty:0==Size?Back==front?q1[back++]=1;intq1[10];Returnq1[front++];BewareofsizeCircularQueue(循環(huán)隊列)123456789frontbackenqueue(10)12345678910frontbackenqueue(11)112345678910frontbacksizeisFull?isEmpty?(back+MaxLen-front)%MaxLensize==MaxLen-1size==0++back;If(back==MaxLen)

back=0;ApplicationsofQueuesVirtuallyeveryreal-lifelineis(supposedtobe)aqueue.Forinstance,linesatticketcountersarequeues,becauseserviceisfirst-comefirst-served.Printqueue.ApplicationsofStackBalancingSymbols(平衡符號)PostfixExpressions(后綴表達式)InfixtoPostfixConversion(中綴到后綴的轉(zhuǎn)換)BalancingSymbolsCheckwhethereverythingisbalanced.Everyrightbrace,bracket,andparenthesismustcorrespondtoitsleftcounterpart.Pairedsymbolssuchasbegin/end,/**/,andsoon.ExampleCheckifthefollowingexpressionisbalance{[()({[]})]}{[(()(]})]}Howtocheckitwithprogram?BalancingSymbolsMakeanemptystack.Readcharactersuntilendoffile.Ifthecharacterisanopeningsymbol,pushitontothestack.Ifitisaclosingsymbolandthestackisempty,reportanerror.Otherwise,popthestack.Ifthesymbolpoppedisnotthecorrespondingopeningsymbol,thenreportanerror.Atendoffile,ifthestackisnotempty,reportanerror.Example{[()({[]})]}{[(()(]})]}{[{([{([{([{{([{[{([{[{([{{([{([{[{{{[{([{(([{(([{(([{(([{InfixandPostfixExpressions5+7*3-(6*2+1)/10infix573*+62*1+10/-postfixApplicationofPostfixExpressions5+7*3-(6*2+1)/10infix573*+62*1+10/-postfixHowtocalculatetheaboveexpressionwithprogramWhenanumberisseen,itispushedontothestackWhenanoperatorisseen,theoperatorisappliedtothetwonumbers(symbols)thatarepoppedfromthestackPushtheresultbacktothestack.Example5+7*3-(6*2+1)/