• 1. Python 內(nèi)置數(shù)據(jù)結(jié)構(gòu)
  • 1.1. 數(shù)值型
  • 1.2. math 模塊
  • 1.3. round 圓整
  • 1.4. 常用的其他函數(shù)
  • 1.5. 類型判斷
• 2. 列表
  • 2.1. 索引訪問(wèn)
  • 2.2. 列表和鏈表的區(qū)別
  • 2.3. 列表的查詢
  • 2.4. 列表元素修改
  • 2.5. 列表的追加和插入
  • 2.6. 列表使用 * 重復(fù)帶來(lái)的問(wèn)題
  • 2.7. 刪除元素
  • 2.8. 其他操作

1. Python 內(nèi)置數(shù)據(jù)結(jié)構(gòu)

??Python 內(nèi)置了很多數(shù)據(jù)結(jié)構(gòu)(容器), 供我們直接進(jìn)行使用，在學(xué)習(xí)結(jié)構(gòu)之前，有一些小的知識(shí)點(diǎn)進(jìn)行補(bǔ)充。

1.1. 數(shù)值型

1. int、float、complex、bool 都是 class（類），1、5.0、2+3j 都是對(duì)象即實(shí)例
2. int：Python3 的 int 就是長(zhǎng)整型，且沒有大小限制，受限于內(nèi)存區(qū)域大小
3. float：有整數(shù)和小數(shù)部分組成。支持十進(jìn)制和科學(xué)計(jì)數(shù)法表示。
4. complex：復(fù)數(shù)，有實(shí)屬和虛數(shù)部分組成，實(shí)數(shù)部分和虛數(shù)部分都是浮點(diǎn)數(shù)
5. bool：int 的子類，僅有 2 個(gè)實(shí)例，True 和 False，其中 True 表示 1，F(xiàn)alse 表示 0

In : int(10.12)    # 直接取整                     
Out: 10

In : int(-12)
Out: -12

In : float(10)     # 轉(zhuǎn)換為浮點(diǎn)數(shù)    
Out: 10.0

In : float(-9)           
Out: -9.0

In : bool(1)       # 1 表示 True（非 0 都為 True)              
Out: True

In : bool(0)       # 0 表示 False   
Out: False

1.2. math 模塊

??數(shù)學(xué)之中，除了加減乘除四則運(yùn)算之外，還有其它更多的運(yùn)算，比如乘方、開方、對(duì)數(shù)運(yùn)算等等，Python 提供了一個(gè)專門輔助計(jì)算的模塊：math, 模塊方法及常量如下：

• math.ceil：向上取整（天花板除）
• math.floor：向下取整（地板除）
• math.pi：數(shù)字常量，圓周率
• math.pow(x, y)：返回 x 的 y 次方，即 x**y
• math.sqrt(x)：求 x 的平方根

In : import math         # 導(dǎo)入模塊              
In : math.pi
Out: 3.141592653589793

In : math.pow(2,3)       # 2**3                  
Out: 8.0

In : math.ceil(-10.6)    # 往數(shù)軸右邊取整
Out: -10

In : math.ceil(12.3)       
Out: 13

In : math.floor(12.3)     # 往數(shù)軸左邊取整
Out: 12

In : math.floor(-12.3)  
Out: -13

In : math.sqrt(10)      
Out: 3.1622776601683795

??注意：

• int 取整：正負(fù)數(shù)都只取整數(shù)
• 整除(向下取整)

?? 如下例所示：

In : int(-12.1)     # 只會(huì)取整數(shù)部分
Out: -12

In : int(10.5)          
Out: 10

In : 1 // 3           # 向下取整             
Out: 0

In : 10 // 3  
Out: 3

1.3. round 圓整

??在 Python 中有一個(gè) round() 函數(shù)，用于對(duì)小數(shù)進(jìn)行取整，不過(guò)在 Python 中的 round() 有些特別，總結(jié)一句話就是 4 舍 6 入 5 取偶。即當(dāng)小數(shù)點(diǎn)后面的數(shù)字 小于 5 會(huì)直接 舍去，大于 5 則會(huì)直接 進(jìn)位，等于 5 則會(huì) 取數(shù)軸上距離最近的偶數(shù)。

