数据结构一--数组

发表于 | 分类于 | 阅读次数: ℃
字数统计: 3.5k | 阅读时长 ≈ 15

所谓数组，就是相同类型的数据按照顺序组成的一种引用数据类型。

数组

数组对于每一门编程语言来说都是重要的数据结构之一，当然不同语言对数组的实现及处理也不尽相同。

Java 语言中提供的数组是用来存储固定大小的同类型元素。

声明数组

在 Java 中有两种声明数组的方式

  • type[] 变量名

    int[] myIntArray; //首选的方法

  • type 变量名[]

    int myIntArray[]; //效果相同，但不是首选的方法

创建数组

Java 中使用 new 操作符来创建数组

  • 语法格式一：先声明后创建

    type[] 变量名;

    变量名 = new type[数组中元素的个数];

    int[] arr;

    arr = new int[10];

    创建一个长度为10的数组

  • 语法格式二：声明的同时创建数组

    type 变量名[] = new type[数组中元素的个数];

    int[] arr = new int[10]；

    创建一个长度为10的数组

注意：数组长度必须指定

以上两种方式都叫做动态初始化，也就是说，只有在程序运行之后，你才能知道数组里到底存了那些数据。

语法格式二的命名方式 C 和 C++ 程序员比较熟悉，但是 Java 官方推荐使用第一种，一看知道是 int 型数组，叫 arr。

  • 静态初始化：int[] arr = new int[]{1,2,3};

    在定义的时候直接初始化，大括号里就是数组的值

  • 隐式初始化：数据类型[] 数组名 = {value0，value1…valuek};

    可以不写 new ,直接使用大括号，其实本质上还是调用了 new 的，只是可以不写出来而已，所以叫隐式初始化。

我们回过头来看看下面这句代码

1
2
> int[] arr = new int[10]；
>

这句代码都做了什么？

1.int[] arr：定义了一个 int 型数组的引用，名字叫做 arr，存放在栈中

2.new int[10]：初始化了一个长度为10的 int 型数组，在堆中开辟相应大小的内存

3.int[] arr = new int[10]：将堆中开辟的数组内存地址赋值给数组引用 arr

这样，就可以通过 arr 这个变量，来操作这个数组了

是不是觉得这个过程很熟悉？没错！我们创建对象的过程也是这样的！那是不是证明，数组其实是一个对象呢？

也没错！ Java 中的数组的确是一个对象，但是是一个特殊的对象，实在是太特殊了，以致我们都不好把它多做对象处理。

这个数组对象并不是从某个类实例化来的，而是由JVM直接创建的，因此查看类名的时候会发现是很奇怪的样子，这个直接创建的对象的父类就是Object，所以可以调用Object中的所有方法，包括你用到的toString()。

数组在内存中的存储

数组会被分配连续的内存空间

比如，我们定义一个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Main{
    public static void main(String[] args) {
        // 数组大小
        int size = 10;
        // 定义数组
        double[] myList = new double[size];
        myList[0] = 5.6;
        myList[1] = 4.5;
        myList[2] = 3.3;
        myList[3] = 13.2;
        myList[4] = 4.0;
        myList[5] = 34.33;
        myList[6] = 34.0;
        myList[7] = 45.45;
        myList[8] = 99.993;
        myList[9] = 11123;
        // 计算所有元素的总和
        double total = 0;
        for (int i = 0; i < size; i++) {
            total += myList[i];
        }
        System.out.println("总和为： " + total);
    }
}

它在内存空间中的存储如下图所示：

数组在内存中的存储

若数组没有赋值，则整型数组的默认值为0，其他类型的数组按照数据类型确定数组的默认值。

处理数组

数组的元素类型和数组的大小都是确定的，所以当处理数组元素的时候，我们通常用基本循环或者 foreach 循环

下面的例子就展示了数组的创建、初始化和操纵数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main{
    public static void main(String[] args) {
        double[] myList = {1.9, 2.9, 3.5, 3.4};
        System.out.println("打印数组：");
        for (int i = 0; i < myList.length; i++) {
            System.out.print(myList[i] + "  ");
        }
        System.out.println();
        System.out.println("计算所有元素的和");
        double sum = 0;
        for (int i = 0; i < myList.length; i++) {
            sum += myList[i];
        }
        System.out.println("数组myList元素的和为：" + sum);
        double max = myList[0];
        for (int i = 0; i < myList.length; i++) {
            if (max<myList[i]){
                max = myList[i];
            }
        }
        System.out.println("数组myList中的最大值为：" + max);
    }
}

运行结果

打印数组：
1.9 2.9 3.5 3.4
计算所有元素的和
数组myList元素的和为：11.700000000000001
数组myList中的最大值为：3.5

foreach循环

foreach 循环可以在不适用下标的情况下遍历数组

1
2
3
4
5
6
7
8
9
10
public class Main{
    public static void main(String[] args) {
        double[] myList = {1.9, 2.9, 3.5, 3.4};
        System.out.println("打印数组：");
        for (double i :
                myList) {
            System.out.print(i + "  ");
        }
    }
}

运行结果

