数据结构和算法（Java版）快速学习（数组Array）

Java数组

在Java中，数组是用来存放同一种数据类型的集合，注意只能存放同一种数据类型。

用类封装数组实现数据结构

数据结构必须具有以下基本功能：

　　①、如何插入一条新的数据项

　　②、如何寻找某一特定的数据项

　　③、如何删除某一特定的数据项

　　④、如何迭代的访问各个数据项，以便进行显示或其他操作

　　而我们知道了数组的简单用法，现在用类的思想封装一个数组，实现上面的四个基本功能：

class EasyAarray{ //数据结构：简易数组

	private int[] ins; //一维整型数组

	private int footer; //数组下标

	private int maxLength; //数组最大长度

	public EasyAarray(){

		footer=0;

		maxLength=100;

		ins=new int[maxLength]; //无参构造默认初始化100长度的数组

	}

	public EasyAarray(int length){ //初始化长度为n的数组

		footer=0;

		maxLength=length;

		ins=new int[maxLength];

	}

	//取得数组的有效长度

	//遍历数组的元素

	//添加

	//判断元素是否存在

	//根据下标查找元素

	//修改元素

	//删除元素

}

具体代码编写：

class EasyAarray{ //数据结构：简易无序数组

	private int[] ins; //一维整型数组

	private int footer; //数组下标

	private int maxLength; //数组最大长度

	public EasyAarray(){

		footer=0;

		maxLength=100;

		ins=new int[maxLength]; //无参构造默认初始化100长度的数组

	}

	public EasyAarray(int length){ //初始化长度为n的数组

		footer=0;

		maxLength=length;

		ins=new int[maxLength];

	}

	//取得数组的有效长度

	public int size(){

		return footer;

	}

	//遍历数组的元素

	public void printAarray(){

		for(int i=0;i<footer;i++){

			System.out.print(ins[i]+" ");

		}

		System.out.println();

	}

	//添加

	public boolean add(int n){

		if(footer>=maxLength){ //若下标超出最大长度，则添加失败（不考虑扩容）

			return false;

		}

		ins[footer++]=n;

		return true;

	}

	//判断元素是否存在

	public boolean exist(int n){

		for(int i=0;i<=footer;i++){

			if(n==ins[i]){

				return false;

			}

		}

		return true;

	}

	//根据下标（索引）查找元素

	public int get(int index){

		return ins[index];

	}

	//修改元素（若有重复元素，只修改第一个）

	public boolean modify(int oldValue,int newValue){

		for(int i=0;i<=footer;i++){

			if(oldValue==ins[i]){

				ins[i]=newValue;

				return false;

			}

		}

		return true;

	}

	//删除元素

	public boolean del(int index){

		if(!exist(index)){ //若元素不存在，返回false

			return false;

		}

		for(int i=index;i<=footer;i++){ //元素依次前移

			ins[i]=ins[i+1];

		}

		footer--; //下标减1

		return true;

	}

}

public class App {

	public static void main(String[] args) {

		EasyAarray ea=new EasyAarray(10);

		System.out.println(ea.size());

		ea.add(4);

		ea.add(7);

		ea.add(3);

		ea.add(1);

		ea.add(9);

		ea.del(2); //删除第3个元素（索引是2）

		ea.printAarray();

	}

}

数组的局限性

　　通过上面的代码，我们发现数组是能够完成一个数据结构具有的所有功能，而且实现起来也不难，但是实际应用中不用它来进行所有的数据存储。

　　数组（不考虑排序）的局限性分析：

　　①、插入快，对于无序数组，上面我们实现的数组就是无序的，即元素没有按照从大到小或者某个特定的顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但是有序数组却不一定了，它需要在指定的位置插入。

　　②、查找慢，当然如果根据下标来查找是很快的。但是通常我们都是根据元素值来查找，给定一个元素值，对于无序数组，我们需要从数组第一个元素开始遍历，知道找到那个元素。有序数组通过特定的算法查找的速度会比无需数组快，后面我们会讲各种排序算法。

　　③、删除慢，根据元素值删除，我们要先找到该元素所处的位置，然后将元素后面的值整体向前面移动一个位置。也需要比较多的时间。

　　④、数组一旦创建后，大小就固定了，不能动态扩展数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面数据个数增加了又添加不进去了。

　　很显然，数组虽然插入快，但是查找和删除都比较慢，所以我们不会用数组来存储所有的数据，那有没有什么数据结构插入、查找、删除都很快，而且还能动态扩展存储个数大小呢，答案是有的，比如ArrayList动态数组就可以动态的扩展存储元素的个数，其他的暂时不需要了解。

巴特西

数据结构和算法（Java版）快速学习（数组Array）

最新文章

热门文章