In : round(1.2)         
Out: 1

In : round(-1.2)        
Out: -1

In : round(1.5)         
Out: 2

In : round(-2.5)        
Out: -2

In : round(0.5)         
Out: 0

In : round(-5.5)        
Out: -6

In : round(1.6)         
Out: 2

In : round(-1.500001)   
Out: -2 

1.4. 常用的其他函數(shù)

• max()：常用來(lái)在可迭代對(duì)象中求最大值
• min(): 常用來(lái)在可迭代對(duì)象中求最小值
• bin()：把對(duì)象轉(zhuǎn)換為二進(jìn)制
• oct()：把對(duì)象轉(zhuǎn)換為八進(jìn)制
• hex()：把對(duì)象轉(zhuǎn)換為十六進(jìn)制

1.5. 類型判斷

??由于 Python 是一種強(qiáng)類型語(yǔ)言，在數(shù)據(jù)比較時(shí)，只有相同數(shù)據(jù)類型，才可以進(jìn)行比較。這時(shí)我們就需要知道對(duì)象到底是什么類型，type 就是用來(lái)查看類型的。

In : type('123')
Out: str

In : type(123)          
Out: int

In : type(True)         
Out: bool

??從上面代碼結(jié)果可以看出 type 返回的是類型，并不是字符串，而在數(shù)據(jù)判斷時(shí)我們需要的是判斷結(jié)果，比如判斷某個(gè)變量是某個(gè)類型的，那么這個(gè)時(shí)候就需要用到 isinstance() 了。

# 基本用法                 
Signature: isinstance(obj, class_or_tuple, /) --> bool
# 接受兩個(gè)參數(shù)，返回一個(gè)布爾值
# obj：要判斷的對(duì)象
# class_or_tuple：一個(gè)類，或者多個(gè)類組成的元組

In : isinstance(123, str)   # 判斷 123 是 str 類型嗎？
Out: False

In : isinstance(123, (str, int))   # 判斷 123 是 str 或者 int 類型中的一種嗎？
Out: True

2. 列表

??列表是 Python 中最基本的數(shù)據(jù)結(jié)構(gòu)。什么是序列呢？我們可以認(rèn)為它是一個(gè)隊(duì)列，一個(gè)排列整齊的隊(duì)伍。列表內(nèi)的個(gè)體稱為元素，它可以是任意對(duì)象(數(shù)字、字符串、對(duì)象、列表)，多個(gè)元素組合在一起，使用逗號(hào)分隔，中括號(hào)括起來(lái)，就是列表。它有如下特點(diǎn)：

1. 列表內(nèi)的元素是 有序的，可以使用 索引(下標(biāo)) 獲取元素，第一個(gè)索引是 0，第二個(gè)索引是 1，依此類推。
2. 線性的存儲(chǔ)結(jié)構(gòu)，從左至右依次存儲(chǔ)
3. 列表是可變的，我們可以對(duì)其內(nèi)的元素進(jìn)行任意的增刪改查

??創(chuàng)建一個(gè)列表，只要把逗號(hào)分隔的不同的數(shù)據(jù)項(xiàng)使用方括號(hào)括起來(lái)即可。如下所示：

In : a = []       # 空列表

In : b = list()    # 空列表                    

In : c = list(range(3))   # 接受一個(gè)可迭代對(duì)象，轉(zhuǎn)換為列表。[0, 1, 2]

注意：列表無(wú)法在初始化時(shí)就指定列表的大小

2.1. 索引訪問(wèn)

??列表的索引有如下特點(diǎn)：

1. 正索引：從左至右，從 0 開始，為列表中每一個(gè)元素編號(hào)
2. 負(fù)索引：從右至左，從 -1 開始
3. 正負(fù)索引不可以超界，否則會(huì)拋出異常 IndexError
4. 為了理解方便，可以認(rèn)為列表是從左至右排列的，左邊是頭部，右邊是尾部，左邊是下界，右邊是上界
5. 列表通過(guò)索引訪問(wèn)，例如：list[index]，index 就是索引，使用中括號(hào)訪問(wèn)。

