5.2 一维数组

一维数组是最简单的数组，其逻辑结构是线性表。要使用一维数组，需要经过定义、初始化和应用等过程。

5.2.1 一维数组的定义

要使用Java语言的数组，一般需经过三个步骤：一是声明数组；二是分配空间；三是创建数组元素并赋值。前两个步骤的语法如下：

     数据类型[]数组名;      //声明一维数组
     数组名=new数据类型[个数];         //分配内存给数组

在数组的声明格式里，“数据类型”是声明数组元素的数据类型，可以是Java语言中任意的数据类型，包括基本类型和引用类型。“数组名”是用来统一这些相同数据类型的名称，其命名规则和变量的命名规则相同。其中“[]”指明该变量是一个数组类型变量，Java语言是将“[]”放到数组名的前面，但也可以像C/C++语言的定义方式将“[]”放在数组名的后面来定义数组，如“数据类型数组名[]；”。与C/C++语言不同，Java语言在数组的定义中并不为数组元素分配内存，因此“[]”中不用给出数组中元素的个数（即数组的长度），但必须在为它分配内存空间后才可使用。

数组声明之后，接下来便是要分配数组所需的内存，这时必须用运算符new，其中“个数”是告诉编译器，所声明的数组要存放多少个元素，所以new运算符是通知编译器根据括号里的个数，在内存中分配一块空间供该数组使用。利用new运算符为数组元素分配内存空间的方式称为动态内存分配方式。

下面举例来说明数组的定义。例如：

     int[]x;    //声明名称为x的int型数组
     x=new int[10]; //x数组中包含有10个元素,并为这10元素分配内存空间

在声明数组时，也可以将两个语句合并成一行，格式如下：

     数据类型[]数组名=new数据类型[个数];

利用这种格式在声明数组的同时，也分配一块内存供数组使用。如上面的例子可以写成如下形式：

     int[]x=new int[10];

等号左边的int[]x相当于定义了一个特殊的变量x，x的数据类型是一个对int型数组对象的引用，x就是一个数组的引用变量，其引用的数组元素个数不定。等号右边的new int[10]就是在堆内存中创建一个具有10个int型变量的数组对象。“int[]x=new int[10]；”就是将右边的数组对象赋值给左边的数组引用变量。若利用两行的格式来声明数组，其意义也是相同的。例如：

     int[]x;  //定义了一个数组x

这条语句执行完成后的内存状态如图5.1所示。

     x=new int[10]; //数组初始化

这条语句执行完后的内存状态如图5.2所示。

执行第2条语句“x=new int[10]；”后，在堆内存里创建了一个数组对象，为这个数组对象分配了10个整数单元，并将数组对象赋给了数组引用变量x。引用变量就相当于C语言中的指针变量，而数组对象就是指针变量指向的那个内存块。所以在Java内部还是有指针，只是把指针的概念对用户隐藏起来了，而用户所使用的是引用变量。

用户也可以改变x的值，让它指向另外一个数组对象，或者不指向任何数组对象。要想让x不指向任何数组对象，只需要将常量null赋给x即可。如“x=null；”这条语句执行完后的内存状态如图5.3所示。

执行完“x=null；”语句后，原来通过new int[10]产生的数组对象不再被任何引用变量所引用，变成了“孤儿”，也就成了垃圾，直到垃圾回收器来将它释放掉。

说明：数组用new运算符分配内存空间的同时，数组的每个元素都会自动赋一个默认值：整数为0，实数为0.0，字符为“\0”，boolean型为false，引用型为null。这是因为数组实际是一种引用型的变量，而其每个元素是引用型变量的成员变量。

Java语言提供的java.util.Arrays类用于支持对数组的操作，如表5.1所示。

5.2.2 一维数组元素的访问

当定义了一个数组，并用运算符new为它分配了内存空间以后，就可以引用数组中的每个元素了。要想使用数组里的元素，可以利用数组名和下标来实现。数组元素的引用方式为：

     数组名[下标]

其中，“下标”可以是整型数或整型表达式，如a[3+i]（i为整数）。Java语言数组的下标是从0开始的。例如：

     int[]x=new int[10];

