淘先锋技术网

首页 1 2 3 4 5 6 7

三、数组

1、数组的概念

数组:数组(Array),是多个相同类型数据按一定顺序排列 的集合,并使用一个名字命名,并通过编号的方式 对这些数据进行统一管理。

数组的常见概念:

  • 数组名
  • 下标(索引)
  • 元素
  • 数组的长度

数组的特点:

1.数组是有序排列的。

2.数组属于引用类型变量。数组的元素,既可以是基本数据类型,也可以是引用数据类型。

3.创建数组对象会在内存中开辟一整块连续的内存空间。

4.数组的长度一旦确定,就不能修改

数组的分类:

① 按照维度:一维数组、二维数组、三维数组、…

② 按照元素的数据类型分:基本数据类型元素的数组、引用数据类型元素的数组(即对 象数组)

2、一维数组的使用

① 一维数组的声明和初始化
 ② 如何调用数组指定位置的元素
 ③ 如何获取数组的长度
 ④ 如何遍历数组
 ⑤ 数组元素的默认初始化值 
  ⑥ 数组的内存分析 

(1)一维数组的声明和初始化

声明: 

  type[]  var  或 type var[]

例如:int a[]   String[]  str

Java语言中声明数组时不能指定其长度(数组中元素的数), 例如: int a[5]; //非法

初始化:

① 静态初始化:数组的初始化和数组的赋值操作 同时进行

a = new int[] {1001,1002,1003};

String[] b = new String[]{"aa","bb","cc"};

② 动态初始化:数组的初始化和数组的赋值操作 分别进行

String[] names = new String[5];

(2)元素的引用

定义并用运算符new为之分配空间后,才可以引用数组中的每个元素;

数组元素的引用方式:数组名[数组元素下标]

  • 数组元素下标可以是整型常量或整型表达式。如a[3] , b[i] , c[6*i]
  • 数组元素下标从0开始;长度为n的数组合法下标取值范围: 0 —>n-1;如int a[]=new int[3]; 可引用的数组元素为a[0]、a[1]、a[2]

(3)获取数组长度

每个数组都有一个属性length指明它的长度,例如:a.length 指明数组a的长 度(元素个数)

  • 数组一旦初始化,其长度是不可变的

(4)一维数组遍历

for(int i = 0;i < array.length;i++) {
            System.out.println(array[i]);
    }

(5)一维数组的默认初始化值

  • 数组元素是 整型:0   (byte、short、int、long)
  • 数组元素是 浮点型:0.0 
  • 数组元素是 字符char型:0 或 'u0000',而非'0'
  •  数组元素是 布尔boolean型:false    0  1
  •  数组元素是 引用类型:null

(6)数组的内存解析

 练习题:

从键盘读入学生成绩,找出最高分, 并输出学生成绩等级。

成绩>=最高分-10 等级为’A’

成绩>=最高分-20 等级为’B’

成绩>=最高分-30 等级为’C’

其余                    等级为’D’

提示:先读入学生人数,根据人数创建int数组, 存放学生成绩。

import java.util.Scanner;

public class ArrayExer1 {

	public static void main(String[] args) {
		
		//1.使用Scanner,接收数据
		Scanner scan = new Scanner(System.in);
		System.out.println("请输入学生人数:");
		int num = scan.nextInt();
		
		
		//2.使用数组,存储学生成绩:动态初始化
		int[] scores = new int[num];
		//3.给数组中元素赋值
		System.out.println("请输入" + num + "个学生成绩");
		for(int i = 0;i < scores.length;i++) {
			scores[i] = scan.nextInt();
		}
		//4.获取数组中的最大值
		int maxScore = 0;
		for(int i = 0;i < scores.length;i++) {
			if(maxScore < scores[i]) {
				maxScore = scores[i];
			}
		}
		System.out.println("最高分为:" + maxScore);
		//5.根据每个学生与最高分的差值,得到每个学生的等级,并输出成绩和等级
		char level;
		for(int i = 0;i < scores.length;i++) {
			if(maxScore - scores[i] <= 10) {
				level = 'A';
			}else if(maxScore - scores[i] <= 20) {
				level = 'B';
			}else if(maxScore - scores[i] <= 30) {
				level = 'C';
			}else {
				level = 'D';
			}
			System.out.println("student " + i + " score is " + scores[i] + " grade is " + level);
			
		}
		
	}
}