2.2. 列表和鏈表的區(qū)別

??我們通常會(huì)把列表和鏈表拿來(lái)做對(duì)比，它倆雖然都是有序的可以被索引，但是內(nèi)部實(shí)現(xiàn)方法以及適用場(chǎng)景有很大區(qū)別。
??列表在內(nèi)存中的存儲(chǔ)方式是線性的，而鏈表是非線性的，他們的差別如下：

liebiao.png

lianbiao.png

??由上圖我們可以得到如下結(jié)論：

• 列表：線性結(jié)構(gòu)，順序結(jié)構(gòu)，可以被索引，數(shù)據(jù)存放的是連續(xù)的內(nèi)存空間，取值時(shí)，只需要進(jìn)行偏移量計(jì)算即可，屬于一步到位型，但是在增刪數(shù)據(jù)時(shí)，需要針對(duì)其后所有的數(shù)據(jù)進(jìn)行移動(dòng)，所以性能不高。
• 鏈表：線性結(jié)構(gòu)，順序結(jié)構(gòu)，可以被索引，放數(shù)據(jù)的地方，在內(nèi)存地址上并不是連續(xù)的。增刪數(shù)據(jù)時(shí)，只需斷開前后兩個(gè)元素先前的連接，增加新元素后，建立新的連接即可，但由于其不連續(xù)的空間，索引起來(lái)效率低，需要從頭開始尋找。

注意：列表的增刪如果是在隊(duì)伍當(dāng)中，那么相對(duì)效率比較低，但是如果在尾部增刪，效率很快。鏈表還分為單向和雙向，表示索引方向

??擴(kuò)展： 下面是其他基于列表 / 鏈表特性的實(shí)現(xiàn)：

1. queue：隊(duì)列(一般是從隊(duì)首或者隊(duì)尾獲取數(shù)據(jù)) 分為：先進(jìn)先出隊(duì)列 和 先進(jìn)后出隊(duì)列 及 優(yōu)先級(jí)隊(duì)列
2. stack：棧。后進(jìn)先出的就被叫做棧(主要應(yīng)用于函數(shù)的壓棧)

2.3. 列表的查詢

??列表提供了很多的方法，使我們可以方便的對(duì)它進(jìn)行查詢、統(tǒng)計(jì)等操作。

# 基本用法

L.index(value, [start, [stop]]) --> integer 
# 在列表中獲取傳入元素的索引值，如果元素不存在，會(huì)報(bào)異常，如果存在多個(gè)，只返回找到的第一個(gè)匹配元素的索引值，其中 start，stop 為表示查找區(qū)間，默認(rèn)為整個(gè)列表

L.count(value) --> integer 
# 統(tǒng)計(jì)傳入元素在列表中出現(xiàn)的次數(shù)并返回

??index 和 count 的時(shí)間復(fù)雜度都是 O(n), 都會(huì)遍歷列表，即隨著列表的規(guī)模增加，效率會(huì)依次下降。
??什么是時(shí)間復(fù)雜度？這是在計(jì)算算法優(yōu)劣時(shí)的主要參考值，我們主要使用大寫的 O 來(lái)表示時(shí)間復(fù)雜度，由于 index 和 count 函數(shù)都需要遍歷列表，所以如果這個(gè)列表有 n 個(gè)元素的話，那么它的時(shí)間復(fù)雜度就為 O(n), 詳細(xì)的解釋，建議自行搜索了解，這里知道這樣表示即可。
??由于 list[1] 通過(guò)偏移量進(jìn)行快速數(shù)據(jù)訪問(wèn)，可以理解為一步到位，所以這種方式的時(shí)間復(fù)雜度為 O(1)，不會(huì)隨著規(guī)模增大而改變。

In : lst    
Out: [1, 2, 3, 1, 2, 3, 3, 2, 4, 5, 7]

