Java数组：基础与操作详解

### Java 数组：基础与操作详解 #### 1. 数组概述 数组是最常用的数据存储结构，几乎内置于所有编程语言中。它是引入数据结构以及理解面向对象编程与数据结构之间关系的便捷起点。我们将介绍 Java 中的数组，并展示一个自制的数组类。同时，还会探讨一种特殊的数组——有序数组，其中的数据按升序（或降序）键序存储，这种排列方式使得二分查找成为可能。 #### 2. 数组操作的 Workshop 小程序演示 假设你正在指导儿童棒球联赛，需要记录练习场的球员出勤情况。你可以使用一个简单的数据结构来存储这些数据，并执行以下操作： - 球员到达场地时，将其插入数据结构。 - 通过在结构中搜索球员编号，检查特定球员是否在场。 - 球员回家时，从数据结构中删除该球员。 这些插入、搜索和删除操作是大多数数据存储结构的基本操作。我们可以使用名为 Array 的 Workshop 小程序来演示数组如何实现这些操作。 启动 Array Workshop 小程序的步骤如下： ```plaintext C:\>appletviewer Array.html ``` 这个小程序有以下功能按钮： - **Ins 按钮**：插入新数据项。 - **Find 按钮**：搜索指定的数据项。 - **Del 按钮**：删除指定的数据项。 - **New 按钮**：创建指定大小的新数组。 - **Fill 按钮**：用随机生成的数据项填充数组，数据项的编号范围是 0 到 999，且数组大小不能超过 60 个单元格。 创建新数组时，需要决定是否允许重复项。默认设置是不允许重复项，因此“无重复项”单选按钮初始时会被选中。 ##### 2.1 插入操作 从默认的 20 个单元格和 10 个数据项开始，选择“无重复项”按钮。插入新项的步骤如下： 1. 按下 Ins 按钮一次，会提示输入要插入项的键值。 2. 在小程序右上角的文本框中输入一个数字，例如 678。 3. 再次按下 Ins 按钮，小程序会确认你的选择。 4. 最后一次按下按钮，包含该值和随机颜色的数据项将出现在数组的第一个空单元格中。 插入过程非常快，只需要一步，因为新项总是插入到数组的第一个空单元格中。 ##### 2.2 搜索操作 开始搜索的步骤如下： 1. 点击 Find 按钮，会提示输入要查找的人的键号。 2. 输入一个数字，然后反复按下 Find 按钮。每次按下按钮，算法会执行一步，红色箭头会从单元格 0 开始，依次检查每个单元格。 3. 当找到指定项时，会显示相应的消息。 假设不允许重复项，搜索算法平均需要查看一半的数据项才能找到指定项。在最坏的情况下，指定项在最后一个占用的单元格中，需要 N 步才能找到。 ##### 2.3 删除操作 删除项的步骤如下： 1. 输入要删除项的编号，反复按下按钮，直到找到该项。 2. 按下 Del 按钮删除该项，单元格将变为空。 3. 为了避免数组中出现空洞，后续单元格的内容会向下移动一个空间以填充空洞。 删除操作平均需要搜索 N/2 个元素，然后移动 N/2 个元素来填充空洞，总共需要 N 步。 ##### 2.4 重复项问题 设计数据存储结构时，需要决定是否允许具有重复键的项。对于棒球球员，不允许重复编号；而对于员工的姓氏，可能会有重复值，因此可以允许重复项。 Workshop 小程序允许你选择是否允许重复项。当选择“允许重复项”时，搜索算法会变得复杂，因为即使找到匹配项，也需要继续查找可能的其他匹配项，直到最后一个占用的单元格，这需要 N 步。插入操作不受重复项的影响，仍然只需要一步。删除操作可能会更复杂，具体取决于“删除”的定义。 以下是不同情况下三种操作的平均比较和移动次数： |操作|无重复项|允许重复项| | ---- | ---- | ---- | |搜索|N/2 次比较|N 次比较| |插入|无比较，1 次移动|无比较，1 次移动| |删除|N/2 次比较，N/2 次移动|N 次比较，超过 N/2 次移动| #### 3. Java 中数组的基础知识 ##### 3.1 创建数组 在 Java 中，有两种类型的数据：基本类型（如 int 和 double）和对象。数组在 Java 中被视为对象，因此必须使用 new 运算符来创建数组。创建数组的示例代码如下： ```java int[] intArray; // 定义一个数组引用 intArray = new int[100]; // 创建数组，并将 intArray 指向它 ``` 或者使用单语句方式： ```java int[] intArray = new int[100]; ``` 也可以使用另一种语法： ```java int intArray[] = new int[100]; // 替代语法 ``` 数组有一个 length 字段，可以用来查找数组的大小： ```java int arrayLength = intArray.length; // 查找数组大小 ``` 创建数组后，不能更改其大小。 ##### 3.2 访问数组元素 使用方括号中的索引编号来访问数组元素，这与其他语言类似： ```java temp = intArray[3]; // 获取数组第四个元素的内容 intArray[7] = 66; // 将 66 插入到第八个单元格 ``` 在 Java 中，第一个元素的编号是 0，因此 10 个元素的数组的索引范围是 0 到 9。如果使用的索引小于 0 或大于数组大小减 1，会出现“数组索引越界”运行时错误。 ##### 3.3 初始化 除非另有指定，整数数组在创建时会自动初始化为 0。即使是在方法中定义的数组也是如此。创建对象数组时，如果没有为数组元素赋予显式值，它们将包含特殊的 null 对象。如果尝试访问包含 null 的数组元素，会出现“空指针赋值”运行时错误。 可以使用以下语法将基本类型的数组初始化为非零值： ```java int[] intArray = { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27 }; ``` 这个单语句替代了引用声明和使用 new 创建数组的操作，花括号内的数字称为初始化列表，数组的大小由列表中的值的数量决定。 #### 4. 数组示例程序 以下是一个旧版的过程式 Java 程序示例： ```java // array.java // demonstrates Java arrays // to run this program: C>java arrayApp //////////////////////////////////////////////////////////////// class ArrayApp { public static void main(String[] args) { long[] arr; // reference to array arr = new long[100]; // make array int nElems = 0; // number of items int j; // loop counter long searchKey; // key of item to search for //-------------------------------------------------------------- arr[0] = 77; // insert 10 items arr[1] = 99; arr[2] = 44; arr[3] = 55; arr[4] = 22; ```