实用数据结构辅导知识点.docx

《实用数据结构辅导知识点.docx》由会员分享，可在线阅读，更多相关《实用数据结构辅导知识点.docx（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -1数组， Arrays类常璐璐，赵玉霞编可编辑资料 - - - 欢迎下载精品名师归纳总结学习目标：1. 把握关于数组概念2. 把握 Arrays类以及常用方法1. 回忆数组概念、定义及使用 。2. 把握 Arrays类常用方法3. 继承关系： Arrays类是Object类直接子类。如下图所示：Java 的二分查找算法:private static int binarySearch0Object a, int fromIndex, int toIndex, Object key int low = fro

2、mIndex; int high = toIndex - 1; while low = high int mid = low + high /2;Comparable midVal = Comparableamid; int cmp = midVpareTokey;if cmp 0high = mid - 1;elsereturn mid; / key foundArrays 类常用方法 :sort对指定的类型数组按数字升序进行排序。binarySearch 使用二分搜寻法来搜寻指定的类型数组， 以获得指定的值。equals用于比较两个数组是否相等。fill 用以某个值填充整个数组。asLis

3、t接受任意的数组为参数，将其转变为List 容器。算法思想描述：查找的数组必需是按关键字值排好序。减半查找范畴，确定待查元素是否存在于数组中。1、猎取中间元素的位置，拿带查元素与中间位置元素比较。2、比中间元素大，在后半部分找。3、比中间元素小，在前半部分找。可编辑资料 - - - 欢迎下载精品名师归纳总结return -low + 1; / key not found.留意问题：sort的使用binarySearch的使用 数组与 Arrays 类的区分练习：请参见读程序写结果中程序1、程序 2、程序 3可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - -

4、- - - - -第 1 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -2 List 、ArrayList学习目标：1. 把握 ArrayList的详细使用2. 把握 List接口的实现ArrayList是一种线性表，在内存中是连续储备的，适合于元素的随机存取。添加和删除操作是需要依据添加的位置来定，假如在ArrayList 最终元素后面添加和删除元素，在性能方面仍算好，但是假如是在ArrayList中间添加和删除元素的话，代价就会很大。1. ArrayList结

5、构 特点 ：数组大小固定，ArrayList可以自动增加空间可编辑资料 - - - 欢迎下载精品名师归纳总结3. 遍历方法 for循环语句： forint i=0;i;i+迭代器： Iterator it = list.iterator; while it.hasNext E e = it.next; forEach结构： forE e : list 4. 明白 ArrayList与 Vector的区分5List接口的实现6. 继承关系如下图：ArrayList常用方法：size返回此列表中的元素数。get返回此列表中指定位置上的元素。set用指定的元素替代此列表中指定位置上的元素。add 将

6、指定的元素添加到此列表的尾部。将指定的元素插入此列表中的指定位置。contains假如此列表中包含指定的元素，就返回true。remove移除此列表中指定位置上的元素。ObjecttoArray按 适 当 顺 序（从第一个到最终一个元素）返回包含此列表中全部元素的数组。可编辑资料 - - - 欢迎下载精品名师归纳总结1. List是有序的Collection，使用此接口能够精确的掌握每个元素插入的位置。2. List接口与其常用实现类的继承实现关系：可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 22 页 - - - -

7、 - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -3. 对比 List接口的两个常用实现类简述实现操作特性成员要求可编辑资料 - - - 欢迎下载精品名师归纳总结List供应基于索引的对成员的随机拜访ArrayListLinkedList供应快速的基于索引的成员拜访，对尾部成员的增加和删除支持较好对列表中任何位置的成员的增加和删除支持较好，但对基于索引的成员拜访支持性能较差成员可为任意Object子类的对象成员可为任意Object子类的对象可编辑资料 - - - 欢迎下载精品名师归纳总结1、上机实现

8、下面程序public static void mainString argsList list = new ArrayList; forint i=0;i5;i+list.add编程词典 +i;ListIterator li = list.listIterator; whileli.hasNextSystem.out.printlnli.next;1、 练习：请参见读程序写结果中程序4、程序 52、 创建一个类Cat： 包含属性name，在构造方法中进行初始化。添加一个方法show ，用以打印 name属性的值创建一个类CatTest ：添加main 方法，实现创建一个ArrayList，向其

9、中添加几个Cat对象遍历该集合，并且对每个Cat 对象调用show 方法参考代码： class Catprivate String name; public CatString namethis.name = name;public void showSystem.out.printlnname;public class CatTest public static void mainString args/ 创建一个 ArrayList，向其中添加几个Cat 对象。ArrayList list = new ArrayList;list.addnew Catmimi; list.addnew C

