数组的使用

数组概述

• 定义：多个相同类型的的数据按照一定顺序排列的集合，使用一个名字命名并通过编号的方式对这些数据进行统一管理。
• 概念：数组名、索引（下标）、元素、长度
• 特点：有序排列；数组属于引用数据类型，数组的元素可以是基本数据类型或者引用数据类型；创建数组对象会在内存中开辟一整块连续的空间；长度固定，不能修改；
• 分类：一维数组和多维数组；基本数据类型元素数组和引用数据类型元素数组；

一维数组

• 概念
• 声明和初始化：静态数组、动态数组
• 默认值
• 数组元素的调用
• 数组的长度
• 数组遍历

数组的内存

• 栈stack
• 堆heap：new出来的结构：对象、数组
• 方法区：常量池（String）、静态域（static）
• 自动垃圾回收机制

package www.wangwei.com;

public class array1 {
    public static void main(String[] args) {
        System.out.println("数组的使用");
        //静态数组声明和初始化
        int[] arr1 = new int[]{1,2,3,4,5};
        //动态数组声明和初始化
        String[] arr2 = new String[5];
        //调用指定位置的元素
        arr2[0] = "元素";
        arr2[1] = "元素";
        arr2[2] = "元素";
        arr2[3] = "元素";
        arr2[4] = "元素";

        //数组的长度
        System.out.println(arr1.length);
        System.out.println(arr2.length);
        //数组遍历
        for(int i = 0;i<  arr1.length;i++){
            System.out.print(arr1[i]+" ");
        }
        System.out.println();
        for(int j = 0;j< arr2.length;j++){
            System.out.print(arr2[j]+" ");
        }
        
        //数组默认值
        int[] arr1 = new int[5];//默认0（byte、short、int、long类型的默认值都是0）
        double[] arr2 = new double[5];//默认0.0（float、double类型的默认值都是0）
        char[] arr3 = new char[5];//默认“空格”(0或'\u0000')
        boolean[] arr4 = new boolean[5];//默认false;
        String[] arr5 = new String[5];//默认null
        
        //练习一
        int[] arr1 = new int[]{8,2,1,0,3};
        int[] index = new int[]{2,0,3,2,4,0,1,3,2,3,3};
        String tel = "";
        for(int i = 0;i < index.length;i++){
            tel += arr1[index[i]];
        }
        System.out.println("联系方式："+tel);

        //学生成绩
        Scanner input = new Scanner(System.in);
        System.out.print("请输入学生人数:");
        int number = input.nextInt();
        System.out.print("请输入"+number+"个学生成绩:");
        int[] source = new int[number];
        int max1 = 0;
        for (int i = 0; i < number; i++) {
            source[i] = input.nextInt();
            if (source[i] >= max1)
                max1 = source[i];
        }
        System.out.println("最高分为：" + max1);

        for (int j = 0; j <= 4; j++) {
            char grade = ' ';
            if (source[j] >= max1 - 10)
                grade = 'A';
            else if (source[j] >= max1 - 20 && source[j] < max1 - 10)
                grade = 'B';
            else if (source[j] >= max1 - 30 && source[j] < max1 - 20)
                grade = 'C';
            else
                grade = 'D';
            System.out.println("student " + j + " source is " + source[j] + ",grade is " + grade);
        }
    }
}

多维数组

• 理解：数组构成的数组；数组的元素也是数组
• 从内存角度来看，都是一维数组

数据结构

• 数据与数据之间的逻辑关系：集合、一对一、一对多、多对多
• 数据的存储结构：
• 线性表（一对一：）顺序表（数组）、链表（非连续的）、栈（先进后出）、队列（先进先出）
• 树型结构（一对多）：二叉树
• 图形结构：

算法

• 排序算法
• 搜索算法

package www.wangwei.com;

