数组

前言

数据结构分类

数据结构中数据按逻辑结构分为：线性结构、非线性结构

• 常用的线性结构有：线性表（顺序存储、链式存储）、栈、队列、双端队列、串(一维数组)；
• 常见的非线性结构有：二维数组、多维数组、矩阵、散列表、树、堆、图。

线性结构的特征

• • 集合中必存在唯一的一个”第一个元素”；
  • 集合中必存在唯一的一个”最后的元素”；
  • 除最后元素之外，其它数据元素均有唯一的”后继”；
  • 除第一元素之外，其它数据元素均有唯一的”前驱”。

线性结构作为最常用的数据结构，其特点是数据元素之间存在一对一的线性关系。

如（a0,a1,a2,…..,an），a0为第一个元素，an为最后一个元素，此集合为一个线性结构的集合。

非线性结构，其逻辑特征是一个节点元素可能有多个直接前驱和多个直接后继。

线性数据结构存储方式

• • 顺序存储结构：顺序表
  • 链式存储结构：链表

常用线性数据结构

常用的线性结构有：线性表（顺序存储、链式存储）、栈、队列、双端队列、串(一维数组)。

线性表(Linear List)就是数据排成像一条线一样的结构，数据只有前后两个方向。

线性表分为顺序存储和链式存储。

按照人们的生活习惯，存放东西时，一般是找一块空间，然后将需要存放的东西依次摆放，这就是顺序存储。

计算机中的顺序存储是指在内存中用一块连续的地址空间依次存放数据元素，用这种方式存储的线性表叫顺序表。其特点是表中相邻的数据元素在内存中存储位置也相邻，如下图：

概念

• 一维数组是最简单、最常用的线性数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
• 数组(Array)是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。
• 每个元素都有下标，下标从0开始
• 一维数组是顺序存储的线性表。二维数组和多维数组的逻辑结构属于非线性结构。
• 连续的内存空间和相同类型的数据是随机访问的前提。

数组的优缺点

• 优点：具有随机访问的特性。
• 缺点：删除、插入数据效率低。

操作数组 - 增删改查

需求：自定义数组工具类，实现增删改查等功能

public class MyArray<E> {

	// 数组最大容量
	private static final int MAX_CAPACITY = Integer.MAX_VALUE-8;
	// 数组默认容量
	private static final int DEFAULT_CAPACITY = 10;
	// 数组
	private Object[] elementData;
	// 数组中当前的数据量
	private int size;

	// 构造方法
	public MyArray() {
		elementData = new Object[DEFAULT_CAPACITY];
	}

	// 构造方法
	public MyArray(int initialCapacity){
		if(initialCapacity > MAX_CAPACITY)
			throw new RuntimeException("initialCapacity过大");
		if(initialCapacity <= 0)
			throw new RuntimeException("initialCapacity必须大于0");
		elementData = new Object[initialCapacity];
	}

	// 在数组尾部添加元素
	public void add(E e){
		if(size >= elementData.length){
			grow();
		}
		elementData[size] = e;
		size++;
	}

	// 数组的扩容
	public void grow(){
		int oldCapacity = elementData.length;
		int newCapacity = oldCapacity*2;
		elementData = Arrays.copyOf(elementData, newCapacity);
	}

	// 在数组的下标位置添加元素
	public void add(int index,E e){

		if(size >= elementData.length){
			grow();
		}

		if(isElementIndex(index)){
			// 数组index之后的元素全部往后移位
			for (int i = index; i < size-1; i++) {
				elementData[i] = elementData[i+1];
			}
			// 给数组第index个元素赋值
			elementData[index] = e;
			size++;
		}else{
			throw new RuntimeException("下标越界");
		}
	}

	// 判断下标是否越界
	public boolean isElementIndex(int index){
		if(index >= 0 && index < elementData.length){
			return true;
		}
		return false;
	}

	// 根据下标位置删除元素
	public Object remove(int index){

		if(isElementIndex(index)){

			Object oldValue = elementData[index];

			int numMoved = size - index - 1;
			if (numMoved > 0)
				System.arraycopy(elementData, index+1, elementData, index,numMoved);
			elementData[--size] = null;

			return oldValue;
		}else{
			throw new RuntimeException("下标越界");
		}
	}

	//根据下标设置元素
	public Object set(int index, E e){
		if(isElementIndex(index)){
			Object oldValue = elementData[index];
			elementData[index] = e;
			return oldValue;
		}else{
			throw new RuntimeException("下标越界");
		}
	}
	
	//根据下标查找元素
	public Object get(int index){
		if(isElementIndex(index)){
			return elementData[index];
		}else{
			throw new RuntimeException("下标越界");
		}
	}

	//获取元素个数
	public int size(){
		return size;
	}

	// 数组的字符串表示
	public String toString(){

		StringBuilder sb = new StringBuilder("[");

		for (int i = 0; i < size; i++) {
			if(sb.length() != 1){
				sb.append(",");
			}
			sb.append(elementData[i]);
		}

		sb.append("]");

		return sb.toString();
	}
}

public class Test {

	public static void main(String[] args) {
		
		MyArray<String> myArray = new MyArray<>();
	
		System.out.println("数组添加元素：");
		myArray.add("张三");
		myArray.add("李四");
		myArray.add("王五");
		myArray.add("赵六");
		myArray.add("吴七");
		System.out.println("获取数组中元素的个数为：" + myArray.size());
		System.out.println("数组中数据为：" + myArray);
		System.out.println("--------------------------------");
		
		//数组修改
		System.out.println("修改指定下标上的元素：");
		myArray.set(1,"abc");
		System.out.println("获取数组中元素的个数为：" + myArray.size());
		System.out.println("数组中数据为：" + myArray);
		System.out.println("--------------------------------");

		//数组删除元素
		System.out.println("删除指定下标上的元素：" + myArray.remove(0));
		System.out.println("获取数组中元素的个数为：" + myArray.size());
		System.out.println("数组中数据为：" + myArray);
		System.out.println("--------------------------------");

		//数组查询元素
		System.out.println("查询指定下标上的元素：" + myArray.get(0));
		System.out.println("获取数组中元素的个数为：" + myArray.size());
		System.out.println("数组中数据为：" + myArray);
		System.out.println("--------------------------------");

	}
}