第08章 多维数组

8.1 引言

• 表或矩阵中的数据可以表示为二维数组

8.2 二维数组基础

• 二维数组中的元素通过行和列的下标来访问

8.2.1 声明二维数组变量并创建二维数组

• 下面是声明二维数组的语法：

  数据类型 [][] 数组名;

• 或者

  数据类型  数组名 [][];允许这种方式，但不推荐使用它

• 可以使用这个语法创建5 × 5 的 int 型二维数组，并将它赋给matrix;

  matrix = new int[5][5];

• 二维数组中使用两个下标，一个表示行，另一个表示列。同一维数组一样，每个下标索引值都是int型的，从0开始，如图8-1a所示。
• 使用matrix[2,1]访问行下标为2、列下标为1的元素是一种常见的错误。在Java中，每个下标必须放在一对方括号中。
• 也可以使用数组初始化简写方式来声明、创建和初始化一个二维数组。

8.2.2 获取二维数组的长度

• 二维数组实际上是一个其中每个元素都是一个一维数组的数组。数组x的长度是数组中元素的个数，可以用x.length获取该值。元素x[0],x[1], … ,x[x.length - 1]也是数组。可以使用x[0].length,x[1].length, … , x[x.length -1 ].length获取它们的长度

8.2.3 不规则数组

• 二维数组中的每一行本身就是一个数组，因此，各行的长度就可以不同。这样的数组称为不规则数组（ragged array）。下面就是一个创建不规则数组的例子
• 如果事先不知道不规则数组的值，但知道它的长度，如前面讲到的，可以使用如下所示的语法创建不规则数组

  int[][] triangleArray = new int[5][];
  triangleArray[0] = new int[5];
  triangleArray[1] = new int[4];
  triangleArray[2] = new int[3];
  triangleArray[3] = new int[2];
  triangleArray[4] = new int[1];

• 现在可以给数组赋值，例如：

  triangleArray[0][3] = 4;
  triangleArray[4][0] = 5;

• 使用语法 new int[5] [] 创建数组时，必须指定第一个下标。语法 new int[] []是错误的。

8.3 处理二维数组

• 嵌套的for循环常用于处理二维数组
• 假设如下创建数组matrix：

  int[][] matrix = new int[10][10];

• 下面是一些处理二维数组的例子：
  • （使用输入值初始化数组）下面的循环使用用户输入值初始化数组：

    java.util.Scanner input = new java.util.Scanner(System.in);
    System.out.println("Enter " + matrix.length + " rows and " + 
                matrix[0].length + " columns: ");
    for(int row = 0; row < matrix.length; row++){
    for(int column = 0; column < matrix[row].length;column++){
      matrix[row][column] = input.nextInt();
    }
    }

• （使用随机值初始化数组）下面的循环使用0到99之间的随机值初始化数组：

  for(int row = 0; row < matrix.length; row++){
  for(int column = 0; column < matrix[row].length;column++){
    matrix[row][column] = (int)(Math.random() * 100);
  }
  }

• （打印数组）为打印一个二维数组，必须使用如下所示的循环打印数组中的每个元素

  for(int row = 0; row < matrix.length; row++){
  for(int column = 0; column < matrix[row].length;column++){
    System.out.print(matrix[row][colume] + " ");
  }
  System.out.println();
  }

• （对所有元素求和）使用名为total的变量存储和。将total初始化为0。利用类似下面的循环，把数组中的每一个元素都加到total上：

  int total = 0;
  for(int row = 0; row < matrix.length; row++){
  for(int column = 0; column < matrix[row].length;column++){
    total += matrix[row][column];
  }
  }

• （按列求和）对于每一列，使用名为total的变量存储它的和。利用类型下面的循环，将该列中的每个元素加到total上：

  for(int column = 0; column < matrix[0].length;column++){
  int total = 0;
  for(int row = 0; row < matrix.length; row++){
    total += matrix[row][column];
  }
  System.out.println("Sum for column " + column + " is " + total);
  }