public class ArrayTwo {
    public static void main(String[] args) {
        System.out.println("二维数组的使用");
        //静态数组声明和初始化
        int[][] arr1 = new int[][]{{1},{2,3},{4,5,6}};
        //动态数组声明和初始化
        String[][] arr2 = new String[3][];
        arr2[0] = new String[2];
        arr2[1] = new String[2];
        arr2[2] = new String[2];
        String[][] arr3 = new String[3][2];

        //调用二维数组指定位置的元素
        System.out.println(arr1[0][0]);//1
        System.out.println(arr2[2][1]);//null
        System.out.println(arr3[2][1]);//null

        //获取数组的长度
        System.out.println(arr1.length);//3
        System.out.println(arr1[0].length);//1
        System.out.println(arr2.length);//3

        //遍历数组的元素
        for(int i = 0;i < arr1.length;i++){
            for(int j = 0;j < arr1[i].length;j++){
                System.out.print(arr1[i][j]);
                System.out.print(" ");
            }
            System.out.println();
        }

        
        //默认初始化值
        nt[][] arr1 = new int[4][3];
        String[][] arr2 = new String[4][3];
        double[][] arr3 = new double[4][];


        System.out.println(arr1[0]);////输出地址值
        System.out.println(arr1[0][0]);////0
        System.out.println(arr3[0]);//null 内层y元素未赋值，不能指向地址
        System.out.println(arr3[0][]);//报错空指针，为赋值
        
        //数组遍历
        for (int i = 0; i < arr1.length; i++){
            for (int j = 0; j < arr1[i].length; j++) {
                System.out.print(arr1[i][j] + "\t");
            }
            System.out.println();
        }

        for (int i = 0; i < arr2.length; i++){
            for (int j = 0; j < arr2[i].length; j++) {
                System.out.print(arr2[i][j] + "\t");
            }
            System.out.println();
        }
        
        
        
        //练习1
        int[][] arr1 = {{3,5,8},{12,9},{7,0,6,4}};
        int sum = 0;
        for (int i = 0; i < arr1.length ; i++) {
            for (int j = 0; j < arr1[i].length; j++) {
                sum += arr1[i][j];
            }
        }
        System.out.println("总和为："+sum);
        

        //练习2 杨辉三角
        int[][] arry = new int[10][10];
        for (int i = 0; i <= 9; i++) {
            for (int j = 0; j <= i; j++) {
                if((i < 2) || (j == 0) || (j == i))
                    arry[i][j] = 1;
                else
                    arry[i][j] = arry[i-1][j-1]+arry[i-1][j];
                System.out.print(arry[i][j]);
                System.out.print(' ');
            }
            System.out.println();
        }
        
        //练习3 生产随机数，不能重复   
        int[] arr = new int[6];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random()*30+1);
            for (int j = 0; j < i; j++) {
                if(arr[i] == arr[j]) {
                    i--;
                    break;
                }
            }
            System.out.print(arr[i] + "\t");
        }
            
        //练习4 回形数  
        System.out.println("请输入一个整数（1-20）：");
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        System.out.println(num);
        int[][] array1 = new int[num][num];
        int minx = 0;
        int miny = 0;
        int maxx = num - 1;
        int maxy = num - 1;
        int count = 0;
        while(minx <= maxx) {
            for (int i = minx; i <= maxx; i++) {
                ++count;
                array1[miny][i] = count;
            }
            miny++;

            for(int i = miny;i <= maxy; i ++){
                ++count;
                array1[i][maxx] = count;
            }
            maxx--;

            for (int i = maxx; i >= minx ; i--) {
                array1[maxy][i] = count++;
            }
            maxy--;

            for (int i = maxy; i >= miny ; i--) {
                array1[i][minx] = count++;

            }
            minx++;
        }

        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1.length; j++) {
                String space = (array1[i][j] + "").length() == 1 ? "0" : "";
                System.out.print(space + array1[i][j] + " ");
            }
            System.out.println();
        }

    }
}

Arrays工具类

• 是否相等：Arrays.equals(arr1,arr2);
• 输出数组：Arrays.toString(arr1)
• 填充数组：Arrays.fill(arr1,10);
• 排序数组：Arrays.sort(arr2);
• 二分查找：Arrays.binarySearch(arr2,6);

package www.wangwei.com;
import java.util.Arrays;
public class Arraystest {
    public static void main(String[] args){
        int[] arr1 = new int[]{1,2,3,4};
        int[] arr2 = new int[]{1,3,2,4};
        //判断两个数组是否相等
        boolean isEquals = Arrays.equals(arr1,arr2);
        System.out.println(isEquals);

        //输出数组信息
        System.out.println(Arrays.toString(arr1));

        //讲指定值填充到数组中
        Arrays.fill(arr1,10);
        System.out.println(Arrays.toString(arr1));

        //对数组进行排序
        Arrays.sort(arr2);
        System.out.println(Arrays.toString(arr2));

        //二分查找
        int index = Arrays.binarySearch(arr2,6);
        //如果值没在所查找的数组中，那么返回值是一个负数
        if(index > 0)
            System.out.println(index);
        else
            System.out.println("未找到");

    }
}

