Python程序设计——列表

一、引言

关键点：一个列表可以存储任意大小的数据集合。

        程序一般都需要存储大量的数值。假设，举个例子，需要读取100个数字，计算出它们的平均值，然后找出多少个数字是高于这个平均值的。程序首先读取100个数字并计算它们的平均值，然后把每个数字和平均值进行比较来确定它是否超过了平均值。为了完成这个任务，这些数字都必须存储在变量内。为了这样做，你必须创建100个变量并且重复编写几乎同样的一段代码100次。显然，编写一个这样的程序是不切实际的。因此，这个问题该怎么，解决?

        我们需要一个高效、条理的方式。Python 提供了一种被称为列表的数据类型，它可以存储一个有序的元素集合。

二、列表基础

关键点：列表是一个用list类定义的序列，它包括了创建、操作和处理列表的方法。列表中的元素可以通过下标来访问。

2.1 创建列表

list类定义了列表。为了创建一个列表，可以使用list的构造方法，如下所示:

list1 = list() # Create an empty list
list2 = list([2，3，4]) # Create a list with elements 2，3，4
list3 = list(["red"， "green"， "blue"]) # Create a Tist with strings
list4 = list(range(3， 6)) # Create a list with elements 3， 4，5
list5 = list("abcd") # Create a list with characters a，b，C，d

也可以使用下面这个更简单一些的语法来创建列表:

listl = [] # Same as 1ist()
list2 = [2，3，4] # Same as list([2，3，4])
list3 = ["red"， "green"] # Same as list(["red", "green"])

列表中的元素用逗号分隔并且由一对中括号([ ])括住。

注意：一个列表既可以包含同样类型的元素也可以包括不同类型的元素。例如，下面的列表也是可以的：

list4 =[2, "three", 4]

2.2 列表是一种序列类型

        Python中的字符串和列表都是序列类型。一个字符串是一个字符序列，而一个列表则是任何元素的序列。序列的常用操作被总结在表10-1 中。对字符串的序列操作同样适用于列表。

2.3 列表使用的函数

        一些Python内嵌函数可以和列表一起使用。可以使用len函数返回列表的元素个数,使用max/min函数返回列表中的最大值元素和最小值元素，而sum函数返回列表中所有元素之和。还可以使用random模块中的shuffle函数随意排列列表中的元素。下面是一些例子:

>>> list1 = [2， 3，4，1，32]
>>> len(list1)
5
>>> max(list1)
32
>>> min(list1)
1
>>> sum(list1)
42
>>> import random
>>> random.shuffle(list1) # Shuffle the elements in 1ist1
>>> list1
[4，1，2，32，3]
>>>

2.4 下标运算符[ ]

一个列表中的元素都可以使用下面的语法通过下标操作符访问：

myList[index]

列表下标是基于0的，也就是说，下标的范围从0到len(myList)-1,如图10-1 中阐述：myList[index]可以像变量一样使用，所以它也被称为下标变量。例如:下面的代码将myList[0]与myList[1]中的值相加并赋给myList[2]。

myList[2] = myList[0] + myList[1]

下面的循环将0赋值给myList[0]、将1赋值给myList[1]、...、将9赋值给myList[9]：

警告：越界访问列表是一个常见的程序设计错误，它会导致一个运行时的“IndexError” 。为了避免这种错误，要确保没有使用超出len(myList)-1的下标。

2.5 列表截取[start:end]

        下标运算符允许选择一个指定下标位置上的元素。而截取操作使用语法list[start:end] 返回列表的一个片段。这个片段是下标从start到end-1的元素构成的一个子列表。下面是一些例子：

>>> list1=[2，3，5，7，9，1]
>>> list1[2 : 4]
[5, 7]
>>>

起始下标和结尾下标是可以省略的。在这种情况下，起始下标为0而结尾下标是最后一个下标。

注意：如果start>=end，那么list[start:end] 将返回一个空表。如果end指定了一个超出列表结尾的位置，那么Python 会将使用列表长度替代end。

2.6  +、*和in/not in运算符

        可以使用连接运算符(+)来组合两个列表，使用复制运算符(*)复制列表中的元素。下面是一些例子：

>>> list1 = [2，3]
>>> 1ist2
[1，9]
>>> list3 = 1ist1 + 1ist2
>>> 1ist3
[2, 3，1，9]
>>>
>>> list4 = 3 * list1
>>> list4
[2, 3，2，3，2，3]
>>>

        通过连接list1 和list2就会得到一个新列表(第3行)。第7行将list1复制三次以创建一个新列表。注意: 3*list1和list1*3相同。

        可以使用in或者not in运算符来判断一个元素是否在列表中。例如:

