讲义数据结构-chapter

DataStructure&inAdamFuChapterThepurposeandcontentsoftheIntroducemostuseddatastructuresandPrerequisiteofotherIntroduce ReviewJavaandThepurposeandcontentsofthe IntroducemostuseddatastructuresandUseproperdatastructurestosolvedifferentExampleGameManagementoflibrarycataloguebyManagementofthetrafficlightsinThebook:selectionsolveapopularwordThepurposeandcontentsoftheExampleNextxhasfiveThepurposeandcontentsoftheExample1usesatreeThepurposeandcontentsoftheExample2:ManagementoflibrarycataloguebySartajItisalinearThepurposeandcontentsoftheExampleManagementofthetrafficlightsinBThisisa

C,Eareone-wayroad,thereare13pathtogo.CDAECangoatthesametime: CDAECannotgoatthesametime: Thepurposeandcontentsofthe2.PrerequisiteofotherPrinciplesofcompiling:usestacktocomputeexpressionandimplementrecursiveprocedureOperatingSystem:usequeuetoimplementjob Database:useB-tree,B+treetoorganize,storeandloadmassivedatainthehardmemory.ThepurposeandcontentsoftheBasicmethodsof standardsoftheperformanceofan timecomplexity, spacecomplexity,andaccuracyexample:sortingn-1+n-2+….+2+1=n(n-1)/2=(n2-Review andWhatisDataisthecarrierofDataisasetofnumbers,characters,andothersymbolsthatcanbeusedtodescribetheobjectiveThesesymbolscanbeinputintocomputers,identifiedandprocessedbythecomputerWhatisData andividedintotwoclasses:numericaldata:int,float,complex,……non-numericaldata:character,string,graph,WhatisData２.DataAdatastructureisadataobjecttogetherwiththerelationshipsamongthedatamembersthatcomposetheobjectＤisadataRisalimitedsetofrelationshipsofallthedatamembersinD.WhatisDataData

LinearNon-linear WhatisData 数据的物理结 从具体实现视图看，是面向计算机的学生表：逻辑结 线性物理结构-----数组 ,删除,查ADTandDataDefinition:isasetofvaluestogetherwithaoperationsetthatoperateonthesetypevalueset:{……,-2,-operation {+,-,*,/,%,ADTandMostoftheprogramminglanguagesprovideagroupofpredefineddatatype.Atomdatatype—int,float,double……Structuredatatype—array,struct,……ADTand Data是将类型和与这个类型有关的操作集合封装在一起的数据模型:isamethodusedtohidetheintx:ofintdata

floatx,y::offloatdatatypedata

ADTandisanewprogrammingmethodparttheusageandimplementation,inordertoencapsulateandhide思想将数据类型的使用与它的表示（机内 ）、实现（机内操作的实现）分开。更确切的说，把一个数据类型示及在这个类上的操实现封装到一个程序模块中，用户不必知道它。ADTNaturalNunber objects一个整数的有序子集合,它开始Zero(end

ADTandobject-object:attributevalues+ 一个几何对attributevalues:左上角坐标,右下角坐标,边线颜色 颜operates:setEdgeColor(c);setInterColor(c)ADTandclass:objectsofsameattributesandoperates.aninstanceisanobjectoftheclass.differentobjecthasdeferentattribute

ADTandbaseclass—integratethesamepart(includingattributesandoperations)inallthederivedclassesderivedclass—addthespecificattributesExample:baseclass—polygonderivedclass—ADTand eachclassobjectcommunicatewithothersusingmessages.Message:instructionsthatoneclassobjectusedinordertorequireanotherclassobjecttoperformsomeoperation.AlgorithmAlgorithm:anoperationsequenceofsolutingaproblemCharacteristic:initialsequenceAlgorithmProgram:iswrittenbylanguagesthatcanbeperformedbymachine.can’tsatisfythefiniteness.Forexample,OS.Algorithm:hasmultipledescriptivemethods,suchaslanguage,graph,table.Algorithmvoidselectsort(inta[],int for(inti=0;i<n-1; intk=for(intj=i+1;j<n; if(a[j]<a[k])k=j;inttemp=a[i];a[i]=a[k];a[k]=}}

MathematicsXaXb=Xa+b(Xa)b=XabXN+XN=2XN2N+2N=2N+1MathematicsLogarithms(alllogarithmsaretothebaseDEFINITIONXA=B ifandonlyif logXB=ATHEOREM1.1logAB=logCB/logCA;A,B,C>0,A!=1THEOREM1.2logAB=logA+logB;A,B>2i=1+21+22+……+2N=2N+1-Ni=1+2+3+……+N=MathematicsModularWesaythatAiscongruenttoBmodularN,writtenAB(modN),ifNdividesA-B.Example:81611(mod10)MathematicsThePWord证明方法Proofby stepisprovingabasetheNextstapaninductivehypothesisisassumed.theoremisassumedtobetrueforallcasesuptosomelimitk.Usingthisassumption,thetheoremthenshowntobetrueforthenextvalue,whichistypicallyk+1.Thisprovesthetheorem(aslongaskisfinite).Example:MathematicsProofbyProofbycontradictionproceedsbyassumingthatthetheoremisfalseandshowingthatthisassumptionimpliesthatsomeknownpropertyisfalse,andhencetheoriginalassumptionwasExample:proofthatthereisaninfinitenumberofABriefIntroductiontodefineafunctionf,validonnonnegativef(x)

x=2f(x-1)+ x>f(1)=1,f(2)=6,f(3)=21,f(4)=publicstaticintf(int if(x==0)//basereturnelsereturn2*f(x-1)+x*x;//recursive}ABriefIntroductiontoAnonterminatingrecursivemethod:publicstaticintbad(intn) if(n==returnelsereturnbad(n/3+1)+n-}twofundamentalrulesofBaseMakingABriefIntroductionto1)direct2)indirectExample1factorial

n>1(recursivef(5)=5f(4)=5*4f(staticlongfactorial(int if(n<=returnelsereturnn*factorial(n-1}ABriefIntroductiontopublicclass publicstaticvoidmain(String[]args System.out.Println(“pleaseenteranonnegativeinteger”intn=MyInput.readInt(Syatem.out.println(“Factorialof“+n+“is“+factorial(n)}staticlongfactorial(int{if(n<=1)returnelsereturnn*factorial(n-}}ABriefIntroductiontoExample2:ComputeFibonacci0,1,1,2,3,5,8,13,21,34,fib(0)=fib(1)=fib(n)=fib(n-2)+fib(n-1);publicstaticlongfib(long if((n==0)||(n==1)return}

returnfib(n-1)+fib(n-ComputeABriefIntroductiontopublicclass publicstaticvoidmain(Stringargs[ System.out.println(“EnteranindexfortheFibonaccinumber“);intn=MyInput.readInt();System.out.println(“Fibonaccinumberatindex“+n+“is“}publicstaticlongfib(long if((n==0)||(n==1))return1;returnfib(n-1)+fib(n-}}ABriefIntroductiontoExamplecomputesthesumoftheelementsa[0]througha[n-1]a[0],a[1],…,a[n-2],a[n-1]ABriefIntroductiontopublicstaticintRsum(int[]a,int{ifreturnRsum(a,n-1)+a[n-return} a1a2 ABriefIntroductiontoExample{a,b,c}:abc,acb,bac,bca,cab,cbapermutationofnelementshasn!下面在黑板上来分析该问题ABriefIntroductiontopublicstaticvoidperm(Char[]list,intk,int intif(k==m){for(i=0;i<=m;i++)cout<<list[i];cout<<endl;}else{for(i=k;i<=m;{swap(list[k],list[i]);perm(list,k+1,m);swap(list[k],list[i]);}}}ABriefIntroductiontoExample5:Hanoitower publicvoidmoveDISKs(intn,charfromTower,if(n=Movedisk1fromthefromTowertothetoTower;{moveDISKs(n-1,fromTower,auxTower,toTower);MovedisknfromthefromTowertothetoTower;}ABriefIntroductiontopublicclass publicstaticvoidmain(String[] System.out.printLn(“Enternumberofdisks”intn=MyInput.readInt(System.out.printLn(“Themoveare:”);moveDISKs(n,‘A’,‘B’,‘C’);}publicstaticvoidmoveDISKs(intn,charfromTower,toTower,char{if(n=System.out.printLn(“movedisk“+n+“fromfromTower+”to”+ moveDISKs(n-1,fromTower,auxTower,toTower);System.out.printLn(“Movedisk“+n+“from“+fromTower+“to“+toTowermoveDISKs(n-1,auxTower,toTower,}}GenericObjectsinThroughoutthistext,wewilldescribealgorithmsdatastructuresthataretype nongenericclass genericclassGenericObjectsinIntCellpublicclass publicIntCell(){this(0);publicIntCell(intinitialValue stoedValue=initialValue;publicintread(){returnstoredValue;}publicvoidwrite(intx){storedValue=x;}privateint}GenericObjectsinpublicandmembleofpublic:maybeaccessedbyanymethodinclassmemberofprivate:mayonlybeaccessedbymethodsitsspecifierisomitted(package-friendlyvisibility)adatamemberwhosevisibilityspecifierisomittedisvisibletootherclassesinthesamepackage.GenericObjectsinAclassmaydefinemethodsthatdescribehowaninstanceoftheclassisconstructed;thesearecalledIfnoconstructorisexplicitlydefined,onethatinitializesthefieldsusinglanguagedefaultsisautomatically

GenericObjectsin Inmanycases,thezero-parameterconstructorcanbeimplementedbycallinganatherconstructor.Byusingthis,weavoidreplicatingcodelogicseparateAdifferentuseofthisisasareferencetothebeingactedGenericObjectsinpublicclass publicstaticvoidmain(String[]args IntCellm=newIntCell(m.write(5System.out.println(“Cellcontents:“+m.read()}}GenericObjectsinstaticandThemainmethodmustbestatic,meanimgthatitappliestotheTestIntCellclassinsteadofasingleinstanceoftheclass.Eachclassmaydeclareamainmethodthatwillusedwhenthejavainterpreteriscalledforthat 下ObjectObjectsarecreatedbyusingGenericObjectsinMethodm.read( //beGenericObjectsinMemoryCelldesignaclassthatworksforanytypeofObject. sortingof a0,a1,a2,a3,……an- intAbc(inta,intb,int{returna+b+b*c+(a+b- floatAbc(floata,floatb,float{returna+b+b*c+(a+b- GenericObjectsinprogram1.1and1.2differonlyinthedatatypeoftheformalparametersandofthevaluereturned.Wecanwriteagenericcodeinwhichthedatatypeisavariablewhosevalueisdeterminedbythecompiler.Thisgenericcodeiswrittenusingthetemplatestatementinprogram1.3GenericObjectsinJavatemplate<classT>TAbc(Ta,Tb,T{returna+b+b*c+(a+b-c)/(a+b)+4;Fromthisgenericcodethecompilercanconstruct1.1bysubstitutingintforTand1.2bysubstitutingfloatfor

GenericObjectsinuseinheritance(pre-javaallobjectsaresubclassesofpublicclass{publicObjectread({returnstoredValue;}publicvoidwrite(Objectx){storedValue=x;privateObject} genericMemoryCellclass(pre-javaTwo

GenericObjectsin Wemustdowncasttothecorrectpublicclass publicstaticvoidmain(String[]args MemoryCellm=newMemoryCell()m.write(“37“stringval=(String)m.read();System.out.println(“Contentsare:“+val)}}Usingt ericMemoryCellclass(pre-Jave5)thereadmethodforMemoryCellreturnsanObject.GenericObjectsinSecondproblem AlthoughallobjectsaresubclassesofObject,theprimitivetypesboolean,short,char,byte,int,long,float,doublearenotobjects.ThuswecannotdirectlyuseMemoryCelltostoreaprimitivevalue.WemustusewrapperclassprovidebyJave.WrapperclassstoreasingleprimitivevalueandcanbeusedwhereveranObjectisneed.thewrapperclassprovidesamethodthatcanbeusedtoaccesstheprimitivevalueitstores.twoFortheIntegerwrapper,thismethodisnamedGenericObjectsinpublicclass Integer(int value=x;publicintintValue( returnvalue;privateint}GenericObjectsinpublicclass publicstaticvoidmain(String[]args MemoryCellm=newMemorycell()m.write(newInteger(37))IntegerwrapperVal=(Integer)m.Read()intval=wrapperVValue()System.Out.Println(“Contentsare:“+val)}} AnillustrationofIntegerwrapperTogettheintvaluethatishiddeninsidetheIntegerobject,wemustconverttheresultofreadbacktoanInteger,andthenusemathodintValueaccessthevalue.Thisinvolvesusingatypeconversion.GenericObjectsinImplementingGenericTheMemoryCellclassrequirednospecialpropertiesofObject;theonlyoperationsperformedwerereferenceassignments,whicharealwaysavailable.Findingthe umiteminanarrayofitemsdoesrequireaspecialproperty;wemustbeabletocomparetwoitemsanddecidewhichislarger.GenericObjectsinComparablefindMax(Comparable[]a ComparablemaxValue=a[0];for(inti=1;i<a.length;i++if(maxValue.lessThan(a[i]))maxValue=a[i];return}agenericfindMaxNoticethattheobjectsthataremanipulatedarenotButinsteadareGenericObjectsinComparableisanInjava,aninterfacedeclaresasetofmethodsthatmustbeimplemented.Inthisexample,anyclassthatisComparableprovideanimplementationof AclassthatisComparablemustalsodeclaresobyusingtheimplementsclause.publicinterface intlessThan(Comparablerhs GenericObjectsinComparablefindMax(Comparable[]a ComparablemaxValue=a[0];for(inti=1;i<a.length;i++if pareTo(a[i])<0maxValue=return}agenericfindMaxInthe

GenericObjectsinClass publicstaticcomparable Comparable[]arr intmaxIndex=for(inti=1;i<arr.length;i++if(arr[i].compareTo(arr[maxIndex])>0)maxIndex=i;returnarr[maxIndex}publicstaticvoidmain(String[]args Shape[]sh1={newCircle(2.0), Square(3.0newRectangle(3.0,4.0)}String[]sta={“Joe”,“Bob”,“Bill”,“Zeke”};System.out.println(findMax(sh1));System.out.println(findMax(st1));}}GenericObjectsin//anotherpublicinterface publicintcompareTo(objecto}publicclass publicstaticComparablemax(Comparableo1,Comparableo2 if(pareTo(o2)>0returno1;elsereturno2;}}class

GenericObjectsin privatedoublepublicCircle(){ radius=1.0;}publicCircle(doubler){ radius=r;}publicdoublegetRadius() returnradius;publicvoidsetRadius(doublenewRadius{radius=newRadius;}publicdoublefindArea(){returnradius*radius*3.14159;}GenericObjectsinclassComparableCircleextendsCircleimplements publicComparableCircle(doubler super(r}publicintcompareTo(objecto if(getRadius()>((Circle)o).getRadius()returnelseif(getRadius()<((Circle)o).getRadius()returnelsereturn}}GenericObjectsinpublicclass publicstaticvoidmain(String[]args ComparableCirclecircle1=newComparableCircle(5);ComparableCirclecircle2=newComparableCircle(4);Comparablecircle=Max.max(circle1,circle2);System.out.println(“Themaxcircle’sradiusis“+((Circle)circle).getRadius());System.out.println(circle);}}//anotherGenericObjectsin2)Java5supportsgenericclassesthatareveryeasytopublicclassGenericMemoryCell<AnyType publicAnyTyperead( returnstoredValue;}publicvoidwrite(AnyTypex) storedvalue=x;privateAnyTypestoredvalue}GenericimplementationoftheMemoryCellGenericObjectsinWhenagenericclassisspecified, theclassdeclarationincludesoneormoretypeparametersaftertheclassnameUsercancreatetypessuchasbutcannotcreateGenericMemoryCell<int>Insidet ericMemoryCellclassdeclaration,wecandeclarefieldsoft erictypeandmethodsthatuse erictypeasaparameterorreturnGenericObjectsinInterfaces sobedeclaredaspriortoJava5,theComparableinterfacewasnotgeneric.InJava5,theComparableclassisgeneric.packagepublicinterface publicintcompareTo(AnyTypeother)}Comparableinterface,Java5versionwhichisGenericObjectsinclass publicstaticvoidmain(String[]args newGenericMemoryCell<Integer>()insertacalltotheIntegerconstructorbehindthescenesm.Write(37); insertacalltotheintValuemethodbehindtheintval=m.Read() System.Out.Println(“contentsare:“+val)}}Autoboxingand**编译程序在箭头处分别调用Integer构造函数与intValue方Java的异常处理提供对运行时错误的语言级处理机制三类语法error,语义error语法通常在编译时发现，又称编译错如：标识符 ，类型不匹配，缺少分号等语义如：除数为0,数组下标越界等。打开的文件不存在，网络连接中断等逻辑运行结果与期望值不符。这类错误最难确定与排除运行时的error又分为两类(根据错误的性质错误 运行时遇到硬件或OS错误如，内存溢出(outof虚拟机错误

不可恢复的异异常 硬件与OS都正常，程序遇到的运行错如，除数为0,网络连接中断，打开文件发现件不存在等Java的异常处异常处理语{}

语句 //存在潜在异常的代catch(异常类常对象{语句 //捕获到异常并进行处理的代}{语句 //最后必须执行的代码，无论是否捕获到异}publicclass

publicstaticvoidmain(stringargs[ inti=0; inta[]={5,6,7,8};for(i=0;i<5;i++) system.out.print(“a[”+i+“]/”+i+“=”+} catch(ArithmeticExceptione) system.out.print(“捕获算术异常！”)}catch(Exceptione) system.out.print(“e.getMessage异常//显示异常信 system.out.println(“i=”+i }system.out.println继续！”）}}

捕获算术异常！i=0a[1]/1=6 i=1a[2]/2= i=a[3]/3= i=i抛出异抛出自定义异常对 异常对由throw语句抛出的异常也必须由try语句捕获并处理publicvoidset(int if(age>0&&age<100)this.age=age;thrownewExceptionIllegaAgeData”//抛出异}一般而言，一个方法通过tro抛出异常，由方法的调用者捕获publicvoidset(intage {if(age>0&&age<100)this.age=age;elsethrownewException(“IllegalAgeData“)}catch(Exceptione system.Out.Println(e.toString())}}方 抛出异常的throws子publicvoidremoveAny()throws if(isEmpty()thrownewUnderflow(}import

Inputand BasicStreamOperations standardinput; standardoutput standarderroroutputinjava:isdonealmostexclusivelybyStringconcatenation,withnobuilt-informatting.useinputinjava:readingformattedistoreadasinglelineintoaStringobjectusingThereadLinemethodreadsuntilitencountersaterminatororendofTousereadLine,wemust constructaBufferedReaderobjectfromanInputStreamReaderobjectthatitselfconstructedfromSystem.in.import

Inputandpublicclass publicstaticvoidmain(String[]args bufferedReaderin=newBufferedReader(InputStreamReader(System.in)intStringSystem.out.println(“Enteraninteger:”);{oneLine=in.readLine( //x=Integer.parseInt(oneLine);//NumberFormatExceptionSystem.out.println(“Halfofxis“+(x/2));}catch(Exceptione{system.out.println(e);}}InputandRecallthattoreadasingleprimitivetype,suchasanusereadLinetoreadthelineasathenapplyamethodtogeneratetheprimitivetypethe Forint,wecanuseTheStringTokenizerSometimeswehaveseveralitemsonaline.Forinstance,eachlinehastwointsJavaprovidestheStringTokenizerobjecttoseparateaintoimportjava.io.*importjava.util.*;publicclassMaxTest

Inputand publicstaticvoidmain(String[]args BufferedReaderin=new(newInputStreamReader(System.in));StringoneLine;StringTokenizerint intSystem.out.println(“Enter2intsononeline:“ oneLine=in.readLine(str=newStringTokenizer(oneLine);if(str.countTokens()!=2)thrownewNumberFormatException();x=Integer.parseInt(str.nextToken());y=Integer.parseInt(str.nextToken());System.out.println(“Max:“+Math.max(x,y))}catch(Excepti