6.数据结构

数据结构（data structure）是计算机中存储、组织数据的方式。本实验将深入了解列表。

一、实验目的

• 列表的方法与列表元素的删除
• 将列表用作栈和队列
• 列表推导式
• 元组、集合、字典的创建与操作
• enumerate() 和 zip() 函数

二、知识要点

1.列表的更多方法

1.1 插入insert(position,value)

a = [1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]
a.insert(0, 1)  # 在列表索引 0 位置添加元素 1
print(a)

>>[1, 1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]

a.insert(0, '1') 
print(a)

>>['1', 1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]

在索引为0的位置插入值，任意属性的值均可。

1.2 计数count(value)

a = [1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]
print(a.count(45))

>>3

检索列表中为45的关键词的数目。

1.3 移除指定值remove(value)

a = [1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]
a.remove(45)
print(a)

>>[1, 2, 5, 7, 64, 66, 97, 68, 45, 69, 45]

可知，remove()函数每次只能移除一个有效值

1.4 反转reverse()

a = [1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]
a.reverse();            #反转a列表
print(a)

>>[45, 69, 45, 45, 68, 97, 66, 64, 7, 5, 2, 1]

1.5 追加extend()

a = [1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]
b = [989, -546, 798]
a.extend(b)             #追加b列表至a列表
print(a)

>>[1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45, 989, -546, 798]

1.6 排序sort()

a = [1, 2, 5, 7, 64, 66, 97, 68, 45, 45, 69, 45]
a.sort()                #对a列表排序
print(a)

>>[1, 2, 5, 7, 45, 45, 45, 64, 66, 68, 69, 97]

2.将列表用作栈

栈是我们通常所说的一种 LIFO （Last In First Out 后进先出）数据结构。它的意思是最后进入的数据第一个出来。一个最简单的例子往一端封闭的管道放入一些弹珠然后取出来，如果你想把弹珠取出来，你必须从你最后放入弹珠的位置挨个拿出来。

2.1 pop(value)方法
使用该方法可以将列表中第value个元素弹出，例如：

a = [0, 1, 2, 3, 4, 5]
print(a.pop(1))
print(a)

>>1
[0, 2, 3, 4, 5]

print(a.pop())
>>5

pop()方法如果不加参数即将最后一个元素弹出，通过这种方法实现了栈。

3.将列表用作队列

队列 是一种在末尾追加数据以及在开始弹出数据的数据结构。与栈不同，它是 FIFO （First In First Out 先进先出）的数据结构。
通过代码来实现队列：

a = [1, 2, 3, 4, 5]
a.append(1)
print(a)
a.pop(0)
print(a)

>>[1, 2, 3, 4, 5, 1]
[2, 3, 4, 5, 1]

4.列表推导式

列表推导式为从序列中创建列表提供了一个简单的方法。如果没有列表推导式，一般都是这样创建列表的：通过将一些操作应用于序列的每个成员并通过返回的元素创建列表，或者通过满足特定条件的元素创建子序列。例如：

a = []
for x in range(10):
    a.append(x**2)
print(a)

