数组的基础知识

要点提示 ： 一旦数组被创建 ， 它的大小是固定的 。 使用一个數组引用变量 ， 通过下标来访问數组中的元素。

数组是用来存储数据的集合 ， 但是 ， 通常我们会发现把数组看作一个存储具有相同类型的变量集合会更有用 。 无须声明单个变量 ， 例如 ： numberO , numberl , number 99 , 只要声明一个数组变量 numbers , 并且用 numbers [ 0 ] , numbers [ 1 ] ,...,numbers [99] 来表示单个变童 。 本节介绍如何声明数组变量 、 创建数组以及使用下标变量处理数组 。

声明数组变置

为了在程序中使用数组 ， 必须声明一个引用数组的变量 ， 并指明数组的元索类型 。 下面是声明数组变量的语法 ：

double [ ] myList ;

注意 ： 也可以用 elementTypearrayRefVar [ ] ( 元素类型数组引用变量 [ ] ) 声明数组变量 。 这种来自 C / C + + 语言的风格被 Java 采纳以适用于 C / C + + 程序贞 。 推荐使用elementType [ ] arrayRefVar ( 元素类型 [ ] 数组引用变量 ） 风格.

创建数组

不同于基本数据类型变量的声明 ， 声明一个数组变量时并不在内存中给数组分配任何空间 。 它只是创建一个对数组的引用的存储位置 。 如果变量不包含对数组的引用 ， 那么这个变量的值为 null 。 除非数组已经被创建 ， 否则不能给它分配任何元素 。 声明数组变量之后,可以使用下面的语法用 nev * 操作符创建数组 ， 并且将它的引用賦给一个变量 ：arrayRefVar = new e 1 ementType [ arrayS 1 ze ] ;

这条语句做了两件事情 ： 1 ) 使用 new elementType [ arrayS " ize ] 创建了一个数组 ； 2 )把这个新创建的数组的引用陚值给变暈 arrayRefVar。

声明一个数组变量 、 创建数组 、 然后将数组引用賦值给变量这三个步驟可以合并在一条语句里 ， 如下所示 ：

elementType 口 arrayRefVar = new elementType [ arraySize ] ;

( 元素类型 [ ] 数组引用变量 = new 元素类型 [ 数组大小 ] ;

或

elementType arrayRefVar [ ] * new e 1 ementType [ arraySize ];

( 元素类型数组引用变量 = new 元素类型 [ 数组大小 ] ;

注意 ： 一个數组变量看起来似乎是存储了一个數组 ， 但实际上它存储的是指向数组的引用 。 严格地讲 ， 一个數组变量和一个教组是不同的 ， 但多教情况下它们的差别是可以忽略的 。 因此 ， 为了简化 ， 通常可以说 myList 是一个数组 ， 而不用更长的陈述 ： myList 是一个含有 10 个 double 型元素數组的引用变量 。

数组大小和默认值

当给数组分配空间时 ， 必须指定该数组能够存储的元素个数 ， 从而确定数组大小 。 创建数组之后就不能再修改它的大小 。 可以使用 arrayRefVar . length 得到数组的大小。可以使用 arrayRefVar . length 得到数组的大小 。

当创建数组后 ， 它的元素被賦予默认值 ， 数值型基本数据类型的默认值为 0 , char 型的默认值为 AuOOOO ’ ， boolean 型的默认值为 false。

访问数组元素

数组元素可以通过下标访问 。 数组下标是基于 0 的 ， 也就是说 ， 其范围从 0 开始到arrayRefVar . length - 1 结束 。

瞀告 ： 一些语言使用圆括号引用数组元素 ， 例如 myList ( 9 ) 。 而 Java 语言使用方括号。

数组初始化语法

Java 有一个简捷的标记 ， 称作数组初始化语法 ， 它使用下面的语法将声明数组 、 创建数组和初始化数组结合到一条语句中 ：

例如 ：

这条语句声明 、 创建并初始化包含 4 个元素的数组 myLi st , 它等价于下列语句 ：

 

警告 ： 数组初始化语法中不使用操作符 new 。 使用数组初始化语法时 ， 必须将声明 、 创建和初始化数组都放在一条语句中 。 将它们分开会产生语法嫌谈 。 因此 ， 下面的语句是嫌误的 ：

 

处理数组

处理数组元素时 ， 经常会用到 for 循环 ， 理由有以下两点 ：

1 ) 数组中所有元素都是同一类型的 。 可以使用循环以同样的方式反复处理这些元素。

2 ) 由于数组的大小是已知的 ， 所以很自然地就使用 for • 循环 。

假设创建如下数组 ：

下面是一些处理数组的例子 ：

foreach 循环

Java 支持一个简便的 for 循环 ， 称为 foreach 循环 ， 即不使用下标变量就可以顺序地遍历整个数组 。 例如 ， 下面的代码就可以显示数组 myList 的所有元素 ：

此代码可以读作“ 对 myList 中每个元素 e 进行以下操作 ” 。 注意 ， 变量 e 必须声明为与myList 中元素相同的数据类型 。

通常 ， foreach 循环的语法为 ：

但是 ， 当需要以其他顺序遍历数组或改变数组中的元素时 ， 还是必须使用下标变量 。

数组的复制

要点提示 ： 要将一个数组中的内容复制到另外一个中 ， 你需要将数组的每个元素复制到另外一个数组中 。

在程序中经常需要复制一个数组或数组的一部分 。 这种情况下 ， 你可能会尝试使用賦值语句 （ = ) , 如下所示 ：