3、二维数组

对于二维数组的理解,我们可以看成是一维数组 array1又作为另一个一维数组array2的元素而存 在。其实,从数组底层的运行机制来看,其实没有多维数组。

二维数组的使用:
 ① 二维数组的声明和初始化
 ② 如何调用数组的指定位置的元素
 ③ 如何获取数组的长度
 ④ 如何遍历数组
 ⑤ 数组元素的默认初始化值
 ⑥ 数组的内存解析 

(1)声明和初始化

//静态初始化
int[][] arr1 = new int[][] {{1,2,3},{4,5},{7,8,9}};
//动态初始化1
String[][] arr2 = new String[3][2];
//动态初始化2
String[][] arr3 = new String[3][];

(2)调用

System.out.println(arr1[0][1]);//2
System.out.println(arr2[1][1]);//null

arr3[1] = new String[4];
System.out.println(arr3[1][0]);
System.out.println(arr3[0]);//


(3)遍历和length属性

 for(int i = 0;i < arr.length;i++){
            for(int j = 0;j < arr[i].length;j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
 }

 (4)二维数组的默认初始化值

  二维数组的使用:
          规定:二维数组分为外层数组的元素,内层数组的元素
                 int[][] arr = new int[4][3];
                 外层数组:arr[0],arr[1]
                 内层数组:arr[0][0],arr[1][2]
 
数组元素的默认初始化值:
    针对于初始化方式一:比如 int[][] arr = new arr[4][3];
        外层元素的初始化值为:地址值
        内层元素的初始化值为:与一维数组相同

    针对于初始化方式二:比如:int[][] arr = new arr[4][];
        外层元素的初始化值为:null
       内层元素的初始化值为:不能调用,否则报错

(5)数组的内存解析

 

 练习题:

1.

 

/*
 * 打印10行杨辉三角
 */
public class YangHuiTest {

	public static void main(String[] args) {
		//1.声明和初始化二维数组
		int[][] yangHui = new int[10][];
		//2.给数组的元素赋值
		for(int i = 0;i < yangHui.length;i++) {
			
			yangHui[i] = new int[i+1];
			//2.1.给首末元素赋值
			yangHui[i][0] = yangHui[i][i] = 1;
			//2.2.给每行非首末元素赋值
			if(i > 1) {
				for(int j = 1;j < yangHui[i].length - 1;j++) {
					yangHui[i][j] = yangHui[i-1][j] + yangHui[i-1][j-1];
				}
			}		
		}
		//3.遍历数组
		for(int i = 0;i < yangHui.length;i++) {
			for(int j = 0;j < yangHui[i].length;j++) {
				System.out.print(yangHui[i][j] +" ");
			}
			System.out.println();
		}
	}
}

 2.创建一个长度为6的int型数组,要求数组元素的值都在1-30之间,且是随机赋值。同时,要求 元素的值各不相同。

/*
 * 创建一个长度为6的int型数组,要求数组元素的值都在1-30之间,且是随机赋值。同时,要求
 *  元素的值各不相同。
 */
public class ArrayExer1 {

	public static void main(String[] args) {
		//方式一:
		
//		//1.创建一维数组
//		int[] arr = new int[6];
//		//2.给数组赋值
//		for(int i = 0;i < arr.length;i++) {
//			//2.1.获取1-30的随机数 [0,1)  [0,30)  [1,31)
//			//要记得加括号,不然先执行强制转换,一直是0
//			arr[i] = (int)(Math.random()*30) + 1;
//			//3.判断元素是否相同
//			boolean isFlag = false;
//			while(true) {
//				for(int j = 0;j < i;j++) {
//					
//					if(arr[i] == arr[j]) {
//						isFlag = true;
//						break;
//					}
//				}
//				//4.如果相同,重新赋值
//				if(isFlag) {
//					arr[i] = (int)(Math.random()*30) + 1;
//					//不要忘记重新初始化
//					isFlag = false;
//					continue;
//				}
//				//跳出while循环
//				break;
//			}
//			
//		}
//		//遍历数组
//		for(int i = 0;i < arr.length;i++) {
//			System.out.print(arr[i] + " ");
//		}
		
		//方式二:
		
		//1.创建一维数组
		int[] arr = new int[6];
		//2.给数组赋值
		for(int i = 0;i < arr.length;i++) {
			//2.1.获取1-30的随机数 [0,1)  [0,30)  [1,31)
			//要记得加括号,不然先执行强制转换,一直是0
			arr[i] = (int)(Math.random()*30) + 1;
			//3.判断元素是否相同
				for(int j = 0;j < i;j++) {
					
					if(arr[i] == arr[j]) {
						i--;
						continue;
					}
				}
			
		}
		//遍历数组
		for(int i = 0;i < arr.length;i++) {
			System.out.print(arr[i] + " ");
		}
		
	}
}

3.回形数格式方阵的实现

从键盘输入一个整数(1~20) 

则以该数字为矩阵的大小,把1,2,3…n*n 的数字按照顺时针螺旋的形式填入其中。例如: 输入数字2,则程序输出: 1 2 

                                4 3 

输入数字3,则程序输出: 1 2 3 

                                           8 9 4 

                                           7 6 5 

输入数字4, 则程序输出: 

1   2   3   4 

12  13  14  5 

11  16  15  6 

10   9  8    7

方式一:
class RectangleTest {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println("输入一个数字");
		int len = scanner.nextInt();
		int[][] arr = new int[len][len];

		int s = len * len;
		/*
		 * k = 1:向右 k = 2:向下 k = 3:向左 k = 4:向上
		 */
		int k = 1;
		int i = 0, j = 0;
		for (int m = 1; m <= s; m++) {
			if (k == 1) {
				if (j < len && arr[i][j] == 0) {
					arr[i][j++] = m;
				} else {
					k = 2;
					i++;
					j--;
					m--;
				}
			} else if (k == 2) {
				if (i < len && arr[i][j] == 0) {
					arr[i++][j] = m;
				} else {
					k = 3;
					i--;
					j--;
					m--;
				}
			} else if (k == 3) {
				if (j >= 0 && arr[i][j] == 0) {
					arr[i][j--] = m;
				} else {
					k = 4;
					i--;
					j++;
					m--;
				}
			} else if (k == 4) {
				if (i >= 0 && arr[i][j] == 0) {
					arr[i--][j] = m;
				} else {
					k = 1;
					i++;
					j++;
					m--;
				}
			}
		}

		// 遍历
		for (int m = 0; m < arr.length; m++) {
			for (int n = 0; n < arr[m].length; n++) {
				System.out.print(arr[m][n] + "\t");
			}
			System.out.println();
		}
	}
}

