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

線性表

01

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

非線性表

01

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

數(shù)組

01

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

02

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

03

正式因?yàn)閿?shù)組是用一組連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)數(shù)據(jù)的，所以數(shù)組支持下標(biāo)隨機(jī)訪問，復(fù)雜度是 O(1)；

04

相比于復(fù)雜度是 O(1)的隨機(jī)訪問操作，對(duì)于數(shù)組而言，插入和刪除操作的復(fù)雜度都為O(n)，因?yàn)槊看我跀?shù)組的第 k 個(gè)位置插入或者刪除一個(gè)元素的話，都需要移動(dòng) k ~ n 個(gè)元素的位置；

    優(yōu)化技巧：

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

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

數(shù)組的特點(diǎn)

01

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

02

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

03

插入和刪除效率低：數(shù)組因?yàn)檫B續(xù)這一特點(diǎn)使得它的的插入和刪除效率低，因?yàn)樾枰巡迦牒蛣h除位置后邊的所有數(shù)據(jù)后挪或者前移；

04

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

05

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

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)注微信公眾號(hào) ：測(cè)開筆記