Python演算法的分享（一）

Python

Python是一門現代、易學、面向物件的編程語言，它擁有強大的內建資料型別以及簡單易用的控制陳述句，由于Python是一門解釋型語言，因此只需要查看和描述互動式會話就能進行學習，你應該記得，解釋器會顯示提示符>>>，然后計算你提供的Python陳述句，例如，以下代碼顯示了提示符、print函式、結果，以及下一個提示符，

>>> print("Algorithms and Data Structures")
>>> Algorithms and Data Structures
>>>

資料

前面提到，Python支持面向物件編程范式，這意味著Python認為資料是問題解決程序中的關鍵點，在Python以及其他所有面向物件編程語言中，類都是對資料的構成（狀態）以及資料能做什么（行為）的描述，由于類的使用者只能看到資料項的狀態和行為，因此類與抽象資料型別是相似的，在面向物件編程范式中，資料項被稱作物件，一個物件就是類的一個實體，

1內建原子資料型別

我們首先復習原子資料型別，Python有兩大內建資料類實作了整數型別和浮點數型別，相應的Python類就是int和float，標準的數學運算子，即+、-、*、/以及**（冪），可以和能夠改變運算優先級的括號一起使用，其他非常有用的運算子包括取余（取模）運算子%，以及整除運算子//，注意，當兩個整數相除時，其結果是一個浮點數，而整除運算子截去小數部分，只回傳商的整數部分，

>>> 2+3*4
14
>>> (2+3)*4
20
>>> 2**10
1024
>>> 6/3
2.0
>>> 7/3
2.3333333333333335
>>> 7//3
2
>>> 7%3
1
>>> 3/6
0.5
>>> 3//6
0
>>> 3%6
3
>>> 2**100
1267650600228229401496703205376
>>>

Python通過bool類實作對表達真值非常有用的布爾資料型別，布爾物件可能的狀態值是True或者False，布爾運算子有and、or以及not，

>>> True
True
>>> False
False
>>> False or True
True
>>> not (False or True)
False
>>> True and True
True

布爾物件也被用作相等（==）、大于（>）等比較運算子的計算結果，此外，結合使用關系運算子與邏輯運算子可以表達復雜的邏輯問題，表展示了關系運算子和邏輯運算子，

關系運算子和邏輯運算子

>>> 5 == 10
False
>>> 10 > 5
True
>>> (5 >= 1) and (5 <= 10)
True

識別符號在編程語言中被用作名字，Python中的識別符號以字母或者下劃線（_）開頭，區分大小寫，可以是任意長度，需要記住的一點是，采用能表達含義的名字是良好的編程習慣，這使程式代碼更易閱讀和理解，

當一個名字第一次出現在賦值陳述句的左邊部分時，會創建對應的Python變數，賦值陳述句將名字與值關聯起來，變數存的是指向資料的參考，而不是資料本身，來看看下面的代碼，

>>> theSum = 0
>>> theSum
0
>>> theSum = theSum + 1
>>> theSum
1
>>> theSum = True
>>> theSum
True

賦值陳述句theSum = 0會創建變數theSum，并且令其保存指向資料物件0的參考（如圖1-3所示），Python會先計算賦值運算子右邊的運算式，然后將指向該結果資料物件的參考賦給左邊的變數名，在本例中，由于theSum當前指向的資料是整數型別，因此該變數型別為整型，如果資料的型別發生改變（如圖1-4所示），正如上面的代碼給theSum賦值True，那么變數的型別也會變成布爾型別，賦值陳述句改變了變數的參考，這體現了Python的動態特性，同樣的變數可以指向許多不同型別的資料，

變數指向資料物件的參考

賦值陳述句改變變數的參考

2內建集合資料型別

除了數值類和布爾類，Python還有眾多強大的內建集合類，串列、字串以及元組是概念上非常相似的有序集合，但是只有理解它們的差別，才能正確運用，集（set）和字典是無序集合，

串列是零個或多個指向Python資料物件的參考的有序集合，通過在方括號內以逗號分隔的一系列值來表達，空串列就是[]，串列是異構的，這意味著其指向的資料物件不需要都是同一個類，并且這一集合可以被賦值給一個變數，下面的代碼段展示了串列含有多個不同的Python資料物件，

>>> [1,3,True,6.5]
[1, 3, True, 6.5]
>>> myList = [1,3,True,6.5]
>>> myList
[1, 3, True, 6.5]

注意，當Python計算一個串列時，這個串列自己會被回傳，然而，為了記住該串列以便后續處理，其參考需要被賦給一個變數，

由于串列是有序的，因此它支持一系列可應用于任意Python序列的運算，如表1-2所示，

可應用于任意Python序列的運算

需要注意的是，串列和序列的下標從0開始，myList[1:3]會回傳一個包含下標從1到2的元素串列（并沒有包含下標為3的元素），

如果需要快速初始化串列，可以通過重復運算來實作，如下所示，

>>> myList = [0] * 6
>>> myList
[0, 0, 0, 0, 0, 0]

非常重要的一點是，重復運算回傳的結果是序列中指向資料物件的參考的重復，下面的例子可以很好地說明這一點，

