列表

• 列表是內建的數據結構，用來存儲一系列元素。

• 列表與字符串相同點：
  都支持索引（[]運算符）、切片（[:]）、拼接（+）、重復（*）、成員（in運算符）、長度（len()函數）和循環（for）操作。

• 不同點：
  列表使用[]生成，元素之間用逗號分離，字符串使用成對引號生成；
  列表可以包含多種類型的對象，字符串只能是字符；
  列表的內容是可變的，字符串一旦生成就不可變。

• 列表的可變性
  可以對列表中的任意元素進行重新賦值，如：lst[0] = ‘a’
  可以通過切片操作對子列表進行賦值，如：lst[0:2] = [1.2, 3, 5.6]
  可以在列表尾部追加元素或列表，如：lst.append(‘abc’)或lst.extend([‘a’, ‘s’])
  可以在任意位置插入元素，如：lst.insert(3, 100)，即在lst[3]處插入100
  可以刪除列表元素，如：lst.pop(3)，如括號內為空則刪除列表最后一個元素并將其返回；lst.remove(2)，即將2刪除無論其在什么地方
  可以對列表排序，如：lst.sort()
  可以將列表逆序，如：lst.reverse()

• 列表賦值：設a為一個列表，如果直接將b = a，不會生成新的列表，只會將b也指向a列表的存儲空間，這樣對b中的元素進行修改，也就相當于修改a中的元素。而寫成b = a[:]這種形式，相當于創建了新的列表b，對b的修改就不會影響到a。

列表作為函數參數

• 交換：需要交換a與b的值，單純使用swap函數依然與上文一樣，只是修改了指向，而將a與b放入列表中再交換，就能夠成功置換，代碼如下。

            
              def swap(lst, a, b):
    tmp = lst[a]
    lst[a] = lst[b]
    lst[b] = tmp
x = [10, 20, 30]
swap(x, 0, 1)
print(x)

            
          

• 查找：在列表中查找一個值，返回該值第一次出現的位置，如不存在則返回-1，可以使用列表.index()方法，這種方法下如果值不在列表中則會拋出異常，代碼如下。

            
              lst = [10, 5, 8, 13]
print(lst.index(8))

            
          

• 還可以使用二分查找的方法，相比于之前的線性查找方法，二分查找時間復雜度要更小，在大規模數據下運算更為方便，實現代碼如下。

            
              def bi_search(lst, x):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == x:
            return mid
        elif lst[mid] > x:
            high = mid - 1
        else:
            low = mid + 1
    return -1
lst = [5, 8, 10, 13]
print(bi_search(lst, 8))

            
          

• 時間復雜度
  量化一個算法的運行時間為輸入長度的函數；
  不需要顯式計算這些常數；
  用O表示，只保留高階項；
  時間復雜度用來做理論上的比較與判斷，不能提供實際運行時間，對于輸入規模較小的情況也不準確。

排序是計算機科學中常見且重要的任務，在此主要介紹選擇排序和冒泡排序。

• 選擇排序

方法一：找到最小的元素刪除它，并將其插入相應位置，對于剩余的元素重復這一操作，代碼示例如下。

            
              def selection_sort(lst):
    for i in range(len(lst)):
        min_index = i
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[min_index]:
                min_index = j
        lst.insert(i, lst.pop(min_index))
lst1 = [10, 5, 8, 13]
print(lst1)
selection_sort(lst1)
print(lst1)

            
          

方法二：找到最小的元素，和第一個元素交換，對于剩余的元素重復這一操作。即將插入方法insert換成交換函數swap，在下文代碼中有所體現。
選擇排序的時間復雜度：O（n^2）

• 冒泡排序

與選擇排序類似，但是每次遍歷不止交換一次，將最大或者最小的值排到最先或最后。
與選擇排序不同，一旦列表排好序，算法就可以停止，代碼示例如下。

            
              def swap(lst, i, j):
    tmp = lst[i]
    lst[i] = lst[j]
    lst[j] = tmp
def bubble_sort(lst):
    top = len(lst) - 1
    is_exchanged = True
    while is_exchanged:
        is_exchanged = False
        for i in range(top):
            if lst[i] > lst[i + 1]:
                is_exchanged = True
                swap(lst, i, i + 1)
        top -= 1
lst1 = [12, 10, 5, 8, 13]
bubble_sort(lst1)
print(lst1)

            
          

冒泡排序與選擇排序時間復雜度相同，但一般冒泡排序執行更快。
python中內建有排序函數sorted()（不改變原列表）和list.sort()（改變原列表）方法，該種算法使用快速排序，時間復雜度為O（nlogn）。