方式二:
class RectangleTest1 {

	public static void main(String[] args) {
		int n = 7;
		int[][] arr = new int[n][n];

		int count = 0; // 要显示的数据
		int maxX = n - 1; // x轴的最大下标
		int maxY = n - 1; // Y轴的最大下标
		int minX = 0; // x轴的最小下标
		int minY = 0; // Y轴的最小下标
		while (minX <= maxX) {
			for (int x = minX; x <= maxX; x++) {
				arr[minY][x] = ++count;
			}
			minY++;
			for (int y = minY; y <= maxY; y++) {
				arr[y][maxX] = ++count;
			}
			maxX--;
			for (int x = maxX; x >= minX; x--) {
				arr[maxY][x] = ++count;
			}
			maxY--;
			for (int y = maxY; y >= minY; y--) {
				arr[y][minX] = ++count;
			}
			minX++;
		}

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

4、数组中涉及的常见算法

1. 数组元素的赋值(杨辉三角、回形数等)

2. 求数值型数组中元素的最大值、最小值、平均数、总和等

3. 数组的复制、反转、查找(线性查找、二分法查找)

4. 数组元素的排序算法

2.

/*
 * 算法的考查:求数值型数组中元素的最大值、最小值、平均数、总和等
 * 
 * 定义一个int型的一维数组,包含10个元素,分别赋一些随机整数,
 * 然后求出所有元素的最大值,最小值,和值,平均值,并输出出来。
 * 要求:所有随机数都是两位数。
 * 
 */
public class ArrayTest1 {

	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);
		}
		
