數(shù)據(jù)結(jié)構(gòu)起步-別小看數(shù)組

'''
數(shù)據(jù)結(jié)構(gòu)起步----01----數(shù)組
'''
__author__ = 'ring04'
__date__ = '2020.11.14'

class Array:
    '''
    定義數(shù)組類
    '''
    def __init__(self, arr=None, capacity=10):
        if isinstance(arr, list):
            self._data = arr[:]
            # 默認數(shù)組容量
            self._size = len(arr)
        else:
            self._size = 0
            self._data = [None] * capacity
    def __getitem__(self, index):
        '''
        獲取數(shù)組元素
        :param index:
        :return:
        '''
        return self._data[index]
    def __setitem__(self, key, value):
        '''
        設(shè)置數(shù)組元素
        :param key:
        :param value:
        :return:
        '''
        return  self.add_last(value)

    def get_capacity(self):
        '''
        獲取數(shù)組容量
        :return:
        '''
        return len(self._data)

    def get_size(self):
        '''
        獲取數(shù)組中元素個數(shù)
        :return:
        '''
        return self._size

    def is_empty(self):
        '''
        判斷數(shù)組是否為空
        :return:
        '''
        return self._size == 0

    def add_last(self,value):
        '''
        在數(shù)組末尾插入元素
        :param value:
        :return:
        '''
        self.add(self._size,value)
    def add_first(self,value):
        '''
        在數(shù)組起始位置插入元素
        :param value:
        :return:
        '''
        self.add(0,value)

    def add(self,index,value):
        '''
        在索引為index的位置插入元素value
        :param index:
        :param value:
        :return:
        '''
        if index <0 or index > self._size:
            raise IndexError('Add failed,Required index >= 0 and index <= size')

        # 數(shù)組full搀擂,擴容
        if self._size == len(self._data):
            if self._size == 0:
                self._resize(1)
            else:
                self._resize(len(self._data) * 2)
        # index后元素后移一位
        for i in range(self._size - 1, index - 1, -1):
            self._data[i+1] = self._data[i]
        self._data[index] = value
        self._size += 1

    def get(self,index):
        '''
        獲取索引為index的元素
        :param index:
        :return:
        '''
        if index <0 or index >= self._size:
            raise IndexError("get failer,index >=0 or index < size")
        return self._data[index]

    def set(self,index,value):
        '''
        設(shè)置index索引值為value
        :param index:
        :param value:
        :return:
        '''
        if index <0 or index >= self._size:
            raise IndexError("set faile")

        self._data[index] = value

    def contains(self,value):
        '''
        查看數(shù)組中是否包含元素value
        :param value:
        :return:
        '''
        for i in range(self._size):
            if self._data[i] == value:
                return True
            else:
                return False

    def find_index(self, value):
        '''
        查找元素值value在數(shù)組中的索引
        :param value:
        :return:
        '''
        for i in range(self._size):
            if self._data[i] == value:
                return i
        return -1

    def remove(self,index):
        '''
        從數(shù)組中刪除索引為index的元素,并返回刪除元素值
        :param index:
        :return:
        '''
        if index <0 or index >= self._size:
            raise IndexError("remove failed")
        ret = self._data[index]
        #index元素之后的往前移動一位
        for i in range(index+1,self._size):
            self._data[i-1] = self._data[i]
        self._size -= 1

        # 如果數(shù)組元素小于容量的1/4卷玉,則縮小容量至現(xiàn)有的1/2
        if self._size < len(self._data) // 4 and len(self._data) // 2 != 0:
            self._resize(len(self._data) // 2)
        return ret

    def remove_first(self):
        self.remove(0)

    def remove_last(self):
        self.remove(self._size - 1)

    def remove_element(self,value):
        index = self.find_index(value)
        self.remove(index)

    def _resize(self,new_capacity):
        '''
        將數(shù)組空間容量變成new_capacity
        :param new_capacity:
        :return:
        '''
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data = new_data

    def swap(self,i,j):
        '''
        交換索引為i和j兩個位置的值
        :param i:
        :param j:
        :return:
        '''
        if i <0 or i > self._size or j <0 or j > self._size:
            raise IndexError("index is illegal")
        self._data[i], self._data[j] = self._data[j],self._data[i]

if __name__ == "__main__":
    array = Array()
    for i in range(10):
        array.add_last(i)
    print("capacity: %d" % array.get_capacity())
    print("size: %d" % array.get_size())

    array.add_last(10)
    print("capacity: %d" % array.get_capacity())
    print("size: %d" % array.get_size())

    array.add(4, "ring04")

    print(array.find_index("ring04"))

    for i in range(array.get_size()):
        print(array.get(i))

    for i in range(8):
        array.remove_last()
    print("capacity: %d" % array.get_capacity())
    print("size: %d" % array.get_size())
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末哨颂,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子相种,更是在濱河造成了極大的恐慌威恼,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,865評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異箫措,居然都是意外死亡腹备,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,296評論 3 399
  • 文/潘曉璐 我一進店門斤蔓,熙熙樓的掌柜王于貴愁眉苦臉地迎上來植酥,“玉大人,你說我怎么就攤上這事附迷【寤ィ” “怎么了?”我有些...
    開封第一講書人閱讀 169,631評論 0 364
  • 文/不壞的土叔 我叫張陵喇伯,是天一觀的道長喊儡。 經(jīng)常有香客問我,道長稻据,這世上最難降的妖魔是什么艾猜? 我笑而不...
    開封第一講書人閱讀 60,199評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮捻悯,結(jié)果婚禮上匆赃,老公的妹妹穿的比我還像新娘。我一直安慰自己今缚,他們只是感情好算柳,可當(dāng)我...
    茶點故事閱讀 69,196評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著姓言,像睡著了一般瞬项。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上何荚,一...
    開封第一講書人閱讀 52,793評論 1 314
  • 那天囱淋,我揣著相機與錄音,去河邊找鬼餐塘。 笑死妥衣,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的戒傻。 我是一名探鬼主播税手,決...
    沈念sama閱讀 41,221評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼需纳!你這毒婦竟也來了冈止?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,174評論 0 277
  • 序言:老撾萬榮一對情侶失蹤候齿,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體慌盯,經(jīng)...
    沈念sama閱讀 46,699評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡周霉,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,770評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了亚皂。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片俱箱。...
    茶點故事閱讀 40,918評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖灭必,靈堂內(nèi)的尸體忽然破棺而出狞谱,到底是詐尸還是另有隱情,我是刑警寧澤禁漓,帶...
    沈念sama閱讀 36,573評論 5 351
  • 正文 年R本政府宣布跟衅,位于F島的核電站,受9級特大地震影響播歼,放射性物質(zhì)發(fā)生泄漏伶跷。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,255評論 3 336
  • 文/蒙蒙 一秘狞、第九天 我趴在偏房一處隱蔽的房頂上張望叭莫。 院中可真熱鬧,春花似錦烁试、人聲如沸雇初。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,749評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽靖诗。三九已至,卻和暖如春辩蛋,著一層夾襖步出監(jiān)牢的瞬間呻畸,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,862評論 1 274
  • 我被黑心中介騙來泰國打工悼院, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留伤为,地道東北人。 一個月前我還...
    沈念sama閱讀 49,364評論 3 379
  • 正文 我出身青樓据途,卻偏偏與公主長得像绞愚,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子颖医,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,926評論 2 361

推薦閱讀更多精彩內(nèi)容