## 03-1 Python資料結構 ###### - Python 小社課 - ###### **Gino** --- ## 資料結構介紹 ---- 當你需要紀錄1個朋友的電話號碼 -> 開1個變數 ---- 當你需要紀錄100個朋友的電話號碼 -> 開100個變數? ---- 當你需要紀錄全台灣$2 \times 10^{7}$人的電話號碼 -> 開$2 \times 10^{7}$個變數???!!?!? ----  **電話簿** ---- 像這樣把**很多資料綁在一起** 變成一個資料們的組合，統一管理 這樣的概念就是資料結構 ---- 而「**結構**」這個名稱 則是跟儲存這些資料的方法有關 ---- 例如： 把資料排成一排儲存 → 陣列 把資料用樹狀結構儲存 → 樹 --- ## Python內建資料結構 - **◆list◆** - tuple - set - dict --- ## list - 列表 **Python內建資料結構 - 1** ---- **特點** 1. 陣列的一種 2. 可任意變換調整大小 3. 一個list可以儲存任何東西，不一定要同個型態 ---- **備註** list中文翻譯：「鏈結串列」 **不同於陣列**的資料結構 但Python把類似陣列的資料結構叫做list 是很糟糕的翻譯 --- ### **list的用法** - **◆建立◆** - 取值 - 修改 - 檢查 - 遍歷 ---- ```python= a = [1, 2, 3, 4] a = list(1, 2, 3, 4) ``` 建立 ---- ```python= a = [1, '2', True, [3, 4, 5]] ``` list裡面可以塞任何東西，甚至另外一個list ---- ```python= a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] ``` **二維list** list裡面都是裝list ---- ```python= a = [2 for i in range(5)] # 2 2 2 2 2 a = [i for i in range(4)] # 0 1 2 3 a = [i*2 + 5 for i in range(3)] # 5 7 9 ``` 用for迴圈建立一個list 這個做法叫做**Comprehension** ---- 把一個整數list輸入進來 (Ex. 輸入為4 2 4 3) ```python= a = list(map(int, input().split(' '))) ``` 1. split(' ')會以空白符號當作隔板，把一個**字串切成好幾段** 2. map(**int**, ...)會把序列裡面的所有東西**變成int** 3. list()會把map處理好的序列變成一個list ----  --- ### **list的用法** - 建立 - **◆取值◆** - 修改 - 檢查 - 遍歷 ---- ```python= a = [1, 2, 3, 4] print(a[0]) # 1 print(a[2]) # 3 ``` 跟C++一樣，用中括號 第一個東西的索引值一樣是0 ---- ```python= a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] print(a[0][1]) # 2 print(a[2][0]) # 7 ``` **二維list取值** ---- ```python= a = [1, 2, 3, 4] print(a[-1]) # 4 print(a[-3]) # 2 ``` Python索引值可以是負的! ---- (不常用用法) ```python= a = [1, 2, 3, 4] x, y, z, w = a print(x, y, z, w) # 1 2 3 4 x, y, z = a # 錯誤 ``` 可以用變數接收list的每一項 注意，變數個數 = list長度 ---- (更奇怪用法) ```python= a = [1, 2, 3, 4] x, y, *z = a # 1, 2, [3, 4] x, *y, z = a # 1, [2, 3], 4 *x, y, z = a # [1, 2], 3, 4 ``` **請注意，\*不是指標！** 前面加\*代表其他變數取完值 剩下的廚餘(?)都會給這個變數 ---- Python超好用語法 - **slice** ---- **slice** 取得資料組裡面一段連續區間 a[開始:結束:間隔] - 開始: 預設是0 - 結束: 預設是最後一個(包含) - 間隔: 預設是1 (有沒有發現其實跟range一樣?) ---- ```python= a = [0, 1, 2, 3, 4, 5] print(a[2:4]) # 2 3 print(a[:4]) # 0 1 2 3 print(a[2:]) # 2 3 4 5 print(a[:]) # 0 1 2 3 4 5 print(a[::-1]) # 5 4 3 2 1 0 ``` --- ### **list的用法** - 建立 - 取值 - **◆修改◆** - 檢查 - 遍歷 ---- ```python= a = [0, 0, 0, 0] a[2] = 1 print(a) # 0, 0, 1, 0 ``` 直接修改 ---- ```python= a = [1, 2, 3, 4] a.append(5) # 1 2 3 4 5 a.extend([6, 7, 8]) # 1 2 3 4 5 6 7 8 a += [9, 10, 11] # 1 2 3 4 5 ... 9 10 11 ``` 新增 ---- ```python= a = [1, 3, 4, 5] a.insert(1, 2) # 1 2 3 4 5 ``` 插入2到a[1] 後面的資料會被往後擠 ---- ```python= a = [1, 2, 2.5, 3, 4, 5] a.pop() # 1 2 2.5 3 4 a.pop(2) # 1 2 3 4 a.remove(3) # 1 2 4 ``` 刪除 - pop: 刪除指定位置 - remove: 刪除指定資料 - 如果資料有重複 → 刪除第1個出現的 ---- ```python= a = [1, 2, 3, 4] a.clear() print(a) # [] del a print(a) # Error ``` - clear: 清空list - del: 刪除整個list ---- ```python= a = [1, 2, 3, 4] a.reverse() # 4, 3, 2, 1 ``` 原地反轉list ---- ```python= a = [1, 2, 3, 4] b = a[:] b = a.copy() b = [i for i in a] b = a # Not Suggested! ``` 複製一個list 不要用`b = a`! 詳細原因等等會介紹 --- ### **list的用法** - 建立 - 取值 - 修改 - **◆檢查◆** - 遍歷 ---- ```python= a = [1, 2, 3, 4] print(len(a)) # 4 ``` 取得長度 ---- ```python= a = [1, 2, 3, 4, 4, 4, 4] print(a.count(4)) # 4 print(a.index(4)) # 3 ``` - count: 檢查出現幾次 - index: 檢查第一次出現的位置 - 找不到就會發生錯誤 ---- ```python= a = [1, 2, 3, 4, 5] if 3 in a: print("YES") else: print("NO") # YES ``` 檢查資料有沒有出現 --- ### **list的用法** - 建立 - 取值 - 修改 - 檢查 - **◆遍歷◆** ---- ```python= a = [1, 2, 3, 4, 5] for i in range(len(a)): print(a[i]) # 1 2 3 4 5 ``` 用索引值遍歷 ---- ```python= a = [1, 2, 3, 4, 5] for i in a: print(i) # 1 2 3 4 5 ``` ---- #### enumerate() 函式 ---- ```python= a = ['a', 'b', 'c', 'd'] for item in enumerate(a): print(item) """ (0, 'a') (1, 'b') (2, 'c') (3, 'd') """ ``` enumerate - 枚舉 把a裡面的物件列舉出來 用括號包著 左邊是**索引值**，右邊是**物件** ---- ```python= a = ['a', 'b', 'c', 'd'] for index, item in enumerate(a): print(index, item) """ 0 'a' 1 'b' 2 'c' 3 'd' """ ``` 也可以用兩個變數，一個存索引值，另一個存物件 ---- ```python= a = ['a', 'b', 'c', 'd'] for index, item in enumerate(a, start=97): print(index, item) """ 97 a 98 b 99 c 100 d """ ``` 可以自己指定開始值，不一定是索引值 (補充:a的ascii碼是97, b是98, 依此類推) --- ### list的運作原理 ---- 還記得嗎? - list可以任意調整大小 - list可以儲存任何元素 - 複製list時不要用`a = b` 上面這些特性都跟list的運作原理有關! ---- **\我大指標/**  (可以動態調整大小其實跟C++的vector幾乎一樣) <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> --- ## Python內建資料結構 - list - **◆tuple◆** - set - dict --- ## tuple - 元組 **Python內建資料結構 - 2** ---- **特點** 1. 陣列的一種 2. **不能任意調整大小** 3. tuple**不能新增/修改刪除**某個物件， 建立tuple以後就不能再動 5. 一個tuple可以儲存任何東西，不一定要同型態 ---- **備註** 雖然tuple不能任意修改某個物件 但是tuple裡面有list的話仍可以修改那個list (這跟tuple的原理有關) --- ### **tuple的用法** - **◆建立◆** - 取值 - 檢查 - 遍歷 ---- **備註** tuple因為不能修改 所以能做的操作比list會少很多 而且能做的操作跟list的幾乎一樣 ---- ```python= a = 1, 2, 3, 4 a = (1, 2, 3, 4) a = tuple(1, 2, 3, 4) ``` 建立 可以不需要括弧 但是有括弧比較好看 ---- ```python= a = ((1, 2, 3), (4, 5, 6), (7, 8, 9)) ``` **二維tuple** tuple裡面都是裝tuple ---- ```python= a = tuple(2 for i in range(5)) # 2 2 2 2 2 a = tuple(i for i in range(4)) # 0 1 2 3 a = tuple(i*2 + 5 for i in range(3)) # 5 7 9 ``` 跟list一樣可以用for迴圈建立一個tuple (還記得嗎?這個做法叫做**Comprehension**) ---- ```python= a = (2 for i in range(3)) print(type(a)) ``` 注意，不可以只有括號，要使用tuple()函式 否則a不會是一個tuple而是一個generator (之後會教到什麼是generator :P) --- ### **tuple的用法** - 建立 - **◆取值◆** - 檢查 - 遍歷 ---- ```python= a = (1, 2, 3, 4) print(a[0]) # 1 print(a[2]) # 3 ``` 跟list一樣，用中括號 第一個東西的索引值一樣是0 ---- ```python= a = (1, 2, 3, 4) print(a[-1]) # 4 print(a[-3]) # 2 ``` Python索引值可以是負的 ---- (不常用用法) ```python= a = (1, 2, 3, 4) x, y, z, w = a print(x, y, z, w) # 1 2 3 4 x, y, z = a # 錯誤 ``` 跟list一樣，可以用變數接收tuple的每一項 注意，變數個數 = tuple長度 ---- (更奇怪用法) ```python= a = (1, 2, 3, 4) x, y, *z = a # 1, 2, (3, 4) x, *y, z = a # 1, (2, 3), 4 *x, y, z = a # (1, 2), 3, 4 ``` **請注意，\*不是指標！** 前面加\*代表其他變數取完值 剩下的廚餘(?)都會給這個變數 ---- ```python= a = (0, 1, 2, 3, 4, 5) print(a[2:4]) # 2 3 print(a[:4]) # 0 1 2 3 print(a[2:]) # 2 3 4 5 print(a[:]) # 0 1 2 3 4 5 print(a[::-1]) # 5 4 3 2 1 0 ``` 跟list一樣可以用slice --- tuple唯一能做的修改(至少我想到的) 只有刪除整個tuple ```python= a = (1, 2, 3, 4) del a ``` --- ### **tuple的用法** - 建立 - 取值 - **◆檢查◆** - 遍歷 ---- ```python= a = (1, 2, 3, 4) print(len(a)) # 4 ``` 取得長度 ---- ```python= a = (1, 2, 3, 4, 4, 4, 4) print(a.count(4)) # 4 print(a.index(4)) # 3 ``` - count: 檢查出現幾次 - index: 檢查第一次出現的位置 - 找不到就會發生錯誤 ---- ```python= a = (1, 2, 3, 4, 5) if 3 in a: print("YES") else: print("NO") # YES ``` 檢查資料有沒有出現 --- ### **tuple的用法** - 建立 - 取值 - 檢查 - **◆遍歷◆** ---- ```python= a = (1, 2, 3, 4, 5) for i in range(len(a)): print(a[i]) # 1 2 3 4 5 ``` 用索引值遍歷 ---- ```python= a = (1, 2, 3, 4, 5) for i in a: print(i) # 1 2 3 4 5 ``` ---- #### enumerate() 函式 ---- ```python= a = ('a', 'b', 'c', 'd') for item in enumerate(a): print(item) """ (0, 'a') (1, 'b') (2, 'c') (3, 'd') """ ``` enumerate - 枚舉 把a裡面的物件列舉出來 用括號包著 左邊是**索引值**，右邊是**物件** ---- ```python= a = ('a', 'b', 'c', 'd') for index, item in enumerate(a): print(index, item) """ 0 'a' 1 'b' 2 'c' 3 'd' """ ``` 也可以用兩個變數，一個存索引值，另一個存物件 ---- ```python= a = ('a', 'b', 'c', 'd') for index, item in enumerate(a, start=97): print(index, item) """ 97 a 98 b 99 c 100 d """ ``` 可以自己指定開始值，不一定是索引值 (補充:a的ascii碼是97, b是98, 依此類推) --- ### tuple的運作原理 ---- tuple的實作方式跟list幾乎一樣 只是他多了很多奇怪優化方式 - tuple不能做的事情很多，但是**速度比list快** ---- ### 結論 速度：tuple > list 便利性：list > tuple <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> <!-- ***************************************** --> --- ## 練習題 - 0026倒背如流(★★) - 0028墊底master(52分子題分)(★★★) - 0024社團點點名(★★★★) - 0029完美的序列(★★★★★) - 0025甜甜圈(★★★★★) 註：墊底master要拿100分需使用二分搜演算法 但前52分只要熟悉list就可以了！ <!-- 雜湊 --> <!-- set --> <!-- dict --> <!-- string -->