In : lst.index(3)   # 獲取元素 3 的索引值    
Out: 2

In : lst.count(2)   # 統(tǒng)計(jì)元素 2 出現(xiàn)的次數(shù)       
Out: 3

??擴(kuò)展： 如果我們要獲取列表的元素總數(shù)，我們需要怎么設(shè)計(jì)呢？

1. 設(shè)計(jì)一個(gè)獲取元素總量的函數(shù)，當(dāng)調(diào)用時(shí)，對(duì)列表進(jìn)行遍歷獲取元素的總數(shù)，并返回值
2. 設(shè)置一個(gè)計(jì)數(shù)器，隨著元素的增加和減少對(duì)計(jì)數(shù)器進(jìn)行修改

??很明顯第一個(gè)方法的時(shí)間復(fù)雜度是 O(n)，而第二個(gè)方法由于事先存儲(chǔ)著列表元素的總數(shù)，所以它的時(shí)間復(fù)雜度是 O(1)，列表使用的就是方式 2，而通過(guò) Python 內(nèi)置的 len 函數(shù) 就可以獲取列表內(nèi)元素的個(gè)數(shù)(不僅僅針對(duì)列表，其他元素也可以)

In : lst    
Out: [1, 2, 3, 1, 2, 3, 3, 2, 4, 5, 7]

In : len(lst)  # 獲取列表內(nèi)元素的個(gè)數(shù)
Out: 11 

2.4. 列表元素修改

??我們使用索引可以獲取列表中對(duì)應(yīng)索引位置的元素，同時(shí)我們也可以通過(guò)索引直接將對(duì)應(yīng)索引位的元素進(jìn)行修改

In : lst    
Out: [1, 2, 3, 1, 2, 3, 3, 2, 4, 5, 7]

In : lst[2] = 100      

In : lst
Out: [1, 2, 100, 1, 2, 3, 3, 2, 4, 5, 7]

需要注意的是，索引不要越界，否則會(huì)報(bào)異常

2.5. 列表的追加和插入

??列表提供了對(duì)其進(jìn)行追加或插入的函數(shù)，即 append 和 insert。先來(lái)看看這兩個(gè)函數(shù)的使用方法。

L.append(object) --> None # 接受一個(gè)元素，用于追加到列表的末尾。

L.insert(index, object) --> None # 接受兩個(gè)變量：索引，元素。在列表中指定的索引位置插入元素。

??說(shuō)明：

1. 列表尾部追加元素時(shí)，append 的返回值是 None，會(huì)直接對(duì)原列表進(jìn)行操作（就地修改），對(duì)應(yīng)的時(shí)間復(fù)雜度是 O(1)
2. 列表插入元素時(shí)，與 append 相同，返回 None，直接對(duì)原列表進(jìn)行操作（就地修改），對(duì)應(yīng)的時(shí)間復(fù)雜度是 O(n), 因?yàn)樵诹斜硎撞坎迦朐貢r(shí)，會(huì)使其他元素整體移動(dòng)。當(dāng)索引超界時(shí)會(huì)有如下兩種情況
   • 超越上界，尾部追加
   • 超越下界，首部追加

In : lst                  
Out: [1, 2, 3]

In : lst.insert(-500,500) 

In : lst               
Out: [500, 1, 2, 3]

In : lst.insert(500,500) 

In : lst               
Out: [500, 1, 2, 3, 500]  

??很多場(chǎng)景下我們對(duì)列表操作不是一個(gè)一個(gè)元素的追加，更多的時(shí)候，我們可能需要的是批量的操作，列表提供了一個(gè) extend 函數(shù)用于滿足這種需求。

L.extend(iterable) --> None # 從一個(gè)可迭代對(duì)象中把元素?cái)U(kuò)展追加到當(dāng)前列表中

??說(shuō)明：

