第6章 顺序表与ArrayList类.pptx

第6章顺序表与ArrayList类2024/9/101

6.1顺序表的特点2024/9/102顺序表也是线性表的一种具体体现，顺序表节点形成的逻辑结构是线性结构、节点的存储结构是顺序存储，即节点的物理地址是依次相邻的。

2024/9/1036.1顺序表的特点顺序表使用数组来实现，顺序表的节点的物理地址是依次相邻的，因此可以随机访问任何一个节点，不必从头节点计数查找其它节点。●查询节点??

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

2024/9/1056.1顺序表的特点?●删除节点?

6.2创建顺序表2024/9/106顺序表由Java集合框架（JavaCollectionsFramework，JCF）中的ArrayListE泛型类所实现。

2024/9/1076.2创建顺序表ArrayListE泛型类的实列使用数组管理节点，因此节点就是对象，后面的叙述不再说节点里的对象。ArrayListE泛型类实现了Java集合框架中的List泛型接口(和链表不同，没有实现Queue泛型接口)。ArrayListE泛型类继承了List泛型接口中的default关键字修饰的方法（去掉了该关键字），实现了List泛型接口中的抽象方法。

2024/9/1086.2创建顺序表顺序表可以使用add(Eobj)方法向顺序表依次增加节点。创建空顺序表，使用ArrayListE泛型类声明顺序表时，必须要指定E的具体类型，类型是类或接口类型（不可以是基本类型，比如int、float、char等）即指定顺序表中节点（对象）的类型。例如，指定E是String类型：ArrayListStringarrlistOne=newArrayList();或ArrayListStringarrlistOne=newArrayListString();例子1Example6_1.java例子1中的主类Example6_1中首先创建一个空顺序表arrlistOne，然后向空链表arrlistOne添加3个节点，随后再用arrlistOne中的节点创建顺序表arrlistTwo。修改arrlistTwo的节点，并不影响arrlistOne的节点.

6.3顺序表常用方法2024/9/109voidadd(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/9/10106.3顺序表常用方法例子2Example6_2.java例子2中的主类Example6_2中比较了顺序表的get(intindex)方法和链表的get(intindex)方法的运行耗时，可以看出顺序表的耗时明显小于链表的耗时。

2024/9/10116.3顺序表常用方法例子3Example6_3.java例子3的主类Example6_3使用了顺序表的一些常用方法.booleanremoveIf(Predicate?superEfilter)删除满足filter给出的条件的全部节点（时间复杂度O(n)）。Predicate是一个函数接口，其中唯一的抽象方法是booleantest(Tt)，在使用removeIf(Predicate?superEfilter)方法时，可以将一个Lambda表达式传递给参数filter，该Lambda表达式的有一个参数，类型和节点类型一致，Lambda表达式的返回值类型是boolean型。

6.4遍历顺序表2024/9/1012ArrayList的存储结构是顺序结构，即节点的物理地址是依次相邻的，因此，顺序表完全可以调用get(intindex)方法来遍历节点。迭代器分单向迭代器和双向迭代器，对于线性表，单向迭代器只能向尾节点方向依次遍历节点（称向后遍历），双向迭代器可以向尾节点方向依次遍历节点，也可以向头节点方向依次遍历节点（称向前遍历）。有关向迭代器和双向迭代器的详细知识点参看第5章的5.9节。

2024/9/10136.4遍历顺序表例子4Example6_4.java例子4中的主类Example6_4中使用双向迭代器遍历一个顺序表