数据结构与算法（Java语言版）课件 第6章 顺序表与ArrayList类

第6章顺序表与ArrayList类2024/11/916.1顺序表的特点2024/11/92顺序表也是线性表的一种具体体现，顺序表节点形成的逻辑结构是线性结构、节点的存储结构是顺序存储，即节点的物理地址是依次相邻的。2024/11/936.1顺序表的特点顺序表使用数组来实现，顺序表的节点的物理地址是依次相邻的，因此可以随机访问任何一个节点，不必从头节点计数查找其它节点。●查询节点

2024/11/946.1顺序表的特点和链表不同，顺序表没有单独添加头节点的操作，但是有添加尾节点的操作。●添加节点

2024/11/956.1顺序表的特点

●删除节点

6.2创建顺序表2024/11/96顺序表由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayList<E>泛型类所实现。2024/11/976.2创建顺序表ArrayList<E>泛型类的实列使用数组管理节点，因此节点就是对象，后面的叙述不再说节点里的对象。ArrayList<E>泛型类实现了Java集合框架中的List泛型接口(和链表不同，没有实现Queue泛型接口)。ArrayList<E>泛型类继承了List泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List泛型接口中的抽象方法。2024/11/986.2创建顺序表顺序表可以使用add(Eobj)方法向顺序表依次增加节点。创建空顺序表，使用ArrayList<E>泛型类声明顺序表时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定顺序表中节点（对象）的类型。例如，指定E是String类型：ArrayList<String>arrlistOne=newArrayList<>();或ArrayList<String>arrlistOne=newArrayList<String>();例子1Example6_1.java例子1中的主类Example6_1中首先创建一个空顺序表arrlistOne，然后向空链表arrlistOne添加3个节点，随后再用arrlistOne中的节点创建顺序表arrlistTwo。修改arrlistTwo的节点，并不影响arrlistOne的节点.6.3顺序表常用方法2024/11/99voidadd(intindex,Ee)向顺序表的index指定位置添加一个新的节点e（时间复杂度O(n)）。publicbooleancontains(Objectobj)判断顺序表中是否有对象obj，如果有节点是对象obj返回true，否则返回false(时间复杂度O(n))。

Eremove(intindex)返回顺序表的第index节点，并删除顺序表的第index节点（时间复杂度O(n)）。booleanremove(Objecto)删除顺序表中首次出现是obj的节点，删除成功返回true，否则返回false（时间复杂度O(n)）。2024/11/9106.3

顺序表常用方法例子2Example6_2.java例子2中的主类Example6_2中比较了顺序表的get(intindex)方法和链表的get(intindex)方法的运行耗时，可以看出顺序表的耗时明显小于链表的耗时。2024/11/9116.3顺序表常用方法例子3Example6_3.java例子3的主类Example6_3使用了顺序表的一些常用方法.booleanremoveIf(Predicate<?superE>filter)删除满足filter给出的条件的全部节点（时间复杂度O(n)）。Predicate是一个函数接口，其中唯一的抽象方法是booleantest(Tt)，在使用removeIf(Predicate<?superE>filter)方法时，可以将一个Lambda表达式传递给参数filter，该Lambda表达式的有一个参数，类型和节点类型一致，Lambda表达式的返回值类型是boolean型。6.4遍历顺序表2024/11/912ArrayList的存储结构是顺序结构，即节点的物理地址是依次相邻的，因此，顺序表完全可以调用get(intindex)方法来遍历节点。迭代器分单向迭代器和双向迭代器，对于线性表，单向迭代器只能向尾节点方向依次遍历节点（称向后遍历），双向迭代器可以向尾节点方向依次遍历节点，也可以向头节点方向依次遍历节点（称向前遍历）。有关向迭代器和双向迭代器的详细知识点参看第5章的5.9节。2024/11/9136.4遍历顺序表例子4Example6_4.java例子4中的主类Example6_4中使用双向迭代器遍历一个顺序表，该顺序表的每个节点是一个小写英文字母。双向迭代器在遍历节点的过程中，动态添加新的节点，当向后遍历时（尾部节点方向），在当节点的遍历方向的前面（尾节点方向）依次插入2个新节点，一个新节点是当前节点的ASCII的值（即在UNICODE表中的顺序位置），另一个新节点是当前节点的大写字母。2024/11/9146.4遍历顺序表例子5Example6_5.javaArrayList类提供的publicvoidforEach(Consumer<?superE>action)方法的参数类型是Consumer函数接口，该接口中的抽象方法voidaccept(Tt)的返回类型是void型。那么在调用forEach(Consumer<?superE>action)方法时，可以将一个Lambda表达式传递给action例子5的主类Example6_5动态遍历节点是Integer对象的一个顺序表，在遍历这个顺序表时，让节点Integer对象参与运算，输出Integer对象的二进制、八进制和十六进制。6.5顺序表与筛选法2024/11/915筛法的算法从2开始：2是素数，把素数2保存，然后把2后面所有能被2整除的数都划去。数字2后面第1个没划去的数是素数3，把素数3保存，然后再把3后面所有能被3整除的数都划去。3后面第1个没划去的数是素数5，把素数5保存，然后再把5后面所有能被5整除的数都划去。……按照筛法，每次留下的数字中的第1个数字一定是素数，如此继续进行，就会把不超过N的全部合数都筛掉，保存的就是不超过N的全部素数。2024/11/9166.5顺序表与筛选法例子6PrimeFilter.java

