05 Python 编程数据结构（26张PPT）

Python
编程
数据结构
简介
数据结构（Data
Structures）基本上人如其名——它们只是一种结构，能够将一些数据聚合在一起。换句话说，它们是用来存储一系列相关数据的集合。
Python
中有四种内置的数据结构——列表（List）、元组（Tuple）、字典（Dictionary）和集合（Set）。我们将了解如何使用它们，并利用它们将我们的编程之路变得更加简单。
列表
list是处理一组有序项目的数据结构，即你可以在一个列表中存储一个
序列
的项目。假想你有一个购物列表，上面记载着你要买的东西，你就容易理解列表了。只不过在你的购物表上，可能每样东西都独自占有一行，而在Python中，你在每个项目之间用逗号分割。
列表中的项目应该包括在方括号中，这样Python就知道你是在指明一个列表。一旦你创建了一个列表，你可以添加、删除或是搜索列表中的项目。由于你可以增加或删除项目，我们说列表是
可变的
数据类型，即这种类型是可以被改变的。
列表
list
Python内置的一种数据类型是列表：list。list是一种有序的集合，可以随时添加和删除其中的元素。
比如，列出班里所有同学的名字，就可以用一个list表示：
>>>
classmates
=
['Michael',
'Bob',
'Tracy']
>>>
classmates
['Michael',
'Bob',
'Tracy']
变量classmates就是一个list。用len()函数可以获得list元素的个数：
>>>
len(classmates)
3
用索引来访问list中每一个位置的元素，记得索引是从0开始的：
>>>
classmates[0]
'Michael'
>>>
classmates[1]
'Bob'
>>>
classmates[2]
'Tracy'
>>>
classmates[3]
Traceback
(most
recent
call
last):
File
"",
line
1,
in

IndexError:
list
index
out
of
range
当索引超出了范围时，Python会报一个IndexError错误，所以，要确保索引不要越界，记得最后一个元素的索引是len(classmates)
-
1。
如果要取最后一个元素，除了计算索引位置外，还可以用-1做索引，直接获取最后一个元素：
>>>
classmates[-1]
'Tracy'
列表
list是一个可变的有序表，所以，可以往list中追加元素到末尾：
>>>
classmates.append('Adam')
>>>
classmates
['Michael',
'Bob',
'Tracy',
'Adam']
也可以把元素插入到指定的位置，比如索引号为1的位置：
>>>
classmates.insert(1,
'Jack')
>>>
classmates
['Michael',
'Jack',
'Bob',
'Tracy',
'Adam']
要删除list末尾的元素，用pop()方法：
>>>
classmates.pop()
'Adam'
>>>
classmates
['Michael',
'Jack',
'Bob',
'Tracy']
要删除指定位置的元素，用pop(i)方法，其中i是索引位置：
列表与字符串
相同点

索引（[
?]
?运算符）

切片（[
?:
?]）

拼接（+）和重复（
）

成员（in
?运算符）

长度（len(
?)
?函数）

循环（for）

不同点

使用
?[
?]
?生成，元素之间用逗号分隔

可以包含多种类型的对象；字符串只能是字符

内容是可变的；字符串是不可变的
列表的方法
列表内容是可变的

?my_list[0]
?=
?'a'
?
my_list[0
?:
?2]
?=
?[1.2,
?3,
?5.6]
?
my_list.append(),
?my_list.extend()?#追加元素

my_list.insert()
?#任意位置插入元素

my_list.pop(),
?my_list.remove()?#删除元素

my_list.sort()
?#排序

my_list.reverse()?#逆序

更多文档

http://docs.python.org/2/tutorial/datastructures.html#more-on-lists
?
例子
?读取30个数字，并计算平均数

内建
?sum
?函数

avg
?=
?sum(nums)
/
?len(nums)

更多内建函数，如
?max，min

http://docs.python.org/2/library/functions.html
?
列表的赋值
动态演示网站