该语句并不能将 listl 引用的数组内容复制给 list 2 , 而只是将 listl 的引用值复制给了ist 2 。 在这条语句之后 ， listl 和 list 2 都指向同一个数组 ， 如图 7 * 4 所示 。 list 2 原先所引用的数组不能再引用 ， 它就变成了垃圾 ， 会被 Java 虚拟机自动收回 （ 这个过程称为垃圾回收）。

在 Java 中 ， 可以使用賦值语句复制基本数据类型的变量 ， 但不能复制数组 。 将一个数组变童賦值给另一个数组变量 ， 实际上是将一个数组的引用复制给另一个变量 ， 使两个变量都指向相同的内存地址。

复制数组有三种方法 ：

1 ) 使用循环语句逐个地复制数组的元素 。

2 ) 使用 System 类中的静态方法 arraycopy 。

3 ) 使用 clone 方法复制数组 ， 这将在第 13 章中介绍 。

可以使用循环将源数组中的每个元素复制到目标数组中的对应元素 。

另一种方式是使用 java . lang . System 类的 arraycopy 方法复制数组 ， 而不是使用循环。arraycopy 的语法如下所示 ：

arraycopy ( sourceArray , srcPos , targetArray , tarPos , length ) ；

其中 ， 参数 srcPos 和 tarPos 分别表示在源数组 sourceArray 和目标数组 targetArray 中的起始位置 。 从 sourceArray 复制到 targetArray 中的元素个数由参数 length 指定 。 例如，可以使用下面的语句改写上述循环 ：

System . arraycopy ( sourceArray , 0 , targetArray , 0 ， sourceArray . length ) 

arraycopy 方法没有给目标数组分配内存空间 。 复制前必须创建目标数组以及分配给它的内存空间 。 复制完成后 ， sourceArray 和 targetArray 具有相同的内容 ， 但占有独立的内存空间 。 注意 ： arraycopy 方法违反了 Java 命名习惯 。 根据命名习慣 ， 该方法应该命名为 arrayCop( 即字母 C 大写 ） 。

将数组传递给方法

要点提示 ： 当将一个數组传递给方法时 ， 數组的引用被传给方法。

正如前面给方法传递基本数据类型的值一样 ， 也可以给方法传递数组 。 例如 ， 下面的方法显示 int 型数组的元素 ：

可以通过传递一个数组调用上面的方法 。

注意 ： 前面的语句使用下述语法创建数组 ：

从方法中返回数组

要点提示 ： 当从方法中返回一个数组时 ， 数组的引用被返回 。

可以在调用方法时向方法传递一个数组 。 方法也可以返回一个数组 。 例如 ， 下面的方法返回一个与输人数组元素顺序相反的数组 ：

 

线性查找法

线性査找法将要査找的关键字 key 与数组中的元素逐个进行比较 。 这个过程持续到在列表中找到与关键字匹配的元素 ， 或者査完列表也没有找到关键字为止 。 如果匹配成功 ， 线性査找法返回与关键字匹配的元素在数组中的下标 。 如果没有匹配成功 ， 则返回
- 1。 程序清单 7 - 6 中的" MnearSearch方法给出解决方案 ：

线性査找法把关键字和数组中的每一个元素进行比较 。 数组中的元素可以按任意顺序排列 。 平均来看 ， 如果关键字存在 ， 那么在找到关键字之前 ， 这种算法必须与数组中一半的元素进行比较 。 由于线性査找法的执行时间随着数组元素个数的增长而线性增长 ， 所以 ， 对于大数组而言 ， 线性査找法的效率并不高 。

二分查找法

二分査找法是另一种常见的对数值列表的査找方法 。 使用二分査找法的前提条件是数组中的元素必须已经排好序 。 假设数组已按升序排列 。 二分査找法首先将关键字与数组的中间元素进行比较 。 考虑下面三种情况 ：

如果关键字小于中€元素 ， 只需要在数组的前一半元素中继续査找关键字 。

如果关键字和中间元素相等 ， 则匹配成功 ， 査找结束 。

如果关键字大于中间元素 ， 只需要在数组的后一半元素中继续査找关键字 。

显然 ， 二分法在每次比较之后就排除掉一半的数组元素 ， 有时候是去掉一半的元素 ， 有时候是去掉一半加 1 个元素 。 假设数组有个元素 。 为方便起见 ， 假设 n 是 2 的幂 。 经过第1 次比较 ， 只剩下 n / 2 个元素需要进一步査找 ； 经过第 2 次比较 ， 剩下 （ n / 2 ) / 2 个元素需要进— 步査找 。 经过 k 次比较之后 ， 需要査找的元素就剩下 n / 2k个 。 当 hl 0 g 2 n 时 ， 数组中只剩下 1 个元素 ， 就只需要再比较丨次 。 因此 ， 在一个已经排序的数组中用二分査找法査找一个元素 ， 即使是最坏的情况 ， 也只需要 login + l 次比较 。 对于一个有 1024 ( 2 W ) 个元素的数组，在最坏情况下 ， 二分査找法只需要比较 11 次 ， 而在最坏的情况下线性査找要比较 1023 次 。