1. extend 直接操作原列表，所以其返回值為 None
2. 如果擴(kuò)展的可迭代對(duì)象過(guò)于大，那么可能會(huì)引起 GC 進(jìn)行內(nèi)存整理，因?yàn)閿U(kuò)充起來(lái)的元素，有可能會(huì)比當(dāng)前列表所申請(qǐng)的內(nèi)存空間更大。建議少用
3. 擴(kuò)充列表還有其他方法比如列表相 +, 列表相 *, 當(dāng)使用這兩種方式會(huì)返回新的列表，不會(huì)修改原列表

# extend

In : lst                  
Out: [500, 1, 2, 3, 500]

In : lst.extend('abc')    

In : lst               
Out: [500, 1, 2, 3, 500, 'a', 'b', 'c']

# 列表相 +, 列表相 *

In : lst                  
Out: [500, 1, 2, 3, 500]

In : lst + ['a','b','c']         
Out: [500, 1, 2, 3, 500, 'a', 'b', 'c']

In : lst * 2              
Out: [500, 1, 2, 3, 500, 500, 1, 2, 3, 500]

??注意：使用 + 進(jìn)行列表拼接的時(shí)候，由于返回了新的列表，原來(lái)相加的兩個(gè)列表可能就沒有用了，而如果這兩個(gè)列表非常大，那么等于重復(fù)占用了新的內(nèi)存空間，內(nèi)存資源很寶貴，省著點(diǎn)用

2.6. 列表使用 * 重復(fù)帶來(lái)的問(wèn)題

??我們使用 * 可以快速的生成一些特定的列表形式，比如我需要一個(gè) 6 個(gè)元素的列表，每個(gè)元素的值為 1，我就可以這樣寫 lst = [1]; lst * 6，這樣寫的確沒什么問(wèn)題，但是在某些場(chǎng)景下會(huì)產(chǎn)生意想不到的問(wèn)題，比如在列表嵌套的時(shí)候。

In : lst = [[1,2,3]]      

In : lst1 = lst * 3       

In : lst1                 
Out: [[1, 2, 3], [1, 2, 3], [1, 2, 3]]

In : lst1[1][1] = 20     

In : lst1             
Out: [[1, 20, 3], [1, 20, 3], [1, 20, 3]]

??有沒有發(fā)現(xiàn)什么問(wèn)題？我明明修改的是 lst1 的第二個(gè)元素的第二個(gè)值為 20，為什么全都改變了？這是因?yàn)樵诹斜硎且粋€(gè)引用類型，lst 中實(shí)際上存儲(chǔ)的是 [1,2,3] 的內(nèi)存地址，而我們使用 * 3 的時(shí)候，等于復(fù)制了三份這個(gè)地址，所以 lst1 的 3 個(gè)元素，其實(shí)都指向了一個(gè)內(nèi)存地址，所以我們隨便修改一個(gè)元素，其他的也都會(huì)跟著被改變(畢竟是 1 個(gè)地址啊)，我們一般稱這種復(fù)制為 影子復(fù)制(shadow copy)，知道了原因，我們就可以想辦法解決了，既然你復(fù)制的是門牌號(hào)，那有沒有辦法復(fù)制門牌號(hào)里面的數(shù)據(jù)呢？答案當(dāng)然是可以的，我們使用 copy 模塊的 deepcopy 完成，它可以幫我們一層一層的找到元素真正的位置，然后進(jìn)行復(fù)制。我們稱 deepcopy 為深拷貝。

In : import copy          # 導(dǎo)入 copy 模塊    

In : lst                 
Out: [[1, 20, 3]]

In : lst1 = lst           # 復(fù)制一個(gè)新的列表                   

In : lst1[0][1] = 1000     # 對(duì)新列表進(jìn)行賦值              

In : lst1                
Out: [[1, 1000, 3]]       # 會(huì)同時(shí)影響 lst 和 lst1

In : lst                 
Out: [[1, 1000, 3]]

In : lst2 = copy.deepcopy(lst)     # 這里使用深 copy            

In : lst2                
Out: [[1, 1000, 3]]

In : lst2[0][1] == 2000   # 對(duì) lst2 進(jìn)行修改后，不會(huì)影響原列表，因?yàn)橐呀?jīng)把元素拷貝過(guò)來(lái)了      

