乐趣区

数据结构-数组

jiezi

为什么要学习数据结构？

因为计算机专业必学，数据结构就是研究数据如何在计算机进行组织和存储，使我们高效的操作数据。今天聊一聊线性结构中的数组。

总体来说可划分为以下三种

线性结构：数组，栈，队列，链表，哈希表
树结构：二叉树，二分搜索树，AVL，红黑树，堆，K- D 树，哈夫曼树，Trie 等等
图结构：邻接矩阵，邻接表

数组的数据结构

索引：数组是通过索引来操作数据的，索引从 0 开始
数组名：通过数组名[索引] 可以操作索引对应的数据，scores[2]

动态数组实践

首先一个数据结构，离不开数据的增删改查，那么就自己创建一个类，内部维护一个数组，来模拟这个过程。后面还可以像集合一样，优化使用泛型特性和动态扩容等机制。

1. 创建类，创建成员 arr，用来存放元素。创建 size 用来维护数组内现有的元素个数。
比如数组长度是 10，但是只存了 5 个元素，那么 size 就是 5 

public class MyArray {
    // 声明一个数组
    private int[] arr;

    // 数组中存在的元素个数（不是 length，length 是数组的长度，也可以说是容量（capacity））private int size;

    // 因为数组提供了 length 方法，所以不需要创建和维护数组长度的变量
    //private int length;

    public MyArray() {this(10);// 不传参数，数组长度默认就是 10
    }

