数据结构与算法之美-线性表(数组)

作者: 魏鹏飞 | 来源:发表于2019-10-08 16:50 被阅读0次

为什么数组要从0开始编号，而不是从1开始呢？

如何实现随机访问？

面试时，常常会问到数组和链表的区别，很多人回答说：“链表适合插入、删除，时间复杂度 $O(1)$ ；数组适合查找，查找时间复杂度为 $O(1)$ ”。

实际上，这种表述是不正确的。正确的表述是，数组支持随机访问，根据下标随机访问的时间复杂度为 $O(1)$ 。

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组的两个核心概念：

第一是线性表（Linear List）。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

image

而与它对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。

image

第二是连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利有弊，删除和插入操作，比较低效，需要做大量的数据搬移工作。

image

当计算机需要随机访问数组中某个元素时，它会首先通过下面的寻址方式，计算出该元素存储的内存地址：

a[i]_address = base_address + i * data_type_size

低效的“插入”和“删除”

如果在数组末尾插入元素，那就不需要移动数据了，这时时间复杂度为 $O(1)$ 。但如果在数组开头插入数据元素，那所有的数据都需要依次往后移动一位，所以最坏时间复杂度是 $O(n)$ 。

如果是无序数组插入，为了避免大规模的数据搬移，我们可以把第k位的数据搬移到数组元素最后，把新的元素直接放入第k个位置。

image

删除操作跟插入数据类似，如果我们要删除第k个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

和插入类似，如果删除数组末尾的数据，则最好情况时间复杂度为 $O(1)$ ；如果删除开头的数据，则最坏情况时间复杂度为 $O(n)$ ；平均情况时间复杂度也为 $O(n)$ 。

实际上，在某些特殊场景下，并非一定追求数组中数据的连续性。如果将多次删除操作几种在一起执行，删除的效率是不是会提高很多呢？

image

为了避免d, e, f, g, h这几个数据会被搬移三次，我们可以先记录下已删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正地删除操作，这样就大大减少了删除操作导致的数据搬移。

如果你了解JVM，你会发现，这不就是JVM标记清除垃圾回收算法的核心思想吗？没错，数据结构和算法的魅力就在于此。

警惕数组的访问越界问题

int main(int argc, char* argv[]){
    int i = 0;
    int arr[3] = {0};
    for(; i<=3; i++){
        arr[i] = 0;
        printf("hello world\n");
    }
    return 0;
}

我们来分析一下这段C语言代码执行结果：这段代码的运行结果并非是打印三行“hello world”，而是会无限打印“hello world”，这是为什么呢？

因为，数组大小3，a[0], a[1], a[2]，而我们的代码因为书写错误，导致for循环的结束条件错写为了i<=3而非i < 3，所以当i = 3时，数组a[3]访问越界。

我们知道，在C语言中，只要不是访问受限的内存，所有的内存空间都是可以自由访问的。根据前面讲的寻址公式，a[3]也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量i的内存地址，那么a[3]=0就相当于i=0，所以就会导致代码无限循环。

但并非所有的语言都像C一样，Java本身就会做越界检查，下面Java代码，会抛出java.lang.ArrayIndexOutOfBoundsException。

int[] a = new int[3];
a[3] = 10;

容器能否完全替代数组？

针对数组类型，很多语言都提供了容器类，比如Java中的ArrayList、C++ STL 中的vector。

ArrayList最大的优势就是可以将很多数组操作的细节封装起来和动态扩容。每次存储空间不够时，它会自动将空间扩容为1.5倍大小。

ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

对于业务开发，直接使用容器就足够了，省时省力。如果是一些非常底层的开发，比如开发网络框架，性能的优化要做到极致，这个时候数组就会优于容器，成为首选。

解答开篇

下标从0开始：

a[k]_address = base_address + k * type_size

下标从1开始：

a[k]_address = base_address + (k-1)*type_size

"下标"最确切的定义应该是“偏移(offset)”。
效仿C语言设计。

程序实现

Java编码实现

public class Array<E> {
    // 容量(cpacity)-大小(size)
    private E[] data; // 默认初始化为null
    private int size; // 默认初始化为0

    // 构造函数，传入参数的容量capacity构造Array
    public Array(int capacity) {
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数，默认数组的容量capacity=10
    public Array() {
        this(10);
    }

    // 获取数组的容量
    public int getCapacity() {
        return data.length;
    }

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

    // 返回数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 添加元素
    public void add(E e) {
        add(size, e);
    }

    // 指定位置添加元素
    public void add(int index, E e) {
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
        }
        // 扩容原来的1.5倍
        int newCapacity = data.length + (data.length >> 1);
        if(size == data.length) {
            resize(newCapacity);
        }
        for(int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size++;
    }

    // 获取index索引位置的元素
    public E get(int index) {
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        }
        return data[index];
    }

