将多个元素组成一个单元的对象.ppt

DYNAMICDATASTRUCTURES Adatastructureisaconstructusedtoorganizedatainaspecificway Sointhischapterwewill BecomefamiliarwithvectorsandhowtheyareusedinJava LearnwhatalinkeddatastructureisandhowitcanberealizedinJava FindouthowtomanipulatelinkedlistsLearnwhatiteratorsareandhowtocreateandusethem CHAPTER10 简介 集合将多个元素组成一个单元的对象用于存储 检索 操纵和传输数据集合框架提供用于管理对象集合的接口和类包括接口 实现和算法 体系结构 用于操纵集合的接口 Collection接口 集合框架的根通用方法booleancontains Objecta booleanequals Objecta Iteratoriterator intsize voidclear booleanadd Objecta Set接口 扩展Collection接口不允许重复元素对add equals 和hashcode 方法添加了限制HashSet和TreeSet是Set的实现 SortedSet接口 扩展了Set接口元素按升序排序重要异常ClassCastExceptionNullPointerException List接口2 1 具有顺序的集合扩展了Collection接口元素可以通过其整型下标访问可以包含重复元素 List接口2 2 方法分类定位方法get set add remove addAll 搜索方法indexOf 和lastIndexOf ListIterator方法listIterator 和subList Map接口 将键映射至值的对象每个键最多都只能映射至一个值重要方法基本操作put get remove containsKey containsValue size 和isEmpty 批操作putAll 和clear 集合视图keySet values 和entrySet 实现2 1 用于存储集合的实际数据对象重要集合类AbstractCollection类提供Collection接口的框架实现AbstractList类提供List接口的框架实现AbstractSequentialList类是List接口的实现LinkedList类提供多个方法 用于在列表开始处和结尾处获得 删除和插入元素 简介 集合将多个元素组成一个单元的对象用于存储 检索 操纵和传输数据集合框架提供用于管理对象集合的接口和类包括接口 实现和算法 体系结构 用于操纵集合的接口 Collection接口 集合框架的根通用方法booleancontains Objecta booleanequals Objecta Iteratoriterator intsize voidclear booleanadd Objecta Set接口 扩展Collection接口不允许重复元素对add equals 和hashcode 方法添加了限制HashSet和TreeSet是Set的实现 SortedSet接口 扩展了Set接口元素按升序排序重要异常ClassCastExceptionNullPointerException List接口2 1 具有顺序的集合扩展了Collection接口元素可以通过其整型下标访问可以包含重复元素 List接口2 2 方法分类定位方法get set add remove addAll 搜索方法indexOf 和lastIndexOf ListIterator方法listIterator 和subList Map接口 将键映射至值的对象每个键最多都只能映射至一个值重要方法基本操作put get remove containsKey containsValue size 和isEmpty 批操作putAll 和clear 集合视图keySet values 和entrySet 实现2 1 用于存储集合的实际数据对象重要集合类AbstractCollection类提供Collection接口的框架实现AbstractList类提供List接口的框架实现AbstractSequentialList类是List接口的实现LinkedList类提供多个方法 用于在列表开始处和结尾处获得 删除和插入元素 实现2 2 重要集合类 续 ArrayList类是List接口的可变大小数组实现AbstractSet类提供Set接口的框架实现HashSet类为基本操作提供固定时间性能TreeSet类确保排序集将按元素升序 example importjava util publicclassListOper publicstaticvoidmain String args if args length 0 System out println 你必须提供列表元素 作为命令行参数 请重试 System exit 0 System out println Listl newArrayList for inti 0 i args length i l add args i Collections reverse l System out println 逆序的列表如下 System out println l Collections sort l System out println 排序的列表如下 System out println l intindex Collections binarySearch l c System out println 元素 c 的位置为 index Collections fill l 一 System out println 用字 一 填充后的列表如下 System out println l Listll newArrayList ll add 第一 ll add 第二 ll add 第三 Collections copy l ll System out println 用ll的元素替代后的列表如下 System out println l 算法3 1 Collections类中的静态方法用于排序 搜索 混排和数据操纵方法的第一个参数是要执行操作的集合重要异常ClassCastExceptionUnsupportedOperationException 算法3 2 算法3 3 classAlgorithmExample publicstaticvoidmain Stringargs LinkedListlink newLinkedList link add newInteger 10 link add newInteger 35 link add newInteger 23 link add newInteger 54 link add newInteger 36 Comparatorcmp Collections reverseOrder Collections sort link cmp Iteratorit link iterator System out println 逆序排序的列表为 while it hasNext System out println it next System out println 给定列表中的最大值为 Collections max link System out println 给定列表中的最小值为 Collections min link 多简单 集合框架的优点 提供一组可用的集合接口提供有效的数据结构和算法可以方便地扩展或改写集合接口的实现都是可交换的使设计新API的工作降到最少接口和算法的可重用性 Vector类 实现可变长度的对象数组组件可以使用整型下标访问构造函数Vector Vector Collectionc Vector intcap Vector intcap intinc Enumeration接口 此接口定义了多个方法 有助于枚举对象集合中的元素 BooleanhasMoreElements ObjectnextElement Enumeratione v elements While e hasMoreElements System out println e nextElement Methodinvector PublicvoidsetElementAt objectnewElement intindex PublicobjectelementAt intindex PublicvoidaddElement objectnewElement PublicvoidinsertElementAt objectnewElement intindex PublicvoidremoveElementAt intindex PublicbooleanremoveElement ObjecttheElement PublicvoidremoveAllElements Publicbooleancontains Objecttarget PublicintindexOf Objecttarget PublicintindexOf Objecttarget intstartIndex PublicintlastIndexOf Objecttarget PublicObjectfirstElement PublicObjectlastElement PublicboolearnisEmpty Publicintsize Publicintcapacity PublicvoidensureCapacity intnewCapacity PublicvoidtrimToSize PublicvoidsetSize intnewSize PublicObjectclone LinkedList Alinkedlistisadatastructureconsistingofobjectsknownasnodes suchthateachnodecancontainbothdataandareferencetooneothernodesothattheentirelinkedlistformsalist asillustratedinDisplay10 3 Thefirstnodeinthelistisknownastheheadnode Inlinkedlistmostnodeshavenoname Thevariableheadcontainsareferencetothefirstnodeinalinkedlist So headcanbeusedasanameforthefirstnode However theothernodesinthelinkedlisthavenonamedvariablethatcontainsareferencetoanyofthem andsotherestofthenodesinthelinkedlistareusuallynameless Theonlywaytonameoneofthemisviasomeindirectreference likehead link link orbyusinganothervariableoftypeListNode suchasthelocalvariablepositioninthemethodshowList Display10 5 page683 UsenullfortheEmptyListLet ssaythevariableheadissupposedtocontainareferencetothefirstnodeinalinkedlist Linkedlistsusuallystartoutempty Whatvaluedogiveheaduntilthefirstnodeisadded Giveheadthevaluenulltoindicateemptylist Thisistraditionalanditworksoutnicelyformanylinkedlistmanipulationalgorithms NodeInnerClassYoucanmakealinkedlist orotherlinkeddatastructure self containedbymakingthenodeclassaninnerclassofthelinkedlistclass Somethingelse Stack类 表示后进先出的对象堆栈一个构造函数 创建空堆栈Stack Booleanempty Objectpeek Objectpop Objectpush Objecta Intsearch Objecta importjava util classStackEg publicstaticvoidmain String args Stacks newStack s push 一 s push 二 s push 三 s push 四 System out println 存储在堆栈中的元素为 System out println s System out println while s empty System out println s pop Hashtable类 以键值对的形式存储数据键被散列 散列码用作存储值的下标构造函数Hashtable Hashtable intcap Hashtable intcap floatload Hashtable Mapm importjava util classHashTableExample publicstaticvoidmain Stringargs Hashtableh newHashtable Enumeratione Stringstr doublebal h put Maria newDouble 4545 50 h put Joseph newDouble 2000 00 h put Johnson newDouble 5000 00 e h keys while e hasMoreElements str String e nextElement System out println str h get str System out println bal Double h get Maria doubleValue h put Maria newDouble bal 1000 System out println Maria snewbalance h get Maria Iterators Supposeyouhaveacollectionofdataitems suchasanarrayoralinkedlist Anyobjectthatallowsyoutostepthroughthecollectiononeitematatimeinareasonablewayiscalledaniterator By areasonableway wemeanthateachitemisvisitedexactlyonceinonefullcycleofiterations andeachitemcanhaveitsdatareadand ifthedataitemsallowit canhavethedatachanged Forexample anintvariablethatholdsanindexvaluecanserveasaniteratorforanarray Togotothenextiteminthecollection yourcodeneedonlyincreasethevalueoftheintvariablebyone ThejavaIteratorinterface JavahasaninterfacenamedIteratorthatspecifieshowJavawouldlikeaniteratortobehave Itisinthepackagejava util Ouriteratorsdonotsatisfythisinterface butitiseasytodefineclassesthatuseouriteratorsandthatdosatisfythisinterface Theiteratorinterfaceusesexceptionhandling butisnotdifficulttounderstand InSelf TestQuestion19youareaskedtodefinealinkedlistclasstatsatisfiestheiteratorinterface CHAPTER11 Ifamethoddefinitioncontainsaninvocationoftheverymethodbeingdefined thenthatinvocationiscalledarecursivecallorrecursiveinvocation Example publicvoidhanno charA charB charC n if n 1 move A B A Belse hanno A C B n 1 move A B hanno C B A n1 RECURSION SuccessfulRecursion Adefineofamethodthatincludesarecursiveinvocationofthemethodbeingdefinedwillnotbehavecorrectlyunlessyoufollowsomespecificdesignguidelines Thefollwingrulesapplytomostcasesthatinvolverecursion Theheartofthemethoddefinitioncanbeanif else statementorsomeotherbranchingstatementthatleadstodifferentcases dependingonsomepropertyofaparametertothemethodbeingdefiend SuccessfulRecursion2 Oneormoreofthebrancesincludearecursiveinvocationofthemethod Theserecursiveinvocationsshouldinsomesenseuse smaller argumentsorsolve smaller versionsofthetaskperformedbythemethod Oneormorebranchesshouldincludenorecursiveinvocations Thesearethestoppingcases alseknownasthebasecases StackOverflow Whenamethodinvocationleadstoinfiniterecursion yourprogramislikelytoendwithanerrormessagethatreferstoa stackoverflow Thetermstackreferstoadatastructurethatisusedtokeeptrackofrecursivecalls andotherthingsaswell Intuitivelyarecordofeachrecursivecallisstoredonsomethinganalogoustoapieceofpaper Thesepiecesofpaperareintuitivelystackedoneontopoftheother Whenthis stack becomestoolargeforthecomputertohandle thatiscalledastackoverflow Summary Vectorscanbethoughtofasarraysthatcangrowinlength ThebasetypeofallvectorsisObject Thus theelementsofavectormaybeofanyclasstype buttheycannotbeofaprimitivetype Alinkedlistisadatastructureconsistingofobjectsknownasnodes suchthateachnodecancontaindataandsuchthateachnodehasareferencetooneothernodesothattheentirelinkedlistformsalist Summary Youcanmakealinkedlistself containedbymakingthenodeclassaninnerclassofthelinkedclass Youcanuseaniterato