Example6_6.java

例子6主类Example6_6使用ArrayList<Integer>primeFilter(intn)方法输出200内的全部素数，以及200以内孪生素数。6.6顺序表与全排列2024/11/917

2024/11/9186.6顺序表与全排列例子7FullPermutatio.javaExample6_7.java

●递归法求全排列2024/11/9196.6顺序表与全排列例子8Example6_8.java●数字填空

例子8中的主类Example6_8，使用全排列的办法给出了所有满足九宫格填数字要求的8种方案。如果考虑旋转、镜像相同的属于同一种，那么这8种方案都是一样的。

2024/11/9206.6顺序表与全排列●迭代法求全排列对于字符1，2，3，5，6，7，8组成的全排列，按字典序，最小的是12345678，最大的是87654321。从最小的全排列（或最大的全排列）开始，按着字典序依次寻找下一个全排列，一直到找到最大的（最小的）全排列为止，就可以给出全部的全排列。这里，我们通过找34587621的下一个全排列，介绍基于字典序找全排列的算法。①寻找正序相邻对在全排列的相邻对中找到最后一对“正序相邻对”（小的在前、大的在后）。2024/11/9216.6顺序表与全排列●迭代法求全排列这里，我们通过找34587621的下一个全排列，介绍基于字典序找全排列的算法。②寻找最小字符

对于：58，找到的字符是6。字符6以后的字符（假如有的话）都比字符5小2024/11/9226.6顺序表与全排列这里，我们通过找34587621的下一个全排列，介绍基于字典序找全排列的算法。③最小字符与pairLast的首字符互换

2024/11/9236.6顺序表与全排列34587621的下一个全排列：34612578。④反转子序列

例子9DictionaryPermutatio.javaExample6_9.java6.7顺序表与组合2024/11/924

2024/11/9256.7顺序表与组合●迭代求组合和排列不同，[1,2,3]和[1,3,2]是不同的排列，是相同的组合。因此，表示组合时可以让组合里的数字都是升序的。

该组合中的每个数，按顺序存放到一个顺序表list中。

得到下一个组合[1,4,5]2024/11/9266.7顺序表与组合●迭代求组合例子10Combination.javaExample6_10.java例子10中Combination类的方法C(intn,intr,List<Integer>start)返回组合start的下一个组合.例子10中的主类Example6_10使用Combination类的方法输出从7个数中取5个数的全部组合.2024/11/9276.7顺序表与组合●递归求组合例子11RecurrenceCom.javaExample6_11.java参考递归求杨辉三角形（见第3章例子9），可以写出递归求组合的算法（作者反复画递归图，找出了递归的规律，见RecurrenceCom类.

2024/11/9286.7顺序表与组合●组合与砝码称重例子12Weight.javaExample6_12.java有n多个重量不同的砝码各一枚，比如，4个重量不同的砝码：1克，3克，5克和8克。能称出多少种重量。有些组合可能称出相同的重量，比如用一个5克的砝码可以称出5克重量，用1个2克砝码和1个3克砝码，同样也可以称出5克重量。遍历全部的组合，发现能称出相同的重量的组合（即方案）时，保留一个即可。

如果允许砝码放在天秤的两端（允许放在被称重的物体一端），那么就把另一端（被称重的物体一端）的砝码拿回到放置砝码的一端、并变成“负码”（重量是负数），就将问题转化为砝码只放天秤一端的情况。6.8顺序表与记录2024/11/929有时候，需要将一维数组，比如一个记录学生成绩的一维数组，看作一个整体，称作一条记录（如果学过数据库，相当于表中的一条记录）。借助顺序表，可以批量处理记录，比如，排序纪录。2024/11/9306.8顺序表与记录●顺序表与一维数组例子13Example6_13.javaArrays类的静态方法：static<T>List<T>asList(T...a)返回一个顺序表。该方法是可变参数，可以把若干个类型相同的对象放入一个顺序表，也可以把一个数组放入一个顺序表。顺序表调用public<T>T[]toArray(T[]a)方法，可以把节点，存到一个数组中。在使用这个方法之前，要实现预备一个数组，长度为1即可，将这个数组传递给toArray(T[]a)方法的参数a，此参数仅仅是通知该方法再创建新的一维数组、将顺序表节点放到新数组中，并返回这个新的数组的引用。2024/11/9316.8顺序表与记录●顺序表与二维数组例子14Example6_14.java二维数组是由若干多个一维数组所构成，即若干条记录所构成，例如，二维数组a:int[][]a={{90,89,77,68},{72,50,97,69},{52,50,67,79}};由3条记录构成。例子14的主类Example6_14把一个二维数据中的记录放入顺序表，并对顺序表中记录进行排序.6.8Vector类2024/11/932Vector<E>泛型类实现了Java集合框架中的List泛型接口(和链表不同，没有实现Queue泛型接口)。Vector<E>泛型类继承了List泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List泛型接口中的抽象方法。Vector<E>泛型类和ArrayList<E>泛型类的主要区别是，Vector<E>泛型类提供的方法都是同步(synchronized)方法，即是线性安全的，而ArrayList<E>泛型类不是线性安全的。当有多个线程访问同一个ArrayList类型的顺序表时，用户必须自己考虑多线程带来的问题，比如一个线程修改顺序表时，是否允许另一个线程访