		//遍历输出
		for(int i = 0;i < arr.length;i++) {
			System.out.print(arr[i] + " ");
		}
		
		System.out.println();
		//数组中的最大值
		int maxValue = arr[0];
		for(int i = 0;i < arr.length;i++) {
			if(maxValue < arr[i]) {
				maxValue = arr[i];
			}
		}
		System.out.println("最大值为:" + maxValue);
		
		//数组最小值
		int minValue = arr[0];
		for(int i = 0;i < arr.length;i++) {
			if(minValue > arr[i]) {
				minValue = arr[i];
			}
		}
		System.out.println("最小值为:" + minValue);
		
		//和
		int sum = 0;
		for(int i = 0;i < arr.length;i++) {
			sum += arr[i];
		}
		System.out.println("和值为:" + sum);
		
		//平均值
		int averageValue = sum / 10;
		System.out.println(averageValue);
	}
}

3.

/*
 * 算法的考查:数组的复制、反转、查找(线性查找、二分法查找)
 * 
 */
public class ArrayTest2 {

	public static void main(String[] args) {
		
		String[] arr = new String[] {"JJ","DD","MM","BB","GG","AA"};
		
		//数组的复制
		String[] arr1 = new String[arr.length];
		for(int i = 0;i < arr1.length;i++) {
			arr1[i] = arr[i];
		}
		
		//数组的反转
		//方法一:
//		for(int i = 0;i < arr.length / 2;i++) {
//			String temp = arr[i];
//			arr[i] = arr[arr.length-1-i];
//			arr[arr.length-1-i] = temp;
//		}
		
		//方法二:
		for(int i=0,j=arr.length-1;i<j;i++) {
			String temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		
		for(int i = 0;i < arr.length;i++) {
			System.out.println(arr[i] + " ");
		}
		
		//查找(或搜索)
		//线性查找
		String dest = "BB";
		boolean flag = true;
		for(int i = 0;i < arr.length;i++) {
			if(dest.equals(arr[i])) {
				System.out.println("找到了指定元素,索引为:" + i);
				flag = false;
				break;
			}
		}
		if(flag) {
			System.out.println("未找到指定元素");
		}
		
		//二分法查找:(熟悉)
		//前提:所要查找的数组必须是有序的
		int[] arr3 = new int[]{-99,-54,-2,0,2,33,43,256,999};
		
		int number = 2561;//要查找的元素
		boolean flag1 = false;
		int head = 0;//首索引位置
		int end = arr3.length - 1;//尾索引位置
		while(head <= end) {
			int middle = (head + end) / 2; 
			
			if(arr3[middle] == number) {
				System.out.println("找到指定的元素,索引为:" + middle);
				flag1 = true;
				break;
			}else if(arr3[middle] > number) {
				end = middle - 1;
			}else {//arr3[middle] < number
				head = middle + 1;
			}
		}
		
		if(flag1 == false) {
			System.out.println("未找到指定元素");
		}
		
	}
}

4.排序算法

十大内部排序算法:

选择排序:

        直接选择排序、堆排序

交换排序:

        冒泡排序快速排序

插入排序:

        直接插入排序、折半插入排序、Shell排序

归并排序

通式排序

基数排序

 冒泡排序

介绍:

冒泡排序的原理非常简单,它重复地走访过要排序的数列,一次比较两个元 素,如果他们的顺序错误就把他们交换过来。

排序思想:

1. 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。

2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步 做完后,最后的元素会是最大的数。

3. 针对所有的元素重复以上的步骤,除了最后一个。

4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要 比较为止。

/*
 * 数组冒泡排序的实现
 * 
 */
public class BubbleSortTest {

