2022年实用数据结构辅导知识点 .pdf

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

1、 1 数组， Arrays类学习目标：1. 掌握关于数组概念2. 掌握 Arrays类以及常用方法1.回忆数组概念、定义及使用 ；2.掌握 Arrays 类常用方法3.继承关系： Arrays类是 Object类直接子类。如下图所示：Arrays类常用方法 : sort()对指定的类型数组按数字升序进行排序。binarySearch()使用二分搜索法来搜索指定的类型数组，以获得指定的值。equals()用于比较两个数组是否相等。fill() 用以某个值填充整个数组。asList()接受任意的数组为参数，将其转变为 List 容器。Java 的二分查找算法: private static int

2、 binarySearch0(Object a, int fromIndex, int toIndex, Object key) int low = fromIndex; int high = toIndex - 1; while (low = high) int mid = (low + high) /2; Comparable midVal = (Comparable)amid; int cmp = midVpareTo(key); if (cmp 0) high = mid - 1; else return mid; / key found return -(low + 1); / ke

3、y not found. 算法思想描述：查找的数组必须是按关键字值排好序；减半查找范围，确定待查元素是否存在于数组中。1、获取中间元素的位置，拿带查元素与中间位置元素比较；2、比中间元素大，在后半部分找；3、比中间元素小，在前半部分找。注意问题：sort()的使用binarySearch()的使用数组与 Arrays 类的区别练习：请参见读程序写结果中程序1、程序 2、程序 3 常璐璐，赵玉霞编精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 23 页 - - - - - - - - - - 2

4、 List 、ArrayList 学习目标：1. 掌握 ArrayList的具体使用2. 掌握 List接口的实现ArrayList 是一种线性表，在内存中是连续存储的，适合于元素的随机存取。添加和删除操作是需要依据添加的位置来定，如果在ArrayList 最后元素后面添加和删除元素，在性能方面还算好，但是如果是在ArrayList 中间添加和删除元素的话，代价就会很大。1.ArrayList结构 特点：数组大小固定，ArrayList可以自动增加空间ArrayList常用方法：size()返回此列表中的元素数。get()返回此列表中指定位置上的元素。set()用指定的元素替代此列表中指定位置

5、上的元素。add()将指定的元素添加到此列表的尾部；将指定的元素插入此列表中的指定位置。contains()如果此列表中包含指定的元素，则返回 true。remove()移除此列表中指定位置上的元素。Object toArray()按 适 当 顺 序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。3. 遍历方法for 循环语句： for(int i=0;i;i+) 迭代器： Iterator it = list.iterator(); while( it.hasNext() ) E e = it.next(); forEach 结构： for(E e : list) 4. 了解 Ar

6、rayList与 Vector 的区别5List接口的实现6. 继承关系如下图：1.List是有序的 Collection，使用此接口能够精确的控制每个元素插入的位置。2.List接口与其常用实现类的继承实现关系：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 23 页 - - - - - - - - - - 3.对比 List接口的两个常用实现类简述实现操作特性成员要求List 提供基于索引的对成员的随机访问ArrayList 提供快速的基于索引的成员访问，对尾部成员的增加和删除支持较好成员