其中，x[0]代表数组中第1个元素，x[1]代表第2个元素，x[9]为第10个元素，也就是最后一个元素。另外，与C/C++不同，Java语言对数组元素要进行越界检查以保证安全性。同时，对于每个数组都有一个属性length指明它的长度，如x.length指出数组x所包含的元素个数。

【例5.1】 声明一个一维数组，其长度为5，利用循环对数组元素进行赋值，然后再利用另一个循环逆序输出数组元素的内容。程序代码如下：

该程序的运行结果如下：

     a[4]=4, a[3]=3, a[2]=2, a[1]=1, a[0]=0
     数组a的长度是:5

该程序的第7行声明了一个整型数组a，第8行为其分配包含5个元素的空间；第9、10行是利用for循环为数组元素赋值；第11、12行是利用for循环将数组a的各元素反序输出；第13行是利用数组的长度属性length输出元素个数。

5.2.3 一维数组的初始化及应用

对数组元素的赋值，既可以使用单独方式进行（如例5.1），也可以在定义数组的同时就为数组元素分配空间并赋值，这种赋值方法称为数组的初始化。其格式如下：

     数据类型[]数组名={初值0,初值1,…,初值n};

在花括号内的初值会依次赋值给数组的第1，2，…，n+1个元素。此外，在声明数组的时候，并不需要将数组元素的个数给出，编译器会根据所给的初值个数来设置数组的长度。如：

     int[]a={1,2,3,4,5};

在上面的语句中，声明了一个整型数组a，虽然没有特别指明数组的长度，但是由于花括号里的初值有5个，编译器会分别依次指定各元素存放，a[0]为1，a[1]为2，…，a[4]为5。

注意：在Java程序中声明数组时，无论用何种方式定义数组，都不能指定其长度。如以“int[5]a；”方式定义数组将是非法的，该语句在编译时将出错。

【例5.2】 设数组中有n个互不相同的数，不用排序求出其中的最大值和次最大值。

该程序运行结果为：

     数组的各元素为：8　50　20　7　81　55　76　93
     其中的最大值是：93　次最大值是:81

该程序的第7行定义并初始化了数组a，第8～17行利用if-else语句将数组前两个元素中大的数保存在变量max中，将小的数存放在变量sec中；第19～29行利用for循环与if语句的结合，从数组的第三个元素开始到最后，对数组中的元素进行输出并检测，若检测到新的最大数，则将其保存到变量max中，次最大数保存到变量sec中；第30、31行将数组中的最大数和次最大数输出。

【例5.3】 设有N个人围坐一圈并按顺时针方向从1到N编号，从第S个人开始进行1到M报数，报数到第M的人，此人出圈，再从他的下一个人重新开始从1到M报数，如此进行下去，每次报数到M的人就出圈，直到所有人都出圈为止。给出这N个人的出圈顺序。

程序运行后的输出结果如下：

     出圈顺序为:
     7 12 4 10 3 11 6 2 1 5 9 13 8

此题是著名的“约瑟夫环”问题。在第9、10行将每个人的编号h存入数组元素a[h—1]中。因为要求从第3个人开始进行1到5报数，而代表第3个人的是a[2]，所以在第7行将控制数组下标的变量i赋值为S—1即i=2，表示从i=2的下标开始报数。第12～22行的do循环共执行N次，其中的第14行用于计算出圈人的下标，因为i=i+（M—1）就是下一个要出圈人的下标。由于变量k表示此时圈中剩余的人数，所当i＞=k时，即是i已经超出剩下的人数，所以第16行是要重新计算数组的下标。第17行是输出出圈人的编号。第18、19行的循环是当下标为i的人出圈后，把后续人的编号前移。由于有一个人出圈，圈中的人数少1，所以第20行将用于表示圈中剩余人数的变量k减1。第21行的变量g是用于控制do循环次数的变量，所以每次加1，每次循环找出一个出圈的人，所以循环共执行N次。

下面再给出该题的另一种算法。

该种解法的输出结果与前一解法的输出结果完全相同。各行代码的功能请读者自行分析解释。