VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > 编程开发 > Java教程 >

  • 学习笔记：Java中的数据结构——数组

一、数组的基础知识

  1. 数组的创建
    在Java中把数组当做对象，不是基本数据类型来看待，所有创建数组要用new操作符。
    例子:



	
		

			
				

					 

					
			
				@Test
		

		

			
				

					 

					
			
				public void test1(){
		

		

			
				

					 

					
			
				int[] array;//定义数组
		

		

			
				

					 

					
			
				array = new int[10];//创建数组
		

	



    
	
  1. 
		数组的初始化 动态初始化：
    2. 






	
		

			
				

					 

					
			
				//数组的动态初始化
		

		

			
				

					 

					
			
				array[0] = 1;
		

		

			
				

					 

					
			
				array[1] = 2;
		

		

			
				

					 

					
			
				array[2] = 3;
		

		

			
				

					 

					
			
				array[3] = 4;
		

		

			
				

					 

					
			
				array[4] = 5;
		

		

			
				

					 

					
			
				System.out.println(array);
		

	




	静态初始化：





	
		

			
				

					 

					
			
				//数组的静态初始化
		

		

			
				

					 

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

		

			
				

					 

					
			
				System.out.println(array2);
		

	



    
	
  1. 
		数组数据项的访问 数组数据项的访问通过使用方括号中的下标数来访问。
    2. 






	
		

			
				

					 

					
			
				//访问数组数据项
		

		

			
				

					 

					
			
				System.out.println(array[1]);//2
		

	



    
	
  1. 
		数组的length属性 length属性记录数组的长度。
    2. 






	
		

			
				

					 

					
			
				//数组的length属性
		

		

			
				

					 

					
			
				System.out.println(array.length);//10
		

	



    
	
  1. 
		数组的常用方法 继承父类Object中的方法
    2. 






	
		

			
				

					 

					
			
				//数组的常用方法
		

		

			
				

					 

					
			
				System.out.println(array.equals(array2));
		

		

			
				

					 

					
			
				array.clone();
		

		

			
				

					 

					
			
				array.hashCode();
		

		

			
				

					 

					
			
				array.toString();
		

		

			
				

					 

					
			
				System.out.println(array.getClass());
		

	




	二、数组中数据的插入、查找、删除、遍历


    
	
  1. 
		可以将数组封装在一个类中，通过调用对象的方法来实现插入、删除等操作。这种用来存取数据对象的类也叫做容器类，不仅可以存取数据，还提供访问数据的方法和排序等操作的方法。
    2. 






	
		

			
				

					 

					
			
				/**
		

		

			
				

					 

					
			
				* @author vetstein
		

		

			
				

					 

					
			
				* @creat 2021-03-2021/3/31-3:42
		

		

			
				

					 

					
			
				*/
		

		

			
				

					 

					
			
				public class ArrayInt {
		

		

			
				

					 

					
			
				private int[] a;//定义数组
		

		

			
				

					 

					
			
				public int num;//记录数据项长度
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				public ArrayInt(int size){
		

		

			
				

					 

					
			
				a = new int[size];//Java中数组的长度可以在运行时再确定
		

		

			
				

					 

					
			
				num = 0;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//查找
		

		

			
				

					 

					
			
				public boolean find(int key){
		

		

			
				

					 

					
			
				int j;
		

		

			
				

					 

					
			
				for (j = 0; j < num; j++) {//遍历数组数据项
		

		

			
				

					 

					
			
				if (a[j] == key) {
		

		

			
				

					 

					
			
				break;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				if (j == num ){ //没找到
		

		

			
				

					 

					
			
				return false;
		

		

			
				

					 

					
			
				}else{
		

		

			
				

					 

					
			
				return true; //找到
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//插入
		

		

			
				

					 

					
			
				public void insert(int data){
		

		

			
				

					 

					
			
				a[num] = data;
		

		

			
				

					 

					
			
				num++;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//删除
		

		

			
				

					 

					
			
				public boolean delete(int value){
		

		

			
				

					 

					
			
				int j;
		

		

			
				

					 

					
			
				for (j = 0; j < num; j++){
		

		

			
				

					 

					
			
				if (a[j] == value ){
		

		

			
				

					 

					
			
				break;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				if (j == num ){ //没找到
		

		

			
				

					 

					
			
				return false;
		

		

			
				

					 

					
			
				}else{ //找到
		

		

			
				

					 

					
			
				for(int i = j; i < num; i++){
		

		

			
				

					 

					
			
				a[i] = a[i+1] ;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				num--;
		

		

			
				

					 

					
			
				return true;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//遍历
		

		

			
				

					 

					
			
				public void show(){
		

		

			
				

					 

					
			
				System.out.println(a.length);
		

		

			
				

					 

					
			
				for(int j = 0; j <num; j++){
		

		

			
				

					 

					
			
				System.out.println(a[j]);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

	




	三、有序数组中的查找


    
	
  1. 
		有序数组中有两种查找算法： 线形查找：依次向后，直到找到匹配项，当找到一个比目标数大的数就退出查找，时间复杂度（N）； 二分查找：一开始设置变量low和higer分别指向数组第一个元素和最后一个元素，通过这两个变量可以确定查找目标值的范围； 在循环中，mid指向当前数组范围的中间值,可以查看mid指向的数据是否和目标值相等，是则找到了并返回mid下标值；循环中每一步将查找范围缩小一半，最终范围会小到无法分割。如果low比higer大，则范围不存在，查找停止。时间复杂度（log2 (N)）；
    2. 






	
		

			
				

					 

					
			
				//查找
		

		

			
				

					 

					
			
				public int find(int key){
		

		

			
				

					 

					
			
				int low = 0;
		

		

			
				

					 

					
			
				int high = num - 1;
		

		

			
				

					 

					
			
				int mid;
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				while(low <= high) {
		

		

			
				

					 

					
			
				mid = (low + high)/2;
		

		

			
				

					 

					
			
				if (a[mid] == key) { //找到返回mid下标值
		

		

			
				

					 

					
			
				return mid;
		

		

			
				

					 

					
			
				} else {
		

		

			
				

					 

					
			
				if (a[mid] > key) { //改变查找范围
		

		

			
				

					 

					
			
				high = mid - 1;
		

		

			
				

					 

					
			
				} else { //改变查找范围
		

		

			
				

					 

					
			
				low = mid + 1;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				return -1;
		

	




	四、有序数组


    
	
  1. 
		同样按照上面将数组封装在一个类中，可以将有序数组封装成一个容器类，通过调用方法实现数据存取和查找、遍历操作。
    2. 






	
		

			
				

					 

					
			
				public class Arraybina2 {
		

		

			
				

					 

					
			
				//有序数组
		

		

			
				

					 

					
			
				private int[] array; //声明数组
		

		

			
				

					 

					
			
				public int num; //记录数组数据长度
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				public Arraybina2(int size) {
		

		

			
				

					 

					
			
				array = new int[size]; //运行时创建数组
		

		

			
				

					 

					
			
				num = 0; //初始化数组长度为0
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//插入数据
		

		

			
				

					 

					
			
				public void insert(int value) {
		

		

			
				

					 

					
			
				int j;
		

		

			
				

					 

					
			
				for (j = 0; j < num; j++) { //找到数据将要插入的位置
		

		

			
				

					 

					
			
				if (array[j] > value) {
		

		

			
				

					 

					
			
				break;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				for (int i = num - 1 ; i >= j; i--) { //将比插入值大的数组项右移
		

		

			
				

					 

					
			
				array[i+1] = array[i];
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				array[j] = value; //插入数据
		

		

			
				

					 

					
			
				num++;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//二分查找
		

		

			
				

					 

					
			
				public int find(int value) {
		

		

			
				

					 

					
			
				int high = num - 1; //定义变量控制查找范围
		

		

			
				

					 

					
			
				int low = 0;
		

		

			
				

					 

					
			
				int mid;
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				while (low <= high) { //每次循环缩小一半的查找范围
		

		

			
				

					 

					
			
				mid = (low +high)/2;
		

		

			
				

					 

					
			
				if (array[mid] == value) { //找到并返回小标
		

		

			
				

					 

					
			
				return mid;
		

		

			
				

					 

					
			
				} else {
		

		

			
				

					 

					
			
				if (array[mid] > value) { //改变查找范围
		

		

			
				

					 

					
			
				high = mid - 1;
		

		

			
				

					 

					
			
				} else {
		

		

			
				

					 

					
			
				low = mid + 1; //改变查找范围
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				return -1; //没找到返回-1
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//删除
		

		

			
				

					 

					
			
				public boolean delete(int value) {
		

		

			
				

					 

					
			
				int j = find(value);
		

		

			
				

					 

					
			
				if (j == -1) {
		

		

			
				

					 

					
			
				return false;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				//用删除值后面数的值覆盖删除值,并左移数组数据项
		

		

			
				

					 

					
			
				for (int i = j; i < num - 1; i++) {
		

		

			
				

					 

					
			
				array[i] = array[i+1];
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				num--;
		

		

			
				

					 

					
			
				return true;
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				//遍历
		

		

			
				

					 

					
			
				public void show() {
		

		

			
				

					 

					
			
				for (int j = 0; j < num; j++) {
		

		

			
				

					 

					
			
				System.out.println(array[j]);
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

		

			
				

					 

					
			
				}
		

	



    
	
  1. 
		测试代码：生成一个容量为10的有序数组，实现下面的操作
    2. 






	
		

			
				

					 

					
			
				@Test
		

		

			
				

					 

					
			
				public void test2(){
		

		

			
				

					 

					
			
				Arraybina2 a1 = new Arraybina2(10);
		

		

			
				

					 

					
			
				a1.insert(10); //插入数据
		

		

			
				

					 

					
			
				a1.insert(22);
		

		

			
				

					 

					
			
				a1.insert(16);
		

		

			
				

					 

					
			
				a1.insert(1);
		

		

			
				

					 

					
			
				a1.insert(160);
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				a1.show(); //遍历数组
		

		

			
				

					 

					
			
				System.out.println(a1.num); //显示数组长度
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				System.out.println(a1.find(16)); //查找数组中的数据
		

		

			
				

					 

					
			
				 
		

		

			
				

					 

					
			
				System.out.println(a1.delete(16)); //删除数组中某一项
		

		

			
				

					 

					
			
				a1.show(); //再次遍历
		

		

			
				

					 

					
			
				}
		

	



    
	
  1. 
		测试结果：
    2. 






	
		

			
				

					 

					
			
				1 10 16 22 160
		

		

			
				

					 

					
			
				5
		

		

			
				

					 

					
			
				2
		

		

			
				

					 

					
			
				true
		

		

			
				

					 

					
			
				1 10 22 160
		

	




	  由上面的结果可以看出这个类实现数组常见的操作，那么有序数组相比普通数组优点是什么呢？显然有序数组查找的速度比无序数组快，插入操作因为要右移部分数据项要慢一些，删除操作有序数组和无序数组都要左移数据项速度一样。



	五、数组存在的缺陷



	  不论是有序数组还是无序数组，查找、插入、删除都不能满足同时都很快，存在这样的缺项。另一方面，创建数组时数组容量已经被确定了，扩容需要新建新的数组，复制旧数组中的数据，初始容量太大又会浪费存储空间，不太灵活。

	

	原文：https://www.cnblogs.com/echoxiatiandefeng/p/14599748.html


      



  

  
  

   
    
    
   

  

  
 
 

 
 
  
 
 
 
 






 






相关教程