    // 修改index索引位置的元素为e
    public void set(int index, E e) {
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        }
        data[index] = e;
    }

    // 从数组中删除index位置的元素，返回删除的元素
    public E remove(int index) {
        if(index < 0 || index >= size) {
            throw new IllegalArgumentException("Remove failed. Index is illegal.");
        }
        E ret = data[index];
        for(int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;

        // 缩容
        if(size == data.length / 2) {
            resize(data.length / 2);
        }
        return ret;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        sb.append("[");
        for(int i = 0; i < size; i++) {
            sb.append(data[i]);
            if(i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // 将数组空间的容量变成newCapacity大小
    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

}

Python编码实现

class Array(object):
    
    def __init__(self, arr=None, capacity=10):
        if isinstance(arr, list):
            self._data = arr
            self._size = len(arr)
            return
        self._data = [None]*capacity
        self._size = 0

    # 获取大小
    def get_size(self):
        return self._size

    # 获取容量
    def get_capacity(self):
        return len(self._data)
    
    # 是否为空
    def is_empty(self):
        return self._size == 0

    # 添加数据(C)
    def addLast(self, e):
        self.add(self._size, e)

    # 添加数据(C)
    def add(self, index, e):
        if index < 0 or index > self._size:
            raise ValueError('add failed. Require index index < 0 or index > self._size.')
        if self._size == len(self._data):
            # 扩容
            new_capacity = self._size + (self._size >> 1)
            self._resize(new_capacity)

        for i in range(self._size-1, index-1, -1):
            self._data[i+1] = self._data[i]
        
        self._data[index] = e
        self._size += 1

    # 读取数据(R)
    def get(self, index):
        if index < 0 or index >= self._size:
            raise ValueError('get failed. Index is illegal.')
        return self._data[index]

    # 更新数据(U)
    def set(self, index, e):
        if index < 0 or index >= self._size:
            raise ValueError('get failed. Index is illegal.')
        self._data[index] = e

    # 删除数据(D)
    def remove(self, index):
        if index < 0 or index >= self._size:
            raise ValueError('remove failed. Index is illegal.')

        ret = self._data[index]
        for i in range(index+1, self._size):
            self._data[i - 1] = self._data[i]
        self._size -= 1

        # 缩容
        if self._size == len(self._data) // 2:
            new_capacity = self._size >> 1
            self._resize(new_capacity)

        return ret

    # 扩容/缩容
    def _resize(self, new_capacity):
        new_data = [None]*new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data

    def __str__(self):
        return 'Array: {}, size: {}, capacity: {}'.format(self._data[:self._size], self.get_size(), self.get_capacity())
        
    def __repr__(self):
        return self.__str__()

if __name__ == "__main__":
    arr = Array()

    for i in range(10):
        arr.addLast(i)
    print(arr)
    
    arr.add(1, 50)
    print(arr)

    arr.set(0, 100)
    print(arr)

    arr.remove(2)
    print(arr)

# 结果
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], size: 10, capacity: 10
Array: [0, 50, 1, 2, 3, 4, 5, 6, 7, 8, 9], size: 11, capacity: 15
Array: [100, 50, 1, 2, 3, 4, 5, 6, 7, 8, 9], size: 11, capacity: 15
Array: [100, 50, 2, 3, 4, 5, 6, 7, 8, 9], size: 10, capacity: 15

C++编码实现

#include <iostream>

template<class T>
class Array {
private:
    T *data;
    int size;
    int capacity;

    // 扩容/缩容
    void resize(int newCapacity) {
        T *newData = new T[newCapacity];
        for(int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
        capacity = newCapacity;
    }
public:
    Array(int capacity) {
        data = new T[capacity];
        size = 0;
        this->capacity = capacity;
    }

    Array() {
        data = new T[10];
        size = 0;
        this->capacity = 10;
    }

    // 获取容量
    int getCapacity() {
        return this->capacity;
    }
    //获取大小
    int getSize() {
        return size;
    }
    //是否为空
    bool isEmpty() {
        return size == 0;
    }

    // 添加数据(C)
    void add(int index, T e) {
        assert(index >= 0 && index <= size);
        if(size == capacity) {
            resize(2 * capacity);
        }
        for(int i = size - 1; i >= index; i--) {
            data[i+1] = data[i];
        }
        data[index] = e;
        size++;
    }

    // 添加数据(C)
    void addLast(T e) {
        add(size, e);
    }

    // 读取数据(R)
    int get(int index) {
        assert(index >=0 && index < size);
        return data[index];
    }

    // 更新数据(U)
    void set(int index, T e) {
        assert(index >=0 && index < size);
        data[index] = e;
    }

    // 删除数据(D)
    T remove(int index) {
        assert(index >= 0 && index < size);
        T ret = data[index];
        for(int i = index + 1; i < size; i++) {
            data[i-1] = data[i];
        }
        size--;
        if(size == capacity / 2) {
            resize(capacity / 2);
        }
        return ret;
    }

    // 打印数据
    void print() {
        std::cout << "Array: size = " << getSize() << ", capacity = " << getCapacity() << std::endl;
        toPrint();
        std::cout << std::endl;
    }

    void toPrint() {
        std::cout << "[";
        for(int i = 0; i < size; i++) {
            std::cout << data[i];
            if(i != size - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "]";
    }
};

Go编码实现

数据结构与算法之美-线性表(数组)

如何实现随机访问？

低效的“插入”和“删除”

警惕数组的访问越界问题

容器能否完全替代数组？

解答开篇

程序实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读