http://www./
?
使用列表
#
Filenam
e:
using_list.py
#This
is
my
shopping
list
shoplist
=
['apple',
'mango',
'carrot',
'banana']
print
'I
have',
len(shoplist),'items
to
purchase.'
print
'These
item
s
are:',
#
Notice
the
com
m
a
at
end
of
the
line
for
item
in
shoplist:
print
item
,
print
'\nI
also
have
to
buy
rice.'
shoplist.append('rice')
print
'My
shopping
list
is
now',
shoplist
print
'I
will
sort
my
list
now'
shoplist.sort()
print
'Sorted
shopping
list
is',
shoplist
print
'The
first
item
I
will
buy
is',
shoplist[0]
olditem
=
shoplist[0]
del
shoplist[0]
print
'I
bought
the',
olditem
print
'My
shopping
list
is
now',
shoplist
嵌套列表
?如何存储如下的数据表？

列表的列表

?x
=
?[[5,4,7,3],
?[4,8,9,7],
?[5,1,2,3]]
访问第三行、第二列的元素：
?x[2][1]

请问：len(x)
?的结果是？

如何获取列数？

嵌套列表示例

计算所有学生的平均分:
按照成绩由高到低排序

students=[['Zhang',84],['Wang',77],['Li',100],['Zhao',53]]
def
f(a):
return
a[1]
students.sort(key=f,reverse=True)
print
(students)
列表解析或推导
一种由原列表创建新列表的简洁方法

[表达式
?for
变量
?in
?列表
?if
?条件]

列表解析

