Java常见数据结构实现.ppt

1、常见数据结构的Java实现,我们在编写程序时经常要和各种数据打交道,为处理这些数据所选的数据结构对于我们的程序的运行效率是非常重要的.这章讲述几种常见的数据结构的Java 实现. 在学习数据结构这门课程的时候,人们要用具体的算法去实现相应的数据结构,例如,为了实现链表这种数据结构,需要实现往链表中插入节点或从链表中删除节点的算法,感觉有些烦琐. 在jdk1.2 之后,Java 提供了实现常见数据结构的类,创建链表等数据结构和创建数组一样简单,不再需要你去写具体的算法.我们主要讲述这些类的用法,但对这些数据结构的原理的掌握对于我们熟练地用好这些类还是很有帮助的.,26.1链表,如果需要处理一些类

2、型相同的数据,人们习惯上使用数组这种数据结构,但数组在使用之前必须定义大小,而且不能动态定义大小.有时可能给数组分配了太多的单元而浪费了宝贵的内存资源,糟糕的一方面是,程序运行时需要处理的数据可能多于数组的单元.当需要动态地减少或增加数据项时,可以使用链表这种数据结构. 链表是由若干个称作节点的对象组成的一种数据结构,每个节点含有一个数据和下一个节点对象的引用(单链表 ),或含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用(双链表) .,1 .创建链表,使用java.util 包中的LinkedList类创建一个链表.例如, LinkedList mylist=new Linked

3、List(); 创建了一个空链表.然后mylist链表可以使用add()方法向这个链表依次增加节点.例如 mylist.add(“It”);mylist.add(“is”); mylist.add(“a”);mylist.add(“door”); mylist可以使用方法 public Object get(index i)获取第i个节点中存储的数据. 存放在节点中的数据都被看作是一个Object 对象.,import java.util.*; public class LinkListOne public static void main(String args) LinkedList my

4、list=new LinkedList(); mylist.add(It); /链表中的第一个节点. mylist.add(is); /链表中的第二个节点. mylist.add(a); /链表中的第三个节点. mylist.add(door); /链表中的第四个节点. int number=mylist.size(); /获取链表的长度. for(int i=0;inumber;i+) String temp=(String)mylist.get(i); System.out.println(第+i+节点中的数据:+temp); ,注:由于任何类都是Object 类的子类,因此可以把任何一个

5、对象作为链表的节点对象.需要注意的是当使用get()获取一个节点对象后,要用类型转换运算符转化回原来的类型.,linkedlist.java,26.4散列表,散列表是使用相关关键字查找被存储的数据项的一种数据结构,关键字不可以发生逻辑冲突,即不要两个数据项使用相同的关键字,如果出现两个数据项对应相同的关键字,那么,先前散列表中的数据项将被替换.散列表在它需要更多的存储空间时会自动增大容量. 例如,如果散列表的装载因子是0.75,那么当散列表的容量被使用了75%时,它就把容量增加到原始容量的2倍. 对于数组和链表这两种数据结构,如果要查找它们存储的某个特定的元素却不知道它的位置,就需要从头开始访

6、问元素直到找到匹配的为止；如果数据结构中包含很多的元素,就会浪费时间.这时最好使用散列表来存储要查找的数据.,hastable.java,26.5 Vector 向量,Java的 java.util包中的Vector类负责创建一个向量对象.如果你已经学会使用数组,那么很容易就会使用向量.当我们创建一个向量时不用象数组那样必须要给出数组的大小.向量创建后,例如,Vector a=new Vector(),a可以使用add(Object o)把任何对象添加到向量的末尾,向量的大小会自动的增加.可以使用add(int index ,Object o)把一个对象追加到该向量的指定位置. 向量a可以使用

7、elementAt(int index )获取指定索引处的向量的元素（索引初始位置是0）a可以使用方法size()获取向量所含有的元素的个数.另外,与数组不同的是向量的元素类型不要求一致.需要注意的是,当你把某一种类型的对象放入一个向量后,数据被默认为是Object 对象,因此当向量中取出一个元素时应用强制类型转化运算符转化为原来的类型.,Vector类的常用方法 public boolean add(Object o) 将对象o添加到向量的末尾. public void add(int index, Object o)将对象o插入到向量的指定位置. public void addElemen

8、ts(Object o)将对象o添加到向量的末尾. public boolean contains(Object o)判断对象o是否为向量的成员. public Object elementAt(int index)获取指定位置处的成员. public Object get(int index)获取此向量指定位置处的成员. public Object firstElement()获取此向量的第一个成员. public Object lastElement()获取此向量的最后一个成员.,public int indexOf(Object o) 获取对象o在此向量中首次出现的位置. public

9、int indexOf(Object o,int index) 从指定位置查找对象o 在此向量中首次现的位置. public int lastIndexOf(Object o) 获取对象o在此向量中最后出现的位置. public int lastIndexOf(Object o,int index) 对象o在此向量位置index之前最后出现的位置. public Object remove(int index) 从此向量中删除指定位置处的成员,并返回这个成员. public void removeAllElements() 删除向量的所有成员. public boolean removeElement(Object o) 删除第一次出现的成员o.,public boolean removeElementAt(int index) 删除指定位置处的成员. public Object set(int index,Object o) 把指定位置处的成员用o替换掉. public void setElementAt(Object o,int index)把指定位置处的成员用o替换掉. public Enumeration el