数据结构.PPT

常见数据结构的Java实现,常见数据结构,链表 散列集 向量 栈 树集,链表,如果需要处理一些类型相同的数据,人们习惯上使用数组这种数据结构,但数组在使用之前必须定义大小,而且不能动态定义大小.有时可能给数组分配了太多的单元而浪费了宝贵的内存资源,糟糕的一方面是,程序运行时需要处理的数据可能多于数组的单元.当需要动态地减少或增加数据项时,可以使用链表这种数据结构。 链表是由若干个称作节点的对象组成的一种数据结构,每个节点含有一个数据和下一个节点对象的引用(单链表 ),或含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用(双链表) 。,创建链表,使用java.util 包中的LinkedList类创建一个链表.例如, LinkedList mylist=new LinkedList(); 创建了一个空链表.然后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 mylist=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 类的子类,因此可以把任何一个对象作为链表的节点对象.需要注意的是当使用get()获取一个节点对象后,要用类型转换运算符转化回原来的类型.,2、LinkedList类中的常用方法 public boolean add(Object element) 向链表的末尾填加一个新的节点对象elememt. public void add(int index ,Object element) 向链表的指定位置尾填加一个新的节点对象elememt. public void addFirst(Object element) 把节点对象 elememt 填加到链表的表头. public void addLast(Object element) 把节点对象elememt 填加到链表的末尾. public void clear() 删除链表的所有节点对象. public Obiect remove(int index) 删除指定位置上的节点对象. public boolean remove(Object element) 将首次出现的节点对象elemen删除. public Obiect removeFirst() 删除第一个节点对象,并返回这个节点对象.,public Obiect removeLast() 删除最后一个节点对象. public Object get(int index) 得到链表中指定位置处的节点对象. public Object getFirst() 得到链表中第一个节点对象. public Object getLast() 得到链表中最后一个节点对象. public int indexOf(Object element) 返回节点对象element 在链表 中首次出现的位置,如果链表中无此节 点对象则返回-1. public int lastIndexOf(Object element) 返回节点对象element 在 链表中最后出现的位置,如果链表中无此节 点对象则返回-1. public Object set(int index ,Object element) 用节点对象element 替换链表中指定位置处的节点对象.并返回被替换的对象。 public int size() 返回链表的长度,即节点的个数. public boolean contains(Object element) 判断链表节点对象中是 否含有element.,看下面的例子 ExampleList.java,使用Iterator类遍历链表,前面的例子借助get方法实现了遍历链表。也可以借助Iterator对象实现遍历链表，一个链表对象可以使用iterator()方法获取一个Iterator对象，Iterator对象中每个数据成员刚好是链表结点中的数据，而且这些数据成员是按顺序存放在Iterator对象中的。Iterator对象使用next()方法可以得到其中的数据成员。显然使用Iterator要比get方法遍历的速度快。,3、使用Iterator类遍历链表 (迭代器) 在上面的例子中我们借助get 方法实现了遍历链表. 我们可以借助Iterator 对象实现遍历链表,一个链表对象可以使用iterator()方法获取一个Iterator 对象,后者使用next()方法遍历链表.在下面的例子 中,我们把学生的成绩存放在一个链表中,并实现了遍历链表. 例子：ExampleList2.java,ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下： 1. 对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一 项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。 2.在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。 3.LinkedList不支持高效的随机元素访问。 4.ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了,散列表,散列表是使用相关关键字查找被存储的数据项的一种数据结构,关键字不可以发生逻辑冲突,即不要两个数据项使用相同的关键字,如果出现两个数据项对应相同的关键字,那么,先前散列表中的数据项将被替换.散列表在它需要更多的存储空间时会自动增大容量. 例如,如果散列表的装载因子是0.75,那么当散列表的容量被使用了75%时,它就把容量增加到原始容量的2倍. 对于数组和链表这两种数据结构,如果要查找它们存储的某个特定的元素却不知道它的位置,就需要从头开始访问元素直到找到匹配的为止；如果数据结构中包含很多的元素,就会浪费时间.这时最好使用散列表来存储要查找的数据.,使用java.util包中的Hashtable类来创建散列表对象,该类的常用方法如下 public Hashtable() 创建具有默认容量和装载因子为0.75 的散列表. public Hashtable (int itialCapacity) 创建具有指定容量和装载因子为0.75的散列表. public Hashtable(int initialCapacity,float loadFactor) 创建具有默认容量和指定装载因子散列表. public void clear() 清空散列表. public boolean contains(Object o) 判断散列表是否有含有元素o. public Object get(Object key) 获取散列表中具有关键字key的数据项. public boolean isEmpty() 判断散列表是否为空.,public Object put(Object key ,Object value) 向散列表添加数据项value并把关键字key关联到数据项value. public Object remove(Object key) 删除关键字是key 的数据项. public int size() 获取散列表中关键字的数目. public Enumeration keys() 返回散列表所用的关键字的一个枚举对象. 使用上述的get 方法可以从散列表中检索某个数据.我们还可以借助Enumeration 对象实现遍历散列表,一个散列表可以使用elements()方法获取一个Enumeration 对象,后者使用nextElement()方法遍历散列表.,Vector 向量,Java的 java.util包中的Vector类负责创建一个向量对象.如果你已经学会使用数组,那么很容易就会使用向量.当我们创建一个向量时不用象数组那样必须要给出数组的大小.向量创建后,例如,Vector a=new Vector(),a可以使用add(Object o)把任何对象添加到向量的末尾,向量的大小会自动的增加.可以使用add(int index ,Object o)把一个对象追加到该向量的指定位置. 向量a可以使用elementAt(int index )获取指定索引处的向量的元素（索引初始位置是0）a可以使用方法size()获取向量所含有的元素的个数.另外,与数组不同的是向量的元素类型不要求一致.需要注意的是,当你把某一种类型的对象放入一个向量后,数据被默认为是Object 对象,因此当向量中取出一个元素时应用强制类型转化运算符转化为原来的类型.,Vector类的常用方法 public void add(Object o) 将对象o添加到向量的末尾. public void add(int index Object o)将对象o插入到向量的指定位置. public void addElements(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(Obkect o) 获取对象o在此向量中首次出现的位置. public int indexOf(Obkect 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 void set(int index,Object o) 把指定位置处的成员用o替换掉. public void setElementAt(Object o,int index)把指定位置处的成员用o替换掉. public Enumeration elements()获取一个枚举对象.,栈,栈是一种”后进先出”的数据结构,只能在一端进行输入或输出数据的操作.堆栈把第一个放入该堆栈的数据放在最底下,而把后续放入的数据放在已有数据的顶上,如图所示.,使用java.util包中的Stack类创建一个栈对象 public Object push(Object data); 输入数据,实现压栈操作 public Object pop(); 输出数据,实现弹栈操作 public Object peek(); 查看栈顶端的数据,但不删除该数据 public boolean empty(); 判断栈是否还有数据,有数据返回false ,否则返回true public int search(Object data); 获取数据在栈中的位置,最顶端的位置是1，向下依次增加，如果栈不含此数据，返回-1。,树集,树集是有一些节点对象组成的数据结构,节点按着树形一层一层的排列,如下图所示.,1.用构造方法TreeSet()创建一个树集 可以使用java.util包中的TreeSet来创建一个树集,如 TreeSet mytree=new TreeSet(); 然后使用add方法为树集添加节点 mytree.add(“boy“); mytree.add(“zoo“); mytree.add(“apple“); mytree.add(“girl“); 和链表不同的是,当使用构造方法TreeSet()创建树集后,再用add 方法增加节点时,节点会按其存放的数据的字典序一层一层地依次排列,在同一层中的节点从左到右按字典序递增排列,下一层的都比上一层的小.mytree的示意图如下图.,两个字符串对象s1,s2可以使用 pare(s2); 按字典序比较大小,即pare(s2) =0时二者相同,pare(s2) 0时,称s1 大于 s2，pare(s2) 0时,称s1 小于s2.,2.用构造方法TreeSet(Comparator c)创建一个树集 但很多对象不适合用字典序进行比较,这时我们在创建树集时可自己规定节点按着什么样的”大小”顺序排列.假如我们有四个学生对象,他们有姓名和成绩,我们想把这四个对象做为一个树集的节点,并按着成绩的高低排列节点,而不是按着姓名的字典序排列节点. 首先创建学生的Student类必须实现接口 Comparable.Comparable 接口中有一个方法 public int compareTo(Object b) Student类通过实现这个接口来规定它创建的对象的大小关系,如下所示.,Java规定 当 pareTo(b) 时,称二者相等 pare(s2)0 时,称a大于b pare(s2)0 时,称a小于b. 然后用带Comparator参数的构造方法 TreeSet(Comparator c); 创建一个树集,通过参数c规定树集的节点按怎样的顺序排列,如下所示 TreeSet mytree=new TreeSet(new Comparator() public int compare(Object a,Object b) Student stu1=(Student)a; Student stu2=(Student)b; return