对象与类
现在对它们做一点解释可以使你更好的理解列表。我们会在相应的章节详细探索这个主题。
列表是使用对象和类的一个例子。当你使用变量i并给它赋值的时候，比如赋整数5，你可以认为你创建了一个类（类型）int的对象（实例）i。事实上，你可以看一下help(int)以更好地理解这一点。
类也有方法，即仅仅为类而定义地函数。仅仅在你有一个该类的对象的时候，你才可以使用这些功能。例如，Python为list类提供了append方法，这个方法让你在列表尾添加一个项目。例如mylist.append('an
item
')列表mylist中增加那个字符串。注意，使用点号来使用对象的方法。
元组
另一种有序列表叫元组：tuple。tuple和list非常类似，但是tuple一旦初始化就不能修改，比如同样是列出同学的名字：
>>>
classmates
=
('Michael',
'Bob',
'Tracy')
现在，classmates这个tuple不能变了，它也没有append()，insert()这样的方法。其他获取元素的方法和list是一样的，你可以正常地使用classmates[0]，classmates[-1]，但不能赋值成另外的元素。
不可变的tuple有什么意义？因为tuple不可变，所以代码更安全。如果可能，能用tuple代替list就尽量用tuple。
tuple的陷阱：当你定义一个tuple时，在定义的时候，tuple的元素就必须被确定下来，比如：
>>>
t
=
(1,
2)
>>>
t
(1,
2)
元组
字典
Python内置了字典：dict的支持，dict全称dictionary，在其他语言中也称为map，使用键-值（key-value）存储，具有极快的查找速度。
举个例子，假设要根据同学的名字查找对应的成绩，如果用list实现，需要两个list：
names
=
['Michael',
'Bob',
'Tracy']
scores
=
[95,
75,
85]
给定一个名字，要查找对应的成绩，就先要在names中找到对应的位置，再从scores取出对应的成绩，list越长，耗时越长。
如果用dict实现，只需要一个“名字”-“成绩”的对照表，直接根据名字查找成绩，无论这个表有多大，查找速度都不会变慢。用Python写一个dict如下：
>>>
d
=
{'Michael':
95,
'Bob':
75,
'Tracy':
85}
>>>
d['Michael']
95
字典
字典的使用
字典运算符和方法
示例：单词计数
f
=
open('emma.txt')
word_freq
=
{}
for
line
in
f:
words
=
line.split()
for
word
in
words:
if
word
in
word_freq:
word_freq[word]
+=
1
else:
word_freq[word]
=
1
word_freq_lst
=
[]
for
word,freq
in
word_freq.items():
word_freq_lst.append((freq,word))
word_freq_lst.sort(reverse
=
True)
for
freq,word
in
word_freq_lst[:10]:
print
word,freq
f.close()
集合
set和dict类似，也是一组key的集合，但不存储value。由于key不能重复，所以，在set中，没有重复的key。
要创建一个set，需要提供一个list作为输入集合：
>>>
s
=
set([1,
2,
3])
>>>
s
set([1,
2,
3])
注意，传入的参数[1,
2,
3]是一个list，而显示的set([1,
2,
3])只是告诉你这个set内部有1，2，3这3个元素，显示的[]不表示这是一个list。
重复元素在set中自动被过滤：
>>>
s
=
set([1,
1,
2,
2,
3,
3])
>>>
s
set([1,
2,
3])
集合
通过add(key)方法可以添加元素到set中，可以重复添加，但不会有效果：
>>>
s.add(4)
>>>
s
set([1,
2,
3,
4])
>>>
s.add(4)
>>>
s
set([1,
2,
3,
4])
通过remove(key)方法可以删除元素：
>>>
s.remove(4)
>>>
s
set([1,
2,
3])
set可以看成数学意义上的无序和无重复元素的集合，因此，两个set可以做数学意义上的交集、并集等操作：
>>>
s1
=
set([1,
2,
3])
>>>
s2
=
set([2,
3,
4])
>>>
s1
&
s2
set([2,
3])
>>>
s1
|
s2
set([1,
2,
3,
4])
集合
总结
使用key-value存储结构的dict在Python中非常有用，选择不可变对象作为key很重要，最常用的key是字符串。
tuple虽然是不变对象，但试试把(1,
2,
3)和(1,
[2,
3])放入dict或set中，并解释结果。
1.
向列表增加元素有哪些方法？
2.
从列表删除元素有哪些方法？
3.
要得到一个列表的有序副本，但又不能改变原来的列表，有哪两种方法？
4.
怎样得出某个值是否在列表中？
5.
如何确定某个值在列表中的位置？
6.
什么是元组？
7.
如何建立双重列表？
8.
如何从一个双重列表中得到一个值？
9.
什么是字典？
10.
如何向字典中增加项？
11.
怎样使用键去查找一个条目？
1.
写一个程序，让用户提供
5
个名字。程序要把这
5
个名字保存在一个列表中，
最后打印出来。就像这样：
Enter
5
names:
Tony
Paul
Nick
Michel
Kevin
The
names
are
Tony
Paul
Nick
Michel
Kevin
2.
修改第
1
题的程序，要求不仅显示原来的名字列表，还要显示出排序后的列表。
3.
修改第
1
题的程序，要求只显示用户键入的第
3
个名字，就像这样：
The
third
name
you
entered
is:
Nick
总结
4.
修改第
1
题的程序，让用户替换其中一个名字。用户应该能选择要替换哪个
名字，然后键入新名字。最后显示这个新的列表：
Enter
5
names:
Tony
Paul
Nick
Michel
Kevin
The
names
are
Tony
Paul
Nick
Michel
Kevin
Replace
one
name.
Which
one?
(1-5):
4
New
name:
Peter
The
names
are
Tony
Paul
Nick
Peter
Kevin
5.
编写一个字典程序，让用户可以添加单词和定义，然后可以查找这些单词。
确保当要查找的单词不存在时，用户能够知晓。运行的时候，它应该是像这
样的：
Add
or
look
up
a
word
(a/l)?
a
Type
the
word:
computer
Type
the
de?nition:
A
machine
that
does
very
fast
math
Word
added!
Add
or
look
up
a
word
(a/l)?
l
Type
the
word:
computer
A
machine
that
does
very
fast
math
Add
or
look
up
a
word
(a/l)?
l
Type
the
word:
qwerty
That
word
isn’t
in
the
dictionary
yet.