	public static void main(String[] args) {
		int[] arr = new int[] {43,32,76,-98,0,64,33,-21,32,99};
		
		for(int i = 0;i < arr.length - 1;i++) {//最后一个数不用再比了
			
			for(int j = 0;j < arr.length - 1 - i;j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		
		for(int i = 0;i < arr.length;i++) {
			System.out.println(arr[i] + " ");
		}
	}
}

快速排序

介绍:

快速排序通常明显比同为O(nlogn)的其他算法更快,因此常被采用,而且快 排采用了分治法的思想,所以在很多笔试面试中能经常看到快排的影子。可 见掌握快排的重要性。

快速排序(Quick Sort)由图灵奖获得者Tony Hoare发明,被列为20世纪十 大算法之一,是迄今为止所有内排序算法中速度最快的一种。冒泡排序的升 级版,交换排序的一种。快速排序的时间复杂度为O(nlog(n))。

排序思想:

1. 从数列中挑出一个元素,称为"基准"(pivot),

2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准 值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后, 该基准就处于数列的中间位置。这个称为分区(partition)操作。

3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数 列排序。

4. 递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好 了。虽然一直递归下去,但是这个算法总会结束,因为在每次的迭代 (iteration)中,它至少会把一个元素摆到它最后的位置去。


/**
 * 快速排序
 * 通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,
 * 则分别对这两部分继续进行排序,直到整个序列有序。
 */
public class QuickSort {
	private static void swap(int[] data, int i, int j) {
		int temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	private static void subSort(int[] data, int start, int end) {
		if (start < end) {
			int base = data[start];
			int low = start;
			int high = end + 1;
			while (true) {
				while (low < end && data[++low] - base <= 0)
					;
				while (high > start && data[--high] - base >= 0)
					;
				if (low < high) {
					swap(data, low, high);
				} else {
					break;
				}
			}
			swap(data, start, high);
			
			subSort(data, start, high - 1);//递归调用
			subSort(data, high + 1, end);
		}
	}
	public static void quickSort(int[] data){
		subSort(data,0,data.length-1);
	}
	
	
	public static void main(String[] args) {
		int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
		System.out.println("排序之前:\n" + java.util.Arrays.toString(data));
		quickSort(data);
		System.out.println("排序之后:\n" + java.util.Arrays.toString(data));
	}
}

5、Arrays工具类的使用

/*
 * 
 * java.util.Arrays:操作数组的工具类,里面定义了很多操作数组的方法
 */
public class ArraysTest {

	public static void main(String[] args) {
		
		//1.boolean equals(int[] a,int[] b) 判断两个数组是否相等
		int[] arr1 = new int[] {1,2,3,4};
		int[] arr2 = new int[] {1,3,4,2};
		boolean isEquals = Arrays.equals(arr1, arr2);
		System.out.println(isEquals);
		
		//2.String toString(int[] a)  输出数组信息 任意类型数组
		System.out.println(Arrays.toString(arr1));
		String[] arr3 = new String[] {"Tom","LingLing","Jerry","DaMing"};
		System.out.println(Arrays.toString(arr3));
		
		//3.void fill(int[] a,int val)  将指定值填充到数组中
		Arrays.fill(arr1,10);
		System.out.println(Arrays.toString(arr1));
		
		//4.void sort(int[] a)  对数组进行排序
		Arrays.sort(arr2);
		System.out.println(Arrays.toString(arr2));
		 
		//5.int binarySearch(int[] a,int key)  对排序后的数组进行二分法检索指定的值
		int[] arr4 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
		int index = Arrays.binarySearch(arr4, 105);
		if(index > 0) {
			System.out.println(index);
		}else {
			System.out.println("未找到指定元素");
		}
		
	}
}

6、数组使用中的常见异常

数组中的常见异常:

1.数组角标越界异常:ArrayIndexOutOfBoundsException

2.空指针异常:NullPointerException

public class ArrayExceptionTest {

	public static void main(String[] args) {
		
		//1.数组角标越界异常:ArrayIndexOutOfBoundsException
		int[] arr = new int[] {1,2,3,4,5};
		
//		for(int i = 0;i <= arr.length;i++) {
//			System.out.println(arr[i]);
//		}
		
//		System.out.println(arr[-2]);
		
		//空指针异常:NullPointerException
		//情况一:
		int[] arr1 = new int[] {1,2,3};
		arr1 = null;
//		System.out.println(arr1[1]);
		
		//情况二:
		int[][] arr2 = new int[4][];
//		System.out.println(arr2[2][0]);
		
		//情况三:
		String[] arr3 = new String[] {"aa","bb","dd"};
		arr3[1] = null;
//		System.out.println(arr3[1].toString());
		System.out.println(arr3[2].toString());
	}
}