10、atqiqi;list.addnew Catding;/ 遍历该集合，并且对每个Cat 对象调用 show 方法。forint i= 0;ilist.size;i+Cat c = Catlist.geti; c.show; 可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -3 LinkedList学习目标：1. 把握 LinkedList类的使用方法2.

11、把握栈和队列的概念可编辑资料 - - - 欢迎下载精品名师归纳总结1. 结点、链表的概念以及链式储备的思想2. LinkedList类的常用方法（对比 ArrayList）的把握3. 与 ArrayList类比较，各自特点，如何应用、挑选4. 用 LinkList类实现栈和队列栈中常用方法：pop从今列表所表示的堆栈处弹出一个元素。push将元素推入此列表所表示的堆栈。LinkedList的常用方法：add 向链表末尾添加一个新的节点remove删除指定位置上的节点。删除首次显现含有数据elemen 的节点。get得到链表中指定位置处节点中的对象。set将当前链表 index 位置结点中的对象

12、替换为参数 element 指定的对象，并返回被替换的对象。新增以下新方法： 构造方法 LinkedListgetFirst 和 getLastremoveFirst 和 removeLastaddFirst 和 addLast可编辑资料 - - - 欢迎下载精品名师归纳总结5、类继承关系如图：List接口实现：可编辑资料 - - - 欢迎下载精品名师归纳总结1. LinkedList是采纳双向循环链表实现的。2. 利 用LinkedList实 现 栈stack、队列 queue 、双向队列 double-ended queue 采纳链表的方法来实现栈：用方法addFirstObject el

13、ement实现进栈操作。用方法 removeFirst 实现出栈。用方法 getFirst 实现栈顶数据查询。用方法 isEmpty 实现栈是否为空。可编辑资料 - - - 欢迎下载精品名师归纳总结练习：请参见读程序写结果中程序6、程序 7、程序 7上机操作： 创建一个类Stack ，代表堆栈（其特点为：后进先出），添加方法 addObject obj、以及 delete ，添加 main 方法进行验证，要求：使用 LinkedList实现堆栈在向 LinkedList中添加时，使用addLast 方法在从 LinkedList中取出时，使用removeLast 方法可编辑资料 - - - 欢

14、迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -4 Collections与 Collection学习目标：1. 会使用 Collections类 2. 把握 Collection接口可编辑资料 - - - 欢迎下载精品名师归纳总结1. 明白 Collection接口2. 把握 Collection接口常用方法3. 把握 Collections类中常用方法4 Comparable

15、 与 Comparator的区分联系5、Collections类的继承关系：Collection接口中常用方法:toArray返回包含此collection 中全部元素的数组。add 确保此 collection 包含指定的元素。equals 比较此 collection 与指定对象是否相等。hashCode 返回此 collection 的哈希码值。size 返回此 collection 中的元素数。iterator 返回调用类集的迭代程序remove从调用类集中删除 obj 的一个实例。假如这个元素被删除了，就返回 true。否就返回 false可编辑资料 - - - 欢迎下载精品名师归纳

16、总结可编辑资料 - - - 欢迎下载精品名师归纳总结6、Collection接口的继承关系：1.Collections中的大多数方法都与List或 collection有关。2 、 Collection的遍历：Collection的实 际 类 型 如 何 ， 它 都 支 持 一 个iterator的方法，该方法返回一个迭代 器 ， 使 用 该 迭 代 器 即 可 逐 一 访 问Collection中 每 一 个 元 素 。 借 助Iterator接口实现。Collections类中常用方法:binarySearch 使用二分搜寻法搜寻指定列表， 以获得指定对象。sort依据元素的自然次序对指定

17、列表按升序进行排序。synchronizedMap返回由指定映射支持的同步（线程安全的）映射。synchronizedSet 返回指定set 支持的同步（线程安全的） set。sort、reverse、max、min 、fill 等方法1 Collection 是最基本的集合接口，一个Collection 代表一组 Object，即 Collection 的元素（ Elements）。一些 Collection 答应相同的元素而另一些不行。一些能排序而另一些不行。JavaSDK 不供应直接继承自Collection 的类， JavaSDK 供应的类都是继承自Collection 的“子接口 ”

18、如 List 和 Set 。2 Collections 类完全由在collection 上进行操作或返回 collection 的静态方法组成。它包含在collection 上操作的多态算法，即“包装器 ”，包装器返回由指定collection 支持的新 collection ，以及少数其他内容。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - -

