java手撸数据结构–数组(无序、有序、稀疏)

数组是java语言内置的数据类型，他是一个线性的序列，所以可以快速访问其他的元素，数组和其他语言不同，当你创建了一个数组时，他的容量是不变的，而且生命周期也是不能改变的，还有JAVA数组会做边界检查，如果发现有越界现象，会报RuntimeException异常错误，当然检查边界会以效率为代价。

数组的局限性分析

• 插入快:对于无序数组，即元素没有按照一定顺序排列，只是按照插入的顺序排列。无序数组增加一个元素很简单，只需要在数组末尾添加元素即可，但有序数组却不一定了，它需要在指定的位置插入。
• 查找慢:当然通过下标查找是很快的。但是通常我们都是根据元素值来查找的，给定一个元素值，对于无序数组，我们需要从数组的第一个元素还是遍历，直到找到那个元素。有序数组通过特定算法查找的速度会比无需数组快。
• 删除慢：根据元素值删除，我们要先找到该元素所在位置，然后将元素后端的值整体向前移动一个位置。也需要比较多的时间。
• 数组一旦创建，大小固定:如果初始化一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面的数据个数增加了又添加不进去了。
  　　
  很显然，数组虽然插入快，但是查找和删除比较慢，而且扩展性差，所以我们一般不会用数组来存储数据。

无序数组

无序数组，顾名思义，就是没有顺序的数组，即元素没有按照一定顺序排列，只是按照插入的顺序排列。

创建一个类来实现无序数组

class MyArray{    //存储具体数据的数组    int[] array;    //当前数组存放数据数量    int size;    //构造函数，初始化无序数组    public MyArray(int maxPage) { array = new int[maxPage]; size = 0;    }}

1. 插入