• 嵌套列表

示例：計算所有學生的平均分，代碼如下。

            
              students = [['zhang', 84], ['wang', 98], ['li', 76]]
s = 0
for student in students:
    s += student[1]
print(float(s) / len(students))

            
          

將所有學生成績，由高到低排序，可以使用key獲得列表的第二個值，代碼如下。

            
              students = [['zhang', 84], ['wang', 98], ['li', 76]]
def f(a):
    return a[1]
students.sort(key=f, reverse=True)
print(students)

            
          

• lambda函數：可以用來定義匿名函數，無法直接調用，可以將匿名函數再賦值給一個變量進行調用。事實上，這種調用會顯得比較麻煩，可以直接在函數或方法中使用lambda，如對上文排序就可以使用該函數簡化，代碼如下。

            
              students = [['zhang', 84], ['wang', 98], ['li', 76]]
students.sort(key=lambda x: x[1], reverse=True)
print(students)

            
          

• 列表解析或推導

一種由原列表創建新列表的簡潔方法，[表達式 for 變量 in 列表 if 條件]，如生成值為{x^2:x in {1…9}}的列表，就可以寫成lst = [x**2 for x in range(1, 10)]。
用列表推導實現求平均分，可以使用函數sum([x[1] for x in students]) / len(students)，代碼如下。

            
              students = [['zhang', 84], ['wang', 98], ['li', 76]]
print(float(sum([x[1] for x in students])) / len(students))

            
          

使用列表解析對所輸入數字x的因數求和，如輸入6，應顯示12，即1+2+3+6=12，可以使用sum([i for i in range(1, x+1) if x % i == 0])。

• 下面的代碼演示了如何定義列表、使用下標訪問列表元素以及添加和刪除元素的操作。

            
              def main():
    list1 = [1, 3, 5, 7, 100]
    print(list1)
    list2 = ['hello'] * 5
    print(list2)
    # 計算列表長度(元素個數)
    print(len(list1))
    # 下標(索引)運算
    print(list1[0])
    print(list1[4])
    # print(list1[5])  # IndexError: list index out of range
    print(list1[-1])
    print(list1[-3])
    list1[2] = 300
    print(list1)
    # 添加元素
    list1.append(200)
    list1.insert(1, 400)
    list1 += [1000, 2000]
    print(list1)
    print(len(list1))
    # 刪除元素
    list1.remove(3)
    if 1234 in list1:
        list1.remove(1234)
    del list1[0]
    print(list1)
    # 清空列表元素
    list1.clear()
    print(list1)


if __name__ == '__main__':
    main()

            
          

• 和字符串一樣，列表也可以做切片操作，通過切片操作我們可以實現對列表的復制或者將列表中的一部分取出來創建出新的列表，代碼如下所示。

            
              def main():
    fruits = ['grape', 'apple', 'strawberry', 'waxberry']
    fruits += ['pitaya', 'pear', 'mango']
    # 循環遍歷列表元素
    for fruit in fruits:
        print(fruit.title(), end=' ')
    print()
    # 列表切片
    fruits2 = fruits[1:4]
    print(fruits2)
    # fruit3 = fruits  # 沒有復制列表只創建了新的引用
    # 可以通過完整切片操作來復制列表
    fruits3 = fruits[:]
    print(fruits3)
    fruits4 = fruits[-3:-1]
    print(fruits4)
    # 可以通過反向切片操作來獲得倒轉后的列表的拷貝
    fruits5 = fruits[::-1]
    print(fruits5)


if __name__ == '__main__':
    main()

            
          

• 下面的代碼實現了對列表的排序操作。

            
              def main():
    list1 = ['orange', 'apple', 'zoo', 'internationalization', 'blueberry']
    list2 = sorted(list1)
    # sorted函數返回列表排序后的拷貝不會修改傳入的列表
    # 函數的設計就應該像sorted函數一樣盡可能不產生副作用
    list3 = sorted(list1, reverse=True)
    # 通過key關鍵字參數指定根據字符串長度進行排序而不是默認的字母表順序
    list4 = sorted(list1, key=len)
    print(list1)
    print(list2)
    print(list3)
    print(list4)
    # 給列表對象發出排序消息直接在列表對象上進行排序
    list1.sort(reverse=True)
    print(list1)


if __name__ == '__main__':
    main()

            
          

• 我們還可以使用列表的生成式語法來創建列表，代碼如下所示。

            
              import sys


