Java语言程序设计基础教程课件(第12章)

第12章常见数据结构的Java实现链表的基本操作栈树集树映射散列表散列集向量容器类数组的优缺点java用于存储数据的集合类存储单个对象的集合存储键值对对象的集合集合遍历工具：迭代器顺序表链表Tree：排序树Hash:哈希值确定存储地址集合工具：静态方法比较器比较器接口List接口（索引读取，可重复）List关心的是索引与其他集合相比，List特有的就是和索引相关的一些方法：get(intindex)、add(intindex,Objecto)、indexOf(Objecto)。ArrayList：可增长的数组，它提供快速迭代和快速随机访问的能力，增删元素慢。LinkedList：双向链表，增删元素快。Set接口（元素唯一）Set关心元素唯一性，它不允许重复，且无序HashSet：不关心元素之间的顺序且无重复值时使用LinkedHashset：希望按照元素的插入顺序进行迭代遍历，且不希望集合中有重复值时采用此类。TreeSet希望按照元素的按大小顺序排列，且不希望集合中有重复值时使用Map接口（键值对映射）Map关心的是唯一的键，可映射到某个元素HashMap当需要键值对表示，又不关心顺序时可采用HashMapHashtable注意Hashtable中的t是小写的，它是HashMap的线程安全版本，已较少使用LinkedHashMap当需要键值对，并且关心插入顺序时可采用它TreeMap当需要键值对，并希望元素按大小排序时可采用它。List常用方法：add(Objecte)将指定对象添加到集合中remove(Objecto)将指定的对象从集合中移除，移除成功返回true,不成功返回falsecontains(Objecto)查看该集合中是否包含指定的对象，包含返回true,不包含返回flasesize()返回集合中存放的对象的个数。返回值为intclear()移除该集合中的所有对象，清空该集合。iterator()返回一个包含所有对象的iterator对象，用来循环遍历toArray()返回一个包含所有对象的数组,类型是ObjectLinkedList的常用方法publicbooleanadd(Objectelement)publicvoidadd(intindex,Objectelement)publicvoidaddFirst(Objectelement)publicvoidaddLast(Objectelement)publicObjectremoveFirst()publicObjectremoveLast()publicObjectremove(intindex)publicObjectget(intindex)publicObjectgetFirst()publicObjectgetLast()intindexOf(Objectelement)publicintlastIndexOf(Objectelement)publicObjectset(intindex,Objectelement)publicintsize()publicbooleancontains(Objectelement)Object[]toArray()迭代器的使用String[]sa={one,two,three,four};Listlist=Arrays.asList(sa);IteratorStringit=list.iterator();//转换成Iteratorwhile(it.hasNext()){//遍历System.out.println(it.next());}12.3.3TreeSet常用方法publicbooleanadd(Objecto)publicvoidclear()publicbooleancontains(Objecto)publicObjectfirst()//最小元素publicObjectlast()//最大元素PublicbooleanisEmpty()publicbooleanremove(Objecto)publicintsize()Object[]toArray()Set集合中如何实现元素的比较方法一：元素对象实现Comparable接口实现方法publicvoidcompareTo(Objecto)方法二：定义TreeSet时指定比较器Comparator重载publicintcompare(Objecta,Objectb)Map接口的常用方法put(Kkey,Vvalue)向集合中添加指定的键值对putAll(Mapt)把一Map中的所有键值对添加到该集合containsKey(Objectkey)如果包含该键，则返回truecontainsValue(Objectval)如果包含该值，则返回trueget(Objectkey)根据键,返回相应的值对象SetkeySet()将该集合中的所有键Collectionvalues()将该集合中所有的值remove(Objectkey)如存在指定的键，移除该键值对，返回键所对应的值，不存在则返回nullclear()清空集合isEmpty()查看Map中是否为空size()集合中包含键值对的个数12.4树映射TreeMap树集TreeSet适合用于数据的排序，TreeMap类树映射的结点存储“关键字/值”对，实现Map接口树映射各结点按照关键字升序排列使用put(Kkey,Vvalue)方法添加结点，该结点不仅存储数据value，而且也存储和其关联的关键字key。HashSet常用方法booleanadd(Ee)voidclear()Objectclone()booleancontains(Objecto)booleanisEmpty()iteratorEiterator()booleanremove(Objecto)intsize()12.5.1Hashtable类常用方法publicHashtable()publicHashtable(intitialCapacity)publicHashtable(intinitialCapacity,floatloadFactor)publicvoidclear()publicbooleancontains(Objecto)publicObjectget(Objectkey)publicbooleanisEmpty()publicObjectput(Objectkey,Objectvalue)publicObjectremove(Objectkey)publicintsize()publicEnumerationelements()HashMap和Hashtable的区别HashMap：不允许nullkey和nullvalue方法不同步Collection.synchronizedMap(hashmap)Hashtable允许nullkey和nullvalue方法同步类型安全的集合在Java5版本之前我们使用：Listlist=newArrayList()在Java5版本之后，我们使用带泛型的写法：ListStringlist=newArrayListString();上面的代码定义了一个只允许保存字符串的列表，尖括号括住的类型就是参数类型，也称泛型。带泛型的写法给了我们一个类型安全的集合。集合中存放的是对象，而不能是基本数据类型，在Java5之后可以使用自动装箱功能，更方便的导入基本数据类型。ListIntegerlist=newArrayListInteger();list.add(newInteger(42));list.add(43);ArrayList的排序：ArrayList本身不具备排序能力，但是我们可以使用Collections类的sort方法使其排序。System.out.println(排序前：+list);Collections.sort(list);System.out.println(排序后：+list);在for-each出现之后，遍历变得简单一些：ListStringlist=Arrays.asList(one,two,three,four);for(Strings:list){System.out.println(s);}作业：使用堆栈实现加减乘除的四则运算如：34+5*6-(23-8)/7设计学生成绩单的输入、查找和输出。P263【例12-2】LinkedList常用方法使用Iterator类遍历链表迭代器（Iterator），又叫做游标（Cursor）。它提供了遍历访问容器对象中各个元素的方法由容器产生一个对应的迭代器:Iterator容器对象名.iterator()迭代器遍历元素的方法：BooleanhasNext()：是否仍有元素可以迭代Objectnext()：返回迭代的下一个元素。voidremove()：移除容器中的最后一个元素。P265【例12-3】把学生的成绩存放在一个链表中，并遍历链表。程序运行后的效果如下所示：importjava.util.*;classStackOne{publicstaticvoidmain(Stringargs[]){Stackmystack=newStack();mystack.push(newInteger(1));mystack.push(newInteger(2));mystack.push(newInteger(3));mystack.push(newInteger(4));mystack.push(newInteger(5));mystack.push(newInteger(6));while(!(mystack.empty())){Integertemp=(Integer)mystack.pop();System.out.print(+temp.toString());}}}【例12-5】将数字１，２，３，４，５，6压入堆栈12.2栈Stack栈（Stack）是一种仅限定在表尾进行插入和删除运算的线性表，是一种后进先出（LIFO）的数据结构。只能在一端进行输入或输出数据的操作表尾称为栈顶top，表头称为栈底bottom。向堆栈中输入数据的操作称为“压栈”，从栈中输出数据的操作称为“弹栈”。栈的物理存储可以用顺序存储结构，也可以用链式存储结构。12.2.1栈的常用方法使用java.util包中的Stack类创建一个堆栈对象StackmyStack=newStack();publicObjectpush(Objectdata)publicObjectpop()publicbooleanempty()publicobjectpeek()publicintsearch(Objectdata)递归是一种很消耗内存的算法，我们可以借助堆栈消除大部分递归，达到和递归算法同样的目的。P271例12-6使用stack输出Fibonacii整数序列12.3树集TreeSet树集是由一些节点对象组成的数据结构，节点按着树形一层一层的排列。树集是个有序集合，可以按照任何顺序将元素插入该集合，该元素将被纳入它的相应的排序位置；当迭代通过该集合时，各个值将自动按照排序后的顺序输出；由java.util.TreeSet类创建的对象称为树集。TreeSet类是实现Set接口的类12.3.1创建树集java.util包中的TreeSet可用来创建一个树集，TreeSetmytree=newTreeSet();然后使用add方法为树集添加节点：mytree.add(boy);mytree.add(apple);mytree.add(girl);add方法增加节点时，节点会按其存放的数据的字典序一层一层地依次排列，在同一层中