• （哪一行的和最大）使用变量maxRow和indexOfMaxRow分别跟踪和的最大值以及该行的下标值。计算每一行的和，如果计算出的新行的和更大，就更新maxRow和indexOfMaxRow。 ```java int maxRow = 0; int indexOfMaxRow = 0;

//Get sum of the first row in maxRow for(int column = 0; column < matrix[0].length; column++){ maxRow += matrix[0][column]; }

for(int row = 1; row < matrix.length; row++){ int totalOfThisRow = 0; for(int column = 0; column < matrix[row].length;column++){ totalOfThiRow += matrix[row][column]; } if(totalOfThisRow > maxRow){ maxRow = totalOfThisRow; indexOfMaxRow = row; } } System.out.println(“Row “ + indexOfMaxRow

• “ has the maximum sum of “ + maxRow); ```

• （随机打乱）在7.2.6节中已经介绍了如何打乱一维数组的元素，那么如何打乱二维数组中的所有元素呢？为了实现这个功能，对每个元素matrix[i] [j] ，随机产生下标 i1 和 j1，然后互换matrix[i] [j] 和matrix[i1] [j1]，如下所示：

  for(int i = 0; i < matrix.length; i++){
  for(int j = 0; j < matrix[i].length ; j++){
    int i1 = (int)(Math.random * matrix.length);
    int j1 = (int)(Math.random * matrix[i].length);
    //Swap matrix[i][j] with matrix[i1][j1]
    int temp = matrix[i][j];
    matrix[i][j] = matrix[i1][j1];
    matrix[i1][j1] = temp;
  }
  }

8.4 将二维数组传递给方法

• 将一个二维数组传递给方法时，数组的引用传递给了方法

程序清单 8-1 PassTwoDimensionalArray.java

import java.util.Scanner;
public class PassTwoDimensionalArray {
    public static void main(String[] args) {
        //Get an array
        int[][] m = getArray();
        //Display sum of elements
        System.out.println("\nSum of all elements is " + sum(m));
    }
    public static int[][] getArray() {
        //Create a Scanner
        Scanner input = new Scanner(System.in);
        //Enter array values
        int[][] m = new int[3][4];
        System.out.println("Enter " + m.length + " rows and "
                + m[0].length + " columns: ");
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[i].length; j++) {
                m[i][j] = input.nextInt();
            }
        }
        return m;
    }
    public static int sum(int[][] m) {
        int total = 0;
        for (int row = 0; row < m.length; row++) {
            for (int column = 0; column < m[row].length; column++) {
                total += m[row][column];
            }
        }
        return total;
    }
}

8.5 示例学习：多选题

• 编写一个可以进行多选题测验评分的程序

程序清单 8-2 GradeExam.java

public class GradeExam {
    /**
     * Main method
     */
    public static void main(String[] args) {
        //Students' answers to the questions
        char[][] answers = {
                {'A', 'B', 'A', 'C', 'C', 'D', 'E', 'E', 'A', 'D'},
                {'D', 'B', 'A', 'B', 'C', 'A', 'E', 'E', 'A', 'D'},
                {'E', 'D', 'D', 'A', 'C', 'B', 'E', 'E', 'A', 'D'},
                {'C', 'B', 'A', 'E', 'D', 'C', 'E', 'E', 'A', 'D'},
                {'A', 'B', 'D', 'C', 'C', 'D', 'E', 'E', 'A', 'D'},
                {'B', 'B', 'E', 'C', 'C', 'D', 'E', 'E', 'A', 'D'},
                {'B', 'B', 'A', 'C', 'C', 'D', 'E', 'E', 'A', 'D'},
                {'E', 'B', 'E', 'C', 'C', 'D', 'E', 'E', 'A', 'D'}};
        //Key yo the questions
        char[] keys = {'D', 'B', 'D', 'C', 'C', 'D', 'A', 'E', 'A', 'D'};
        //Grade all answers
        for (int i = 0; i < answers.length; i++) {
            //Grade one student
            int correctCount = 0;
            for (int j = 0; j < answers[i].length; j++) {
                if (answers[i][j] == keys[j]) {
                    correctCount++;
                }
            }
            System.out.println("Student " + i + " 's correct count is " + correctCount);
        }
    }
}

8.6 示例学习：找出距离最近的点对

• 本节提供一个几何问题的解决 —- 找到距离最近的点对
• 一种直观的方法就是计算所有点对之间的距离，并且找出最短的距离，它的实现如程序清单8-3所示

程序清单 8-3 FindNearestPoints.java

