數(shù)據(jù)結(jié)構(gòu)與算法-數(shù)組

線性表

01

線性表是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)，每個線性表上的數(shù)據(jù)最多有向前和向后兩個方向。除了數(shù)組外，鏈表、隊列、棧也是線性表數(shù)據(jù)結(jié)構(gòu)。

非線性表

01

和線性表相對立，數(shù)據(jù)之間不是簡單的前后關(guān)系，這樣的結(jié)構(gòu)稱為非線性表，如圖、樹、堆等數(shù)據(jù)結(jié)構(gòu)。

數(shù)組

01

數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)，是用一組連續(xù)的內(nèi)存空間，來存儲一組具有相同數(shù)據(jù)類型的數(shù)據(jù)。在每一種編程語言中，基本都有數(shù)組這種數(shù)據(jù)類型，當然它不僅是一種數(shù)據(jù)類型，還是一種基礎(chǔ)、簡單的數(shù)據(jù)結(jié)構(gòu)。

02

數(shù)組有上界和下界，數(shù)組的元素在上下界內(nèi)是連續(xù)的。

03

正式因為數(shù)組是用一組連續(xù)的內(nèi)存空間來存儲數(shù)據(jù)的，所以數(shù)組支持下標隨機訪問，復(fù)雜度是 O(1)；

04

相比于復(fù)雜度是 O(1)的隨機訪問操作，對于數(shù)組而言，插入和刪除操作的復(fù)雜度都為O(n)，因為每次要在數(shù)組的第 k 個位置插入或者刪除一個元素的話，都需要移動 k ~ n 個元素的位置；

    優(yōu)化技巧：

    （1）插入操作：如果不需要追求數(shù)組中元素的有序，則可以考慮直接將第 k 個位置的元素移到數(shù)組的末尾，然后把要插入的新元素放到第 k 個位置就行，這樣，復(fù)雜度也就是O(1)；

    （2）刪除操作：在一些場景下，并不追求數(shù)組中數(shù)據(jù)的連續(xù)性，可以將多次刪除操作集中在一起執(zhí)行。先記錄下已經(jīng)刪除的元素，并不真的刪除，當數(shù)組沒有更多空間時，再觸發(fā)真正的刪除操作，這樣可以省下大量重復(fù)的數(shù)據(jù)移動操作；警惕數(shù)組越界問題。

數(shù)組的特點

01

隨機訪問性高：數(shù)組隨機訪問效率高，因為在內(nèi)存中是連續(xù)的，所以可以直接訪問該地址的數(shù)據(jù)；

02

查找速度快：如果根據(jù)下標來查找是很快的，但是通常我們都是根據(jù)元素值來查找，給定一個元素值，對于無序數(shù)組，需要從數(shù)組第一個元素開始遍歷，直到找到那個元素；有序數(shù)組通過特定的算法查找的速度會比無序數(shù)組快；

03

插入和刪除效率低：數(shù)組因為連續(xù)這一特點使得它的的插入和刪除效率低，因為需要把插入和刪除位置后邊的所有數(shù)據(jù)后挪或者前移；

04

不易于擴展：數(shù)組不利于動態(tài)擴展，數(shù)組一旦定義，長度是固定的，擴展起來比較麻煩，需要重新定義數(shù)組；對內(nèi)存要求高，需要連續(xù)的空間；

05

對內(nèi)存要求高，需要連續(xù)的空間：數(shù)組需要預(yù)留儲存空間，在使用前需要先申請內(nèi)存的大小，有可能造成內(nèi)存的浪費，數(shù)組一旦創(chuàng)建后，大小就固定了，不能動態(tài)擴展數(shù)組的元素個數(shù)。如果初始化你給一個很大的數(shù)組大小，那會白白浪費內(nèi)存空間，如果給小了，后面數(shù)據(jù)個數(shù)增加了又添加不進去了；

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


歡迎關(guān)注微信公眾號 ：測開筆記