10 Java数据结构

《10 Java数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第10章Java数据结构10.1概述10.2链表10.3栈10.4向量10.5树集10.6树映射10.7散列集10.8散列表10.1概述在Java语言的标准类库中提供了丰富的数据结构接口和类，如集合、列表和映射，使得人们可以很轻松地在程序中操纵各种过去看起来比较复杂的数据结构。10.1概述Collection接口Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。JavaSDK不提供直接实现自Collection的类，JavaSDK

2、提供的类都是实现自Collection的“子接口”如List和Set。　所有实现Collection接口的类都必须提供两个标准的构造方法：无参数的构造方法用于创建一个空的Collection，有一个Collection参数的构造方法用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后一个构造方法允许用户复制一个Collection。10.1概述publicinterfaceCollection{//返回集合中的元素个数intsize();//判集合是否为空

3、booleanisEmpty();//判一个对象是否包含在集合中booleancontains(Objecto);//返回集合的迭代器Iteratoriterator();//将集合中的所有元素存入一个数组中返回Object[]toArray();//将集合中的元素存入数组中返回Object[]toArray(Objecta[]);10.1概述//将对象o添加到集合中booleanadd(Objecto);//从集合中删去对象obooleanremove(Objecto);//判本集合是否包含集合cbooleanc

4、ontainsAll(Collectionc);//将集合c中的所有元素添加到本集合中booleanaddAll(Collectionc);//删除所有包含在集合c中的元素booleanremoveAll(Collectionc);//删除没有包含在集合c中的元素booleanretainAll(Collectionc);10.1概述//清空集合voidclear();//比较集合与对象o是否相等booleanequals(Objecto);//返回对象的hash码inthashCode();}10.1概述Iter

5、ator接口Iterator接口隐藏底层集合的数据结构，向客户程序提供了遍历各种类型的集合的统一接口。Iterator接口中声明了如下方法：hasNext();判断集合中的元素是否遍历完毕。next():返回下一个元素。romeve():从集合中删除一个由next()方法返回的元素。Collection接口的iterator()返回一个包含集合一个Iterator对象。10.1概述List接口List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。可以使用索引（元素在List中的位置，类似

6、于数组下标）来访问List中的元素，这类似于Java的数组。另外，List允许有相同的元素。　除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素，还能向前或向后遍历。　　实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。10.1概述Set接口Set接口是

7、一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false。因此，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。放入Set中的自定义类的对象，需要有判断是否重复的方法。Set接口的主要实现类有：TreeSet和HashSet。10.1概述Map接口Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个value。放入Map中的自定义类的对象，需要重写

8、equals()。实现Map接口的主要类有：HashMap和TreeMap。10.2链表（LinkedList）LinkedList类实现了List接口。链表是由若干个称作节点的对象组成的一种数据结构，每个节点含有一个数据和下一个节点的引用（单链表），或含有一个数据并含有上一个节点的引用和下一个节点的引用（双链表）。publicbooleanadd(Obje