19、- - - - - - - - - -Iterator接口结构：模板代码：可编辑资料 - - - 欢迎下载精品名师归纳总结利用 Collection接口的iterator 获得一个实现了Iterator 接口的迭代器，然后利用其完成Collection接口对象的遍历操作。模板代码如右所示：对象排序方法：1、Comparable 接口全部可以”排序“的类都实现了java.lang.Comparable 接口Iterator it=collection.iterator;/获得一个迭代器whileit.hasNext Object obj = it.next;/得到下一个元素Comparable

20、接口中只有一个方法：public int compareToObject obj;可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结2、Comparator接口Comparator 通常在对于自然排序不能满意需要时使用。Comparator 接口定义了两个方法：compare 和 equals 。public interface Comparator int compareT o1, T o2; boolean equalsObject obj;可编辑资料 - - - 欢迎下载精品名师归纳总结练习：请参见读程序写结果中程序9（ Collection

21、s）练习：请参见读程序写结果中程序10（ Collections、Iterator接口）练习：请参见读程序写结果中程序11（ Comparator 接口）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -5 Set与 HashSet学习目标：1把握 Set 接口常用方法2. 把握 HashSet的特点及学会使用HashSet 类 3. 明白其它的Set 接

22、口实现类可编辑资料 - - - 欢迎下载精品名师归纳总结1、Set 接口：扩展了 Collection接口， Set接口是Collection接口的子接口，不包含重复元素。它采纳全部原始方法，并且 未引入任何新方法。继承关系如下图：Set 接口定义：publicinterfaceSet extendsCollection / 接口定义请参照API 帮忙文档Set 接口中的常用方法:可编辑资料 - - - 欢迎下载精品名师归纳总结2、Set接口供应了两种通用实现：HashSet和 TreeSetHashSet，采纳散列函数对元素进行排序，这是特的为快速查询而设计的。来储备不重复的集合。TreeS

23、et ，当需要以一种排序的方式从集合中提取元素的时候使用。为了正确运行，添加到 TreeSet中的元素必需是可排序的。采纳二叉树的数据结构进行排序元素。可编辑资料 - - - 欢迎下载精品名师归纳总结3、HashSet 类定义： 是 Set 接口最常用的实现之 一 ， 存 入HashSet的 对 象 必 须 定 义 hashCode ，其元素在其中储备不保证任何顺序。实际上，HashSet储备对象引用时是依据哈希策略 来实现的。publicclassHashSetextends AbstractSetimplementsSet ,Cloneable,java.io.Serializable/详

24、细方法实现参考API帮忙文档HashSet 类常用方法：HashSet 类继承关系：可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 7 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -HashSet 类的几个构造器:public HashSet ： 该构造器将构造一个空的 HashSet 对象。该对象的初始容量为 16。publicHashSetintini

25、talCapacity：参数initalCapacity表 示 指 定 的 初 始 容量，该构造器将构造一个具有指定容量的空 HashSet 对象。publicHashSetCollectionc ： 参数 c 为包含指定元素的Collection。该构造器将构造一个以c 中的元素为初始内容的HashSet 对象。4、 TreeSet类 定 义 ： 实 现了SortedSet接口，此类保证排序后的Set依据升序排列元素，底层为树结构。使用它可以从Set 中提取有序的序列。publicclassTreeSetextends AbstractSetimplementsNavigableSet, C

26、loneable, java.io.SerializableTreeSet类继承关系：TreeSet类中常用方法见右图：1 Set 中的几个重要方法：equals、contains、hashCode 2 Set 接口中元素具有唯独性，改写equals方法。Set是一种不包含重复的元素的Collection，即任意的两个元素e1 和e2 都有e1.equalse2=false， Set 最多有一个null元素。3 HashSet散 列 hash， 特 点 ： 查 找 的 高 效 率 （ 例 如 两 个 集 合 相 交 ） ， 改 写hashCode 方法分析： HashSet 要求放入的对象必需

27、实现hashCode 方法，放入的对象，是以hashcode 码作为标识的，而具有相同内容的String对象， hashcode是一样，所以放入的内容不 能重复。但是同一个类的对象可以放入不同的实例。4明白其它的Set 相关类：LinkedHashSet可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 8 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结随堂练

28、习：1、分析程序，写出结果import java.util.Collection; import java.util.HashSet; import java.util.Iterator; public class SetTest2 public static voidmainStringargs Collection c;c = new HashSet ;c.add1;c.add3;c.add2;Iterator it = c.iterator; while it.hasNext System.out.printlnit.next; /返回集合元素2、分析程序，写出结果 import jav

29、a.util.*;public class HashSetTest public static voidmainString args HashSet set = new HashSet; set.add1st;set.add2nd;set.add3rd;set.addnew StringFour; set.addnew Integer6;set.add“ 2nd” ;/重复的元素没有被加入System.out .printlnset;/元素的次序与加入的次序没有关系可编辑资料 - - - 欢迎下载精品名师归纳总结练习：请参见读程序写结果中程序12（Arrays和 HashSet ）练习：请参