    /**     * 插入     */    public void insert(int value) { if (size < array.length) {      //数组未满，则插入     array[size++] = value; }    }

2. 查找

  /**     * 查找返回下标     */    public int find(int value) { int i; for (i = 0; i < array.length; i++) {     if (array[i] == value) {  break;     } } if (i == size) {     System.out.println("数组中不存在当前数据");     return -1; } else {     return i; }    }

3. 删除

    /**     * 删除     */    public void delete(int value) { int j; if((j=this.find(value))>-1){     for (int i = j; i < size-1; i++) {  array[i]=array[i+1];     }     //删除完把记录-1     size--; }    }

4. 遍历

    /**     * 遍历     */    public void forEach(){ for (int i = 0; i < size; i++) {     System.out.print(array[i]+" "); } System.out.println();    }

5.测试

public static void main(String[] args) { MyArray myArray = new MyArray(10); myArray.insert(12); myArray.insert(5); myArray.insert(1); myArray.forEach(); myArray.delete(5); myArray.forEach();    }

值：

12 5 1 12 1 

有序数组

有序数组优缺点分析

• 优点：
  采用二分查找效率高，比无序数组效率高。
• 缺点：
  插入的时候，要移动元素，比无序数组效率低。

创建一个类来实现有序数组

/** * 有序数组 */class MySequenceArray {    //存储有序数组的集合    private int[] array;    //元素数量    private int size;    public MySequenceArray(int size) { array = new int[size]; size = 0;    }｝

查找

    /**     * 查找返回下标(二分查找)     */    public int find(int value) { if (size == 0) {     return -1; } int index; //当前比对的最大下标 int maxIndex = size - 1; // 当前比对的最小下标 int minIndex = 0; //当前下标 int currentIndex; while (true) {     if (minIndex > maxIndex) {  return -1;     }     currentIndex = (maxIndex + maxIndex) / 2;     if (value == array[currentIndex]) {  return currentIndex;     } else if (value > array[currentIndex]) {  minIndex = currentIndex + 1;     } else {  maxIndex = currentIndex - 1;     } }    }

插入

    /**     * 插入     */    public void insert(int value) { if (array.length > size) {     int index;     for (index = 0; index < size; index++) {  if (value < array[index]) {      //找到了      break;  }     }     if (index < size) {  //数组中存在比value大的数，则index以后的数向后移动一位  for (int i = size; i > index; i--) {      array[i] = array[i - 1];  }  //将value插入index处  array[index] = value;     } else {  //最后找不到比value大的数  array[index] = value;     }     size++; }    }

删除

    /**     * 删除     */    public void delete(int value) { int index; if ((index = find(value)) > -1) {     for (int i = index; i < size - 1; i++) {  array[i] = array[i + 1];     }     size--; }    }

遍历

    /**     * 遍历     */    public void forEach() { for (int i = 0; i < size; i++) {     System.out.print(array[i] + " "); } System.out.println();    }

测试

public static void main(String[] args) { MySequenceArray mySequenceArray = new MySequenceArray(10); mySequenceArray.insert(10); mySequenceArray.insert(1); mySequenceArray.insert(55); mySequenceArray.insert(3); mySequenceArray.forEach(); mySequenceArray.delete(3); mySequenceArray.delete(2); mySequenceArray.forEach();    }

1 3 10 55 1 10 55 

稀疏数组

所谓稀疏数组就是数组中大部分的内容值都未被使用（或都为零），在数组中仅有少部分的空间使用。
因此造成内存空间的浪费，为了节省内存空间，并且不影响数组中原有的内容值，我们可以采用一种压缩的方式来表示稀疏数组的内容。

稀疏数组实现方式

如下：

• 方式一：二维数组存储，用空间换取时间，占用空间大，查询效率高

int[][] array = new int[7][9];  //占用63 array[1][1] = 3; array[3][0] = 1; array[3][1] = 4; array[4][2] = 7; array[5][5] = 5;

遍历

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

遍历值如下：

0  0  0  0  0  0  0  0  0  0  3  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  4  0  0  0  0  0  0  0  0  0  7  0  0  0  0  0  0  0  0  0  0  0  5  0  0  0  0  0  0  0  0  0  0  0  0  

• 方式二：使用压缩方式，执行效率较低，占用空间小

创建一个类来实现稀疏数组

/** * 稀疏数组实现 */class MySparseArray{    //稀疏数组的行数    private int row;    //稀疏数组的列数    private int col;    //稀疏数组当前行当前列的值    private int val;    //通过构造函数实例化    public MySparseArray(int row, int col, int val) { this.row = row; this.col = col; this.val = val;    }    public int getRow() { return row;    }    public int getCol() { return col;    }    public int getVal() { return val;    }}

稀疏数组的使用

//定义五个节点的稀疏数组，这里的6不包含第一行记录 MySparseArray[] mySparseArrays = new MySparseArray[6]; //第一行为记录行数、列数、节点数，下标为0 //7行、9列 mySparseArrays[0] = new MySparseArray(7, 9, 6); mySparseArrays[1] = new MySparseArray(1, 1, 3); mySparseArrays[2] = new MySparseArray(3, 0, 1); mySparseArrays[3] = new MySparseArray(3, 1, 4); mySparseArrays[4] = new MySparseArray(4, 2, 7); mySparseArrays[5] = new MySparseArray(5, 5, 5); // 遍历 for (int i = 0; i < mySparseArrays[0].getRow(); i++) {     for (int j = 0; j < mySparseArrays[0].getCol(); j++) {  int k;//这个字段用来记录有值的下标  //第一行记录为0，要跳过第一行  for (k = 1; k < mySparseArrays.length; k++) {      if (mySparseArrays[k].getRow() == i && mySparseArrays[k].getCol() == j) {   break;      }  }  if (k < mySparseArrays.length) {      System.out.print(mySparseArrays[k].getVal() + " ");  } else {      System.out.print(0 + " ");  }     }     //换行     System.out.println(); }

值为：

0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 4 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 

jcg路由器知识网