数组中常用算法

• 数组元素的赋值（杨辉三角、回形数）
• 求数值型数组中的值
• 数组的赋值、反转、查找
• 数组元素的排序算法

package www.wangwei.com;

public class ArrayAlgo1 {
    public static void main(String[] args) {
        //练习一 求一维数组的最大值、最小值、和、平均数
        //获取随机数的一维数组
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 90 + 10);
            System.out.print(arr[i] + "\t");
        }
        System.out.println();
        //求最大值、最小值、和、平均数
        int maxnum = arr[0];
        int minnum = arr[0];
        int sum = 0;
        int avg = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > maxnum)
                maxnum = arr[i];
            if(arr[i] < minnum)
                minnum = arr[i];
            sum+=arr[i];
        }
        System.out.println("最大值是："+maxnum);
        System.out.println("最小值是："+minnum);
        System.out.println("总和值是："+sum);
        System.out.println("平均值是："+(sum/arr.length));
        System.out.println();

        //练习一 复制数组与赋值数组
        int[] array1 = new int[]{2,3,5,7,11,13,17,19};
        int[] array2 = new int[8];
        System.out.print("数组array1原始值：");
        for (int i = 0; i < array1.length; i++) {
            System.out.print(array1[i]+"\t");
        }
        System.out.println();
        //数组复制 修改array2时 array1不会发生改变
        System.out.print("数组array2复制值：");
        for (int i = 0; i < array1.length; i++) {
            if(i % 2 == 0)
                array2[i] = i;
            else
                array2[i]= array1[i];
            System.out.print(array2[i]+"\t");
        }
        System.out.println();
        /*
        以下操作相当于把array赋值给了array3
        地址值相同，修改array3时，array1也会相应发生变化
        int[] array3 = new int[8];
        array3 = array1;
         */
        
        //数组的反转
        System.out.print("数组array1反转值：");
        for (int i = 0; i < (array1.length / 2); i++) {
            int temp = array1[i];

            array1[i] = array1[array1.length - 1 -i];
            array1[array1.length - 1 -i] = temp;
        }
        for (int i = 0; i < array1.length; i++) {
            System.out.print(array1[i]+"\t");
        }
        System.out.println();
        System.out.println();

        //查找 线性查找
        int num = 13;
        boolean isflag = true;
        for (int i = 0; i < array1.length; i++) {
            if(num == array1[i]) { //if后面跟了好几行操作时，最好加上{}
                System.out.println("找到了指定的元素"+num+"，位置是" + i);
                isflag = false;
                break;
            }
        }
        if(isflag) {
            System.out.println("很遗憾，没有找到指定的元素");
        }

        //查找，二分法查找，前提是数组有序
        int num2 = 11;
        int head = 0;
        int end = array1.length - 1;
        boolean isflag1 = true;
        while(head <= end){
            int middle = (head + end)/2;
            if(num2 == array1[middle]){
                System.out.println("找到了指定的元素"+num2+"，位置是" + middle);
                isflag1 = false;
                break;
            }
            else if(num2 > array1[middle]){
                head = middle + 1;
            }
            else{
                end = middle - 1;
            }
        }
        if(isflag1)
            System.out.println("很遗憾没有找到元素"+num2);

    }
}

算法五大特征

• 输入
• 输出
• 有穷性
• 确定性
• 可行性

十大内部排序算法

• 选择排序
• 插入排序
• 堆排序
• 归并排序
• 基数排序
• 计数排序
• 快速排序
• 冒泡排序
• 桶排序
• 希尔排序

排序算法优劣

• 时间复杂度
• 空间复杂度
• 稳定性

package www.wangwei.com;

public class BubbleSort {
    public static void main(String[] args){
        //冒泡排序算法的实现
        int[] array = new int[]{-4,67,92,-54,6,40,102,-906};
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }
        System.out.println();
        for(int i = 0;i < array.length - 1; i++){
            for (int j = 0; j < array.length - 1 - i; j++) {
                if(array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + "\t");
        }

    }
}

数组常见异常

• 数组脚标越界异常：ArrayIndexOutOfBoundsException
• 空指针异常：NullPointerException