打印数组：
1.9 2.9 3.5 3.4

数组作为函数的参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main{
    public static void main(String[] args) {
        double[] myList = {1.9, 2.9, 3.5, 3.4};
        System.out.println("打印数组:");
        printArray(myList);
    }

    public static void printArray(double[] arr){
        for (double i :
                arr) {
            System.out.print(i + "  ");
        }
    }
}

运行结果

打印数组:
1.9 2.9 3.5 3.4

数组作为函数的返回值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main{
    public static void main(String[] args) {
        double[] myList = {1.9, 2.9, 3.5, 3.4};
        System.out.println("打印数组:");
        double[] result = reverse(myList);
        for (double i :
                result) {
            System.out.print(i + "  ");
        }
    }

    public static double[] reverse(double[] list) {
        double[] result = new double[list.length];

        for (int i = 0, j = result.length - 1; i < list.length; i++, j--) {
            result[j] = list[i];
        }
        return result;
    }
}

运行结果

打印数组:
3.4 3.5 2.9 1.9

数组内容的比较

数组内容的比较可以通过 equals() 吗？我们先来看个例子

1
2
3
4
5
6
7
public class Main{
    public static void main(String[] args) {
        int[] a = {1,2,3};
        int[] b = {1,2,3};
        System.out.println(a.equals(b));
    }
}

运行结果

false

所以，不能直接用 equals() 比较数组内容。那么该怎么比较呢？

有两种方法：一种是自己实现，另一种是利用 Arrays。

Arrays 中的方法全是static的。其中包括了 equals() 方法的各种重载版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Arrays;

public class Main{
    public static boolean isEquals(int[] a, int[] b){
        if (a==null || b==null){
            return false;
        }
        if (a.length!=b.length){
            return false;
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i]!=b[i]){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {

        int[] a = {1,2,3};
        int[] b = {1,2,3};
        System.out.println(isEquals(a,b));
        System.out.println(Arrays.equals(a,b));
    }
}

运行结果

true
true

Arrays类的使用

Arrays 能方便的操作数组，他提供的方法都是静态的。

具有以下功能

  • 对数组赋值：通过 fill 方法
  • 对数组排序：用过 sort 方法，按升序。
  • 比较数组：通过 equals 方法，比较数组中的元素是否相等
  • 查找数组元素：通过 binarySearch 方法能对排序好的数组进行二分查找。
  • …….

多维数组

多维数组可以看成是数组的数组，比如二维数组就是一个特殊的一维数组，其每一个元素都是一个一维数组。

其实 Java 只有一维数组，但是由于数组可以存放任意类型的数据，当然也就可以存放数组了，这个时候，就可以模拟多维数组了。

基本的定义方法同样有两种

type[][] i = new type[2][3];//（推荐）

type i[][] = new type[2][3];//（推荐）

变长的二维数组

二维数组的每个元素是一个一维数组，这些数组不一定都是等长的。

声明二维数组的时候可以只指定第一维的大小，空缺处第二维的大小，之后在指定不同长度的数组。但是注意，第一维大小不能空缺（可以指定行数不指定列数，不能只指定列数不指定行数）。

1
2
3
4
5
6
7
8
public class Main{
    public static void main(String[] args) {
        int[][] arr = new int[3][];
        arr[0] = new int[3];
        arr[1] = new int[1];
        arr[2] = new int[4];
    }
}

二维数组也可以在定义的时候初始化，使用花括号的嵌套完成，这时候不指定两个维数的大小，并且根据初始化值的个数不同，可以生成不同长度的数组元素。

1
int[][] arr = {{1,3,9},{7,},{4,6,8,2}};

可变参数

有时候，你需要一个方法，但是你调用它之前不知道要传递几个参数给它，这个时候你就需要可变参数了

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Main{
    public static void main(String[] args) {
        System.out.println(add(2,3));
        System.out.println(add(3,4,5));
    }
    public static int add(int ...args){
        int sum = 0;
        for (int i = 0; i < args.length; i++) {
            sum = sum + args[i];
        }
        return sum;
    }
}

那个奇怪的int ...args就是可变参数，这样你就可以传递任意个你想传递的数据了。

java把可变参数当做数组处理。

注意：可变参数必须位于最后一项。当可变参数个数多余一个时，必将有一个不是最后一项，所以只支持有一个可变参数。因为参数个数不定，所以当其后边还有相同类型参数时，java无法区分传入的参数属于前一个可变参数还是后边的参数，所以只能让可变参数位于最后一项。

面试中关于数组的常见问题

寻找数组中第二小的元素

1.做容易想到的方法，先排序，然后找到第二个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
import java.util.Arrays;

public class Main{
    public static void main(String[] args) {
        int [] array={1,8,3,6,9,3,5,7,2,6,18,19,20,20,31,27,27};
        System.out.println("第二大的是:" + FindSecMax(array));
    }
    public static int FindSecMax(int[] arr){
        Arrays.sort(arr);
        int sec_max = arr[arr.length-2];
        return sec_max;
    }
}

运行结果

第二大的是:27

不过这个方法的时间复杂度和空间复杂度都比较大。

2.先定义两个变量：一个变量用来存储数组的最大数，初始值为数组首元素，另一个变量用来存储第二大的数，初始值为最小负整数，然后遍历数组元素，如果数组元素的值比最大数变量还大，更新最大数；若数组元素的值比最大值还小，则与第二大的数比较，若该数比第二大数大，则更新第二大的数；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Main{
    public static void main(String[] args) {
        int [] array={1,8,3,6,9,3,5,7,2,6,18,19,20,20,31,27,27};
        System.out.println("第二大的是:" + FindSecMax(array));
    }
    public static int FindSecMax(int[] arr){
        int max=arr[0];
        int sec_max=Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>max){
                sec_max = max;
                max = arr[i];
            }else {
                if (arr[i]>sec_max){
                    sec_max = arr[i];
                }
            }
        }
        return sec_max;
    }
}