>>> list1 = [2，3，5，2，33， 21]
>>> 2 in listl
True
>>> 2 not in list1
False
>>>

2.7 使用for循环遍历元素

        Python列表中的元素是可迭代的。Python支持一种便利的for循环，它可以让你在不使用下标变量的情况下顺序遍历列表。例如，下面的代码显示列表mylist中的所有元素。

for u in myList:print(u)

可以这样读代码:“对于mylist中的每个元素u,输出它。”
        如果希望以不同的顺序遍历列表或者改变列表中的元素，那么仍然必须使用下标变量。
例如，下面的代码显示奇数位置上的元素。

for i in range(0, len(myList), 2):print(myList[i])

2.8 比较列表

        可以使用比较运算符(>、>=、<、<=、==、!=)对列表进行比较。为了进行比较，两个列表必须包含同样类型的元素。比较使用的是字典顺序：首先比较前两个元素，如果它们不同就决定了比较的结果;如果它们相同，那就继续比较接下来两个元素，一直重复这个过程，直到比较完所有的元素。下面是一些示例。

>>> listl = ["green", "red", "blue"]
>>> list2 = ["red", "blue", "green"]
>>> list2 == listl
False
>>> list2 != list1
True
>>> list2 >= listl
True
>>> list2 > list1
True
>>> list2 < list1
False
>>> list2 <= listl
False
>>>

2.9 列表解析

        列表解析提供了一种创建顺序元素列表的简洁方式。一个列表解析由多个方括号组成，方括号内包含后跟一个for子句的表达式，之后是0或多个for或if子句。列表解析可以产生一个由表达式求值结果组成的列表。这里是一些例子。

>>> list1 = [ x for x in range(5)] #Returnsalistof0，1,2，3，4
>>> list1
[0，1,2，3，4]
>>>
>>> list2 = [0.5 * x for x in list1]
>>> list2
[0.0，0.5，1.0，1.5，2.0]
>>>
>>> list3 = [x for x in list2 if x < 1.5]
>>> list3
[0.0， 0.5，1.0]
>>>

2.10 列表方法

一旦列表被创建，可以使用list类的方法(如图10-2 所示)来操作列表。

2.11 将字符串分成列表

        str类包括了split 方法，它对于将字符串中的条目分成列表是非常有用的。例如，下面的语句:

items = "Jane John Peter Susan".split()

        就会将字符串“Jane John Peter Susan”分离成列表['Jane' ，'John'， 'Peter' ，'Susan']。在这种情况下，字符串中的条目是被空格分隔的。可以使用一个非空格的限定符。例如，下面的语句:

items = "09/20/2012".split("/")

将字符串“09/20/2012” 分成了列表['09'，'20'， '2012']。

注意: Python 支持正则表达式，它是一种使用模式来匹配和分隔字符串的最有效且最有力的特征。正则表达式对于初学者来讲是复杂的。

2.12 输入列表

        可能经常需要编写代码从控制台将数据读入列表。可以在循环里每一行输入一个数据条目并将它追加到列表。例如:下面的代码将10个数字读入一个列表，每一行读一个数字。