7、可为任意Object子类的对象LinkedList 对列表中任何位置的成员的增加和删除支持较好，但对基于索引的成员访问支持性能较差成员可为任意Object子类的对象1、上机实现下面程序public static void main(String args) List list = new ArrayList(); for(int i=0;i5;i+) list.add(编程词典 +i); ListIterator li = list.listIterator(); while(li.hasNext() System.out.println(li.next(); 1、 练习：请参见读程序写结果中

8、程序4、程序 52、 创建一个类Cat ：包含属性name ，在构造方法中进行初始化；添加一个方法show() ，用以打印 name属性的值创建一个类CatTest ：添加 main 方法，实现创建一个ArrayList，向其中添加几个Cat对象遍历该集合，并且对每个Cat 对象调用 show() 方法参考代码： class Cat private String name; public Cat(String name) this.name = name; public void show() System.out.println(name); public class CatTest pub

9、lic static void main(String args)/ 创建一个 ArrayList，向其中添加几个Cat 对象；ArrayList list = new ArrayList(); list.add(new Cat(mimi); list.add(new Cat(qiqi); list.add(new Cat(ding);/ 遍历该集合，并且对每个Cat 对象调用 show() 方法。for(int i= 0;ilist.size();i+) Cat c = (Cat)list.get(i); c.show(); 精品资料 - - - 欢迎下载 - - - - - - - - -

10、 - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 23 页 - - - - - - - - - - 3 LinkedList 学习目标：1. 掌握 LinkedList类的使用方法2. 掌握栈和队列的概念1. 结点、链表的概念以及链式存储的思想2.LinkedList类的常用方法（对比 ArrayList）的掌握3. 与 ArrayList类比较，各自特点，如何应用、选择LinkedList的常用方法：add()向链表末尾添加一个新的节点remove()删除指定位置上的节点；删除首次出现含有数据elemen的节点。get()得到链表中指定位置处节点中的对象。s

11、et()将当前链表index 位置结点中的对象替换为参数element 指定的对象，并返回被替换的对象。4. 用 LinkList类实现栈和队列栈中常用方法：pop()从此列表所表示的堆栈处弹出一个元素。push()将元素推入此列表所表示的堆栈。新增以下新方法：构造方法 LinkedList() getFirst()和 getLast() removeFirst()和 removeLast() addFirst()和 addLast()5、类继承关系如图：List接口实现：1.LinkedList是采用双向循环链表实现的。2. 利 用LinkedList实 现 栈(stack)、队列 (que

12、ue) 、双向队列(double-ended queue ) 采用链表的方法来实现栈：用方法addFirst(Object element)实现进栈操作。用方法 removeFirst()实现出栈。用方法 getFirst()实现栈顶数据查询。用方法 isEmpty() 实现栈是否为空。练习：请参见读程序写结果中程序6、程序 7、程序 7 上机操作： 创建一个类Stack ，代表堆栈（其特点为：后进先出），添加方法 add(Object obj)、以及 delete( )，添加 main 方法进行验证，要求：使用 LinkedList实现堆栈在向 LinkedList中添加时，使用addLas

13、t( )方法在从 LinkedList中取出时，使用removeLast( )方法精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 23 页 - - - - - - - - - - 4 Collections 与 Collection学习目标：1. 会使用 Collections类 2. 掌握 Collection接口1. 了解 Collection接口2. 掌握 Collection接口常用方法3. 掌握 Collections类中常用方法Collection接口中常用方法: toArray(

14、) 返回包含此 collection 中所有元素的数组。add() 确保此 collection 包含指定的元素。equals() 比较此 collection 与指定对象是否相等。hashCode() 返回此 collection 的哈希码值。size() 返回此 collection 中的元素数。iterator() 返回调用类集的迭代程序remove()从调用类集中删除obj 的一个实例。如果这个元素被删除了，则返回true；否则返回false4Comparable 与 Comparator 的区别联系5、Collections类的继承关系：Collections类中常用方法: bina

15、rySearch()使用二分搜索法搜索指定列表，以获得指定对象。sort()根据元素的自然顺序对指定列表按升序进行排序。synchronizedMap() 返回由指定映射支持的同步（线程安全的）映射。synchronizedSet() 返回指定set 支持的同步（线程安全的） set。sort()、reverse()、max()、min()、fill() 等方法6、Collection接口的继承关系：1.Collections中的大多数方法都与List或 collection有关。1Collection 是最基本的集合接口，一个Collection 代表一组 Object，即 Collecti

16、on 的元素（Elements）。一些 Collection 允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK 不提供直接继承自Collection 的类， Java SDK 提供的类都是继承自Collection 的“ 子接口 ”如 List 和 Set。2Collections 类完全由在 collection 上进行操作或返回 collection 的静态方法组成。它包含在collection 上操作的多态算法，即“ 包装器 ” ，包装器返回由指定 collection 支持的新 collection，以及少数其他内容。2、 Collection 的遍历： Colle

17、ction的实 际 类 型 如 何 ， 它 都 支 持 一 个iterator()的方法，该方法返回一个迭代器 ， 使 用 该 迭 代 器 即 可 逐 一 访 问Collection中 每 一 个 元 素 。 借 助Iterator接口实现。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 23 页 - - - - - - - - - - Iterator接口结构：模板代码：Iterator it=collection.iterator(); / 获得一个迭代器while(it.hasNext(

18、) Object obj = it.next(); / 得到下一个元素利用 Collection接口的iterator()获得一个实现了Iterator 接口的迭代器，然后利用其完成Collection 接口对象的遍历操作。模板代码如右所示：对象排序方法：1、Comparable 接口所有可以”排序“的类都实现了java.lang.Comparable 接口Comparable 接口中只有一个方法：public int compareTo(Object obj); 2、Comparator 接口Comparator 通常在对于自然排序不能满足需要时使用。Comparator 接口定义了两个方法

19、：compare( )和equals( )。 public interface Comparator int compare(T o1, T o2); boolean equals(Object obj); 练习：请参见读程序写结果中程序9（ Collections）练习：请参见读程序写结果中程序10（ Collections、Iterator接口）练习：请参见读程序写结果中程序11（ Comparator 接口）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 23 页 - - - - - -

20、 - - - - 5 Set 与 HashSet 学习目标：1掌握 Set 接口常用方法2. 掌握 HashSet 的特点及学会使用HashSet 类 3. 了解其它的Set 接口实现类1、Set 接口：扩展了 Collection 接口， Set 接口是Collection接口的子接口，不包含重复元素。它采用所有原始方法，并且未引入任何新方法。继承关系如下图：Set 接口定义：publicinterface Set extends Collection / 接口定义请参照API 帮助文档Set 接口中的常用方法: 2、Set 接口提供了两种通用实现：HashSet 和 TreeSet Has

21、hSet ，采用散列函数对元素进行排序，这是专门为快速查询而设计的；来存储不重复的集合。TreeSet ，当需要以一种排序的方式从集合中提取元素的时候使用。为了正确运行，添加到 TreeSet 中的元素必须是可排序的。采用二叉树的数据结构进行排序元素。3、HashSet 类定义： 是 Set 接口最常用的实现之 一 ， 存 入HashSet的 对 象 必 须 定 义hashCode() ，其元素在其中存储不保证任何顺序。实际上，HashSet 存储对象引用时是按照哈希策略 来实现的。publicclassHashSet extendsAbstractSet implementsSet , Cl

22、oneable, java.io.Serializable / 具体方法实现参考API 帮助文档HashSet 类常用方法：HashSet 类继承关系：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 23 页 - - - - - - - - - - HashSet 类的几个构造器: public HashSet()： 该构造器将构造一个空的HashSet 对象。该对象的初始容量为16。public HashSet(int initalCapacity)：参数initalCapacity表 示

23、指 定 的 初 始 容量，该构造器将构造一个具有指定容量的空 HashSet 对象。public HashSet(Collection c) ： 参数 c 为包含指定元素的Collection。该构造器将构造一个以c 中的元素为初始内容的HashSet 对象。4、 TreeSet类 定 义 ： 实现了SortedSet接口，此类保证排序后的Set按照升序排列元素，底层为树结构。使用它可以从Set中提取有序的序列。publicclassTreeSet extendsAbstractSet implementsNavigableSet, Cloneable, java.io.Serializabl

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

25、 方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的String对象， hashcode 是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例。4了解其它的Set 相关类： LinkedHashSet 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 23 页 - - - - - - - - - - 随堂练习：1、分析程序，写出结果import java.util.Collection; import java.util.HashSet; import java

26、.util.Iterator; public class SetTest2 public static void main(Stringargs) Collection c; c = new HashSet (); c.add(1); c.add(3); c.add(2); Iterator it = c.iterator(); while (it.hasNext() System.out.println(it.next(); / 返回集合元素 2、分析程序，写出结果import java.util.*; public class HashSetTest public static void

27、main(String args) HashSet set = new HashSet(); set.add(1st); set.add(2nd); set.add(3rd); set.add(new String(Four); set.add(new Integer(6); set.add(“2nd”); / 重复的元素没有被加入 System.out.println(set); / 元素的顺序与加入的顺序没有关系 练习：请参见读程序写结果中程序12（Arrays和 HashSet）练习：请参见读程序写结果中程序13（TreeSet 和 SortedSet ）精品资料 - - - 欢迎下载

28、- - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 23 页 - - - - - - - - - - 6 Map 与 HashMap 学习目标：1掌握 Map接口的使用 2. 掌握 HashMap类的应用1、 Map接口：将键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。Map 看起来比较像由映射组 成 的Set 。 Map接 口 不 是Collection 接口的继承。定义：publicinterface Map /具体方法请查看API 帮助文档继承关系：Map接口中常见方法：其 中 重 要 方 法 :

29、get()、 put()、 equals()、hashCode()、keySet()、values()、containsKey()、 containsValue() 2、 Map接口的可用实现类主要有：HashMap,TreeMap,Hashtable,Properties 其中： Hashtable,Properties是 JDK1.0/1.1中的。HashMap对 key 进行散列。 HashMap通过哈希码对其内部的映射关系进行快速查找。TreeMap 按照 key 进行排序。 TreeMap 中的映射关系存在一定的顺序，如果希望在遍历集合时是有序的，则应该使用由TreeMap 类实现的

30、Map 集合，否则建议使用由HashMap类实现的Map 集合，因为由HashMap 类实现的Map 集合对于添加和删除映射关系更高效。3、 Map接口提供三种collection 视图允许以键集、值集或键- 值映射关系集的形式查看某个映射的内容。允许以三种方法将映射视作集合。如下表：keySet 是映射中包含的键集Set keys=map. keySet(); values是映射中的值的集合Collections values=map. values(); entrySet 是包含在映射中的键-值对的集Set kvs=map. entrySet(); 4、 HashMap类定义： HashM

31、ap类实现了 Map接口publicclass HashMap extends AbstractMap implementsMap, HashMap的常用方法：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 23 页 - - - - - - - - - - Cloneable, Serializable / 具体方法请查看API 帮助文档 继承关系：HashMap类常见方法见右图：其中重要的方法有：get()、 put()、equals()、hashCode()、keySet()、value

32、s()、containsKey()、containsValue() 5、 HashMap类说明：由 HashMap 类实现的Map 集合，允许以null作为键对象，但是因为键对象不可以重复，所以这样的键对象只能有一个。如果经常需要添加、删除和定位映射关系，建议利用 HashMap类实现 Map集合，不过在遍历集合时，得到的映射关系是无序的。在使用由HashMap类实现的Map集合时，需要重写作为主键对象类的hashCode() 方法重写 hashCode() 方法时，有以下两条基本原则：（1）不唯一原则：不必为每个对象生成一个唯一的哈希码，只要通过hashCode 方法生成的哈希码能够利用ge

33、t() 方法得到利用put()方法添加的映射关系就可以。（2）分散原则：生成哈希码的算法应尽量使哈希码的值分散一些，不要很多哈希码值都集中在一个范围内，这样有利于提高由HashMap类实现的Map集合的性能。6、 遍历 HashMap的方法：/ 遍历方法 1 for (Iterator iter=map.keySet().iterator(); iter.hasNext();) System.out.println(iter.next(); / 遍历方法 2 Iterator iter=map.keySet().iterator(); while (iter.hasNext() ) Syste

34、m.out.println(iter.next(); 7、 TreeMap 类定义 : TreeMap 类不仅实现了Map 接口，还实现了Map 接口的子接口java.util.SortedMap。支持对键有序地遍历，使用时建议先用HashMap增加和删 除 成 员 ， 最 后 从HashMap 生 成TreeMap类常用方法：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 23 页 - - - - - - - - - - TreeMap。publicclass TreeMap extend

35、s AbstractMap implementsNavigableMap, Cloneable, java.io.Serializable /具体方法请查看API 帮助文档继承关系：TreeMap类中的较重要的方法：除了get() 、 put()、equals()、hashCode() 、keySet()、 values()、 containsKey()、containsValue()等方法外，有comparator()、 compare() 、 firstKey()、 lastKey()、headMap() 、subMap() 、tailMap()等。8、 TreeMap类说明：键成员要求实

36、现Comparable 接口，或者使用Comparator 构造 TreeMap 键成员一般为同一类型。9、hashCode() 方法由于作为 key 的对象将通过计算其散列函数来确定与之对应的value 的位置，因此任何作为key 的对象都必须实现hashCode和 equals 方法。 hashCode和 equals 方法继承自根类Object ，如果你用自定义的类当作key 的话，要相当小心，按照散列函数的定义，如果两个对象相同，即obj1.equals(obj2)=true，则它们的hashCode必须相同；但如果两个对象不同，则它们的hashCode 不一定不同，如果两个不同对象的

37、 hashCode 相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode() 方法，能加快哈希表的操作。注意：在使用由HashMap类实现的Map 集合时，需要重写作为主键对象类的hashCode()方法前提要先重写equals()方法。练习：请参见读程序写结果中程序14（Map和 HashMap ）上机实验：创建一个 Book 类 ：包含属性：title（标题），使用构造方法进行初始化重写 toString()方法，用以返回Title属性的值创建一个 BookTest 测试类，添加main 方法，要求：使用 HashMap进行存储，键为Book对象的编

38、号，值为Book 对象通过某一个编号获取Book 对象，并打印该Book 对象的标题精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 23 页 - - - - - - - - - - 读程序写结果程序 1：importjava.util.* ; publicclassArraysDemo publicstaticvoidmain(String args) inttemp = 3, 5, 7, 9, 1, 2, 6, 8 ;/ 声明一个整型数组Arrays.sort(temp);/ 数组排序Sy

39、stem.out.print(排序后的数组) ; System.out.println(Arrays.toString(temp) ;/ 以字符串输出数组intpoint = Arrays.binarySearch(temp, 3) ; / 检索数据位置System.out.println(元素 3 的位置在： + point) ; Arrays.fill(temp, 3) ; / 填充数组System.out.print(数组填充： ) ; System.out.println(Arrays.toString(temp) ; / 以字符串输出数组 程序 2：import java.util.

40、Arrays; public class Quest public static void main(String args) String colors = blue,red,green,yellow,orange; Arrays.sort(colors); System.out.println(Arrays.deepToString(colors); int s2 = Arrays.binarySearch(colors, orange); int s3 = Arrays.binarySearch(colors, violet); System.out.println(s2+ +s3);

41、程序 3：/ Using Java arrays. import java.util.Arrays; public class UsingArrays 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 23 页 - - - - - - - - - - private int intArray = 1, 2, 3, 4, 5, 6 ; private double doubleArray = 8.4, 9.3, 0.2, 7.9, 3.4 ; private int filledIntArray

42、, intArrayCopy; / 构造方法，初始化数组public UsingArrays() filledIntArray = new int10; / 创建 10 元素的int型数组， filledIntArray持有引用intArrayCopy = new intintArray.length;/创建含有6 个int型元素的数组，intArrayCopy持有引用 / 输出数组元素public void printArrays() System.out.print(doubleArray: ); for (double doubleValue : doubleArray) System.

43、out.printf(%.1f , doubleValue); System.out.print(nintArray: ); for (int intValue : intArray) System.out.printf(%d , intValue); System.out.print(nfilledIntArray: ); for (int intValue : filledIntArray) System.out.printf(%d , intValue); System.out.print(nintArrayCopy: ); for (int intValue : intArrayCop

44、y) System.out.printf(%d , intValue); System.out.println(n); / end method printArrays public int searchForInt(int value) / 在 int型数组中查找元素return Arrays.binarySearch(intArray, value); public void printEquality() / 比较数组内容boolean b=Arrays.equals(intArray, intArrayCopy); System.out.printf(intArray %s intAr

45、rayCopyn, (b ? = : !=); b=Arrays.equals(intArray, intArrayCopy); System.out.printf(intArray %s filledIntArrayn, (b ? = : !=); / end method printEquality public static void main(String args) UsingArrays usingArrays = new UsingArrays(); usingArrays.printArrays(); usingArrays.printEquality(); 精品资料 - -

46、- 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 23 页 - - - - - - - - - - int location = usingArrays.searchForInt(5); if (location = 0) System.out.printf(Found 5 at element %d in intArrayn, location); else System.out.println(5 not found in intArray); location = usingArrays.searchFo

47、rInt(8763); if (location = 0) System.out.printf(Found 8763 at element %d in intArrayn, location); else System.out.println(8763 not found in intArray); / end main 程序 4：import java.util.List; import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; public class CollectionTes

48、t private static final String colors = MAGENTA, RED, WHITE, BLUE, CYAN ; private static final String removeColors = RED, WHITE, BLUE ; / 创建 ArrayList, 向容器中添加colors public CollectionTest() List list = new ArrayList(); List removeList = new ArrayList(); / 把 colors数组中的元素添加到list列表中for (String color : co

49、lors) list.add(color); / 把 removeColor 数组中的元素添加到removeList列表中for (String color : removeColors) removeList.add(color); System.out.println(ArrayList: ); / 输出列表内容for (int count = 0; count list.size(); count+) System.out.printf(%s , list.get(count);/使用泛型化后就不用强制类型转换/ 把 removeList列表中的内容从list列表中移除removeCol

50、ors(list, removeList); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 23 页 - - - - - - - - - - System.out.println(nnArrayList after calling removeColors: ); / 输出列表内容for (String color : list) System.out.printf(%s , color); / 从 collection1中 移除 collection2 指定的内容private void