Java语言程序设计基础教程课件第12章.ppt

《Java语言程序设计基础教程课件第12章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

第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当需要键值对表示，又不关心顺序时可采用HashMapHashtable注意Hashtable中的t是小写的，它是HashMap的线程安全版本，已较少使用LinkedHashMap当需要键值对，并且关心插入顺序时可采用它TreeMap当需要键值对，并希望元素按大小排序时可采用它。 List常用方法：add(Objecte)将指定对象添加到集合中remove(Objecto)将指定的对象从集合中移除，移除成功返回true,不成功返回falsecontains(Objecto)查看该集合中是否包含指定的对象，包含返回true,不包含返回flasesize()返回集合中存放的对象的个数。返回值为intclear()移除该集合中的所有对象，清空该集合。iterator()返回一个包含所有对象的iterator对象，用来循环遍历toArray()返回一个包含所有对象的数组,类型是Object LinkedList的常用方法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);Iteratorit=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()iteratoriterator()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版本之后，我们使用带泛型的写法：Listlist=newArrayList();上面的代码定义了一个只允许保存字符串的列表，尖括号括住的类型就是参数类型，也称泛型。带泛型的写法给了我们一个类型安全的集合。 集合中存放的是对象，而不能是基本数据类型，在Java5之后可以使用自动装箱功能，更方便的导入基本数据类型。Listlist=newArrayList();list.add(newInteger(42));list.add(43); ArrayList的排序：ArrayList本身不具备排序能力，但是我们可以使用Collections类的sort方法使其排序。System.out.println("排序前："+list);Collections.sort(list);System.out.println("排序后："+list); 在for-each出现之后，遍历变得简单一些：Listlist=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方法增加节点时，节点会按其存放的数据的字典序一层一层地依次排列，在同一层中的节点从左到右按字典序递增排列，下一层的都比上一层的小。 12.3.2定义对象的比较器很多对象不适合用字典序进行比较，在创建树集时可自己规定节点按着什么样的“大小”顺序排列。假如我们有四个学生对象，他们有姓名和成绩，我们想把这四个对象做为一个树集的节点，并按着成绩的高低排列节点，而不是按着姓名的字典序排列节点。 1．学生类必须实现Comparable功能接口Comparable接口中有一个方法：publicintcompareTo(Objectb);通过实现接口的这个来规定创建的对象的大小关系，如下所示。Java规定：a.compareTo(b)＝0时，称二者相等；a.compare(b)>0时，称a大于b；a.compare(b)<0时，称a小于b。 publicclassNewStudentimplementsComparable{intenglish=0;Stringname;NewStudent(inte,Stringn){english=e;name=n;}publicintcompareTo(Objectb){NewStudentst=(NewStudent)b;return(this.english-st.english);//按成绩大小排列对象。}} 2．构造TreeSet(Comparatorc)创建一个树集，通过参数c指定树集节点的比较器TreeSetmytree=newTreeSet(newComparator(){publicintcompare(Objecta,Objectb){Studentstu1=(Student)a;Studentstu2=(Student)b;returnstu1.compareTo(stu2);}}); 【例12-12】本例使用了TreeMap，分别按学生的英语成绩和数学成绩排序结点。importjava.util.*;classStudentKeyimplementsComparable{doubled=0;StudentKey(doubled){this.d=d;}publicintcompareTo(Objectb){StudentKeyst=(StudentKey)b;if((this.d-st.d)==0){return-1;}else{return(int)((this.d-st.d)*1000);}}} TreeMaptreemap=newTreeMap(newComparator(){publicintcompare(Objecta,Objectb){StudentKeykey1=(StudentKey)a;StudentKeykey2=(StudentKey)b;returnkey1.compareTo(key2);}}); 程序运行后的结果如下所示： 12.5散列表Hashtable散列表是使用相关关键字查找被存储的数据项的一种数据结构，关键字必须唯一，任何非null对象都可以用作键或值。散列表在它需要更多的存储空间时会自动增大容量。例如，如果散列表的装载因子是0.75，那么当散列表的容量被使用了75%时，它就把容量增加到原始容量的２倍。使用java.util包中的Hashtable类来创建散列表对象。在哈希表中存储和检索对象，用作键的对象必须实现hashCode方法和equals方法。 下面这个示例12-13创建了一个数字的哈希表。它将数字的名称用作键：//【例12-13】Hashtablenumbers=newHashtable();numbers.put("one",newInteger(1));numbers.put("two",newInteger(2));numbers.put("three",newInteger(3));Integern=(Integer)numbers.get("two");if(n!=null){System.out.println("two="+n);} 12.5.2Hashtable类的应用使用Hashtable()创建一个散列表，存放Student对象，每个Student对象用该对象的学号作为关键字。P283例12-14 12.6散列集HashSet散列表是个链接式列表的阵列，每个列表称为一个散列表元，散列表为每个对象计算出一个整数，称为散列码，不存在重复的多个元素；若要查找表中的某个对象的位置，只要计算出它的散列码，再将它减去以散列表元的总数为模数的值，得出的数就是拥有该元素的散列表元的索引。 Java提供的HashSet类，用于根据散列表来实现一个散列集；构造函数如下：HashSet(intinitialCapacity);HashSet(intinitialCapacity,floatloadFactor);不在乎集合中的各元素的顺序时，可使用散列集Java增加了一个类LinkedHashSet，用于跟踪添加给散列集的元素顺序；其迭代器会按照元素的插入顺序来访问各个元素。 HashSet和TreeSet的比较：HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。我们通常都应该使用HashSet，在我们需要排序的功能时，才使用TreeSet。P287例12-16散列表 12.7向量向量相当于动态的，可存储不同数据类型数据的数组。与数组一样，它包含可以使用整数索引进行访问的组件。java.util包中的Vector类负责创建一个向量对象，可实现可增长的对象数组。Vector的大小可以根据需要增大或缩小 12.7.1Vector类常用方法voidadd(Objecto)voidadd(intindexObjecto)voidaddElements(Objecto)booleancontains(Objecto)ObjectelementAt(intindex)Objectget(intindex)ObjectfirstElement() intindexOf(Objecto)intindexOf(Objecto,intindex)intlastIndexOf(Objecto)Objectremove(intindex)voidremoveAllElements()BooleanremoveElement(Objecto)BooleanremoveElementAt(intindex)Voidset(intindex,Objecto)Enumerationelements() P288例12-17将不同对象添加到向量中 作业：使用堆栈实现加减乘除的四则运算如：34+5*6-(23-8)/7设计学生成绩单的输入、查找和输出。 12.1链表线性表的逻辑结构是n个数据元素的有限序列：(a1,a2,a3,…an)(n>=0)线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。在实际应用中是广泛采用的一种数据结构。a1a2a3an…. 线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储，也就是将线性表中的数据元素依次存放在某个存储区域中的表称为顺序表；一维数组是用顺序方式存储的线性表。用链式存储结构存储的线性表称为链表。单链表：每个节点含有一个数据和下一个节点对象的引用；双链表：含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用。 12.1.1链表的创建使用java.util.LinkedList类，可以创建一个双向链表对象。例如：LinkedListmylist=newLinkedList();add()方法:向链表依次增加节点。mylist.add(“It”);mylist.add(“is”);这样就形成了2个节点的链表，数据依次为“It”、“is”