我理解的数据结构（一）—— 数组(Array)

首先，我是一个phper，但是毕竟php是一个脚本语言，如果使用脚本语言去理解数据结构具有一定的局限性。因为脚本语言是不需要编译的，如果你的语法写的不错，可能执行起来会要比用一个更好的数据结构来的更快、更高效（在数据量不大的情况下）。而且数据结构是脱离任何一门语言存在的。所以，下面会选用java去更深入的理解数据结构。

注：这里不会去过多的解释java的语法。

一、定义一个数组的两种方式

int[] arr = new int[10];
int[] arr = new int[] {10, 20, 30};

二、数组基础

数组的容量在数组一开始定义的时候就固定了。
数组最大的优点：根据索引快速查询。如：arr[2]。
数组最好应用于“索引有语意”的情况下。
但并非所有有语意的索引都适用于数组：比如索引是一个人的身份证号，会开辟过大的空间，不现实。
下面会讨论数组“索引没有语意”的情况，基于java数组，二次封装属于我们自己的数组类，更深入的理解数组。

三、创建一个最基本的数组类

学习任何一个数据结构，CRUD必不可少。下面，让我们来一起一步步完善属于我们自己的数组的增、删、改、查

```
public class Array {

// 数组的实际大小

private int size;

// 数组

private int[] data;

// 构造函数，根据传入的容纳量定义一个int类型的数组

public Array(int capacity) {

    data = new int[capacity];

    size = 0;

}

// 重载，没有传入容纳量，定义一个长度为10的int类型数组

public Array() {

    this(10);

}

// 数组的实际大小

public int getSize() {

    return size;

}

// 数组的容纳量

public int getCapacity() {

    return data.length;

}

// 数组是否为空

public boolean isEmpty() {

    return size == 0;

}

}



<h3>四、增</h3>

//往数组的任意位置插入

public void add(int index, int ele) {

// 数组已满

if (size == data.length) {

    throw new IllegalArgumentException("add failed. arr is full");

}

// 插入的索引位不合法

if (index &lt; 0 || index &gt;= size) {

    throw new IllegalArgumentException("add failed. index &lt; 0 or index &gt;= size");

}

// 从index向后的所有元素均向后赋值

for (int i = size - 1; i &gt;= index; i--) {

    data[i + 1] = data[i];

}

data[index] = ele;

size++;

}

// 第一个位置插入

public void addFirst(int ele) {

add(0, ele);

}

// 最后一个位置插入

public void addLast(int ele) {

add(size, ele);

}



<h3>五、查和改</h3>

// 查询index索引位置的元素

public int get(int index) {

if (index < 0 || index >= size) {

throw new IllegalArgumentException("get failed. index is illegal");

}

return data[index];

}

// 查询ele元素的索引，不存在返回-1

public int find(int ele) {

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

if (data[i] == ele) {

return i;

}

}

return -1;

}

// 更新Index的元素

public void set(int index, int ele) {

if (index < 0 || index >= size) {

throw new IllegalArgumentException("get failed. index is illegal");

}

data[index] = ele;

}



<h3>六、删</h3>

// 根据索引删除数组中的第一个ele，返回ele

public int remove(int index) {

if (index < 0 || index >= size) {

throw new IllegalArgumentException("remove failed. index is illegal");

}

for (int i = index + 1; i &lt; size; i++) {

    data[i - 1] = data[i];

}

size--;

return data[index];

}

// 删除第一个元素

public int removeFirst() {

return remove(0);

}

// 删除最后一个

public int removeLast() {

return remove(size - 1);

}

// 删除指定元素

public void removeElement(int ele) {

int index = find(ele);

if (index != -1) {

remove(index);

}

}



<h3>七、包含和重写toString</h3>

Override

public String toString() {

StringBuffer res = new StringBuffer();

res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));

res.append("[");

for (int i = 0; i &lt; size; i++) {

    res.append(data[i]);

    if (i != size - 1) {

        res.append(", ");

    }

}

res.append("]");

return res.toString();

}

// 查询数组中是否包含元素ele

public boolean contain(int ele) {

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

if (data[i] == ele) {

return true;

}

}

return false;

}



<p><strong>注：</strong>通过以上方法我们已经创建了一个<strong>最最最最最</strong>基本的数组类（见下图）。当然，你也可以去添加一些自己需要的方法，例如：<code>removeAll</code>、<code>findAll</code>之类的。<br></p>

![](https://img2018.cnblogs.com/blog/1504257/201811/1504257-20181117174850402-826338619.png)

<blockquote>但是，我们现在的数组只支持int类型，太过局限。接下来，我们去给我们的数组升华一哈~</blockquote>

<h3>八、使用泛型让我们的数组支持“任意”数据类型</h3>

<blockquote>首先，为什么我要在<strong>任意</strong>这两个字加上引号，因为java的泛型不支持基本数据类型，只能是类的对象。<br>但是，这并不代表如果我们使用了泛型，就不可以使用基本数据类型了，因为每一个基本数据类型都有一个对应的<strong>包装类</strong>。<br>使用泛型的时候，我们只需要传入对应的包装类即可。</blockquote>

<h4>java的基本数据类型</h4>

<table>

<thead><tr>

<th align="center">基本数据类型</th>

<th align="center">包装类</th>

</tr></thead>

<tbody>

<tr>

<td align="center">boolean</td>

<td align="center">Boolean</td>

</tr>

<tr>

<td align="center">byte</td>

<td align="center">Byte</td>

</tr>

<tr>

<td align="center">char</td>

<td align="center">Char</td>

</tr>

<tr>

<td align="center">short</td>

<td align="center">Short</td>

</tr>

<tr>

<td align="center">int</td>

<td align="center">Int</td>

</tr>

<tr>

<td align="center">long</td>

<td align="center">Long</td>

</tr>

<tr>

<td align="center">float</td>

<td align="center">Float</td>

</tr>

<tr>

<td align="center">double</td>

<td align="center">Double</td>

</tr>

</tbody>

</table>

<h4>所以，我们的代码只需要进行极小的改动即可：</h4>

public class ArrayNew&lt;E&gt; {

// 数组的实际大小

private int size;

// 数组

private E[] data;

// 构造函数，根据传入的容纳量定义一个 E 类型的数组

public ArrayNew(int capacity) {

    // 强转

    data = (E[]) new Object[capacity];

    size = 0;

}

// 重载，没有传入容纳量，定义一个长度为10的int类型数组

public ArrayNew() {

    this(10);

}

// 数组的实际大小

public int getSize() {

    return size;

}

// 数组的容纳量

public int getCapacity() {

    return data.length;

}

// 数组是否为空

public boolean isEmpty() {

    return size == 0;

}

// 往数组的任意位置插入

public void add(int index, E ele) {

    // 数组已满

    if (size == data.length) {

        throw new IllegalArgumentException("add failed. arr is full");

    }

    // 插入的索引位不合法

    if (index &lt; 0 || index &gt; size) {

        throw new IllegalArgumentException("add failed. index &lt; 0 or index &gt; size");

    }

    // 从index向后的所有元素均向后赋值

    for (int i = size - 1; i &gt;= index; i--) {

        data[i + 1] = data[i];

    }

    data[index] = ele;

    size++;

}

// 第一个位置插入

public void addFirst(E ele) {

    add(0, ele);

}

// 最后一个位置插入

public void addLast(E ele) {

    add(size, ele);

}

// 查询index索引位置的元素

public E get(int index) {

    if (index &lt; 0 || index &gt;= size) {

        throw new IllegalArgumentException("get failed. index is illegal");

    }

    return data[index];

}

// 查询ele元素的索引，不存在返回-1

public int find(E ele) {

    for (int i = 0; i &lt; size; i++) {

        if (data[i].equals(ele)) {

            return i;

        }

    }

    return  -1;

}

// 更新Index的元素

public void set(int index, E ele) {

    if (index &lt; 0 || index &gt;= size) {

        throw new IllegalArgumentException("get failed. index is illegal");

    }

    data[index] = ele;

}

// 根据索引删除数组中的第一个ele，返回ele

public E remove(int index) {

    if (index &lt; 0 || index &gt;= size) {

        throw new IllegalArgumentException("remove failed. index is illegal");

    }

    E result = data[index];

    for (int i = index + 1; i &lt; size; i++) {

        data[i - 1] = (data[i]);

    }

    // 空间释放，垃圾回收会自动回收

    data[--size] = null;

    return result;

}

// 删除第一个元素

public E removeFirst() {

    return remove(0);

}

// 删除最后一个

public E removeLast() {

    return remove(size - 1);

}

// 删除指定元素

public void removeElement(E ele) {

    int index = find(ele);

    if (index != -1) {

        remove(index);

    }

}

// 查询数组中是否包含元素ele

public boolean contain(E ele) {

    for (int i = 0; i &lt; size; i++) {

        if (data[i].equals(ele)) {

            return true;

        }

    }

    return  false;

}

@Override

public String toString() {

    StringBuffer res = new StringBuffer();

    res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));

    res.append("[");

    for (int i = 0; i &lt; size; i++) {

        res.append(data[i]);

        if (i != size - 1) {

            res.append(", ");

        }

    }

    res.append("]");

    return res.toString();

}

}



<p><strong>注：</strong>创建数组时，只需<code>ArrayNew&lt;Student&gt; arr = new ArrayNew&lt;&gt;(20);</code>即可。</p>

<h3>九、动态数组</h3>

<blockquote>

<strong>原理：</strong>其实，动态数组的原理非常简单，如果我们希望我们的数组具有可伸缩性，只需要我们在添加或者删除元素时判断<code>size</code>是否到达临界。然后去创建一个新<code>capacity</code>的数组，然后把旧数组的引用指向新数组即可。<br>所以，我们上述代码的改变极小，只需要改变<code>add</code>、<code>remove</code>即可。然后添加一个<code>resize</code>方法。</blockquote>

// 往数组的任意位置插入

public void add(int index, E ele) {

// 插入的索引位不合法

if (index < 0 || index > size) {

throw new IllegalArgumentException("add failed. index < 0 or index > size");

}

// 如果size == data.length，数组长度已满

if (size == data.length) {

    resize(data.length * 2);

}

// 从index向后的所有元素均向后赋值

for (int i = size - 1; i &gt;= index; i--) {

    data[i + 1] = data[i];

}

data[index] = ele;

size++;

}

// 根据索引删除数组中的第一个ele，返回ele

public E remove(int index) {

if (index < 0 || index >= size) {

throw new IllegalArgumentException("remove failed. index is illegal");

}

E result = data[index];

for (int i = index + 1; i &lt; size; i++) {

    data[i - 1] = (data[i]);

}

// 空间释放，垃圾回收会自动回收

data[--size] = null;

// 减小数组长度，不要浪费空间

if (size == data.length / 2 &amp;&amp; size != 0) {

    resize(size);

}

return result;

}

// 自动伸缩数组

private void resize(int newCapacity) {

E[] newData = (E[])new Object[newCapacity];

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

newData[i] = data[i];

}

data = newData;

}



<h3>十、简单复杂度分析我们封装的数组</h3>

<blockquote>通过上面的分析和代码实现，我们封装了一个自己的数组，并且实现了一些数组<strong>最基本</strong>的功能，包括支持增、删、改、查、支持任意数据类型以及动态数组。那么我们就来分析一下我们自己封装数组的复杂度。</blockquote>

<table>

<thead><tr>

<th align="center">操作</th>

<th align="center">复杂度</th>

</tr></thead>

<tbody>

<tr>

<td align="center">增</td>

<td align="center">O(n)</td>

</tr>

<tr>

<td align="center">删</td>

<td align="center">O(n)</td>

</tr>

<tr>

<td align="center">改</td>

<td align="center">已知索引O(1);未知索引O(n)</td>

</tr>

<tr>

<td align="center">查</td>

<td align="center">已知索引O(1);未知索引O(n)</td>

</tr>

</tbody>

</table>

<p><strong>但是：</strong>在我们的数组中，增和删我们都调用了<code>resize</code>方法，如果<code>size &lt; data.length</code>，其实我们执行<code>addLast</code>复杂度只是<code>O(1)</code>而已（<code>removeLast</code>同理）。所以，我们应该怎么去分析<code>resize</code>方法所带来的复杂度呢？</p>

<h3>十一、均摊复杂度和防止复杂度的震荡</h3>

<h4>（1）均摊复杂度</h4>

<blockquote>让我们拿 <strong>增</strong> 来举例</blockquote>

<table>

<thead><tr>

<th align="center">方法</th>

<th align="center">复杂度</th>

</tr></thead>

<tbody>

<tr>

<td align="center">addLast(ele)</td>

<td align="center">O(1)</td>

</tr>

<tr>

<td align="center">addFirst(ele)</td>

<td align="center">O(n)</td>

</tr>

<tr>

<td align="center">add(index, ele)</td>

<td align="center">O(n/2) = O(n)</td>

</tr>

<tr>

<td align="center">resize(newCapacity)</td>

<td align="center">O(n)</td>

</tr>

</tbody>

</table>

<p>其实，在执行<code>addLast</code>的时候，我们并不是每次都会触发<code>resize</code>方法，更多的时候，复杂度只是<code>O(1)</code>而已。<br><strong>比方说：</strong><br>当前的<code>capacity = 8</code>，并且每一次添加操作都使用<code>addLast</code>，第9次<code>addLast</code>操作，触发<code>resize</code>，总共17次基本操作（<code>resize</code>方法会进行8次操作，<code>addLast</code>方法进行9次操作）。平均，每次<code>addLast</code>操作，进行2次基本操作（17 / 9 ≈ 2）。<br><strong>假设：</strong><br><code>capacity = n</code>， <code>n + 1</code>次<code>addLast</code>，触发<code>resize</code>，总共进行了<code>2n + 1</code>次操作，平均每次<code>addLast</code>操作，进行了2次基本操作。</p>

<p><strong>这样均摊计算，时间复杂度是O(1)！</strong></p>

<h4>（2）防止复杂度的震荡</h4>

<blockquote>让我们来假设这样一种情况：<br>当<code>size == data.length</code>时，我们执行了<code>addLast</code>方法添加一个元素，这个时候我们需要去执行<code>resize</code>方法，此时，<code>addLast</code>的复杂度为<code>O(n)</code>。<br>然后，我去<code>removeLast</code>，此时的<code>removeLast</code>复杂度也是<code>O(n)</code>。<br>再然后，我再去执行<code>addLast</code>。<br>.<br>.<br>.</blockquote>

<p>有没有发现，在这样一种极端情况下，<code>addLast</code>和<code>removeLast</code>的复杂度变成了<code>O(n)</code>，其实，这个就是<strong>复杂度的震荡</strong>。</p>

<ul>

<li>

<p>为什么我们会产生这种震荡？</p>

<ul><li>

<code>add</code>情况下，我们去扩容数组无可厚非。但是<code>remove</code>情况下，我们立刻去缩容数组就有点不合适了。</li></ul>

</li>

<li>

<p>怎么去解决这种情况？</p>

<ul>

<li>因为我们之前采取的措施是<code>Eager</code>

</li>

<li>所以，我们采取一种<code>Lazy</code>的方式：当<code>size == data.length / 2</code>，我们不要立刻缩容，当<code>size == data.length / 4</code>时，我们才去缩容，就可以很好的解决这种震荡。</li>

</ul>

</li>

</ul>

<blockquote>具体代码如下，其实只是对<code>remove</code>进行了极小的改变</blockquote>

public E remove(int index) {

if (index &lt; 0 || index &gt;= size) {

    throw new IllegalArgumentException("remove failed. index is illegal");

}

E result = data[index];

for (int i = index + 1; i &lt; size; i++) {

    data[i - 1] = data[i];

}

// 空间释放，垃圾回收会自动回收

data[--size] = null;

// 减小数组长度，不要浪费空间，防止震荡

if (size == data.length / 4 &amp;&amp; data.length / 2 != 0) {

    resize(data.length / 2);

}

return result;

}



原文地址：https://segmentfault.com/a/1190000016064569

巴特西

我理解的数据结构（一）—— 数组(Array)

我理解的数据结构（一）—— 数组(Array)

一、定义一个数组的两种方式

二、数组基础

三、创建一个最基本的数组类

最新文章

热门文章