数据结构与算法-数组

线性表

01

线性表是数据排成像一条线一样的结构，每个线性表上的数据最多有向前和向后两个方向。除了数组外，链表、队列、栈也是线性表数据结构。

非线性表

01

和线性表相对立，数据之间不是简单的前后关系，这样的结构称为非线性表，如图、树、堆等数据结构。

数组

01

数组是一种线性表数据结构，是用一组连续的内存空间，来存储一组具有相同数据类型的数据。在每一种编程语言中，基本都有数组这种数据类型，当然它不仅是一种数据类型，还是一种基础、简单的数据结构。

02

数组有上界和下界，数组的元素在上下界内是连续的。

03

正式因为数组是用一组连续的内存空间来存储数据的，所以数组支持下标随机访问，复杂度是 O(1)；

04

相比于复杂度是 O(1)的随机访问操作，对于数组而言，插入和删除操作的复杂度都为O(n)，因为每次要在数组的第 k 个位置插入或者删除一个元素的话，都需要移动 k ~ n 个元素的位置；

    优化技巧：

    （1）插入操作：如果不需要追求数组中元素的有序，则可以考虑直接将第 k 个位置的元素移到数组的末尾，然后把要插入的新元素放到第 k 个位置就行，这样，复杂度也就是O(1)；

    （2）删除操作：在一些场景下，并不追求数组中数据的连续性，可以将多次删除操作集中在一起执行。先记录下已经删除的元素，并不真的删除，当数组没有更多空间时，再触发真正的删除操作，这样可以省下大量重复的数据移动操作；警惕数组越界问题。

数组的特点

01

随机访问性高：数组随机访问效率高，因为在内存中是连续的，所以可以直接访问该地址的数据；

02

查找速度快：如果根据下标来查找是很快的，但是通常我们都是根据元素值来查找，给定一个元素值，对于无序数组，需要从数组第一个元素开始遍历，直到找到那个元素；有序数组通过特定的算法查找的速度会比无序数组快；

03

插入和删除效率低：数组因为连续这一特点使得它的的插入和删除效率低，因为需要把插入和删除位置后边的所有数据后挪或者前移；

04

不易于扩展：数组不利于动态扩展，数组一旦定义，长度是固定的，扩展起来比较麻烦，需要重新定义数组；对内存要求高，需要连续的空间；

05

对内存要求高，需要连续的空间：数组需要预留储存空间，在使用前需要先申请内存的大小，有可能造成内存的浪费，数组一旦创建后，大小就固定了，不能动态扩展数组的元素个数。如果初始化你给一个很大的数组大小，那会白白浪费内存空间，如果给小了，后面数据个数增加了又添加不进去了；

class Array(object):
    def __init__(self, size=32):
        self.__size = size
        self.__items = [None] * size

    def __getitem__(self, index):
        return self.__items[index]

    def __setitem__(self, key, value):
        self.__items[key] = value

    def __len__(self):
        return self.__size

    def clear(self, value=None):
        for i in range(len(self.__items)):
            self.__items[i] = value

    def __iter__(self):
        for item in self.__items:
            yield item


作者：David

欢迎关注微信公众号 ：测开笔记