列表

• 列表是内建的数据结构，用来存储一系列元素。

• 列表与字符串相同点：
  都支持索引（[]运算符）、切片（[:]）、拼接（+）、重复（*）、成员（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在有列表的情况下，依然需要元组这种不能更改的数据类型。这是因为，在项目尤其是多线程环境中，不变对象反而更被喜欢，它可以避免不必要的程序错误，更容易维护，也能够保证一个不变的对象是安全的。
• 即如果不需要对元素进行添加、删除、修改的时候，可以考虑使用元组，当然如果一个方法要返回多个值，使用元组也是不错的选择，元组在创建时间和占用的空间上面也都优于列表。