'''
數(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())
數(shù)據(jù)結(jié)構(gòu)起步-別小看數(shù)組
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門斤蔓,熙熙樓的掌柜王于貴愁眉苦臉地迎上來植酥,“玉大人,你說我怎么就攤上這事附迷【寤ィ” “怎么了?”我有些...
- 文/不壞的土叔 我叫張陵喇伯,是天一觀的道長喊儡。 經(jīng)常有香客問我,道長稻据,這世上最難降的妖魔是什么艾猜? 我笑而不...
- 正文 為了忘掉前任,我火速辦了婚禮捻悯,結(jié)果婚禮上匆赃,老公的妹妹穿的比我還像新娘。我一直安慰自己今缚,他們只是感情好算柳,可當(dāng)我...
- 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著姓言,像睡著了一般瞬项。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上何荚,一...
- 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼需纳!你這毒婦竟也來了冈止?” 一聲冷哼從身側(cè)響起,我...
- 正文 年R本政府宣布跟衅,位于F島的核電站,受9級特大地震影響播歼,放射性物質(zhì)發(fā)生泄漏伶跷。R本人自食惡果不足惜,卻給世界環(huán)境...
- 文/蒙蒙 一秘狞、第九天 我趴在偏房一處隱蔽的房頂上張望叭莫。 院中可真熱鬧,春花似錦烁试、人聲如沸雇初。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽靖诗。三九已至,卻和暖如春辩蛋,著一層夾襖步出監(jiān)牢的瞬間呻畸,已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 前言 最近在在看《Java數(shù)據(jù)結(jié)構(gòu)和算法》這本書位衩,這本書很不錯,值得細看熔萧√锹浚看完了第二章-數(shù)組篇僚祷。所以寫這一篇章節(jié)小...
- 數(shù)組是最基本的數(shù)據(jù)結(jié)構(gòu)之一,當(dāng)然我們每天也都在使用數(shù)組贮缕,那么你知道數(shù)組的CURD的操作的背后是什么嗎辙谜?我來說一下,...
- 1. 屬性 (1)一個數(shù)組就是一系列的插槽感昼,每一個插槽都包含一個元素(值或?qū)ο螅?(2)每個插槽都有一個固定的索引...
- 堆的數(shù)據(jù)結(jié)構(gòu)能夠使得堆頂總是維持最大(對于大根堆)或最辛杓颉(對于小根堆),給定一個數(shù)組层玲,對這個數(shù)組進行建堆号醉,則平均復(fù)...
- 內(nèi)容簡介 前言 數(shù)組和鏈表的定義 數(shù)組和鏈表的基本操作 第七課預(yù)告 1. 前言 上一課 [算法和數(shù)據(jù)結(jié)構(gòu)-初級 |...