In : lst2                
Out: [[1, 2000, 3]]

In : lst1                
Out: [[1, 1000, 3]]

In : lst                 
Out: [[1, 1000, 3]]

2.7. 刪除元素

??列表對(duì)象同時(shí)提供了專門的方法用于對(duì)列表元素進(jìn)行刪除：remove、pop、clear。

L.remove(value) --> None   # 刪除列表中匹配 value 的第一個(gè)元素

L.pop([index]) --> item   # 刪除并返回 index 對(duì)應(yīng)的 item, 索引超界拋出 IndexError 錯(cuò)誤，如果不指定 index, 默認(rèn)是列表的最后一個(gè)

L.clear() --> None   # 清空列表，不建議進(jìn)行操作，可以等待 GC 自行進(jìn)行銷毀

??當(dāng)我們使用 remove 和 pop 時(shí)，依然需要考慮 效率問(wèn)題，remove 刪除一個(gè)元素的時(shí)候，它首先要遍歷這個(gè)列表，查找到匹配的元素后移除，它的時(shí)間復(fù)雜度是 O(n)， 使用 pop 指定 index 刪除時(shí)，雖然可以 1 步定位到元素，但是如果刪除的列表是首部或者中間的元素，那么將會(huì)使列表中的后續(xù)數(shù)據(jù) 集體搬家， 但當(dāng)你使用 pop 不指定 index 時(shí)，它默認(rèn)會(huì)在列表的尾部刪除，這種操作的時(shí)間復(fù)雜度為 O(1)。所以建議如果需要頻繁的對(duì)列表進(jìn)行增刪改，建議使用鏈表類型，而如果需要頻繁的查或者只是從末尾彈出，就可以使用列表，因?yàn)檫@樣效率更高。

In : lst = [1,2,3,4]       

In : lst.remove(2)         

In : lst                   
Out: [1, 3, 4]

In : lst.pop()             
Out: 4

In : lst                   
Out: [1, 3]

In : lst.pop(1)            
Out: 3

In : lst                   
Out: [1]

In : lst.clear()           

In : lst                
Out: []

2.8. 其他操作

??當(dāng)我們的列表中存儲(chǔ)的是 int 類型的數(shù)據(jù)，而我們想要對(duì)其進(jìn)行排序，那么就可以使用列表的排序，當(dāng)我們想要判斷一個(gè)元素是否存在于列表中時(shí)，就可以使用成員判斷。
??in: 成員判斷，判斷元素是否在列表中 1 in [1,2,3]，由于要遍歷，所以它的時(shí)間復(fù)雜度為 O(n)

L.reverse()   # 原地反轉(zhuǎn)，原地將列表元素進(jìn)行反轉(zhuǎn)

L.sort(key=None, reverse=False) --> None   # 原地修改，對(duì)列表進(jìn)行排序，默認(rèn)升序

??sort 比較特別，它有兩個(gè)參數(shù)，其中 key 可以接受一個(gè)函數(shù)，使列表中的元素按照函數(shù)處理過(guò)后的類型進(jìn)行排序，默認(rèn)為空，即不處理。reverse 則有兩個(gè)值 True 和 False, 表示正序或者反序，默認(rèn)為 False 表示正序。

線性數(shù)據(jù)結(jié)構(gòu)的通病，找元素，需要進(jìn)行遍歷。

# 列表是順序結(jié)構(gòu)，但凡是順序不一致，那么兩個(gè)列表就不相等

In : l1 = [1,2,3,[4,5]] 
In : [4,5] in l1        
Out: True

In : [5,4] in l1      # 順序改變，所以不相等    
Out: False


In : lst = [2, 1 ,3 ,4 ,5]          
In : lst.reverse()        
In : lst                  
Out: [5, 4, 3, 1, 2]

In : lst.sort()           

In : lst                
Out: [1, 2, 3, 4, 5]

In : lst.sort(reverse=True)    # 就地修改      
In : lst                  
Out: [5, 4, 3, 2, 1]