Java数据结构(1)——数组
数据结构：数据结构是计算机存储，组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合(源自百科)。
个人对数据结构的理解是根据某种需要有规则的去存储组织数据。数据结构这个词语关键在于"结构"。
如果没有需要，数据随便存啊，根本不用考虑读取，查找数据的效率问题，那数据想怎么存放就怎么存放，何必花心思去设计存放方式呢？
Java中常见的数据结构有如下几种：
数组 栈 堆 队列 链表 树 哈希表 图
Java中的set，list等可以理解为数据结构的体现或者使用，不能简单的认为set list就是数据结构。
这几种数据结构的优劣先不介绍，等到最后我们可以进行总结。
数据结构和算法是分不开的。算法的解释是：解决问题的步骤。
同一个问题，选择不同的数据结构，处理问题的难易程度是不一样的。
算法有如下几个特点：
<1>有穷性：算法应该是在若干步骤之后终止或者结束，如果一个算法没有尽头，那么这个问题能算是解决了么？
<2>确切性：算法的每个步骤都应该具有一定的目的性，其步骤要有相对明确的含义。
<3>输入项：算法需要输入，如果是0个输入，可能就表示算法本身定义了初始条件。
<4>输出项：至少一个输出，如果一个算法没有输出就没多大意义。
<5>可行性：算法的每个步骤都会在有限时间范围内完成（这是百科的解释）。个人对算法可行性的理解是，在当前条件下，算法是可以执行并且在一定时间
范围内会结束。如果设计的一个算法，当前的技术条件或者设备不足以支撑，那么设计的这个算法对当下是没有意义的。
数组中只能存放已经声明的类型的数据，而且数组的大小在声明时候已经确定，不能在程序中动态改变数组的大小。
我们可以分析出数组的一些特点：
<1>数组是一个对象，不是基本数据类型，所以数组对象是保存在堆内存中的。
<2>数组中存放的可以是基本数据类型也可以是对象实例。那么数组中是不是能能保存数组呢？答案是肯定的。
数组中保存数组是什么样的数据形式？不就是多维数组么。
所以数组中只有一维数组，没有二维，三维这种数据结构，因为一维数组就可以实现多维，为什么还要设计多维数组这种数据结构呢？
我们看下实例代码和内存示意图：
Object[] aa = new Object[4];
aa[0] = new int[]{1,2,3,4};
aa[1] = new int[]{5,6,7,8};
aa[2] = new int[]{9,10,11,12};
aa[3] = new int[]{13,14,15,16};
内存中示意图：
这种声明如下声明是同样效果：
Object [][] bb = new Object[4][5];//new Object[一维数组的数量，可以理解为多少行][一维数组的长度，可以理解为多少列]
int num = 1;
for (int i=0; i < bb.length; i ++) {//多少行
for (int j = 0; j < bb[i].length; j ++) {//每行的长度
bb[i][j] = num;
num++;
}
}
或者声明时候就初始化：
int[][] bb = {{1,2},{3},{4,5,6},{7,8,9,10}};
<3>数组声明时候内存是连续的一块。我们知道声明数组时候大小必须确定，我们假设数据大小在声明时候不用确定大小，那么我们要追加一个元素时候，除了这个元素实际的值，是不是还要补充一个指向————让最后一个元素指向追加元素，同时原来的数组代表原来元素的内存地址，追加了元素，原来数组的指向也应该做出改变。
老鸭子生了6个小鸭子，名字都起好了，老大老二...老六，现在你突然给老鸭子一只鸭子，那么老鸭子需要知道自己多了个老七，同时让老六知道自己后面还有个老七。
数组通过角标来读取元素，也没有保存每个元素的内存地址，所以变向说明数组内存是连续的。
<4>数组中查找和删除元素是比较慢的。
数组中追加元素：
对于无序数组的插入，直接在数组末尾追加就行了；如果是有序数组，需要查询到插入元素的位置，然后将插入位置之后的元素后移；
数组中读取和删除元素：
如果按照下标读取元素当然很快，但很多时候我们是按照元素值来读取的。
对于无序数组，读取只能一个个比较，删除的话，也只能先找到指定位置，然后将后面的元素前移；
对于有序数组，读取也是依次比较（当然我们可以通过算法加快速度，如二分查找/插入），删除的话，也要将对应元素前移；
下面是数组关于插入，删除，查找的一些操作，我们尝试用类来对数组做一个封装：
package com.sai.pub.utils;
public class SaiArray {
private final MyArray array;
public SaiArray() {
this(0);
}
public SaiArray(int size) {
if (size <= 0) {
this.array = null;
} else {
this.array = new MyArray(new int[size]);
}
}
/**
* 查找某个元素在数组中的位置
* @param value 要查找元素
* @return 元素在数组中的位置
*/
public int findElement(int value) {
if (this.array != null) {
return this.array.findElement(value);
}
return -1;
}
/**
* 获取数组指定位置上的元素
* @param index 数组下标
* @return 数组指定位置上的元素
*/
public int getElement(int index) {
if (this.array != null) {
return this.array.getElement(index);
}
return -1;
}
/**
* 删除指定位置上的元素
* @param
* index 数组下标
* @return
* false失败,true成功
*/
public boolean deleteElementByIx(int index) {
if (this.array != null) {
return this.array.deleteElementByIx(index);
}
return false;
}
/**
* 删除数组上的某个元素值
* @param value 要删除元素
* @return 是否删除成功
*/
public boolean deleteElementByVe(int value) {
if (this.array != null) {
return this.array.deleteElementByVe(value);
}
return false;
}
/**
* 向数组中添加某个元素
* @param value 要添加的元素
* @return 是否添加成功
*/
public boolean addElement(int value) {
if (this.array != null) {
return this.array.addElement(value);
}
return false;
}
/**
* 向数组指定位置插入一个元素
* @param index 要插入元素的位置
* @param value 要插入的元素
* @return 是否插入成功
*/
public boolean addElement(int index, int value) {
if (this.array != null) {
return this.array.addElement(index, value);
}
return false;
}
/**
* 获取数组的实际长度
* @return
*/
public int getRealLength() {
if (this.array != null) {
return this.array.getRealLength();
}
return -1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
if (this.array == null || this.getRealLength() == 0) {
sb.append("数组为null或者数组还未添加元素.");
} else {
for (int i = 0; i <array.realLength; i++) {
sb.append(this.getElement(i));
sb.append(",");
}
sb.deleteCharAt(sb.length()-1);
}
return sb.toString();
}
private class MyArray{
private final int[] array;
private final int length;//数组长度
private int realLength; //数组实际长度，也就是插入了多少元素
public MyArray(int[] array) {
this.array = array;
length = array.length;
realLength = 0;
}
//查找元素下表,不存在则返回-1
public int findElement(int value) {
for (int i = 0; i < realLength; i++) {
if (value == this.array[i]) {
return i;
}
}
return -1;
}
//获取指定位置上的元素
public int getElement(int index) {
if (index >=0 && index < realLength) {
return array[index];
}
return -1;
}
//删除指定下标上的元素
public boolean deleteElementByIx(int index) {
return moveArrayByDel(index);
}
//删除元素中的某个元素
public boolean deleteElementByVe(int value) {
int index = this.findElement(value);
if (index < 0) {
return false;
}
return deleteElementByIx(index);
}
//添加元素
public boolean addElement(int value) {
if (realLength == length) {
return false;
}
array[realLength] = value;
realLength++;
return true;
}
//往数组指定位置插入一个元素
public boolean addElement(int index, int value) {
if (realLength == length) {//数组满了
return false;
}
return moveArrayByAdd(index, value);
}
//获取数组的实际长度
public int getRealLength() {
return realLength;
}
private boolean moveArrayByDel(int index) {
if (index < 0 || index >= length) {
return false;//越界
}
if (index >= realLength) {
return false;
}
if (index == realLength-1) {//最后一个元素
array[realLength] = 0;//为什么置0?思考创建类对象时候对象属性的初始化值是多少
realLength--;
return true;
}
for (int i = index; i < realLength-1; i++) {
array[i] = array[i+1];//指定下标后面的元素前移
}
realLength--;
return true;
}
private boolean moveArrayByAdd(int index, int value) {
if (index < 0 || index >= length) {
return false; //越界
}
if (index >= realLength-1) {
array[realLength] = value;
realLength++;
return true;
}
for (int i = realLength; i > index; i--) {
array[i] = array[i-1];
}
array[index] = value;
realLength++;
return true;
}
}
}
ps：可能封装的不太好，但是如果要练习，自己想怎么写就怎么写，各种方法都写了，在比较下，就知道怎么写最好了，不用怕调试出错，你又不上线，怕什么。