实用Python程序设计MOOC-第六章列表

[TOC]

实用Python程序设计MOOC-第六章列表

列表的操作

列表的增删和修改

• 列表可以增删元素，列表的元素可以修改，列表元素可以是任何类型

empty = []	#[]表示空表
list1 = ['Pku', 'Huawei', 1997, 2000];
list1[1] = 100 #列表元素可以赋值
print(list1)	#>>['Pku', 100, 1997, 2000]
del list1[2]	#删除元素
print(list1)	#>>['Pku', 100, 2000]
list1 += [100, 110]	#添加另一列表的元素100和110，在list1原地添加，没有新建一个列表
print(list1)	#>>['Pku', 100, 2000, 100, 110]
list1.append(200) #添加元素200,append用于添加单个元素，括号的内容被认为是一个元素
print(list1)	#>>['Pku', 100, 2000, 100, 110, 200]
list1.append(['ok', 123])	#添加单个元素
print(list1)	#>>['Pku', 100, 2000, 100, 110, 200, ['ok', 123]]

a = ['a', 'b', 'c']
n = [1, 2, 3]
x = [a, n]	#a若变，x也变
a[0] = 1
print(x)	#>>[[1, 'b', 'c'], [1, 2, 3]]
print(x[0])	#>>[1, 'b', 'c']
print(x[0][1])	#>>b

列表相加

• 列表相加可以得到新的列表

a = [1, 2, 3, 4]
b = [5, 6]
c = a + b
print(c)	#>>[1, 2, 3, 4, 5, 6]
a[0] = 100	#此时c已经是新建的列表，并没有和a建立联系，所以和a没有关系
print(c)	#>>[1, 2, 3, 4, 5, 6]

列表和+=

• 对列表来说，a += b 和a = a + b不同

b = a = [1, 2]
a += [3]	#b和a指向相同地方,在a末尾添加元素,b也受影响
print(a, b)	#>>[1, 2, 3] [1, 2, 3]

a = a + [4, 5] #对a重新赋值,不会影响到b
print(a)	#>>[1, 2, 3, 4, 5]
print(b)	#>>[1, 2, 3]

列表乘法

print([True] * 3)	#>>[True, True, True]
a = [1, 2]
b = a * 3
print(b)	#>>[1, 2, 1, 2, 1, 2]

print([a * 3])	#>>[[1, 2, 1, 2, 1, 2]]

c = [a] *3
print(c)	#>>[[1, 2], [1, 2], [1, 2]]

a.append(3)
print(c)	#>>[[1, 2, 3], [1, 2, 3], [1, 2, 3]]
print(b)	#>>[1, 2, 1, 2, 1, 2]

重点题目

a = [[0]] * 2 + [[0]] * 2	#>>[[0], [0], [0], [0]]
a[0][0] = 5
print(a)	#>>[[5], [5], [0], [0]]

列表的切片

• 列表的切片返回新的列表，用法和字符串切片相同

a = [1, 2, 3, 4]
b = a[1:3]
print(b)	#>>[2, 3]
b[0] = 100
print(b)	#>>[100，3]
print(a)	#>>[1, 2, 3, 4]
print(a[::-1]) #>>[4, 3, 2, 1]
print([1, 2, 3, 4, 5, 6] [1:5:2])	#[2, 4]

列表的遍历

lst = [1, 2, 3, 4]
for x in lst:
	print(x, end = " ")
	x = 100	#不会修改列表的元素
print(lst)	#>>[1, 2, 3, 4]

for i in range(len(lst)):
	lst[i] = 100
print(lst)	#[100, 100, 100, 100]

列表比大小

• 两个列表比大小，就是逐个元素比大小，直到分出胜负。
• 如果有两个对应元素不可比大小，则出runtime error。

print([1, 'a', 12] < [1, 'b', 7])	#>>True
print([1, 'a'] < [1, 'a', 13])	#>>True
print([2, 'a'] > [1, 'b', 13])	#>>True
print([2, 'a'] < ['ab' , 'b', 13])	#runtime error

列表应用例题:校门外的树

某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，…. L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树(包括区域端点处的两棵树)移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

• 输入
  第一行有两个整数L(1<=L<=10000)和M(1<=M<=100)，L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

