什么是數據結構？

數據結構是指相互之間存在著一種或多種關系的數據元素的集合和該集合中數據元素之間的關系組成。 簡單來說，數據結構就是設計數據以何種方式組織并存儲在計算機中。 比如：列表、集合與字典等都是一種數據結構。

N.Wirth: “程序=數據結構+算法”

數據結構的分類

數據結構按照其邏輯結構可分為線性結構、樹結構、圖結構

線性結構：數據結構中的元素存在一對一的相互關系

樹結構：數據結構中的元素存在一對多的相互關系

圖結構：數據結構中的元素存在多對多的相互關系

線性結構/線性表

順序表

鏈表

順序表

1. 列表 / 數組

動態數組也稱數組列表，在python中一般為List。

列表：在其他編程語言中稱為“數組”，是一種基本的數據結構類型。列表又叫做順序表(連續存儲的方式)。

數組的缺點是大小固定, 一旦聲明長度就要占用連續的內存空間, 當空間不夠用時更換更大的空間, 此時就需要將原數組的所有數據遷移過去, 比較費時。

順序存儲數據

連續存儲

任意順序訪問，可變大小的列表數據結構允許增加、刪除元素

2. 數組操作函數：

3. 數組內置操作函數的時間復雜度

4.用python實現內置函數的方法

classDynamicArray:def __init__(self):'Create an empty array.'self._n= 0 #size

self._capacity = 10 #先給個10

self._A =self._make_array(self._capacity)def __len__(self):returnself._ndefis_empty(self):return self._n ==0#O(1)

def __getitem__(self, k):if not 0 <= k

defappend(self, obj):if self._n == self._capacity: #首先要判斷該容器是否放得下

self._resize(2 *self._capacity)

self._A[self._n]=obj

self._n+= 1

def_make_array(self, c):return (c *ctypes.py_object)()def_resize(self, c):

B=self._make_array(c)for k inrange(self._n):

B[k]=self._A[k]

self._A=B

self._capacity=c#O(n)

definsert(self, k, value):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

#O(n)

defremove(self, value):for k inrange(self._n):if self._A[k] == value: #一個個查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):for i inrange(self._n):print(self._A[i], end=' ')print()

在append和insert函數里面，要先判斷是否超出給定的capacity，如果超出，要擴容resize擴容；

insert時，從后往前找，remove的時候從前往后找，然后找到之后，將后面的元素一一往前移動?self._A[j] = self._A[j + 1]，最后一個元素賦值為None，然后總n-1；

__getitem__?當訪問元素時會調用該方法li[i]

5. list進行reverse

復雜度 O(n)

defreverse(list):

i, j = 0, len(list)-1

while i

list[i],list[j] =list[j],list[i]

i += 1j -= 1

returnlist

li = [1,2,3,4,5,6]

print(reverse(li))

'''

[6, 5, 4, 3, 2, 1]

'''

注意：因為下標從0開始，所以len后要減1

defreverse(self):

elems =self.elements

i, j = 0, len(elems)-1

while i

elems[i],elems[j] =elems[j],elems[i]

i, j= i+1,j-1

注意：寫法

6. 關于列表的問題

列表中元素使如何存儲的？

列表提供了哪些基本的操作？

這些操作的時間復雜度是多少？append是O(1)；插入和刪除是O(n)

擴展：Python的列表是如何實現的？

其他語言中的數組：一個整數占4個字節(bytes), 假設有一個數組a，在內存中會記錄它的起始點300處，找a[2]就是300+2*4=308

python中的列表，如何解決append的問題呢？

會在后面的內存中開辟一個比append前長一倍的內存，然后，將前面的元素全部復制過去。

如何解決數據類型不一樣的問題，因為數據類型不一樣，占用的內存就不一樣，就不好去計算。

另外開辟一段內存來存放真實數據。仍然通過之前的方式找到數據所在地址，比如找a[1]，就通過300+4*1找到304，304處存放的是真實數據所在的內存地址2000，通過二次尋址的方式，找到真實數據2000處存放的是3.2。

總結

以上是生活随笔為你收集整理的python顺序表数组_数据结构 | 顺序表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。