每次比较后 ， 数组要査找的部分就会缩小一半 。 用 low 和 high 分别表示当前査找数组的第一个下标和最后一个下标 。 初始条件下 ， low 为 0 , 而 high 为 list . length - 1 。 让 nrid表示列表的中间元素的下标 。 这样 ， mid 就是 （ low + high ) / 2 。 图 7 - 9 显示怎样使用二分法从列表 { 2 , 4 , 7 , 10 , 11 , 4 S , S 0 , 59 , 60 , 66 , 69 , 70 , 79 } 中找出关键字 11 。

现在知道了二分査找法是如何工作的 。 下一个任务就是在 Java 中实现它 。 不要急于给出一个完整的实现 。 逐步地实现这个程序 ， 一次一步 。 可以从査找的第一次迭代开始 ， 如图7 - 10 a 所示 。 它将关键字 key 和低下标 low 为 0 、 髙下标 high 为 list . length - 1 的列表的中7 - 10 a 所示 。 它将关键字 key 和低下标 low 为 0 、 髙下标 high 为 list . length - 1 的列表的中间元素进行比较 。 如果 key < list [ nrid ] , 就将下标 high 设置为 nrid - 1 ; 如果 key ~" Mst [ mid ] ,则匹配成功并返回 mid ; 如果 keydisttmid ] ， 就将下标 low 设置为 mid + 1 。

接下来就要考虑增加一个循环 ， 实现这个方法重复地完成査找 ， 如图 7 - 10 b 所示 。 如果找到这个关键字 ， 或者当 low > high 时还没有找到这个关键字 ， 就结束这个査找 。

 

当没有找到这个关键字时 ， low 就是一个插入点 ， 这个位置将插入关键字以保持列表的有序性 。 一种更实用的方法是返回插入点减去 1。 这个方法必须返回一个负值 ， 表明这个关键字不在该序列中 。 可以只返回-low 吗 ？ 答案是 ： 不可以 。 如果关键字小于 list [ 0 ] , 那么low 就是 0 ,-0 也是 0 。 这就表明关键字匹配 list [ 0 ] 。 一个好的选择是 ， 如果关键字不在该序列中 ， 方法返回-low - 1 。 返回不仅表明关键字不在序列中 ， 而且还给出了关键字应该插人的地方 。

 

数组的排序

要点提示 ： 如同查找一样 ， 排序是计算机编程中非常普遍的一个任务 。 对于排序已经开发出很多不同的算法 。 本节介绍一个直观的排序算法 ： 选择排序

假设要按升序排列一个数列 。 选择排序法先找到数列中最小的数 ， 然后将它和第一个元素交换 。 接下来 ， 在剩下的数中找到最小数 ， 将它和第二个元素交换 ， 依此类推 ， 直到数列中仅剩一个数为止 。 图 7 - 11 显示如何使用选择排序法对数列 { 2 , 9 , 5 , 4 , 8 , 1 , 6 } 进行排序 。

可以如下描述解决方案 ：