    public MyArray(int capacity) {arr = new int[capacity];//// 初始化数组
        size = 0;// 刚开始数组中没有数据
}

2. 创建好了之后，提供一些方法吧，先编写一些基本的方法，比如数组的容量，数组已存在的元素个数，数组是否为空等。这些方法都比较基础，所以也不需要过多解释了。

// 返回数组中存在的元素个数
public int getSize() {return this.size;}

// 获取容量
public int getCapacity() {return arr.length;}

// 判断数组是否为空
public boolean isEmpty() {return this.size == 0;}

// 查看数组中是否包含指定元素
public boolean contains(int e)
{for(int x = 0; x < size; x++) {if(arr[x] == e) {return true;}
    }
    return false;
}

// 查找指定元素在数组中的位置，如果没有，返回 -1
public int find(int e)
{for(int x = 0; x < size; x++) {if(arr[x] == e) {return x;}
    }
    return -1;
}

3. 添加元素，首先是添加元素到末尾。因为 size 就是目前数组内元素的个数，也就是需要添加到末尾索引的位置。如下图所示，要想添加元素到末尾，那么获取 size 的位置，添加就可以了，添加过后，维护一下 size 的数量。哦，对，记得方法的开始判断一下元素的边界，增加程序的健壮性。

// 添加元素到数组末尾
public void addLast(int e)
{if(size == arr.length) {throw new IllegalArgumentException("Add last failed.Array is Full");
    }
    arr[size] = e;
    size++;
}

如果想在指定索引处添加一个元素呢？除了添加以外，还要维护其他的数据。比如下图所示，原来数组是 66 88 99 100，现在要插入元素为“77”到索引 1 的位置，那么就要把索引 1 以后的元素，全部向右移动一格，给 ”77″ 腾出个地方，然后在插入，就解决问题了。（注意不可以跳跃插入，最大使用索引不能超过 size 所在的索引）

// 通过索引添加元素
public void addByIndex(int index,int e)
{
    // 插入的元素的索引只能在 0 和 size 期间
    if(index < 0 || index > size) {throw new ArrayIndexOutOfBoundsException("Add failed.Require index >=0 & <= size");
    }
    // 添加一个元素，size 就加一，等 size 个数等于数组长度时，抛异常
    if(size == arr.length) {throw new IllegalArgumentException("Add last failed.Array is Full");
    }
    // 改变原始数据的位置，从 size- 1 的位置到 index 的位置
    for(int i = size - 1; i >= index; i--)
    {arr[i + 1] = arr[i];
    }
    // 插入新的元素
    arr[index] = e;
    size++;
}

那添加一个元素到头部也就很 easy 了，因为原理和上面一样，需要把头部往后的所有元素都向右移动一格，然后在插入。仔细一看，向尾部和头部插入元素都可以复用上面的代码。

// 添加元素到数组末尾
public void addLast(int e)
{addByIndex(size,e);
}

// 添加元素到数组开头
public void addFirst(int e)
{addByIndex(0,e);
}

4. 删除元素，删除元素和添加其实差不多，添加是要把从添加位置的索引到最后的元素索引的所有数据做一个向右移动，删除是把从添加位置的索引到最后的元素索引的所有元素做一个向左移动。


public int removeByIndex(int index)
{if(index < 0 || index >= size) {throw new ArrayIndexOutOfBoundsException("Remove failed.Require index >=0 & <= size");
    }
    int temp = arr[index];
    for(int x = index; x < size; x++)
    {arr[x] = arr[x + 1];
    }
    size--;
    return temp;
}

public int removeFirst()
{return removeByIndex(0);
}
public int removeLast()
{return removeByIndex(size-1);
}


// 按照元素删除
public boolean removeElement(int e)
{int result = find(e);// 先找对应的元素
    if(result != -1)// 如果有这个元素，则删除
    {removeByIndex(result);// 删除这个元素
        return true;
    }
    else
    {return false;}
}

5. 重写 toString，方便使用 System.out.print 的时候显示数据的容量变化以及元素变化

// 展示数组元素的方法
@Override
public String toString() {StringBuilder sb = new StringBuilder();
    sb.append(String.format("Array size = %d,capacity=%d\n",size,arr.length));
    sb.append("[");
    for(int x = 0; x < size; x++)
    {sb.append(arr[x]);
        if(x != size - 1)
        {sb.append(",");
        }
    }
    sb.append("]");
    return sb.toString();}

6. 可以自己定义个 main 方法测试一下，都没啥问题。

public static void main(String[] args)
{MyArray arr = new MyArray(20);
    for(int x = 1000; x < 1010; x++)
    {arr.addLast(x);
    }
    System.out.println(arr);
}
Array size = 10,capacity=20
[1000,1001,1002,1003,1004,1005,1006,1007,1008,1009]

7. 泛型
但是这个代码目前是有弊端的，能不能像 Java 中集合那样，可以往数组里面添加任意类型的数据呢？可不可以等到数组容量不够的时候，自动帮我扩容呢？首先先解决一下 ” 泛型 ” 问题，这个问题比较简单，把类改成泛型类就可以啦，增加元素的方法都改成泛型，返回的元素也修改成泛型。

// 这样
public class MyArray<E> {
    // 声明一个数组
    private E[] arr;
// 这样
public MyArray(int capacity) {arr = (E[])new Object[capacity];//// 初始化数组
// 还有这样
public E removeByIndex(int index)
public boolean removeElement(E e)

8. 扩容操作

假如数组是这些元素，那么当 size = capacity 的时候，也就是插入的元素数量等于数组长度，俗话说就是数组满了，那么这时候开始扩容。

扩容的原理其实就是再申请一个比当前这个数组还要大的一个数组（至于大多少呢？你可以自己定义。ArrayList 扩容机制是大原数组的 1.5 倍，当然这个值没有对和错，你自己根据业务场景定就好。但尽量做一个权衡，太大了浪费空间，太小了会经常扩容，导致程序变慢。）然后一次性的把原数组的数据放到新数组，在改变一下变量对数组的引用，让变量指向新数组，这个扩容操作在方法内，方法执行完就弹栈了，也就没有变量在指向原数组了，原数组也就会被垃圾回收了。

扩容内存图解

扩容方法实现

// 数组扩容方法
private void resize(int length) {E[] newArr = (E[])new Object[length];// 声明新的数组
    for(int x = 0; x < size; x++)// 将原数组所有的数据复制到新数组中
    {newArr[x] = arr[x];
    }
    arr = newArr;// 改变引用，变量指向新数组
}

addByIndex 方法的变动，当元素占满数组时，进行扩容

// 元素添加的时候，满了不再抛异常了，进行扩容扩容机制
if(size == arr.length) {resize(arr.length * 2);
    //throw new IllegalArgumentException("Add last failed.Array is Full");
}

如果元素变少时，数组太大，也会浪费空间，可以进行缩容
removeByIndex 方法的变动

// 如果元素个数只占到整体数组长度的一半以下，为了避免浪费内存空间，进行缩容
if(size < arr.length / 2)
{resize(arr.length / 2);
}

明天记录该数组实现的时间复杂度，以及均摊复杂度问题和防止复杂度震荡问题。

退出移动版