30、见读程序写结果中程序13（TreeSet和 SortedSet ）可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 9 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -6 Map与 HashMap学习目标：1把握 Map接口的使用2. 把握 HashMap类的应用可编辑资料 - - - 欢迎下载精品名师归纳总结1、 Map接口：将键映射到值的对象。一个映射不能 包含重复的键。每个键最多只能映射 到一个值。M

31、ap 看起来比较像由映射组 成 的Set。 Map接 口 不 是Collection接口的继承。定义：publicinterfaceMapMap接口中常见方法：可编辑资料 - - - 欢迎下载精品名师归纳总结/详细方法请查看API 帮忙文档继承关系：其 中 重 要 方 法 :get、 put、 equals、hashCode、keySet、values、containsKey、 containsValue2、 Map接口的可用实现类主要有：HashMap,TreeMap,Hashtable,Properties其中： Hashtable,Properties是 JDK1.0/1.1中的。 Ha

32、shMap对 key 进行散列。 HashMap通过哈希码对其内部的映射关系进行快速查找。 TreeMap 依据 key 进行排序。 TreeMap 中的映射关系存在肯定的次序，假如期望在遍历集合时是有序的，就应当使用由TreeMap 类实现的Map 集合，否就建议使用由HashMap类实现的Map 集合，由于由HashMap 类实现的Map 集合对于添加和删除映射关系更高效。3、 Map接口供应三种collection视图答应以键集、值集或键- 值映射关系集的形式查看某个映射的内容。答应以三种方法将映射视作集合。如下表：keySet是映射中包含的键集Set keys=map. keySet;

33、values是映射中的值的集合Collectionsvalues=map.values;entrySet是包含在映射中的键- 值对的集Set kvs=map. entrySet;可编辑资料 - - - 欢迎下载精品名师归纳总结4、 HashMap类定义： HashMap类实现了Map接口publicclassHashMap extendsAbstractMapimplementsMap,HashMap的常用方法：可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 10 页，共 22 页 -

34、 - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -Cloneable, Serializable/ 详细方法请查看API帮忙文档继承关系：HashMap类常见方法见右图：其中重要的方法有：get、 put、 equals、hashCode、keySet、values、containsKey、containsValue5、 HashMap类说明： 由 HashMap 类实现的Map 集合，答应以null作为键对象，但是由于键对象不行以重复，所以这样的键对象只能有一个。假如常常需要添加、删除

35、和定位映射关系，建议利用 HashMap类实现 Map集合，不过在遍历集合时，得到的映射关系是无序的。 在使用由HashMap类实现的Map集合时，需要重写作为主键对象类的hashCode 方法重写 hashCode 方法时，有以下两条基本原就：（ 1）不唯独原就：不必为每个对象生成一个唯独的哈希码，只要通过hashCode 方法生成的哈希码能够利用get方法得到利用put方法添加的映射关系就可以。（ 2）分散原就：生成哈希码的算法应尽量使哈希码的值分散一些，不要许多哈希码值都集中在一个范畴内，这样有利于提高由HashMap类实现的Map集合的性能。6、 遍历 HashMap的方法：/ 遍历方

36、法1for Iterator iter=map.keySet.iterator; iter.hasNext; System.out.printlniter.next;/ 遍历方法2Iterator iter=map.keySet.iterator; while iter.hasNext System.out.printlniter.next;可编辑资料 - - - 欢迎下载精品名师归纳总结7、 TreeMap 类定义 : TreeMap 类不仅实现了Map 接口，仍实现了Map 接口的子接口java.util.SortedMap。支持对键有序的 遍历，使用时建议先用HashMap 增加和删 除

37、 成 员 ， 最 后 从HashMap 生 成TreeMap 类常用方法：可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 11 页，共 22 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -TreeMap。publicclassTreeMap extendsAbstractMap implementsNavigableMap, Cloneable, java.io.Ser

38、ializable/详细方法请查看API 帮忙文档继承关系：TreeMap 类中的较重要的方法：除了get、 put、 equals、 hashCode 、keySet、 values、 containsKey、containsValue等方法外，有comparator、 compare 、 firstKey、 lastKey、headMap 、subMap 、tailMap等。8、 TreeMap 类说明：键成员要求实现Comparable 接口，或者使用Comparator 构造 TreeMap 键成员一般为同一类型。9、 hashCode 方法由于作为 key 的对象将通过运算其散列函数来确定与之对应的val