>>> myList = [1,2,3,4]
>>> A = [myList]*3
>>> A
[[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
>>> myList[2] = 45
>>> A
[[1, 2, 45, 4], [1, 2, 45, 4], [1, 2, 45, 4]]
>>>

變數A包含3個指向myList的參考，myList中的一個元素發生改變，A中的3處都隨即改變，

串列支持一些用于構建資料結構的方法，如表所示，后面的例子展示了用法，

Python串列提供的方法

>>> myList
[1024, 3, True, 6.5]
>>> myList.append(False)
>>> myList
[1024, 3, True, 6.5, False]
>>> myList.insert(2,4.5)
>>> myList
[1024, 3, 4.5, True, 6.5, False]
>>> myList.pop()
False
>>> myList
[1024, 3, 4.5, True, 6.5]
>>> myList.pop(1)
3
>>> myList
[1024, 4.5, True, 6.5]
>>> myList.pop(2)
True
>>> myList
[1024, 4.5, 6.5]
>>> myList.sort()
>>> myList
[4.5, 6.5, 1024]
>>> myList.reverse()
>>> myList
[1024, 6.5, 4.5]
>>> myList.count(6.5)
1
>>> myList.index(4.5)
2
>>> myList.remove(6.5)
>>> myList
[1024, 4.5]
>>> del myList[0]
>>> myList
[4.5]

你會發現，像pop這樣的方法在回傳值的同時也會修改串列的內容，reverse等方法則僅修改串列而不回傳任何值，pop默認回傳并洗掉串列的最后一個元素，但是也可以用來回傳并洗掉特定的元素，這些方法默認下標從0開始，你也會注意到那個熟悉的句點符號，它被用來呼叫某個物件的方法，myList.append(False)可以讀作“請求myList呼叫其append方法并將False這一值傳給它”，就連整數這類簡單的資料物件都能通過這種方式呼叫方法，

>>> (54).__add__(21)
75
>>>

在上面的代碼中，我們請求整數物件54執行其add方法（該方法在Python中被稱為__add__），并且將21作為要加的值傳給它，其結果是兩數之和，即75，我們通常會將其寫作54+21，稍后會更多地討論這些方法，

range是一個常見的Python函式，我們常把它與串列放在一起討論，range會生成一個代表值序列的范圍物件，使用list函式，能夠以串列形式看到范圍物件的值，下面的代碼展示了這一點，

>>> range(10)
range(0, 10)
>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> range(5,10)
range(5, 10)
>>> list(range(5,10))
[5, 6, 7, 8, 9]
>>> list(range(5,10,2))
[5, 7, 9]
>>> list(range(10,1,-1))
[10, 9, 8, 7, 6, 5, 4, 3, 2]
>>>

范圍物件表示整數序列，默認情況下，它從0開始，如果提供更多的引數，它可以在特定的點開始和結束，并且跳過中間的值，在第一個例子中，range(10)從0開始并且一直到9為止（不包含10）；在第二個例子中，range(5,10)從5開始并且到9為止（不包含10）；range(5,10,2)的結果類似，但是元素的間隔變成了2（10還是沒有包含在其中），

字串是零個或多個字母、數字和其他符號的有序集合，這些字母、數字和其他符號被稱為字符，常量字串值通過引號（單引號或者雙引號均可）與識別符號進行區分，

>>> "David"
'David'
>>> myName = "David"
>>> myName[3]
'i'
>>> myName*2
'DavidDavid'
>>> len(myName)
5
>>>

由于字串是序列，因此之前提到的所有序列運算子都能用于字串，此外，字串還有一些特有的方法，列舉了其中一些，

Python字串提供的方法

>>> myName
'David'
>>> myName.upper()
'DAVID'
>>> myName.center(10)
'  David   '
>>> myName.find('v')
2
>>> myName.split('v')
['Da', 'id']

split在處理資料的時候非常有用，split接受一個字串，并且回傳一個由分隔字符作為分割點的字串串列，在本例中，v就是分割點，如果沒有提供分隔字符，那么split方法將會尋找如制表符、換行符和空格等空白字符，

串列和字串的主要區別在于，串列能夠被修改，字串則不能，串列的這一特性被稱為可修改性，串列具有可修改性，字串則不具有，例如，可以通過使用下標和賦值操作來修改串列中的一個元素，但是字串不允許這一改動，

>>> myList
[1, 3, True, 6.5]
>>> myList[0]=2**10
>>> myList
[1024, 3, True, 6.5]
>>>
>>> myName
'David'
>>> myName[0]='X'

Traceback (most recent call last):
  File "<pyshell#84>", line 1, in -toplevel-
    myName[0]='X'
TypeError: object doesn't support item assignment
>>>

由于都是異構資料序列，因此元組與串列非常相似，它們的區別在于，元組和字串一樣是不可修改的，元組通常寫成由括號包含并且以逗號分隔的一系列值，與序列一樣，元組允許之前描述的任一操作，

>>> myTuple = (2,True,4.96)
>>> myTuple
(2, True, 4.96)
>>> len(myTuple)
3
>>> myTuple[0]
2
>>> myTuple * 3
(2, True, 4.96, 2, True, 4.96, 2, True, 4.96)
>>> myTuple[0:2]
(2, True)
>>>

然而，如果嘗試改變元組中的一個元素，就會遇到錯誤，請注意，錯誤訊息指明了問題的出處及原因，

>>> myTuple[1]=False
Traceback (most recent call last):
  File "<pyshell#137>", line 1, in -toplevel-
    myTuple[1]=False
TypeError: object doesn't support item assignment
>>>

集（set）是由零個或多個不可修改的Python資料物件組成的無序集合，集不允許重復元素，并且寫成由花括號包含、以逗號分隔的一系列值，空集由set()來表示，集是異構的，并且可以通過下面的方法賦給變數，

>>> {3, 6, "cat", 4.5, False}
{False, 4.5, 3, 6, 'cat'}
>>> mySet = {3, 6, "cat", 4.5, False}
>>> mySet
{False, 4.5, 3, 6, 'cat'}
>>>

盡管集是無序的，但它還是支持之前提到的一些運算，如下所示，

Python集支持的運算

>>> mySet
{False, 4.5, 3, 6, 'cat'}
>>> len(mySet)
5
>>> False in mySet
True
>>> "dog" in mySet
False
>>>

集支持一系列方法，如表1-6所示，在數學中運用過集合概念的人應該對它們非常熟悉，注意，union、intersection、issubset和difference都有可用的運算子，

Python集提供的方法

>>> mySet
{False, 4.5, 3, 6, 'cat'}
>>> yourSet = {99,3,100}
>>> mySet.union(yourSet)
{False, 4.5, 3, 100, 6, 'cat', 99}
>>> mySet | yourSet
{False, 4.5, 3, 100, 6, 'cat', 99}
>>> mySet.intersection(yourSet)
{3}
>>> mySet & yourSet
{3}
>>> mySet.difference(yourSet)
{False, 4.5, 6, 'cat'}
>>> mySet - yourSet
{False, 4.5, 6, 'cat'}
>>> {3,100}.issubset(yourSet)
True
>>> {3,100}<=yourSet
True
>>> mySet.add("house")
>>> mySet
{False, 4.5, 3, 6, 'house', 'cat'}
>>> mySet.remove(4.5)
>>> mySet
{False, 3, 6, 'house', 'cat'}
>>> mySet.pop()
False
>>> mySet
{3, 6, 'house', 'cat'}
>>> mySet.clear()
>>> mySet
set()
>>>

最后要介紹的Python集合是字典，字典是無序結構，由相關的元素對構成，其中每對元素都由一個鍵和一個值組成，這種鍵–值對通常寫成鍵:值的形式，字典由花括號包含的一系列以逗號分隔的鍵–值對表達，如下所示，

>>> capitals = {'Iowa':'DesMoines','Wisconsin':'Madison'}
>>> capitals
{'Wisconsin':'Madison', 'Iowa':'DesMoines'}
>>>

可以通過鍵訪問其對應的值，也可以向字典添加新的鍵–值對，訪問字典的語法與訪問序列的語法十分相似，只不過是使用鍵來訪問，而不是下標，添加新值也類似，

>>> capitals['Iowa']
'DesMoines'
>>> capitals['Utah']='SaltLakeCity'
>>> capitals
{'Utah':'SaltLakeCity', 'Wisconsin':'Madison', 'Iowa':'DesMoines'}
>>> capitals['California']='Sacramento'
>>> capitals
{'Utah':'SaltLakeCity', 'Wisconsin':'Madison', 'Iowa':'DesMoines', 'California':'Sacramento'}
>>> len(capitals)
4
>>>

需要謹記，字典并不是根據鍵來進行有序維護的，第一個添加的鍵–值對（‘Utah’:‘SaltLakeCity’）被放在了字典的第一位，第二個添加的鍵–值對（‘California’:‘Sacramento’）則被放在了最后，鍵的位置是由散列來決定的，第5章會詳細介紹散列，以上示例也說明，len函式對字典的功能與對其他集合的功能相同，

字典既有運算子，又有方法，表1-7和表1-8分別展示了它們，keys、values和items方法均會回傳包含相應值的物件，可以使用list函式將字典轉換成串列，在表1-8中可以看到，get方法有兩種版本，如果鍵沒有出現在字典中，get會回傳None，然而，第二個可選引數可以回傳特定值，

Python字典支持的運算

Python字典提供的方法

>>> phoneext={'david':1410, 'brad':1137}
>>> phoneext
{'brad':1137, 'david':1410}
>>> phoneext.keys()
dict_keys(['brad', 'david'])
>>> list(phoneext.keys())
['brad', 'david']
>>> phoneext.values()
dict_values([1137, 1410])
>>> list(phoneext.values())
[1137, 1410]
>>> phoneext.items()
dict_items([('brad', 1137), ('david', 1410)])
>>> list(phoneext.items())
[('brad', 1137), ('david', 1410)]
>>> phoneext.get("kent")
>>> phoneext.get("kent", "NO ENTRY")
'NO ENTRY'
>>>

推薦參考書籍：