import java.util.Scanner;
public class FindNearestPoints {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("Enter the number of points: ");
        int numberOfPoints = input.nextInt();
        //Create an array to store points
        double[][] points = new double[numberOfPoints][2];
        System.out.print("Enter " + numberOfPoints + " point: ");
        for (int i = 0; i < points.length; i++) {
            points[i][0] = input.nextDouble();
            points[i][1] = input.nextDouble();
        }
        //p1 and p2 are the indices in the points' array
        //Initial two points
        int p1 = 0, p2 = 1;
        double shortestDistance = distance(points[p1][0], points[p1][1],
                points[p2][0], points[p2][1]);
        //Compute distance for every two points
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                //Find distance
                double distance = distance(points[i][0], points[i][1],
                        points[j][0], points[j][1]);
                if (shortestDistance > distance) {
                    //Update p1 and p2
                    p1 = i;
                    p2 = j;
                    //Update shortestDistance
                    shortestDistance = distance;
                }
            }
        }
        //Display result
        System.out.println("The closest two points are " + "(" + points[p1][0]
                + ", " + points[p1][1] + ") and (" + points[p2][0] + ", " + points[p2][1] + ")");
    }
    public static double distance(double x1, double y1, double x2, double y2) {
        return Math.sqrt(Math.pow((x2 - x1), 2) + Math.pow((y2 - y1), 2));
    }
}

• 也可能会有不止一对具有相同最小距离的点对。本程序只需找到这样的一对点。可以在编程练习题8.8中修改这个程序，找出所有距离最短的点对。
• 从键盘输入所有的点是很烦琐的。可以将输入存储在一个名为FindeNearestPoints.txt的文件中，并使用下面的命令编译和运行这个程序：

  java FindNearestPoints < FindNearestPoints.txt

8.7 示例学习：数独

• 要解决的问题是检验一个给定的数独解决方案是否正确。
• 本节介绍一个每天都会出现在报纸上的有趣问题。这是一个关于数字放置的问题，通常称为数独（Sudoku）。它是一个非常有挑战性的问题。为了使之能被编程新手接受，本节给出数独问题的简化版本，即检验某个解决方案是否正确。数独问题的完整解决方案放在补充材料VI.C中
• 数独是一个9×9的网格，它被分为更小的3×3的盒子（也称为区域或者块），如图8-4所示。一些称为固定方格（fixed cell）的格子里放置了从1到9的数字。该程序的目标是将从1到9的数字放入那些称为自由方格（free cell）的格子，以使得每行每列以及每个3×3的盒子都包含从1到9的数字，如图8-4b所示。

程序清单 8-4 FindNearestPoints.java

import java.util.Scanner;
public class CheckSudokuSolution {
    public static void main(String[] args) {
        //Read a Sudoku solution
        int[][] grid = readASolution();
        System.out.println(isValid(grid) ? "Valid solution" : "Invalid solution");
    }
    /**
     * Read a Sudoku solution from the console
     */
    public static int[][] readASolution() {
        //Create a Scanner
        Scanner input = new Scanner(System.in);
        System.out.println("Enter a Sudoku puzzle solution: ");
        int[][] grid = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                grid[i][j] = input.nextInt();
            }
        }
        return grid;
    }
    /**
     * Check whether a solution is valid
     */
    public static boolean isValid(int[][] grid) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (grid[i][j] < 1 || grid[i][j] > 9 || !isValid(i, j, grid)) {
                    return false;
                }
            }
        }
        //The solution is valid
        return true;
    }
    /**
     * Check whether grid[i][j] is valid in the grid
     */
    public static boolean isValid(int i, int j, int[][] grid) {
        //Check whether grid[i][j] is unique in j's column
        for (int column = 0; column < 9; column++) {
            if (column != j && grid[i][column] == grid[i][j]) {
                return false;
            }
        }
        //Check whether grid[i][j] is unique in j's column
        for (int row = 0; row < 9; row++) {
            if (row != i && grid[row][j] == grid[i][j]) {
                return false;
            }
        }
        //Check whether grid[i][j] is unique in the 3-by-3 box
        for (int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++) {
            for (int col = (j / 3) * 4; col < (j / 3) * 3 + 3; col++) {
                if (!(row == i && col == j) && grid[row][col] == grid[i][j]) {
                    return false;
                }
            }
        }
        //The current value at grid[i][j] is valid
        return true;
    }
    /* 输入的数据
    9 6 3 1 7 4 2 5 8
    1 7 8 3 2 5 6 4 9
    2 5 4 6 8 9 7 3 1
    8 2 1 4 3 7 5 9 6
    4 9 6 8 5 2 3 1 7
    7 3 5 9 6 1 8 2 4
    5 8 9 7 1 3 4 6 2
    3 1 7 2 4 6 9 8 5
    6 4 2 5 9 8 1 7 3
     */
}