def main():
    f = [x for x in range(1, 10)]
    print(f)
    f = [x + y for x in 'ABCDE' for y in '1234567']
    print(f)
    # 用列表的生成表達式語法創建列表容器
    # 用這種語法創建列表之后元素已經準備就緒所以需要耗費較多的內存空間
    f = [x ** 2 for x in range(1, 1000)]
    print(sys.getsizeof(f))  # 查看對象占用內存的字節數
    print(f)
    # 請注意下面的代碼創建的不是一個列表而是一個生成器對象
    # 通過生成器可以獲取到數據但它不占用額外的空間存儲數據
    # 每次需要數據的時候就通過內部的運算得到數據(需要花費額外的時間)
    f = (x ** 2 for x in range(1, 1000))
    print(sys.getsizeof(f))  # 相比生成式生成器不占用存儲數據的空間
    print(f)
    for val in f:
        print(val)


if __name__ == '__main__':
    main()

            
          

• 除了上面提到的生成器語法，Python中還有另外一種定義生成器的方式，就是通過yield關鍵字將一個普通函數改造成生成器函數。下面的代碼演示了如何實現一個生成斐波拉切數列的生成器。所謂斐波拉切數列可以通過下面遞歸的方法來進行定義：
  F0=0，F1=1，Fn=Fn-1+Fn-2(n>=2)
  

            
              def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
        yield a


def main():
    for val in fib(20):
        print(val)


if __name__ == '__main__':
    main()

            
          

---

元組

• 元組（Tuple）即不可變（inmutable）列表，除了可改變列表內容的方法外，其它方法均適用于元組。因而索引、切片、len()、print()等均可用，但append、extend、del等不可用。

• 使用“,”即可創建元組，也可在數據外整體加()，使用元組是為了保證列表內容不被修改。

• 元組賦值
  使用元組對兩個值進行交換，可以直接寫成 a, b = b, a，用此方法切分一個郵件地址，即可寫為：name, domain = ‘car@hit.edu.cn’.split(’@’)，即從@處將郵件地址切分為用戶名和域名。

• 函數和元組
  函數只能有一個返回值，但該值可以是一組值，例如一個元組。
  例如，同時返回列表中的最大和最小值，即可寫為：return max, min。

• DSU模式，即Decroate（裝飾）、Sort（排序）and Undecorate（反裝飾）模式。

例如，根據單詞長度對一個單詞列表進行排序，代碼如下。

            
              words = ['abc', 'defgh', 'df', 'lsefg']
# decroate裝飾，即定義空列表，并使用for循環將(單詞長度,單詞)元組作為元素填入列表
lst = []
for word in words:
    lst.append((len(word), word))
# sort排序，即對列表中元素進行從大到小順序排列
lst.sort(reverse=True)
# undecroate反裝飾，即生成新列表，忽略舊列表的長度信息，只獲得其單詞信息
res = []
for length, word in lst:
    res.append(word)
print(res)

            
          

也可以使用lambda函數對其進行排序，代碼如下。

            
              words = ['abc', 'defgh', 'df', 'lsefg']
words.sort(key=lambda x: len(x), reverse=True)
print(words)

            
          

• Python 的元組與列表類似，不同之處在于元組的元素不能修改，把多個元素組合到一起就形成了一個元組，所以它和列表一樣可以保存多條數據。下面的代碼演示了如何定義和使用元組。

            
              def main():
    # 定義元組
    t = ('駱昊', 38, True, '四川成都')
    print(t)
    # 獲取元組中的元素
    print(t[0])
    print(t[3])
    # 遍歷元組中的值
    for member in t:
        print(member)
    # 重新給元組賦值
    # t[0] = '王大錘'  # TypeError
    # 變量t重新引用了新的元組原來的元組將被垃圾回收
    t = ('王大錘', 20, True, '云南昆明')
    print(t)
    # 將元組轉換成列表
    person = list(t)
    print(person)
    # 列表是可以修改它的元素的
    person[0] = '李小龍'
    person[1] = 25
    print(person)
    # 將列表轉換成元組
    fruits_list = ['apple', 'banana', 'orange']
    fruits_tuple = tuple(fruits_list)
    print(fruits_tuple)


if __name__ == '__main__':
    main()

            
          

• python在有列表的情況下，依然需要元組這種不能更改的數據類型。這是因為，在項目尤其是多線程環境中，不變對象反而更被喜歡，它可以避免不必要的程序錯誤，更容易維護，也能夠保證一個不變的對象是安全的。
• 即如果不需要對元素進行添加、刪除、修改的時候，可以考慮使用元組，當然如果一個方法要返回多個值，使用元組也是不錯的選擇，元組在創建時間和占用的空間上面也都優于列表。