• 输出
  包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

• 样例输入

  500 3
  150 300
  100 200
  470 471

• 样例输出
  298

• 代码

s = input().split()
L, M = int(s[0]), int(s[1])
good = [True] * (L + 1) #good[i] 为True表示坐标i的树还在

for i in range(M):
    s = input().split()
    start, end = int(s[0]), int(s[1])
    for k in range(start, end + 1):
            good[k] = False #坐标k处的树被移走了

print(sum(good))    #sum是python函数，可以求列表元素和，True是1，False是0

列表的朴素排序

如果有N个元素需要排序，那么首先从N个元素中找到最小的那个(称为第0小的)放在第0个位子上(和原来的第0个位子上的元素交换位置)，然后再从剩下的N-1个元素中找到最小的放在第1个位子上，然后再从剩下的N-2个元素中找到最小的放在第2个位子…..直到所有的元素都就位。

选择排序

def SelectionSort(a): #选择排序
	#将列表a从小到大排序
	n = len(a)
	for i in range(n - 1):	#每次从a[i]及其右边的元素里选出最小的，放在a[i]这个位置
		for j in range(i, n):	#依次考察a[i]及其右边元素
			if a[i] > a[j]:
				a[i], a[j] = a[j], a[i]
lst = [1, 12, 4, 56, 6, 2]
SelectionSort(lst)	#>>[1，2，4，6，12，56]
print(lst)

选择排序：时间复杂度 $ O(n^2) $，即对有n个元素的列表(数组)，需要做 $ n^2 $ 次比较
冒泡排序、插入排序时间复杂度都是$ O(n^2) $

好的排序算法，比如归并排序，快速排序，复杂度是$ O(nlog(n)) $
python自带的排序功能，复杂度是$ O(nlog(n)) $
可以认为排序这件事，复杂度就是$ O(n*log(n)) $

用排序函数对简单列表排序

简单顺序排序

• a.sort()可以对列表a从小到大排序，改变a的内存结构
• sorted(a)返回a经过从小到大排序后的新列表，a不变，创建新的列表

a = [5, 7, 6, 3, 4, 1, 2]
a.sort()	#[1, 2, 3, 4, 5, 6, 7]
a = [5, 7, 6, 3, 4, 1, 2]
b = sorted(a)	#b:[1, 2, 3, 4, 5, 6, 7], a不变
a = [25, 7, 16, 33, 4, 1, 2]
a.sort(reverse = True)	#[33, 25, 16, 7, 4, 2, 1]
b = sorted(a, reverse = True)	#[33, 25, 16, 7, 4, 2, 1]

默认多组对比顺序排列

元组比大小是按照元组需要比较

students = [('John', 'A', 15),	#姓名, 成绩, 年龄
			('Mike', 'C', 19),
			('Mike', 'B', 12),
			('Mike', 'C', 18),
			('Bom', 'D', 10)]
students.sort()	#先按姓名, 再按成绩, 再按年龄排序
print(students)	#>>[('Bom', 'D', 10), ('John', 'A', 15), ('Mike', 'B', 12), ('Mike', 'C', 18), ('Mike', 'C', 19)]

自定义比较排序

自定义比较函数key
比较的不是元素本身，而是元素调用key的函数得到的返回值。

def myKey(x): #自定义比较函数
	return x % 10

a = [25, 7, 16, 33, 4, 1, 2]
a.sort(key = myKey)
# key是函数, sort按对每个元素调用该函数的返回值从小到大排序
# [1, 2, 33, 4, 25, 16, 7]按个位数排序

sorted("This is a test string from Andrew".split(), key = str.lower)
# ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']不区分大小写排序

复杂列表的自定义排序

• 用不同关键字排序

students = [('John', 'A', 15), #姓名，成绩，年龄
			('Mike', 'B', 12),
			('Mike', 'C', 18),
			('Bom', 'D', 10)]

students.sort(key = lambda x : x[2]) #按年龄排序
#[('Bom', 'D', 10), ('Mike', 'B', 12), ('John', 'A', 15), ('Mike', 'C', 18)]
students.sort(key = lambda x : x[0]) #按姓名排序
#[('Bom', 'D', 10), ('John', 'A', 15), ('Mike', 'B', 12), ('Mike', 'C', 18)]

