您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)Python實(shí)現(xiàn)動(dòng)態(tài)數(shù)組的方法,小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
Python序列類型
在本博客中,我們將學(xué)習(xí)探討Python的各種“序列”類,內(nèi)置的三大常用數(shù)據(jù)結(jié)構(gòu)——列表類(list)、元組類(tuple)和字符串類(str)。
不知道你發(fā)現(xiàn)沒有,這些類都有一個(gè)很明顯的共性,都可以用來保存多個(gè)數(shù)據(jù)元素,最主要的功能是:每個(gè)類都支持下標(biāo)(索引)訪問該序列的元素,比如使用語法 Seq[i]。其實(shí)上面每個(gè)類都是使用 數(shù)組 這種簡單的數(shù)據(jù)結(jié)構(gòu)表示。
但是熟悉Python的讀者可能知道這3種數(shù)據(jù)結(jié)構(gòu)又有一些不同:比如元組和字符串是不能修改的,列表可以修改。
計(jì)算機(jī)內(nèi)存中的數(shù)組結(jié)構(gòu)
計(jì)算機(jī)體系結(jié)構(gòu)中,我們知道計(jì)算機(jī)主存由位信息組成,這些位通常被歸類成更大的單元,這些單元?jiǎng)t取決于精準(zhǔn)的系統(tǒng)架構(gòu)。一個(gè)典型的單元就是一個(gè)字節(jié),相當(dāng)于8位。
計(jì)算機(jī)系統(tǒng)擁有龐大數(shù)量的存儲(chǔ)字節(jié),那么如何才能找到我們的信息存在哪個(gè)字節(jié)呢?答案就是大家平時(shí)熟知的 存儲(chǔ)地址 ?;诖鎯?chǔ)地址,主存中的任何字節(jié)都能被有效的訪問。實(shí)際上,每個(gè)存儲(chǔ)字節(jié)都和一個(gè)作為其地址的唯一二進(jìn)制數(shù)字相關(guān)聯(lián)。如下圖中,每個(gè)字節(jié)均被指定了存儲(chǔ)地址:
一般來說,編程語言記錄標(biāo)識(shí)符和其關(guān)聯(lián)值所存儲(chǔ)的地址之間的關(guān)系。比如,當(dāng)我們聲明標(biāo)識(shí)符 xx 就有可能和存儲(chǔ)器中的某一值相關(guān)聯(lián),而標(biāo)識(shí)符 yy就可能和其他的值相關(guān)聯(lián)。一組相關(guān)的變量能夠一個(gè)接一個(gè)地存儲(chǔ)在計(jì)算機(jī)存儲(chǔ)器的一塊連續(xù)區(qū)域內(nèi)。我們將這種方式稱為 數(shù)組。
我們來看Python中的例子,一個(gè)文本字符串 HELLO 是以一列有序字符的形式存儲(chǔ)的,假定該字符串的每個(gè)Unicode字符需要兩個(gè)字節(jié)的存儲(chǔ)空間。最下面的數(shù)字就是該字符串的索引值。
我們可以看到,數(shù)組可以存儲(chǔ)多個(gè)值而無需構(gòu)造具有特定索引的多個(gè)變量來指定其中的每個(gè)項(xiàng)目,并且?guī)缀踉谒芯幊陶Z言(例如C、Java、C#、C++)中使用,但是Python更具有優(yōu)勢(shì)。Python在構(gòu)建列表時(shí),熟悉的讀者可能知道,不需要預(yù)先定義數(shù)組或列表的大小,相反,在Python中,列表具有動(dòng)態(tài)性質(zhì),我們可以不斷的往列表中添加我們想要的數(shù)據(jù)元素。接下來,讓我們看看Python列表的知識(shí)(已經(jīng)熟悉的讀者可以快速瀏覽或者跳過)。
Python列表
Python列表的操作
創(chuàng)建列表的語法格式:
[ele1, ele2, ele3, ele4, ...]
創(chuàng)建元組的語法格式:
(ele1, ele2, ele3, ele4, ...)
元組比列表的內(nèi)存空間利用率更高,因?yàn)樵M是固定不變的,所以沒有必要?jiǎng)?chuàng)建擁有剩余空間的動(dòng)態(tài)數(shù)組。
我們先在Python的IDE中創(chuàng)建一個(gè)列表,然后大致了解一下列表部分內(nèi)置操作,我們先創(chuàng)建了一個(gè)名為test_list的列表,然后修改(插入或刪除)元素,反轉(zhuǎn)或清空列表,具體如下:
>>> test_list = [] # 創(chuàng)建名為test_list的空列表 >>> test_list.append("Hello") >>> test_list.append("World") >>> test_list ['Hello', 'World'] >>> test_list = ["Hello", "Array", 2019, "easy learning", "DataStructure"] # 重新給test_list賦值 >>> len(test_list) # 求列表的長度 5 >>> test_list[2] = 1024 # 修改列表元素 >>> test_list ['Hello', 'Array', 1024, 'easy learning', 'DataStructure'] >>> >>> test_list.insert(1, "I love") # 向列表中指定位置中插入一個(gè)元素 >>> test_list ['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure'] >>> test_list.append(2020) # 向列表末尾增加一個(gè)元素 >>> test_list ['Hello', 'I love', 'Array', 1024, 'easy learning', 'DataStructure', 2020] >>> >>> test_list.pop(1) # 刪除指定位置的元素 'I love' >>> test_list.remove(2020) # 刪除指定元素 >>> >>> test_list.index('Hello') # 查找某個(gè)元素的索引值 0 >>> test_list.index('hello') # 如果查找某個(gè)元素不在列表中,返回ValueError錯(cuò)誤 Traceback (most recent call last): File "<pyshell#11>", line 1, in <module> test_list.index('hello') ValueError: 'hello' is not in list >>> >>> test_list.reverse() # 反轉(zhuǎn)整個(gè)列表 >>> test_list ['DataStructure', 'easy learning', 2019, 'Array', 'Hello'] >>> test_list.clear() # 清空列表 >>> test_list []
我們看上面的代碼,可以看到list的相關(guān)操作——增刪改查,已經(jīng)很強(qiáng)大了,還有一些內(nèi)置方法這里并沒有做展示,留給讀者自己去發(fā)現(xiàn)并體驗(yàn)。
那么Python內(nèi)置的list類是如何被實(shí)現(xiàn)的呢?
好吧,答案是動(dòng)態(tài)數(shù)組。說到這里,不知道大家學(xué)Python列表的時(shí)候是不是這樣想的——列表很簡單嘛,就是list()類、用中括號(hào)[]括起來,然后指導(dǎo)書籍或文檔上的各類方法append、insert、pop...在IDE或者Pycharm一頓操作過后,是的我學(xué)會(huì)了。
但其實(shí)真的很不簡單,比如我舉個(gè)例子:A[-1]這個(gè)操作怎么實(shí)現(xiàn)?列表切片功能怎么實(shí)現(xiàn)?如何自己寫pop()默認(rèn)刪除列表最右邊的元素(popleft刪除最左邊簡單)?...這些功能用起來爽,但真的自己實(shí)現(xiàn)太難了(我也還在學(xué)習(xí)中,大佬們請(qǐng)輕噴!)如果我們能學(xué)習(xí)并理解,肯定可以加強(qiáng)我們對(duì)數(shù)組這一結(jié)構(gòu)的理解。
動(dòng)態(tài)數(shù)組
什么是動(dòng)態(tài)數(shù)組
動(dòng)態(tài)數(shù)組是內(nèi)存的連續(xù)區(qū)域,其大小隨著插入新數(shù)據(jù)而動(dòng)態(tài)增長。在靜態(tài)數(shù)組中,我們需要在分配時(shí)指定大小。在定義數(shù)組的時(shí)候,其實(shí)計(jì)算機(jī)已經(jīng)幫我們分配好了內(nèi)存來存儲(chǔ),實(shí)際上我們不能擴(kuò)展數(shù)組,因?yàn)樗拇笮∈枪潭ǖ?。比如:我們分配一個(gè)大小為10的數(shù)組,則不能插入超過10個(gè)項(xiàng)目。
但是動(dòng)態(tài)數(shù)組會(huì)在需要的時(shí)候自動(dòng)調(diào)整其大小。這一點(diǎn)有點(diǎn)像我們使用的Python列表,可以存儲(chǔ)任意數(shù)量的項(xiàng)目,而無需在分配時(shí)指定大小。
所以實(shí)現(xiàn)一個(gè)動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)的關(guān)鍵是——如何擴(kuò)展數(shù)組?當(dāng)列表list1的大小已滿時(shí),而此時(shí)有新的元素要添加進(jìn)列表,我們會(huì)執(zhí)行一下步驟來克服其大小限制的缺點(diǎn):
分配具有更大容量的新數(shù)組 list2
設(shè)置 list2[i] = list1[i] (i=0,1,2,...,n-1),其中n是該項(xiàng)目的當(dāng)前編號(hào)
設(shè)置list1 = list2,也就是說,list2正在作為新的數(shù)組來引用我們的新列表。
然后,只要將新的元素插入(添加)到我們的列表list1即可。
接下來要思考的問題是,新數(shù)組應(yīng)該多大?通常我們得做法是:新數(shù)組的大小是已滿的舊數(shù)組的2倍。我們將在Python中編程實(shí)現(xiàn)動(dòng)態(tài)數(shù)組的概念,并創(chuàng)建一個(gè)簡單的代碼,很多功能不及Python強(qiáng)大。
實(shí)現(xiàn)動(dòng)態(tài)數(shù)組Python代碼
在Python中,我們利用ctypes的內(nèi)置庫來創(chuàng)建自己的動(dòng)態(tài)數(shù)組類,因?yàn)閏types模塊提供對(duì)原始數(shù)組的支持,為了更快的對(duì)數(shù)組進(jìn)行學(xué)習(xí),所以對(duì)ctypes的知識(shí)可以查看官方文檔進(jìn)行學(xué)習(xí)。關(guān)于Python的公有方法與私有方法,我們?cè)诜椒Q前使用雙下劃線**__**使其保持隱藏狀態(tài),代碼如下:
# -*- coding: utf-8 -*- # @Time : 2019-11-01 17:10 # @Author : yuzhou_1su # @ContactMe : https://blog.csdn.net/yuzhou_1shu # @File : DynamicArray.py # @Software : PyCharm import ctypes class DynamicArray: """A dynamic array class akin to a simplified Python list.""" def __init__(self): """Create an empty array.""" self.n = 0 # count actual elements self.capacity = 1 # default array capacity self.A = self._make_array(self.capacity) # low-level array def is_empty(self): """ Return True if array is empty""" return self.n == 0 def __len__(self): """Return numbers of elements stored in the array.""" return self.n def __getitem__(self, i): """Return element at index i.""" if not 0 <= i < self.n: # Check it i index is in bounds of array raise ValueError('invalid index') return self.A[i] def append(self, obj): """Add object to end of the array.""" if self.n == self.capacity: # Double capacity if not enough room self._resize(2 * self.capacity) self.A[self.n] = obj # Set self.n index to obj self.n += 1 def _resize(self, c): """Resize internal array to capacity c.""" B = self._make_array(c) # New bigger array for k in range(self.n): # Reference all existing values B[k] = self.A[k] self.A = B # Call A the new bigger array self.capacity = c # Reset the capacity @staticmethod def _make_array(c): """Return new array with capacity c.""" return (c * ctypes.py_object)() def insert(self, k, value): """Insert value at position k.""" if self.n == self.capacity: self._resize(2 * self.capacity) for j in range(self.n, k, -1): self.A[j] = self.A[j-1] self.A[k] = value self.n += 1 def pop(self, index=0): """Remove item at index (default first).""" if index >= self.n or index < 0: raise ValueError('invalid index') for i in range(index, self.n-1): self.A[i] = self.A[i+1] self.A[self.n - 1] = None self.n -= 1 def remove(self, value): """Remove the first occurrence of a value in the array.""" for k in range(self.n): if self.A[k] == value: for j in range(k, self.n - 1): self.A[j] = self.A[j+1] self.A[self.n - 1] = None self.n -= 1 return raise ValueError('value not found') def _print(self): """Print the array.""" for i in range(self.n): print(self.A[i], end=' ') print()
測試動(dòng)態(tài)數(shù)組Python代碼
上面我們已經(jīng)實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)數(shù)組的類,相信都很激動(dòng),接下來讓我們來測試一下,看能不能成功呢?在同一個(gè)文件下,寫的測試代碼如下:
def main(): # Instantiate mylist = DynamicArray() # Append new element mylist.append(10) mylist.append(9) mylist.append(8) # Insert new element in given position mylist.insert(1, 1024) mylist.insert(2, 2019) # Check length print('The array length is: ', mylist.__len__()) # Print the array print('Print the array:') mylist._print() # Index print('The element at index 1 is :', mylist[1]) # Remove element print('Remove 2019 in array:') mylist.remove(2019) mylist._print() # Pop element in given position print('Pop pos 2 in array:') # mylist.pop() mylist.pop(2) mylist._print() if __name__ == '__main__': main()
測試結(jié)果
激動(dòng)人心的時(shí)刻揭曉,測試結(jié)果如下。請(qǐng)結(jié)合測試代碼和數(shù)組的結(jié)構(gòu)進(jìn)行理解,如果由疏漏,歡迎大家指出。
The array length is: 5 Print the array: 10 1024 2019 9 8 The element at index 1 is : 1024 Remove 2019 in array: 10 1024 9 8 Pop pos 2 in array: 10 1024 8
關(guān)于“Python實(shí)現(xiàn)動(dòng)態(tài)數(shù)組的方法”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,使各位可以學(xué)到更多知識(shí),如果覺得文章不錯(cuò),請(qǐng)把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。