java技术从入门到精通(孙鑫)学习笔记Lesson 6（数据结构）.doc

LinkedListl LinkedList是采用双向循环链表实现的。l 利用工作之便LinkedList实现栈（stack）、队列（queue）、双向队列（double-ended queue）。import java.util.*;class MyStackprivate LinkedList ll=new LinkedList();public void push(Object o)ll.addFirst(o);public Object pop()return ll.removeFirst();public Object peek()return ll.getFirst();public boolean empty()return ll.isEmpty();public static void main(String args)MyStack ms=new MyStack();ms.push(one);ms.push(two);ms.push(three);System.out.println(ms.pop();System.out.println(ms.peek();System.out.println(ms.pop();System.out.println(ms.empty();运行结果为： three two two false import java.util.*;class MyQueueprivate LinkedList ll=new LinkedList();public void put(Object o)ll.addLast(o);public Object get()return ll.removeFirst();public boolean empty()return ll.isEmpty();public static void main(String args)MyQueue mq=new MyQueue();mq.put(one);mq.put(two);mq.put(three);System.out.println(mq.get();System.out.println(mq.get(); System.out.println(mq.get(); System.out.println(mq.empty();运行结果为： one two threeArrayList和LinkedList的比较l ArrayList底层采用数组完成，而LinkedList则是以一般的双向链表(double-linked list)完成，其内每个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素。l 如果我们经常在List的开始处增加元素，或者在List中进行插入和删除操作，我们应该使用LinkedList，否则的话，使用ArrayList将更加快速。HashSetl 实现Set接口（不能有重复元素）的hash table（哈希表），依靠HashMap来实现的。import java.util.*;class HashSetTestpublic static void main(String args)HashSet hs=new HashSet();hs.add(one);hs.add(two);hs.add(three);hs.add(one);Iterator it=hs.iterator();while(it.hasNext()System.out.println(it.next();运行结果为： one two threeimport java.util.*;class HashSetTestpublic static void main(String args)HashSet hs=new HashSet();hs.add(new Student(1,zhangsan);hs.add(new Student(2,lisi);hs.add(new Student(3,wangwu);hs.add(new Student(1,zhangsan);Iterator it=hs.iterator();while(it.hasNext()System.out.println(it.next();class Studentint num;String name;Student(int num,String name)this.num=num;=name;public String toString()return num+:+name;运行结果为： 3：wangwu 2：lisi 1：zhangsan 1：zhangsanl 我们应该为要存放到散列表的各个对象定义hashCode()和equals()。import java.util.*;class HashSetTestpublic static void main(String args)HashSet hs=new HashSet();hs.add(new Student(1,zhangsan);hs.add(new Student(2,lisi);hs.add(new Student(3,wangwu);hs.add(new Student(1,zhangsan);Iterator it=hs.iterator();while(it.hasNext()System.out.println(it.next();class Studentint num;String name;Student(int num,String name)this.num=num;=name;public int hashCode()return num*name.hashCode();public boolean equals(Object o) Student s=(Student)o;return num=s.num&name.equals();public String toString()return num+:+name;运行结果为： 1：zhangsan 3：wangwu 2：lisi散列表l 散列表又称为哈希表。散列表算法的基本思想是：以结点的关键字为自变量，通过一定的函数关系（散列函数）计算出对应的函数值，以这个值作为该结点存储在散列表中的地址。l 当散列表中的元素存放太满，就必须进行再散列，将产生一个新的散列表，所有元素存放到新的散列表中，原先的散列表将被删除。在Java语言中，通过负载因子（load factor）来决定何时对散列表再散列。例如：如果负载因子是0.75,当散列表中已经有75%的位置已经放满，那么将进行再散列。l 负载因子越高（越接近1.0），内存的使用效率越高，元素的寻找时间越长。负载因子越低（越接近0.0），元素的寻找时间越短，内存浪费越多。l HashSet类的缺省负载因子是0.75。TreeSetl TreeSet是依靠TreeMap来实现的。l TreeSet是一个有序集合，TreeSet中元素将按照升序排列，缺省是按照自然顺序进行排列，意味着TreeSet中元素要实现Comparable接口。l 我们可以在构造TreeSet对象时，传递实现了Comparator接口的比较器对象。import java.util.*;class TreeSetTestpublic static void main(String args)TreeSet ts=new TreeSet();ts.add(winsun);ts.add(weixin);ts.add(mybole);Iterator it=ts.iterator();wh