Iambda表达式

lambda x : x[2]

表示一个函数，参数是x，返回值是x[2]

k = lambda x, y : x + y #k是一个函数，参数是x, y, 返回值是x+y.
print(k(4, 5))	#>>9

当关键字相同，排序前哪个在前面，排完之后就在前

多级排序

def f(x):
	return (-x[2], x[1], x[0])
students = [('John', 'A', 15), ('Mike', 'C', 19), ('Wang', 'B', 12), ('Mike'，'B', 12), ('Mike', 'C', 12), ('Mike', 'C', 18), ('Bom', 'D', 10)]
students.sort(key = f)	#先按年龄从高到低，再按成绩从高到低，再按姓名字典序
print(students)	#>>[('Mike', 'C', 18), ('John', 'A', 15), ('Mike', 'B', 12), ('Wang', 'B', 12)，( 'Mike', 'C', 12)，('Bom'，'D'， 10) ]

Python元组的排序

• 元组不能修改，因此无sort函数，可以用sorted得到新的排序后的列表

def f(x):
	return (-x[2], x[1], x[0])
students = (('John', 'A', 15), ('Mike', 'C', 19), ('Wang', 'B', 12),('Mike', 'B', 12), ('Mike', 'C', 12), ('Mike', 'C', 18), ('Bom', 'D', 10))	#students是元组

print(sorted(students, key = f))	#sorted的结果是列表
#>>[('Mike', 'C', 19), ('Mike', 'C', 18), ('John', 'A', 15), ('Mike', 'B', 12), ('Wang', 'B', 12), ('Mike', 'C', 12), ('Bom', 'D', 10)]

列表相关函数

append(x)添加元素x到尾部
extend(x)添加列表x中的元素到尾部
insert(i,x)将元素x插入到下标i处
remove(x)删除元素x
del(i)删除下标为i的元素
reverse()颠倒整个列表
index(x)查找元素x，找到则返回第一次出现的下标，找不到则引发异常

a, b = [1, 2, 3], [5, 6]
a.append(b)
print(a)	#>>[1, 2, 3, [5, 6]]

b.insert(1, 100)
print(a)	#>>[1, 2, 3, [5, 100, 6]]

a.extend(b)
print(a)	#>>[1, 2, 3, [5, 100, 6], 5, 100, 6]

a.insert(1, 'K')
print(a)	#>>[1, 'K', 2, 3, [5, 100, 6], 5, 100, 6]

a.insert(3, 'K')
print(a)	#>>[1, 'K', 2, 'K', 3, [5, 100, 6], 5, 100, 6]

a.remove('K')	#只会删掉第一个K
print(a)	#>>[1, 2, 'K', 3, [5, 100, 6], 5, 100, 6]

a.reverse()
print(a)	#>>[6, 100, 5, [5, 100, 6], 3, 'K', 2, 1]

print(a.index('K'))	#>>5
try:
	print(a.index('m')) #找不到'm',会引发异常
except Exception as e:
	print(e)	#>>'m' is not in list

列表映射

• map(function, sequence)， 可用于将一个序列（列表、元组、集合…）映射到另一个序列
• 返回一个延时求值对象，可以转换成list, tuple, set…

def f(x):
	print(x, end="")
	return x * x

a = map(f, [1, 2, 3])
print(list(a))	#>>123[1, 4, 9]

#a延时操作已经没有结果了
print(tuple(a))	#>>()

#一般是执行中进行
a = list(map(lambda x : 2 * x, [2, 3, 4]))
print(a)	#>>[4, 6, 8]

• map用于输入

x, y, z = map(int, input().split())
print(x, y, z)

输入:1 23 45
输出:1 23 45

列表过滤

• filter(function, sequence)，抽取序列中令function(x)为True的元素x
• 返回一个延时求值对象，可以转换成list, tuple, set…

def f(x):
	return x % 2 == 0

lst = tup1e(filter(f, [1, 2, 3, 4, 5]))	#抽取出偶数
print(lst)	#>>(2, 4)

列表生成式

[x * x for x in range(1, 11)]
#=>[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

[x * x for x in range(1, 11) if x % 2 == 0]
#=>[4, 16, 36, 64, 100]