8.8 多维数组

• 二维数组由一个一维数组的数组组成，而一个三维数组可以认为是由一个二维数组的数组所组成的
• 可以对二维数组变量的声明以及二维数组的创建方法进行推广，用于声明n ≥ 3的 n维数组变量和创建n维数组

8.8.1 示例学习：每日温度和湿度

• 在文件中，天是从1到10编号的，而小时是从1到24编号的。因为数组下标是从0开始的，所以，data[][][0] [0] [0] 存储的是第1天第1小时的温度，而data[9] [23] [1]存储的是第10天第24小时的湿度。
• 该程序在程序清单8 - 5 中给出

程序清单 8-5 Weather.java

import java.util.Scanner;
public class Weather {
    public static void main(String[] args) {
        final int NUMBER_OF_DAYS = 10;
        final int NUMBER_OF_HOURS = 24;
        double[][][] data = new double[NUMBER_OF_DAYS][NUMBER_OF_HOURS][2];
        Scanner input = new Scanner(System.in);
        //Read input using input redirection from a file
        for (int k = 0; k < NUMBER_OF_DAYS * NUMBER_OF_HOURS; k++) {
            int day = input.nextInt();
            int hour = input.nextInt();
            double temperature = input.nextDouble();
            double humidity = input.nextDouble();
            data[day - 1][hour - 1][0] = temperature;
            data[day - 1][hour - 1][1] = humidity;
        }
        //Find the average daily temperature and humidity
        for (int i = 0; i < NUMBER_OF_DAYS; i++) {
            double dailyTemperatureTotal = 0, dailyHumidityTotal = 0;
            for (int j = 0; j < NUMBER_OF_HOURS; j++) {
                dailyTemperatureTotal += data[i][j][0];
                dailyHumidityTotal += data[i][j][1];
            }
            //Display result
            System.out.println("Day " + i + " 's average temperature is " +
                    dailyTemperatureTotal / NUMBER_OF_HOURS);
            System.out.println("Day " + i + " 's average humidity is "
                    + dailyHumidityTotal / NUMBER_OF_HOURS);
        }
    }
}

数据文件： 链接：https://pan.baidu.com/s/1ALH2WrGT6owqJDhcnWyaIQ
提取码：1024 网址：https://liveexample.pearsoncmg.com/data/Weather.txt

8.8.2 示例学习：猜生日

程序清单 8-6 GuessBirthdayUsingArray.java

import java.util.Scanner;
public class GuessBirthdayUsingArray {
    public static void main(String[] args) {
        //Day to be determined
        int day = 0;
        int answer;
        int[][][] dates = {
                {{1, 3, 5, 7},
                        {9, 11, 13, 15},
                        {17, 19, 21, 23},
                        {25, 27, 29, 31}},
                {{2, 3, 6, 7},
                        {10, 11, 14, 15},
                        {18, 19, 22, 23},
                        {26, 27, 30, 31}},
                {{4, 5, 6, 7},
                        {12, 13, 14, 15},
                        {20, 21, 22, 23},
                        {28, 29, 30, 31}},
                {{8, 9, 10, 11},
                        {12, 13, 14, 15},
                        {24, 25, 26, 27},
                        {28, 29, 30, 31}},
                {{16, 17, 18, 19},
                        {20, 21, 22, 23},
                        {24, 25, 26, 27},
                        {28, 29, 30, 31}}};
        //Create a Scanner
        Scanner input = new Scanner(System.in);
        for (int i = 0; i < 5; i++) {
            System.out.println("Is your birthday in Set" + (i + 1) + " ? ");
            for (int j = 0; j < 4; j++) {
                for (int k = 0; k < 4; k++) {
                    System.out.printf("%4d", dates[i][j][k]);
                }
                System.out.println();
            }
            System.out.print("\nEnter 0 for No and 1 for Yes: ");
            answer = input.nextInt();
            if (answer == 1) {
                day += dates[i][0][0];
            }
        }
        System.out.println("Your birthday is " + day);
    }
}