>>[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

但是当我们输入代码：

print(x)

>>9

会发现x值仍然存在，通过下面方法达到生成列表且不产生资源浪费：

a = [x**2 for x in range(10)]
print(a)

>>[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

而对于坐标，同样可以通过这种方法：

m = [(x, y) for x in [1, 2, 3] for y in [3, 1, 4] if x != y]
print(m)

>>[(1, 3), (1, 4), (2, 3), (2, 1), (2, 4), (3, 1), (3, 4)]

5.元组

元组与列表类似，不同之处在于元组的元素不能修改。元组使用小括号，列表使用方括号。元组创建很简单，只需要在括号中添加元素，并使用逗号隔开即可。例如：

tup1 = ()     #创建空元组
tup2 = (12,)  #创建只包含一个元素的元组

元组与字符串类似，下标索引从0开始，可以进行截取，组合等。

5.1 元组运算符
与字符串一样，元组之间可以使用 + 号和 * 号进行运算。这就意味着他们可以组合和复制，运算后会生成一个新的元组。

Python 表达式	结果	描述
len((1, 2, 3))	3	计算元素个数
(1, 2, 3) + (4, 5, 6)	(1, 2, 3, 4, 5, 6)	连接
(‘Hi!’,) * 4	(‘Hi!’, ‘Hi!’, ‘Hi!’, ‘Hi!’)	复制
3 in (1, 2, 3)	True	元素是否存在
for x in (1, 2, 3): print x,	1 2 3	迭代

5.2 元组索引、截取
因为元组也是一个序列，所以我们可以访问元组中的指定位置的元素，也可以截取索引中的一段元素，如下所示：

L = ('spam', 'Spam', 'SPAM!')

Python 表达式	结果	描述
L[2]	‘SPAM!’	读取第三个元素
L[-2]	‘Spam’	反向读取，读取倒数第二个元素
L[1:]	(‘Spam’, ‘SPAM!’)	截取元素

任意无符号的对象，以逗号隔开，默认为元组

5.3 元组内置函数

方法及描述
cmp(tuple1, tuple2) 比较两个元组元素。
len(tuple) 计算元组元素个数。
max(tuple) 返回元组中元素最大值。
min(tuple) 返回元组中元素最小值。
tuple(seq) 将列表转换为元组。

6.集合

集合是一个无序不重复元素的集。基本功能包括关系测试和消除重复元素。集合对象还支持 union（联合），intersection（交），difference（差）和 symmetric difference（对称差集）等数学运算。大括号或 set() 函数可以用来创建集合，例如：

a = {'1', '2', '3', '2'}
b = set('1232')
print(a)
print(b)

>>{'2', '3', '1'}
{'2', '3', '1'}

6.1 常用运算

• 代码：

a = set('abracadabra')
b = set('alacazam')
print('a=', a)
print('b=', b)
print('a - b=', a - b)  # a 有而 b 没有的字母
print('a | b=', a | b)  # 存在于 a 或 b 的字母
print('a & b=', a & b)  # a 和 b 都有的字母
print('a ^ b=', a ^ b)  # 存在于 a 或 b 但不同时存在的字母
print('a.pop()=', a.pop()) #随机弹出一个元素

• 结果：

a= {'r', 'c', 'b', 'd', 'a'}
b= {'c', 'm', 'a', 'z', 'l'}
a - b= {'r', 'b', 'd'}
a | b= {'r', 'c', 'b', 'a', 'd', 'm', 'z', 'l'}
a & b= {'c', 'a'}
a ^ b= {'l', 'z', 'b', 'r', 'd', 'm'}
a.pop()= d

7.字典

字典是是无序的键值对（key:value）集合，同一个字典内的键必须是互不相同的。一对大括号 {} 创建一个空字典。初始化字典时，在大括号内放置一组逗号分隔的键：值对，这也是字典输出的方式。我们使用键来检索存储在字典中的数据。格式如下：

d = {key1 : value1, key2 : value2 }

值可以取任何数据类型，但键必须是不可变的，如字符串，数字或元组。

7.1 字典键的特性
字典值可以没有限制地取任何python对象，既可以是标准的对象，也可以是用户定义的，但键不行。两个重要的点需要记住：

• 不允许同一个键出现两次。创建时如果同一个键被赋值两次，后一个值会被记住
• 键必须不可变，所以可以用数字，字符串或元组充当，所以用列表就不行

7.2 字典内置函数和方法

函数及描述
cmp(dict1, dict2) 比较两个字典元素。
len(dict) 计算字典元素个数，即键的总数。
str(dict) 输出字典可打印的字符串表示。
type(variable) 返回输入的变量类型，如果变量是字典就返回字典类型。
dict.clear() 删除字典内所有元素
dict.copy() 返回一个字典的浅复制
dict.fromkeys(seq[, val]) 创建一个新字典，以序列 seq 中元素做字典的键，val 为字典所有键对应的初始值
dict.get(key, default=None) 返回指定键的值，如果值不在字典中返回default值
dict.has_key(key) 如果键在字典dict里返回true，否则返回false
dict.items() 以列表返回可遍历的(键, 值) 元组数组
dict.keys() 以列表返回一个字典所有的键
dict.setdefault(key, default=None) 和get()类似, 但如果键不存在于字典中，将会添加键并将值设为default
dict.update(dict2) 把字典dict2的键/值对更新到dict里
dict.values() 以列表返回字典中的所有值
pop(key[,default]) 删除字典给定键 key 所对应的值，返回值为被删除的值。key值必须给出。 否则，返回default值。
popitem() 返回并删除字典中的最后一对键和值。

三、实验内容

1.常用的元组操作

• 访问元组
  元组可以使用下标索引来访问元组中的值，如下实例:

tup1 = ('physics', 'chemistry', 1997, 2000)
tup2 = (1, 2, 3, 4, 5, 6, 7 )
 
print ("tup1[0]: ", tup1[0])
print ("tup2[1:5]: ", tup2[1:5])

>>tup1[0]:  physics
tup2[1:5]:  (2, 3, 4, 5)

• 修改元组
  元组中的元素值是不允许修改的，但我们可以对元组进行连接组合，如下实例:

tup1 = (12, 34.56)
tup2 = ('abc', 'xyz')
 
# 以下修改元组元素操作是非法的。
# tup1[0] = 100
 
# 创建一个新的元组
tup3 = tup1 + tup2
print(tup3)

>>(12, 34.56, 'abc', 'xyz')

• 删除元组
  元组中的元素值是不允许删除的，但我们可以使用del语句来删除整个元组，如下实例:

tup = ('physics', 'chemistry', 1997, 2000)
 
print(tup)
del(tup)
print( "After deleting tup : ")
print(tup)

以上实例元组被删除后，输出变量会有异常信息，输出如下所示：

('physics', 'chemistry', 1997, 2000)
After deleting tup :
Traceback (most recent call last):
  File "test.py", line 9, in <module>
    print tup
NameError: name 'tup' is not defined

2.常用字典操作

• 访问字典操作

car = {'name': 'byd', 'light': 2, 'wheel': 4}
print(car['name'])

>>byd

• 修改字典

car = {'name': 'byd', 'light': 2, 'wheel': 4}
car['name'] = 'bmw'        #修改
car['owner'] = 'Metatron'  #添加
print(car['name'], car['owner'])

>>bmw Metatron

• 删除字典元素

car = {'name': 'byd', 'light': 2, 'wheel': 4}
del car['name']  #删除键是name的条目
print(car)
car.clear() #清空字典所有条目
print(car)
del car  #删除字典
print(car)

输出报错：

Traceback (most recent call last):
  File "F:/Python/6/eg 6-6.py", line 11, in <module>
    print(car)
NameError: name 'car' is not defined
{'light': 2, 'wheel': 4}
{}

• 查看某元素是否在字典中

car = {'name': 'byd', 'light': 2, 'wheel': 4}
print('bmw' in car)

>>false

• dict()从包含键值对的元组中创建字典

print(dict((('Indian', 'Delhi'), ('Bangladesh', 'Dhaka'))))

>>{'Indian': 'Delhi', 'Bangladesh': 'Dhaka'}

• 遍历字典item()

data = {'Kushal': 'Fedora', 'Jace': 'Mac', 'kart_': 'Debian', 'parthan': 'Ubuntu'}
for x, y in data.items():
    print("{} uses {}".format(x, y))

>>Kushal uses Fedora
Jace uses Mac
kart_ uses Debian
parthan uses Ubuntu

• dict.setdefault(key, default)

许多时候我们需要往字典中的元素添加数据，我们首先要判断这个元素是否存在，不存在则创建一个默认值。如果在循环里执行这个操作，每次迭代都需要判断一次，降低程序性能。

data = {}
data.setdefault('names', []).append('Ruby')
data.setdefault('names', []).append('Python')
data.setdefault('names', []).append('C')
print(data)

>> {'names': ['Ruby', 'Python', 'C']}

• dict.get(key, default)

试图索引一个不存在的键将会抛出一个 keyError 错误。我们可以使用 dict.get(key, default) 来索引键，如果键不存在，那么返回指定的 default 值。

data = {'name': 'byd', 'light': 2, 'wheel': 4}
print(data.get('foo', 0))

>>0

• enumerate()

在遍历列表（或任何序列类型）的同时获得元素索引值

data = {'name': 'byd', 'light': 2, 'wheel': 4}
for x in enumerate(data.items()):
    print(x)

>>(0, ('name', 'byd'))
(1, ('light', 2))
(2, ('wheel', 4))

• zip()

遍历两个序列类型

a = ['Pradeepto', 'Kushal']
b = ['OpenSUSE', 'Fedora']
for x, y in zip(a, b):
    print("{} uses {}".format(x, y))

>>Pradeepto uses OpenSUSE
Kushal uses Fedora

四、实验结果

1.students.py

这是一个判断学生成绩是否达标的程序，要求输入学生数量，以及各个学生物理、数学、历史三科的成绩，如果总成绩小于 120，程序打印 “failed”，否则打印 “passed”。

• 代码：

n = int(input("Enter the number of students: "))
data = {} # 用来存储数据的字典变量
Subjects = ('Physics', 'Maths', 'History') # 所有科目
for i in range(0, n):
    name = input('Enter the name of the student {}: '.format(i + 1)) # 获得学生名称
    marks = []
    for x in Subjects:
        marks.append(int(input('Enter marks of {}: '.format(x)))) # 获得每一科的分数
    data[name] = marks
for x, y in data.items():
    total =  sum(y)
    print("{}'s total marks {}".format(x, total))
    if total < 120:
        print(x, "failed :(")
    else:
        print(x, "passed :)")

• 结果：

Enter the number of students: 2
Enter the name of the student 1: me
Enter marks of Physics: 123
Enter marks of Maths: 12
Enter marks of History: 31
Enter the name of the student 2: you
Enter marks of Physics: 20
Enter marks of Maths: 20
Enter marks of History: 20
me's total marks 166
me passed :)
you's total marks 60
you failed :(

• 解释：

name和 marks是变量，name用来存储学生的名称，marks 是个列表，用来存储输入的学生的成绩数据。data 是个字典，字典的键值对中，键指的是 name的值，值指的是 marks 的值。因此会使用 data[name] = marks将学生数据存入到data字典。
最后通过for循环遍历字典，x为学生的name，y为学生成绩列表 marks，sum()函数会将传入的列表进行加和。

2.matrixmul.py

这个例子里我们计算两个矩阵的 Hadamard 乘积。要求输入矩阵的行/列数（在这里假设我们使用的是 n × n 的矩阵）。

• 代码：

n = int(input("Enter the value of n: "))
print("Enter values for the Matrix A")
a = []
for i in range(n):
    a.append([int(x) for x in input().split()])
print("Enter values for the Matrix B")
b = []
for i in range(n):
    b.append([int(x) for x in input().split()])
c = []
for i in range(n):
    c.append([a[i][j] * b[i][j] for j in range(n)])
print("After matrix multiplication")
print("-" * 7 * n)
for x in c:
    for y in x:
        print(str(y).rjust(5), end=' ')
    print()
print("-" * 7 * n)

• 结果

Enter the value of n: 3
Enter values for the Matrix A
1 2 3 
4 5 6
7 8 9
Enter values for the Matrix B
9 8 7
6 5 4 
3 2 1
After matrix multiplication
---------------------
    9    16    21 
   24    25    24 
   21    16     9 
---------------------

Process finished with exit code 0

• 解释：

这里我们使用了几次列表推导式。[int(x) for x in input().split()] 首先通过 input() 获得用户输入的字符串，再使用split()分割字符串得到一系列的数字字符串，然后用int() 从每个数字字符串创建对应的整数值。我们也使用了 [a[i][j] * b[i][j] for j in range(n)] 来得到矩阵乘积的每一行数据。

---

下一篇：7.字符串
上一篇：5.循环
目 录：Python学习