《数据结构与抽象:Java语言描述(原书第4版)》一2.2.1 可变大小数组

简介:

本节书摘来华章计算机《数据结构与抽象:Java语言描述(原书第4版)》一书中的第2章 ,第2.2.1节,[美]弗兰克M.卡拉诺(Frank M. Carrano) 蒂莫西M.亨利(Timothy M. Henry) 著 罗得岛大学  新英格兰理工学院 辛运帏 饶一梅 译 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.2.1 可变大小数组

策略。当教室满了时,能容纳更多学生的一种办法是移到一间更大的教室。用类似的方式,当数组满了时,可以将它的内容移到一个更大的数组中。这个过程称为调整(resizing)数组大小。图2-7显示两个数组:一个是有5个连续内存单元的原始数组,另一个数组(两倍于原始数组大小)在计算机的另一块内存中。如果将数据从原始的小数组中复制到新的大数组的开头部分,得到的结果像是扩展了原来的数组一样。这种机制的唯一不足是新数组的名字:你想让它与原始数组同名。马上就会看到如何完成这个工作。

image

细节。假定已有myArray指向的数组,如图2-8a所示。我们先定义一个别名oldArray,它也指向这个数组,如图2-8b所示。下一步是创建一个比原始数组更大的新数组,让myArray指向这个新数组。如图2-8c所示,一般地新数组要两倍于原始数组的大小。最后一步是将原始数组的内容复制到新数组中(见图2-8d),然后丢弃原始数组(见图2-8e)。下列伪代码概括了这些步骤:

image

图2-8 a)一个数组;b)指向同一数组的两个引用;c)原始数组变量现在指向新的更大的数组;d)原始数组中的项复制到新数组中;e)丢弃原始数组

注:当数组不再被引用时,它的内存在垃圾回收时被收回,就像是对其他对象发生的那样。
代码。将前面的伪代码转换为Java时,可以使用Java类库中的方法Arrays.copyOf (sourceArray, newLength)来做很多事情。例如,对如下的简单整数数组进行操作:

image

此时,myArray指向一个数组,如图2-9a所示。接下来,调用Arrays.copyOf。将变量myArray中的引用赋给这个方法的第一个参数sourceArray,如图2-9b所示。接下来,方法创建一个新的更大的数组,并将参数数组中的项复制给它(见图2-9c)。最后,方法返回指向新数组的一个引用(见图2-9d),我们将这个引用赋给myArray(见图2-9e)。下面的语句执行这些步骤:
image

图2-9 语句myArray = Arrays.copyOf(myArray, 2 * myArray.length);的效果。a)参数数组;
b)指向参数数组的参数;c)获得参数数组内容的新的更大的数组;d)指向新数组的返回值;
e)将返回值赋给参数变量

注:图2-9中的数组含有整数。这些整数是基本类型值,且像这样占据数组中的位置。与之相对,例如图2-6中的数组,含有指向对象的引用而不是对象本身。

调整数组的大小或许没有第一眼看上去这样有吸引力。每次扩展数组的大小时,必须复制它的内容。如果每次需要数组外的一个额外空间而让数组增大一个元素,则这个过程将耗时过大。例如,如果含50个元素的数组满了,为了容纳另一个项,需要将数组复制到有51个元素的数组中。再添加一项时又会要求你将含有51个元素的数组复制到含有52个元素的数组中,以此类推。每次添加都会导致复制数组。如果在原含有50个项的数组中添加100项,则要复制100次数组。
另一种做法是将数组扩展m个元素,将复制开销分摊在m次添加上而不是集中在一次上。每次当数组满时倍增它的大小,这是一种典型的方法。
例如,当在含有50个项的满数组中添加一项时,在进行添加前先将50个元素的数组复制到100个元素的数组中。那么接下来的49次添加都可以快速完成而不需要复制数组。所以数组复制只需一次。

程序设计技巧:当增大数组时,将它的项复制到更大的数组中。应该充分地扩展数组,以减少复制代价的影响。常用的办法是倍增数组大小。
注:说“调整数组的大小”实际上是用词不当,因为数组的长度不会改变。调整数组大小的过程是创建了一个含有原始数组项的全新数组。给新数组与原始数组一样的名字——换句话说,指向新数组的引用赋给指向原始数组引用的变量。然后丢弃原始数组。
注:引入一个类

若一个类使用了Java类库中的类,则它的定义前必须有import语句。例如,要使用类Arrays,应该将下面的语句写在你的类定义和描述性注释之前:
image

有些程序员将这条语句中的Arrays替换为星号,目的是在程序中可以使用包java.util中的所有类。

自测题18 考虑下列语句定义的字符串数组:

image

为数组text增大5个元素的容量且不改变当前内容的Java语句是什么?

自测题19 考虑字符串数组text。如果放到这个数组中的字符串的个数小于它的长度(容量),你如何减少数组的长度而不改变它的当前内容?假定字符串的个数保存在变量size中。

相关文章
|
6天前
|
Java
PTA帅到没朋友(Java语言)+测试点
PTA帅到没朋友(Java语言)+测试点
12 1
|
6天前
|
机器学习/深度学习 算法 Java
全排列(分治)(Java语言 +全排列模板)
全排列(分治)(Java语言 +全排列模板)
12 2
|
6天前
|
Java
阶乘末尾0的个数(Java语言+思路优化)
阶乘末尾0的个数(Java语言+思路优化)
8 1
|
6天前
|
Java C++
社交集群(pta) (并查集) Java语言
社交集群(pta) (并查集) Java语言
13 3
|
6天前
|
存储 Java
ZigZagging on a Tree二叉树蛇形层次遍历(Java语言)
ZigZagging on a Tree二叉树蛇形层次遍历(Java语言)
11 1
|
6天前
|
Java
Tree Traversals Again(Java语言)(先序和中序创建二叉树)(遍历树)
Tree Traversals Again(Java语言)(先序和中序创建二叉树)(遍历树)
13 4
|
1天前
|
存储 算法
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)(下)
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)
5 0
|
1天前
|
存储 算法 C语言
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)(上)
数据结构与算法②(复杂度相关OJ)(六道数组OJ题)
17 2
|
5天前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
6天前
|
Java C++
PTA 小字辈(Java语言)
PTA 小字辈(Java语言)
10 1