[m + n for m in 'ABC' for n in 'XYZ']
#=>['AX', 'AY', 'AZ', 'BX', 'BY', 'BZ', 'CX', 'CY', 'CZ']

[[m + n for m in 'ABC'] for n in 'XYZ']
#=>[['AX', 'BX', 'CX'], ['AY', 'BY', 'CY'], ['AZ', 'BZ', 'CZ']]

L = ['Hello', 'World', 18, 'Apple', None]
[s.lower() for s in L if isinstance(s, str)]
#=>['hello', 'world', 'apple']

[s for s in L if isinstance(s, int)]
#=>[18]

元组生成式

print(tuple(x * x for x in range (1, 11)))
#>>(1, 4, 9, 16, 25, 36, 49, 64, 81, 100)

二维列表

• 二维列表a可以看作是矩阵，a[i][j]就是第i行第j列的元素

• 错误生成二维列表的方法

a = [0, 0, 0]
b = [a] * 3	#b有三个元素，都是指针，都和a指向同一地方
print(b)	#>>[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

b[0][1] = 1
a[2] = 100
print(b)	#>>[[0, 1, 100], [0, 1, 100], [0, 1, 100]]

• 正确生成二维列表的方法

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix)	#>>[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix[1][2], matrix[2][2])	#>>6 9

matrix[1][1] = 100
print(matrix)	#>>[[1, 2, 3], [4, 100, 6], [7, 8, 9]]

matrix = [[0 for i in range(3)] for i in range (3)]
print(matrix)	#>>[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

matrix = [[i * 3 + j for j in range(3)] for i in range (3) ]
print(matrix)	#>>[[0, 1, 2], [3, 4, 5]]

• 生成一个3行4列的矩阵，所有元素都是0

lst = []
for i in range(3):
	lst.append([0] * 4)
lst[0][0] = lst[2][3] = 100
for i in range(3):
	for j in range(4):
		print(lst[i][j], end = " ")
	print("")

100 0 0 0
0 0 0 0
0 0 0 100

matrix = ((1, 2, 3), (4, 5, 6), (7, 8, 9))
print(matrix)	#>>((1, 2, 3), (4, 5, 6), (7, 8, 9))

matrix = tuple(tuple(0 for i in range(3)) for i in range(3))
print(matrix)	#>>((0, 0, 0), (0, 0, 0), (0, 0, 0))

列表拷贝

a = [1, 2, 3, 4]
b = a[:]	#是a的拷贝,b和a不是同一个对象,指向不同东西
b[0] = 5
print(a)	#[1, 2, 3, 4]
print(b)	#[5, 2, 3, 4]

b += [10]
print(a)	#[1, 2, 3, 4]
print(b)	#[5, 2, 3, 4, 10]

列表深拷贝

• 列表浅拷贝

a = [1, [2]]
b = a[:]
b.append(4)
print(a)	#>>[1, [2]]
print(b) #>>[1, [2], 4]

a[1].append(3)
print(a) #>>[1, [2, 3]] 
print(b) #>>[1, [2, 3], 4]

未能进行深拷贝!

浅拷贝：只拷贝指针，并没有拷贝指针指向的内容
深拷贝：不仅拷贝指针，还拷贝指针指向的内容

• 列表深拷贝

import copy

a= [1, [2]]
b = copy.deepcopy(a)
b.append(4)
print(a)	#>>[1, [2]]
print(b)	#>>[1, [2], 4]

a[1].append(3)
print(a)	#>>[1, [2, 3]]
print(b)	#>>[1, [2], 4]

元组和列表互转

a = [1, 2, 3]
b = tuple(a)	#b:(1,2,3)
c = list(b)	#c:[1,2,3]

t = (1, 3, 2)
(a, b, c) = t	#a=1, b=3, c=2

s = [1, 2, 3]
[a, b, c] = s	#a=1, b=2, c=3

元组、列表和字符串互转

print(list("he1lo"))	#>>['h', 'e', 'l', 'l', 'o'] 
print("".join(['a', '44', 'c']))	#>>a44c
print (tup1e ("hello") )	#>>('h', 'e', 'l', 'l', 'o')
print("".join(('a', '44', 'c'))) #>>a44c