lst = [] # Create a list
print("Enter 10 numbers: ")
for i in range(10) :lst.append(eval(input())

        有时候在一行中以空格分隔数据会更加方便。可以使用字符串的split方法从一行输入中提取数据。例如：下面的代码从-行读取10个空格分隔的数给列表。

# Read numbers as a string from the console，
s = input("Enter 10 numbers separated by spaces from one line: ")
items = s.split() # Extract items from the string
lst = [eval(x) for x in items] # Convert items to numbers

        调用input()来读取一-个字符串。使用s.split()来提取字符串s中被空格分隔的条目并返
回列表中的条目。最后一行通过将条目转化成数字来创建一个数字列表 。

2.13 对列表移位

        有时候，需要将列表中的元素向左或向右移动。Python并没有在list类中提供这样的方法，但是可以编写下面的函数来实现向左移。

2.14 简化代码

        列表可以大大简化某些任务的。例如:假设你希望通过给定的月份数字来得到月份的英文名。如果月份名被存储在一个列表中，那么给定月份的名字可以简单地通过下标访问。下面的代码提示用户输人月份数，然后显示它的月份名:

months = ["January", "February", "March"， ...., "December"]
monthNumber = eval(input("Enter a month number (1 to 12): "))
print("The month is"， months [monthNumber - 1])

        如果不使用months列表，你就只能使用一个冗长的多重if-else语句来决定月份名，如下所示:

if monthNumber == 0:print("The month is January")
elif monthNumber == 1:print("The month is February")
else:print("The month is December")

三、复制列表

关键点：为了将一个列表中的数据复制给另一个列表，必须将元素逐个地从源列表复制到目标列表。

        经常需要在程序中复制一个列表或列表的一部分。在某些情况下，可能会尝试使用赋值语句(=)，如下所示:

list2 = list1

        但是，这条语句不会将listl1引用的列表内容复制给list2 ;事实上，它仅仅将list1引用值赋给list2。在这条语句之后，list1 和list2都将指向同一个列表，如图10-7所示。list2 之前指向的列表将不再被引用，它就变成了垃圾( garbage)。list2 所占用的内存空间将被自动收集起来被Python编译器重新使用。

为了将listl完全相同地复制给list2，可以使用:

list2 = [x for x in list1]

或者简化为:

list2 = [] + list1

四、将列表传递给函数

关键点：当列表被传递给函数时，由于列表是一个可变对象，所以列表的内容可能会在函数调用后改变。

        因为列表是一个对象，所以将列表传递给函数就像给函数传递一个对象。例如:下面的函数显示列表中的元素。

def printList(lst) :for element in 1st:print(e1 ement)

可以通过传递列表来调用它。例如:下面的语句调用printlist 函数显示3、1、2、6、4和2。

printList([3，1，2，6，4，2])

注意：前面的语句创建了一个列表，然后把它传递给函数。这里没有显示指向列表的引用变量。这样的列表被称作匿名列表。

        因为列表是可变对象，所以列表的内容可能会在函数内改变。

五、从函数返回一个列表

关键点：当函数返回一个列表时，就会返回这个列表的引用值。

        在调用函数时可以传递列表参数。函数也可以返回列表。例如:下面的函数返回了一个列表，它是另一个列表倒置的结果。

        第2行创建一个新列表result。第4~5行将名为lst的列表中的元素复制给名为result的列表。第7行返回这个列表。例如:下面的语句返回元素为6、5、4、3、2和1的新列表list2。

list1=[1，2，3，4，5，6]
list2 = reverse(list1)

注意: list 类有reverse()方法，可以调用它来倒置一个列表。

六、 查找列表

关键点：如果一个列表是排好序的，那么要查找一个列表中的某个元素，二分查找比线性查找更高效。

        查找是在列表中查找一个特定元素 的方法。例如:判定某个分数是不是包含在一个分数列表里。list 类提供了index 方法来查找并返回匹配列表中某个元素的下标。它也支持in和not in运算符以决定一个元素是否在列表中。

6.1、线性查找法

        线性查找法顺序地将关键元素key和列表中的每一个元素进行比较。它连续这样做，直到这个关键字匹配列表中的某个元素，或者在没有找到匹配元素时已经查找完整个列表。如果找到一个匹配元素，那么线性查找将返回匹配元素在列表中的下标。如果没有匹配，那么查找返回-1。程序清单10-9 中的linearSearch函数可以解释这个方法。

        为了更好地理解这个函数，使用下面的语句对程序进行跟踪。

lst = [1，4，4，2，5，-3，6，2]
i = linearSearch(1st， 4) # Returns 1
j = linearSearch(1st，-4) # Returns -1
k = linearSearch(1st， -3) # Returns 5

        线性查找函数将关键字和列表的每一个 元素进行比较。这些元素可以是任意顺序。如果这，个元素存在，那么算法在找到这个关键字之前需要平均检测列表的一半元素。因为线性查找的运行时间和列表中元素的数量成正比，所以对于大型列表而言，线性查找的效率是很低的。

6.2、 二分查找法

二分查找是对列表值进行查找的另一种常用方法。想运用二分查找法，列表中的元素必须是事先排好序的。假设列表是升序排列的，那么二分查找法会首先将关键字和列表的中间元素进行比较，这时需要考虑下面三种情况

• 如果关键字小于列表中间的元素，那么你只需要在列表的前半部分继续寻找关键字。
• 如果关键字等于列表中间的元素，那么查找因为找到一个匹配而结束。
• 如果关键字大于列表中间的元素，那么你只需要在列表的后半部分继续寻找关键字。

        注意：毫无疑问，二分查找法每次比较之后都排除了一半的列表。有时排除一半的元素，有时排除一半加一个元素。假定这个列表有n个元素。为方便起见，假设n是2的幂。在第一次比较之后，n/2 个元素被留下来进行下一步比较;在第二次比较之后，(n/2) /2个元素被留下。在第k次比较之后，n/2的k次方个元素被留下进行下一步查找。当k= log2n时，列表中只剩下一个元素，只需要进行一次比较即可。因此，在用二分查找时，最坏情况下需要进行log2n+1次比较来在排序列表中找到那个元素。对于一个有着1024 (29) 个元素的列表来说，最坏情况下二分查找只需要进行11次比较，而线性查找则需要进行1023次比较。

        每一次比较之后列表中需要查找的部分就减少一半，分别用low和high来表示列表中当前要查找的第一个下标和最后一个下标。初始情况下，low 是0，而high是len(lst)-1。mid表示中间元素的下标，因此mid是(low+high)/2，图10-9 给出如何利用二分查找在列表[2,4,7,10,11,45,50,59,60,66,69,70,79]中找到关键字11。

        现在，你知道二分查找是如何工作的。下一个任务是如何用Python实现它。但是不要急于一下子就完全实现它。应该逐步开发，一次只做一步。如图10-10a所示，可以从查找的第一次迭代开始。它将关键字和列表的中间元素进行比较，这时low下标是0而high是len(lst)-1。如果key<lst[mid],将high下标指向mid-1 ;如果key==lst[mid]，就找到了一个匹配对象，程序将返回mid;如果key>lst[mid]，将low下标指向mid+1。

        接下来，考虑添加一个循环来实现函数以完成重复查找，如图10-10b所示。当找到这个关键字，或者当low>high还没有找到，那么这个查找结束。

        当没有找到关键字时，low 是关键字应该被插入以保证列表顺序的插入点。返回插入点要比返回-1更有用。这个函数必须返回一个负值来表示这个关键字不在列表中。能否简单地返回-low?不可以，因为关键字小于lst[0]。一个好的选择是如果关键字不在列表中则让函数返回-low-1。返回-low-1不仅表示这个值不在列表中，也表示值应该被插入的地方。

注意：线性查找法在一个小列表或未排序队列中查找元素时很有用，但是对大型列表而言效率很低，而二分查找法更高效，但是它们需要列表是提前排好序的。

七、排序列表

关键点：对列表元素进行排序的策略有很多种。选择排序和插入排序是两种常用方法。

        就像查找一样，排序也是程序设计中的一个常见任务。类list提供了sort 方法来对一个列表进行排序。

        已经有很多排序算法被开发出来。下面介绍两种简单、直观的排序算法:选择排序和插入排序。通过使用这些算法，可以学会开发和实现其他算法的有价值的技巧。

7.1、选择排序

        假设你希望对一个列表进行升序排列。选择排序会找到列表中的最小元素并将它和第一个元素交换。然后找到剩余元素中值最小的元素并和剩余列表的第一个元素交换，依此类推，直到只剩一个元素。图10-11给出如何运用选择排序对列表[2,9,5,4,8,1,6]进行排序。

        第一次尝试开发一个完整的排序程序可能是比较困难的。编写一段代码完成第一轮迭代，它找到列表的最小元素之后和列表的第一个元素互换，然后观察第二轮迭代时有什么不同，接着是第三轮，依此类推。这样观察会让你能编写一个推广到所有迭代的循环。

7.2、 插入排序

        假如想升序排列一个列表。插入排序算法是通过重复地将一个新元素插 人到一个已排好序的子列表中，直到整个列表排好序。图10-12给出如何利用插入排序对列表[2,9,5,4,8,1,6]进行排序。

 八、总结

• 可以利用Python内置的len、max、min和sum函数返回一个列表的长度、列表的最大和最小值以及列表中所有元素之和。
• 可以使用random模块中的shuffle函数将一个列表中的元素打乱。
• 可以使用下标运算符[]来引用列表中的一个独立元素。
• 程序员常常会错误地用下标1来引用列表中的第一个元素，但它应该是0。这被称为下标出1错误。
• 可以使用连接操作符+来连接两个列表，使用复制运算符*来复制元素，使用截取运算符[:]获取一个子列表，使用in和not in运算符来检-一个元素是否在列表中。
• 可以使用for循环来遍历列表中的所有元素。
• 可以使用比较运算符来比较两个列表中的元素。
• 一个列表对象是可变的。可以使用方法append、extend、insert、pop和remove向一个列表添加元素和从一个列表删除元素。
• 可以使用index方法获取列表中一个元素的下标，使用count方法来返回列表中元素的个数。
• 可以使用sort和reverse方法来对一个列表中的元素进行排序和翻转。
• 可以使用split方法来将一个字符串分离成列表。
• 当调用一个带列表参数的函数时，列表的引用则被传递给这个函数。
• 如果一个列表已经排好序，那么在列表中查找一个元素时二分查找比线性查找效率更高。
• 选择排序将列表中的最小元素和第一个元素交换。然后找到剩余元素中最小的元素并与剩余元素的第一个交换，依此类推，直到只剩一个元素为止。
• 插入排序算法重复地将一个新元素插入排好序的子列表中，直到整个表都排好序为止。