• 1. 常见数据结构的Java实现
  • 2. 我们在编写程序时经常要和各种数据打交道,为处理这些数据所选的数据结构对于我们的程序的运行效率是非常重要的.这章讲述几种常见的数据结构的Java 实现. 在学习数据结构这门课程的时候,人们要用具体的算法去实现相应的数据结构,例如,为了实现链表这种数 据结构,需要实现往链表中插入节点或从链表中删除节点的算法,感觉有些烦琐. 在jdk1.2 之后,Java 提供了实现常见数据结构的类,创建链表等数据结构和创建数组一样简单,不再需要你去写具体的算法.我们主要讲述这些类的用法,但对这些数据结构的原理的掌握对于我们熟练地用好这些类还是很有帮助的.
  • 3. 26.1链表 如果需要处理一些类型相同的数据,人们习惯上使用数组这种数据结构,但数组在使用之前必须定义大小,而且不能动态定义大小.有时可能给数组分配了太多的单元而浪费了宝贵的内存资源,糟糕的一方面是,程序运行时需要处理的数据可能多于数组的单元.当需要动态地减少或增加数据项时,可以使用链表这种数据结构. 链表是由若干个称作节点的对象组成的一种数据结构,每个节点含有一个数据和下一个节点对象的引用(单链表 ),或含有一个数据并含有上一个节点对象的引用和下一个节点对象的引用(双链表) .
  • 4. 1 .创建链表 使用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 对象.
  • 5. (本页无文本内容)
  • 6. 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;i
  • 7. 注:由于任何类都是Object 类的子类,因此可以把任何一个对象作为链表的节点对象.需要注意的是当使用get()获取一个节点对象后,要用类型转换运算符转化回原来的类型.
  • 8. 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() 删除第一个节点对象,并返回这个节点对象.
  • 9. 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.
  • 10. linkedlist.java
  • 11. 3、使用Iterator类遍历链表 (迭代器) 在上面的例子中我们借助get 方法实现了遍历链表. 我们可以借助Iterator 对象实现遍历链表,一个链表对象可以使用iterator()方法获取一个Iterator 对象,后者使用next()方法遍历链表.在下面的例子 中,我们把学生的成绩存放在一个链表中,并实现了遍历链表.
  • 12. (本页无文本内容)
  • 13. 26.4散列表 散列表是使用相关关键字查找被存储的数据项的一种数据结构,关键字不可以发生逻辑冲突,即不要两个数据项使用相同的关键字,如果出现两个数据项对应相同的关键字,那么,先前散列表中的数据项将被替换.散列表在它需要更多的存储空间时会自动增大容量. 例如,如果散列表的装载因子是0.75,那么当散列表的容量被使用了75%时,它就把容量增加到原始容量的2倍. 对于数组和链表这两种数据结构,如果要查找它们存储的某个特定的元素却不知道它的位置,就需要从头开始访问元素直到找到匹配的为止;如果数据结构中包含很多的元素,就会浪费时间.这时最好使用散列表来存储要查找的数据.
  • 14. 使用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() 判断散列表是否为空.
  • 15. 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()方法遍历散列表.
  • 16. 下面的例子使用Hashtable()创建一个散列表,存放Student 对象,每个Student 对象用该对象的学号作为关键字.
  • 17. hastable.java
  • 18. 26.5 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 对象,因此当向量中取出一个元素时应用强制类型转化运算符转化为原来的类型.
  • 19. 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()获取此向量的最后一个成员.
  • 20. 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.
  • 21. public boolean removeElementAt(int index) 删除指定位置处的成员. public void set(int index,Object o) 把指定位置处的成员用o替换掉. public void setElementAt(Object o,int index)把指定位置处的成员用o替换掉. public Enumeration elements()获取一个枚举对象.
  • 22. 堆栈 堆栈是一种”后进先出”的数据结构,只能在一端进行输入或输出数据的操作.堆栈把第一个放入该堆栈的数据放在最底下,而把后续放入的数据放在已有数据的顶上,如图所示.
  • 23. (本页无文本内容)
  • 24. 使用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。
  • 25. 树集 树集是有一些节点对象组成的数据结构,节点按着树形一层一层的排列,如下图所示.
  • 26. 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的示意图如下图.
  • 27. (本页无文本内容)
  • 28. 两个字符串对象s1,s2可以使用 s1.compare(s2); 按字典序比较大小,即s1.compare(s2) 时二者相同,s1.compare(s2)> 时,称s1 大于 s2,s1.compare(s2)< 时,称s1 小于s2.下面的例子使用构造方法TreeSet()创建了一个树集,并填加了4个节点.
  • 29. tree.java
  • 30. 2.用构造方法TreeSet(Comparator c)创建一个树集 但很多对象不适合用字典序进行比较,这时我们在创建树集时可自己规定节点按着什么样的”大小”顺序排列.假如我们有四个学生对象,他们有姓名和成绩,我们想把这四个对象做为一个树集的节点,并按着成绩的高低排列节点,而不是按着姓名的字典序排列节点.
  • 31. 首先创建学生的Student类必须实现接口 Comparable.Comparable 接口中有一个方法 public int compareTo(Object b) Student类通过实现这个接口来规定它创建的对象的大小关系,如下所示.
  • 32. (本页无文本内容)
  • 33. Java规定 当 a.compareTo(b) 时,称二者相等 s1.compare(s2)> 时,称a大于b s1.compare(s2)< 时,称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 stu1.compareTo(stu2); }}); 注 Comparator 是java.util 包中的一个接口,compare 是接口中的方法,因此必须给出方法体.
  • 34. 注 树集中不容许出现大小相等的两个节点,例如,在上述例子中如果再添加语句 st5=new Student(76,"keng wenyi"); mytree.add(st5); 是无效的.如果允许成绩相同,可把上述例子中Student 类中的compareTo 方法更改为 public int compareTo(Object b) { Student st=(Student)b; if((this.english-st.English)==0) return 1; else return (this.english-st.english); } 注 理论上已经知道,把一个元素插入树集的合适位置要比插入数组或链表中的合适位置效率高.
  • 35. TreeSet类的一些常用方法 public boolean add(Object o) 向树集添加加节点,添加成功返回true,否则返回false. public void clear() 删除所有的节点. public void contains(Object o) 如果包含节点o返回true . public Object first() 返回根节点,即第一个节点 最小的节点 . public Object last() 返回最后一个节点 最大的节点 . public isEmpty() 判断是否是空树集,如果树集不含节点返回true . public boolean remove(Object o) 删除节点o. public int size() 返回节点数目.