运行结果

第二大的是:27

合并两个数组

不管数组有没有顺序，都有一个统一的思路：定义一个新数组，长度为两个数组长度之和，然后对新数组排序

  • 如果数组是有序的
    • 定义一个新数组，长度为两个数组长度之和
    • 分别定义 i：a数组下标, j：b数组下标, k：新数组下标
    • 按位循环比较两个数组，较小元素的放入新数组，下标加一（较大元素对应的下标不加一），直到某个小标等于数组长度时退出循环
    • 再写两个 while 循环来保证两个数组作比较完后剩下的数组还能顺利传入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main{
    public static void main(String[] args) {
//        int[] arrayA={1,8,3,6,9,3,5,7,2,6,18,19,20,20,31,27,27};
//        int[] arrayB = {37,3,8,85,87,44,22,39,40,80,58,10,69,75,90};
        int[] arrayA = {1,8,3,6,9,3};
        int[] arrayB = {37,3,8,85,87};
        Arrays.sort(arrayA);
        Arrays.sort(arrayB);
        System.out.print("arrayA：");
        for (int i :
                arrayA) {
            System.out.print(i+" ");
        }
        System.out.println();
        System.out.print("arrayB：");
        for (int i :
                arrayB) {
            System.out.print(i+" ");
        }
        //合并两个有序数组
        int[] arrayC = combineSortedArray(arrayA,arrayB);
        System.out.println();
        System.out.print("arrayC：");
        for (int i :
                arrayC) {
            System.out.print(i+" ");
        }
    }
    public static int[] combineSortedArray(int[] arrA, int[] arrB){
        if (arrA == null){
            return arrB;
        }
        if (arrB == null){
            return arrA;
        }
        int[] arrayC = new int[arrA.length+arrB.length];
        System.out.println(arrayC.length);
        int i=0,j=0,k=0;
        while (i < arrA.length && j < arrB.length){
            if (arrA[i] <= arrB[j]){
                arrayC[k++] = arrA[i++];
            }else {
                arrayC[k++] = arrB[j++];
            }
        }
        while (i< arrA.length){
            arrayC[k++] = arrA[i++];
        }
        while (j< arrB.length){
            arrayC[k++] = arrB[j++];
        }
        return arrayC;
    }
}
  • 如果数组是无序的
    • 将两个数组分别排序，然后按照上面的思路

重新排列数组中的正值和负值

给定一个包含正数和负数的整数数组，重新排列它，使得所有的负数排在前面，所有的正数排在后面。正数间和负数间的相对顺序保持不变。

eg： 给定 [-1,2,-2,3,5,-4], 重新排列后变成 [-1,-2,-4,2,3,5]

  • 思路一：先遍历第一遍，将负数挑出来放在一个新的数组中，再遍历一遍，将正数放进去
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.Arrays;

public class Main{
    public static void main(String[] args) {
        int[] arrayA = {1,7,-5,-12,-13,99,-6,31,15};
        int[] arrayB = positiveAndMinus(arrayA);
        System.out.println(Arrays.toString(arrayB));
    }

    public static int[] positiveAndMinus(int[] arr){
        int[] result = new int[arr.length];
        int j = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0){
                result[j] = arr[i];
                j++;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i]>=0){
                result[j] = arr[i];
                j++;
            }
        }
        return result;
    }
}
  • 思路二：冒泡排序的一种改进，将负数逐个“冒”出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Arrays;

public class Main{
    public static void main(String args[])
    {
        int[]x={1,7,-5,-12,-13,99,-6,31,15};
        int p=0;
        for(int i=x.length-1;i>p;)
        {
            if(x[i]<0)
            {
                int j=i;
                while(j!=0)
                {
                    int t=x[j];
                    x[j]=x[j-1];
                    x[j-1]=t;//交换
                    j--;
                }
                p++;
            }
            else i--;
        }
        System.out.println(Arrays.toString(x));
    }
}
-------------本文结束感谢您的阅读-------------

本文标题:数据结构一--数组

文章作者:Cui Zhe

发布时间:2018年10月23日 - 21:10

最后更新:2018年10月25日 - 11:10

原始链接:https://cuizhe1023.github.io/2018/10/23/数据结构一/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。