Python基础--PART2

PART3. 数据结构

​ 在任何一门编程语言中，字符串都是最基础、最重要的数据结构。前面我们已经学习过字符串的基本使用方法，现在继续深入的学习更多的知识。

1. 字符串“”/‘’

1.1 字符串的格式化输出

1.1.1 格式化运算符

​ 在之前while循环的一个例子中， 有这样一行代码：

print("我跑完了第" + str(lap + 1) + "圈")
1

​ 这里我们使用了两个加号做了字符串拼接，并且将整形转换成了字符串，现在介绍一种更好的办法，使用格式化输出来打印这句话。

print("我跑完了第%d圈" % 1)
1

​ 这里的百分号就是格式化符号，跟模运算符一样，但在不同的地方用法不一样。%d是一种占位，表示要显示在这里是一个整数，常用的占位符有以下几种：

# 如果给%d 传入一个浮点数，那它会自动将它转换成整数
print("%d" % 3.14)	# 输出3
print("%d" % 3.99)	# 输出3

# %f的用法有两种，一种就是直接使用
print("%f" % 3.14)	# 输出3.140000
# 只想要输出小数点后两位，可以这样
print("%.2f" % 3.14)	#输出3.14
print("%.2f" % 3.1415926)	#输出3.14
# 如果不足两位，或者是个整数，会自动补零到两位
print("%.2f" % 3)	#输出 3.00
print("%.2f" % 3.1)	#输出 3.10

# %s 是胜任最广泛的占位符，它可以对应任何类型的变量。
print("%s" % 100) # 输出100
print("%s" % 3.14) # 输出3.14
print("%s" % "python") # 输出python
# 在同一个字符串可以同时使用多个占位符：
report = "%d年%s公司营收增长了百分之%.2f" % (2023, "腾讯", -50.28)
print(report)

# 当我们需要在字符串输出一个百分比，就需要用到%%，比如说：
report = "%d年%s公司营收增长了%.2f%%" % (2022, "腾讯", 20.28)
print(report)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1.1.2 format函数

​ 除了%运算符外，Python还为我们提供了字符串的format函数提供丰富的格式化。比如说，在输出一个较长的数字时，根据国际惯例，每三位用逗号分隔：

print('{:,}'.format(1234567890))
# 1,234,567,890
1
2

​ format函数也可以像%那样来格式化多个参数：

# {0}表示第一个参数，{1}{2}表示第二、第三个参数，以此类推。这样做的好处是，如果有参数在字符串出现多次，可以不用重复的传入。
report = "{0}年{1}公司营收增长了{2}%".format(2019, "腾讯", 20.28)
print(report)

# 假设这个GDP数据在报告中多处被引用，万一需要修订的话，我们只需要修改一处就行了。
print('{0}的GDP为{1:,}, 虽然它的GDP只有{1:,}美元，但它的人均GDP高达18万美元'.format("摩纳哥",7100000000))
1
2
3
4
5
6

1.2 字符串的下标与切片

​ 字符串其实也是一种序列，可以理解为一串整齐的按顺序排着队的字符，组成了字符串，那每个字符在队伍中都有自己的位置，这个位置就是下标，又叫作索引。

​ 如上图，"CHINA"这个字符串，从左往右每一个字符对应了一个下标（索引），需要特别注意的是，在计算机编程中，所有的下标都是从0开始的，当我们要访问一个字符串的第1个字符时，使用的下标应该是0。

print("CHINA"[0])

# 使用中括号加数字的方式，表示要访问的是具体哪个位置上的字符。
"CHINA"[1] # 第2个字符"H"
"CHINA"[4] # 第5个字符"A"
"CHINA"[-1] # 最后一个字符"A"
"CHINA"[-2] # 倒数第二个字符"N"
1
2
3
4
5
6
7

​ 使用负数下标可以从右往左访问，这种写法是Python特有的，非常的快捷，对于任意长度的字符串，我们都可以使用-1来获取它的最后一个字符，注意使用负数下标是是从-1开始的，因为-0也是0，产生重复了。

​ 切片操作也是Python的一大特色，极大简化了序列访问和操作。

"CHINA"[0:3]	# 输出 CHI

"CHINA"[0:0]	# 空字符串
"CHINA"[0:-1]	# CHIN
"CHINA"[0:6]	# CHINA
# 冒号右边的省略，表示一直截取到最后一个字符
"CHINA"[0:]		# CHINA

# 前面的0也可以不写，冒号左边为空表示从第一个字符开始截取
# 从0到末尾
"CHINA"[:] # CHINA
# 从0到第3个
"CHINA"[:3] # CHI
# 从第3个到末尾
"CHINA"[2:] # INA

# 如果想要隔一个字符取一个，可以这样写，步长：默认为1，也可以为负数
# 每隔两个字符截取一个
"CHINA"[::2] # CIA
# 从右往左每隔两个两个字符截取一个
"CHINA"[::-2] # AIC
# 倒序输出一个字符串
"CHINA"[::-1] # ANIHC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.3 字符串函数

​ 字符串本身有很多函数，前面其实已经学习过一个format函数，我们再来介绍几个其他的常用函数

1.3.1 去除空白字符函数

​ 空白符包括空格、换行（\n）、制表符（\t）

print("A\tB\tC\nD\tE\tF")
1

​ 按键盘上的空格键会产生一个空格，按回车键则会产生一个换行符，按Tab键则会产生一个制表符，用户在输入数据的时候有时候经常会误输入这几个字符，所以在在处理用户输入的数据时，要先去除头尾的空白字符。

password = "123"
input_password = " 123"
print(password == input_password)	#输出 false

password = "123"
input_password = " 123"
print(password == input_password.strip())	#输出 true
1
2
3
4
5
6
7

​ strip函数的作用就是去除字符串首尾的所有空白字符

print(" abc ".strip())
print("\t abc \n".strip())

# strip函数并不会去除掉字符串之间的空白字符
print(" a b c ".strip())	#输出 a b c

# lstrip 和 rstrip 函数，分别去除字符串左边和右边的空白字符
" abc ".lstrip() # 结果'abc '
" abc ".rstrip() # 结果' abc'

1
2
3
4
5
6
7
8
9
10

1.3.2 大小写操作

# 将所有字符变成大写
"china".upper() # CHINA

# 将字符串的首字母变成大写
"china".capitalize() # China

# 将所有字符变成小写
"CHINA".lower() # china

# 将每个单词的首字母变成大写
"i have a dream".title() # I Have A Dream
1
2
3
4
5
6
7
8
9
10
11

1.3.3 字符串判断

​ 判断字符串是否以指定的字符串开头或者结尾

String = input("")
if str(String).startswith('1'):
    print("yes")
else:
    print("no")
1
2
3
4
5

1.3.4 查找与替换

​ 在前面密码锁的案例中，我们用过in来判断一个字符串是否被包含在另一个字符中

password = '123'
input_pwd = '456123789'
password in input_pwd # True
1
2
3

​ 这样可以判断出是input_pwd中是否有password，但如果想要知道password在input_pwd中的确切位置，就需要使用find函数

input_pwd.find(password) # 结果是3
1

​ 除了find函数，index函数也有相同的功能，唯一的区别是 ，index函数如果没有找到相应的字符串就会报错

input_pwd.index(password)	# 结果是3
# 这行代码将会在运行时报错
input_pwd.index("notexists")	# ERROR
1
2
3

​ count函数能够查找出指定的字符串一共出现了几次，如果没有出现，则返回0

"abba".count('a')	# 2
'abba'.count('c')	# 0
1
2

​ replace函数提供了替换字符串中某些部分的功能

"abba".replace('a', 'b')	# 结果是'bbbb'
'apple banana'.replace('apple', 'orange')	# 结果是'orange banana'
1
2

1.3.5 字符串长度

​ 字符串本身没有测量长度的函数，需要借助一个Python内置函数len

len("China") # 5
len("") # 0
len("a") # 1
1
2
3

​ len函数非常重要，它不光可以测量字符串的长度，也可以测量其他所有有长度的对象

r = range(10)
len(r) # 10
1
2

1.4 举个栗子

​ 结合以上的字符操作知识，可以开发一个电话号码识别程序，用户输入一串数字，程序识别它是不是一个有效的电话号码，如果是有效电话号码，我们再识别它是一个固定电话号码、手机号码、还是400号码。用户输入"exit"后，程序退出。

​ 分析一下需求。先列举一下常见的几种电话号码形式，手机号码是11位的，以1开头，不同运营商的前三位不一样，由于三位太多了，我们就以前两位来判断，包括【13,15,17,18,19】。

​ 再看固定号码，区号+电话号码的方式，区号可能是三位（010），也可能是四位（0888），电话号码是8位，那加起来一共是11位或12位。

​ 最是400电话，这个特征很明显，以400开头，共10位。

cellphone_number_start = "13,15,17,18,19"
telephone_number_start = "010,021,022,025,0888,0555"
while True:
    num = input("请输入一个电话号码: \n")
    if num == 'exit':
        break
    if not num:
        print("电话号码不能为空")
    num = num.strip()
    if not num.isdigit():
        print("您输入的是一个无效电话号码")
        continue
    if num.startswith('1') and len(num) == 11 and num[0:2] in cellphone_number_start:
        print("这是一个手机号码")
        continue
    elif num.startswith('400') and len(num) == 10:
        print("这是一个广告电话")
        continue
    elif num.startswith("0"):
        # 当代码太长时，可以用反斜杠分割成多行。
        if (len(num) == 12 and num[0:4] in telephone_number_start) or \
        (len(num) == 11 and num[0:3] in telephone_number_start):
            print("这是一个固定电话")
            continue
        print("无法识别该号码")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. 元祖 tuple()

2.1 定义元祖

​ 现在我们知道了字符串是一种序列，它可以迭代循环，也可以按索引访问，也可以切片访问。但它的组成只能是单个的字符，现在来介绍一种更多元化的序列：元组，英文叫tuple，可这样来定义一个元组：

t = ('My', 'age', 'is', 18)

# 事实上元组定义的时候也可以不用括号，但当，元组中只有一个元素的时候，必须要加一个逗号
t = 'My', 'age', 'is', 18
t = ('solo',）
# 或者不带括号
t = 'solo',
1
2
3
4
5
6
7

​ 在这个元组中包含了3个字符串，一个整形数字，元组中的每一项称作元素，4个元素按照从左到右的顺序排列。可以用下标索引访问：

t[0]	# 'my'
t[-1]	# 18
1
2

​ 也可以通过切片来访问，注意切片返回的是一个包含切片片段的新元组

t[0:2]	# ('My', 'age')
1

​ 可以将一个序列强制转换为元组

# 后面的逗号表明这是一个元组，否则就会被认为是一个字符串
tuple('abc')	# ('a', 'b', 'c')
tuple(range(5))	# (0, 1, 2, 3, 4)
1
2
3

2.2 元祖操作

​ 现在我们介绍字符串的另一个函数join，有了它，可以把元组这样的序列拼接成一个整体的字符串。

# 注意最后一个元素
t = ('My', 'age', 'is', "18")
print(" ".join(t))
# 输出结果：'My age is 18'
1
2
3
4

​ 注意最后一个元素，这次我们将它设置成了字符串，因为join函数要求参数序列中的每一个元素都必须是字符串。

​ 和字符串一样，元组也有count, index函数，使用的方法也是一样：

t = ('a', 'b', 'b', 'a')
t.count('a')	# 2
t.index('b')	# 1
t.index('c')	# Error
# 查看长度
len(t) # 4
1
2
3
4
5
6

​ 元组也支持 in 操作，想要判断元组中是否包含某个元素：

'a' in t	# True
'x' in t	# False
1
2

​ 最后，需要记住的是元组和字符串都是只读的，也就是不可修改的。我们不能单独改变元组中的某个元素，或者是字符串中的某个字符。

2.3 遍历元祖

​ 元组属于序列，所以可以像字符串那样去遍历它：

lst = ('a', 'b', 'c', 'd', 'e')
for i in lst:
	print(i)
1
2
3

​ 使用for循环可以方便快捷的遍历元组，上面的例子将打印出元组中的每一个元素。也可以使用while来遍历元组，虽然并不经常这样使用。

lst = list(range(10))
i = 0
while i < 10:
	print(lst[i])
	i += 1
1
2
3
4
5

2.4 举个栗子

​ 销售数据统计-销冠：在真实的项目中，数据结构通常是比较复杂，经常碰到嵌套的元组，甚至是多层嵌套，我们来看一个例
子。

# 当元组元素较多、较长时，可以这样书写
sales = (
	("Peter", (78, 70, 65)),
	("John", (88, 80, 85)),
	("Tony", (90, 99, 95)),
	("Henry", (80, 70, 55)),
	("Mike", (95, 90, 95)),
)
1
2
3
4
5
6
7
8

​ 这是包含某公司所有销售人员第一季度销售业绩的元组，单位是万元，其中的每一个元素对应一个销售人员的信息，人员信息也是一个元组，包括姓名和业绩，业绩又是一个元组，按照顺序分别是1、2、3月份的销售额。需求：找出总销售额最高的那个员工，并将TA的名字和总销售额输出。

champion = ''
max_amount = 0
for sale in sales:
    name = sale[0]
    quarter_amount = sale[1]
    total_amount = 0
    for month_amount in quarter_amount:
        total_amount += month_amount
    if total_amount > max_amount:
        max_amount = total_amount
        champion = name
print("第一季度的销冠是%s, TA的总销售额是%d万元" % (champion, max_amount))
1
2
3
4
5
6
7
8
9
10
11
12

​ 优化

champion = ''
max_amount = 0
for name, quarter_amount in sales:
    total_amount = sum(quarter_amount)
    if total_amount > max_amount:
        champion, max_amount = name, total_amount
print("第一季度的销冠是%s, TA的总销售额是%d万元" % (champion, max_amount))
1
2
3
4
5
6
7

3. 列表 list[]

3.3.1 定义列表

​ 列表可以理解为可变的元组，它的使用方式跟元组差不多，区别就是列表可以动态的增加、修改、删除元素。

# 定义一个空列表
lst = []
lst = list()

# 定义带有初始值的列表
lst = [1, 2, 3]
lst = ["a", 1, 2, 3, "b", "c"]
lst = list(range(5))
lst = list("abc")
lst = list((1, 2, 3))
1
2
3
4
5
6
7
8
9
10

​ 以上方式都可以定义一个列表。注意变量名使用了lst，有意的避开了list，虽然list不是关键字，但我们在命名变量的时候不要使用这些内置名称。

3.3.2 增删改查

​ 列表的访问和字符串、元组一样，索引或者下标都可以。

lst = ['a', 'b', 'c', 'd', 'e']
lst[0] # 'a'
lst[1:3] # ['b', 'c']

# append函数总是在列表后面添加元素
lst.append('x')

# 修改列表中的元素
lst[-1] = 'f'
# 修改后列表变为：
# ['a', 'b', 'c', 'd', 'e', 'f']

# 删除列表中的元素
del lst[0]
# 删除后列表变为：
['b', 'c', 'd', 'e', 'f']
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

​ 注意，由于我们删除的是第一个元素，现在剩下的所有元素的索引都发生了变化，第一个lst[0]变成了’b’，后面的也都往前挪了一位。但是lst[-1]没有变，还是’f’。涉及到删除操作的时候要小心，防止使用错误的索引。

3.3.3 列表函数

​ 列表也是一种序列，它也具有index和count函数和支持len函数，这些函数的用法和元组一样，它的循环遍历也和元组一样。下面来介绍一下列表特有的一些函数。

insert

​ insert函数和刚刚介绍的append函数一样，用来向列表中添加一个新的元素，区别就是append是在最后添加，insert则可以向任意位置添加。

lst = ['a', 'c', 'e']
# 在第二个元素'c'前面插入一个字符串'b'
lst.insert(1, 'b')
# lst现在的值是['a', 'b', 'c', 'e']
# 在最后一个元素'e'前面插入一个字符串'd'
lst.insert(-1, 'd')
# lst现在的值是['a', 'b', 'c', 'd', 'e']
1
2
3
4
5
6
7

pop

​ 每次调用pop函数会从列表中“弹”出一个元素，接着上面的lst操作

temp = lst.pop()
print(lst) # ['a', 'b', 'c', 'd']
print(temp) # 'e'

# 我们发现列表最后一个元素'e'不见了，并被在控制台打印出了。如果想“弹”出其他位置的元素，可以传一个位置参数给pop函数
temp = lst.pop(2)
print(lst) # ['a', 'b', 'd']
print(temp) # 'c'
1
2
3
4
5
6
7
8

remove

​ 前面我们已经学习了使用del关键字去删除列表元素，del操作可删除指定下标索引的元素，如果我们要删除指定内容的元素，就需要用到remove函数。

lst = [1, 2, 1, 'a', 'b', 'c']
lst.remove('a')
print(lst) # lst的值为[1, 2, 1, 'b', 'c']
lst.remove(1) # 注意这里的1是元素值，不是索引
print(lst) # lst的值为[2, 1, 'b', 'c']
1
2
3
4
5

​ remove函数会从左至右找到与指定的值相匹配的第一个元素，并将它删除。在使用的时候需要区分del,pop, remove的区别。

clear

​ clear函数会清空列表内的所有元素

lst = [1,2,3,4]
lst.clear()
print(lst) # 结果为[]
1
2
3

extend

​ extend函数有点像append函数，但append函数每次只能添加一个元素，而extend可以添加一组

lst = []
lst.extend(range(5))
print(lst) # [0, 1, 2, 3, 4]
lst.extend([5, 6, 7])
print(lst) # [0, 1, 2, 3, 4, 5, 6, 7]
1
2
3
4
5

reverse

​ 将整个列表反转，以上一步的lst为例

lst.reverse()
print(lst) # [7, 6, 5, 4, 3, 2, 1, 0]
1
2

sort

​ 按照一定的规则将列表中的元素重新排序，对于数值，默认按从小到大的顺序排列

lst = [3, 5, 2, 1, 4]
lst.sort()
print(lst) # [1, 2, 3, 4, 5]

#想要让列表从大到小排列，可以加上reverse参数
lst = [3, 5, 2, 1, 4]
lst.sort(reverse=True)
print(lst) # [5, 4, 3, 2, 1]
1
2
3
4
5
6
7
8

​ 对于字符串，则会按照它们的ASCII值的顺序排列

ord('A') # 65
chr(66) # 'B'
1
2

​ 列表的元素不是简单的字符或者数字，那怎么进行排序

​ 注意列表中的每一个元素是一个元组，元组的第一项是月份，第二项是销售额，现在想要按照它的销售额来从高到低排序。如果直接调用sort函数，它会按照元组中第一项的字符串顺序进行排序。

revenue = [('1月', 5610000), ('2月', 4850000), ('3月', 6220000)]
revenue.sort(reverse=True, key=lambda x:x[1])
# 排序后为 [('3月', 6220000), ('1月', 5610000), ('2月', 4850000)]
1
2
3

​ key参数接收的是一个函数，我们在这里给它传递了一个匿名函数，关于函数的使用后面再学习，这里我们需要了解是通过key参数，我们指定了sort排序的依据，就是每个元组里面的第二项。

copy

lst1 = [1, 2, 3]
lst2 = lst1
lst1.append(4)
1
2
3

​ 上面的代码执行完成以后，lst 和 lst2的值都变成了[1, 2, 3, 4] ，但我们在代码里面只修改了lst1,lst2的值也跟着改变了，这不符合我的预期，可能会导致bug。所以，如果我们想要创建一个跟lst1一模一样的新列表，且不再受它以后操作的影响，就可以使用copy函数：

lst1 = [1, 2, 3]
lst2 = lst1.copy()
lst1.append(4)
print(lst1) # [1, 2, 3, 4]
print(lst2) # [1, 2, 3]
1
2
3
4
5

3.3.4 列表表达式

​ 列表表达式是一种快捷的创建列表的表达式，可以将多行代码省略为一行。比如，列出20以内的所有偶数

[i * 2 for i in range(10)]
# [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

# 等效
[i for i in range(0, 20, 2)]
1
2
3
4
5

​ range函数可以接收三个参数：第一个是起始数值（包含），可以省略，默认从0开始；第二个是结束数值（不包含）；第三个是步长，可以省略，默认为1。

# 上面的代码就相当于
even_nums = []
for i in range(0, 20, 2):
	even_nums.append(i)

# 65是大写字母‘A’的ASCII值
[chr(i) for i in range(65, 65 + 26)]
1
2
3
4
5
6
7

3.3.5 举个栗子

​ 销售冠军的例子进一步分析

sales = (
	("Peter", (78, 70, 65)),
	("John", (88, 80, 85)),
	("Tony", (90, 99, 95)),
	("Henry", (80, 70, 55)),
	("Mike", (95, 90, 95)),
)
1
2
3
4
5
6
7

​ 现在我们将计算出每人的总销售额，并按销售额从多到少，存放到一个列表里

top_sales = []
for name, quarter_amount in sales:
	total_amount = sum(quarter_amount)
	top_sales.append((name, total_amount))
top_sales.sort(key=lambda x:x[1], reverse=True)
print(top_sales)
# [('Tony', 284), ('Mike', 280), ('John', 253), ('Peter', 213), ('Henry', 205)]
1
2
3
4
5
6
7

​ 列表表达式，看懂就行

top_sales = [(sale, sum(amount))for sale, amount in sales]
top_sales.sort(key=lambda x:x[1], reverse=True)
print(top_sales)
1
2
3

4. 字典 dict{}

​ 元组或者列表存储数据

top_sales = [('Peter', 213), ('John', 253), ('Tony', 284), ('Henry', 205),('Mike', 280)]
1

​ 可以很方便的取出在这个榜单中第一名、第二名或者任意一名的销售数据。但它有一个缺点，如果我们想取出特定的某个销售人员的数据时，它会很麻烦。比如如果想要找出Mike的数据，只能去循环遍历，一个个的去比对。

for sale, amount in top_sales:
	if sale == 'Mike':
		print(sale, amount)
1
2
3

​ 这样不光写起来麻烦，执行效率也很低，假设这是一个庞大的销售数据库，那要花多少时间寻找呢？所以可以考虑使用字典。

4.1 字典的定义

​ 使用花括号，可以直接定义字典

sales = {
	'Peter': 213,
	'John': 253,
	'Tony': 284,
	'Henry': 205,
	'Mike': 280
}
1
2
3
4
5
6
7

​ 每一行冒号左边的是键（key）,右边的是值（value），称作键值对，以逗号分隔开。在这里我们故意写成每行一个键值对，实际并不要求每行一个，只要用逗号分隔开来就可以。键是不能重复的，值可以重复。

​ 对于top_sales 这种两个一组、一一对应的列表来说，可以直接转换为字典。

# 数据类型强转
sales = dict(top_sales)
# sales现在的值变成了
{
	'Peter': 213,
	'John': 253,
	'Tony': 284,
	'Henry': 205,
	'Mike': 280
}
1
2
3
4
5
6
7
8
9
10

4.2 增删改查

​ 有了字典，那现在就可以快速的取出任意一个人的数据了

# 大小写敏感
print(sales["Mike"])

# 往字典中添加数据
sales['mike'] = 0

# 修改字典中的值
sales['mike'] = 300

# 删除字典中的数据
del sales['mike']
1
2
3
4
5
6
7
8
9
10
11

4.3 遍历字典

​ 字典的遍历和列表、元组、字符串有所区别，由于它的每一项都是一个键值对，所以在遍历时也要注意。

for key_value in sales.items():
	print(key_value)
1
2

​ 注意sales.items() 这种写法，在遍历字典时，这是一种通用的写法。items函数将字典内的内容转换成了一种可迭代的序列，以供for循环遍历，遍历出来的每一项是一个元组，包含了键和值。所以通常我们直接写成这样：

for key, value in sales.items():
	print(key, value)
    
# 如果不使用items函数，那遍历的就是字典所有的key，修改为其他值也一样
for key in sales:
    print(key)
1
2
3
4
5
6

4.4 字典函数

​ 字典有一些函数和列表是一样的，比如clear, copy，这两个不再介绍，我们来看看其他的函数。

get

​ 如果直接访问字典中一个不存在的key，就会产生报错，所以，通常我们如果不确定是否存在某个key时，会先判断一下：

if 'mike' in sales:
	print(sales['mike'])
else:
	print('mike', "no")
1
2
3
4

​ in关键字又一次派上用场了, 在这里用in来检查字典中是否包含"mike"这个键，如果包含则返回True，无论"mike"所对应的值是否为空。这样的写法，很麻烦，每次都要先判断，再查询，这时候get函数就派上用场了。

print(sales.get("Mike"))
print(sales.get("mike", "no"))
# 它表示在字典中查询'mike'键所对应的值，如果不存在'mike'键，则返回0
1
2
3

key/values

​ 如果只想单独列出所有的销售人员名单，可以这样写:

print(sales.keys())
1

​ 进行遍历

for name in sales.keys():
	print(name)
1
2

​ 如果只想计算出所有销售人员的销售额总和，也就是公司总销售额，可以直接取出value部分并求和：

# 仅对单value适用
sum(sales.values())
1
2

5. 集合 set{}

​ 集合在Python中是一个无序的不重复的序列，一般用来删除重复数据，还可以计算交集、并集等。

5.1 集合的定义

​ 这两方式都可以定义一个集合

nums = {1, 2, 3, 4, 5}
nums = set([1, 2, 3, 4, 5])

'''
集合是无序的，虽然我们在书写的时候是按照从小到大的顺序，有时候遍历出来也是有序的，但不能把它视为有序，并作为某些逻辑的依据。
集合最常用的用法是用来消除列表或者元组中的重复元素
'''

lst = [1, 2, 1, 3, 4, 5]
lst = list(set(lst))
# 将lst转成了集合，再将集合转成了列表，最终得到了一个没有重复元素的列表
1
2
3
4
5
6
7
8
9
10
11

5.2 遍历集合

​ 集合的遍历和列表、元组很相像，再次重申，它不是有序的

for n in nums:
	print(n)
1
2

​ 也可以通过len函数来测量它的长度，准备地讲，在数学上叫集合的基数

len(nums)	# 5
1

​ 可以通过in 来判断集合中是否有某个特定的元素

5 in nums	# True
1

5.3 增删改查

​ 往集合里添加一个元素

nums.add(5) # 重复值，do nothing
nums.add(6)
1
2

​ 已经加入集合的元素不能修改，只能删除，删除集合里的元素

# remove函数会从集合里删除指定元素，但如果元素不存在，则会报错
nums.remove(5)
nums.remove(5) # Error

# 如果不想报错，可以使用diiscard函数
nums.discard(5)
1
2
3
4
5
6

​ 从集合内删除并返回一个元素：

# 目测从左侧开始
num = nums.pop()

# 如果集合是空的，则会报错。有时候，我们也会使用pop函数来迭代一个集合
while len(nums) > 0:
	print(nums.pop())
# 这样的好处是可以保证每个元素只被使用一次，不会重复使用
1
2
3
4
5
6
7

5.4 集合函数

# 定义两个集合
s1 = {1, 2, 3}
s2 = {3, 4, 5}

# 求交集
s1.intersection(s2) # {3}

# 求并集
s3 = s1.union(s2)
print(s3) # {1, 2, 3, 4, 5}

# 是否是子集
s1.issubset(s3) # True

# 是否是父集
s3.issuperset(s2) # True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6. 高级数据结构

6.1 树（一对多）

树的一些基础概念：
节点的度：一个节点含有的子树的个数称为该节点的度；
树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
路径：对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径

在树里面有一种特殊的树–二叉树，即每个节点最多含有两个子树的树。

这种树我们称为完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;

1.数学性质：
1）在二叉树的第i层上至多有2^(i-1)个结点（i>0）
2）深度为k的二叉树至多有2^k - 1个结点（k>0）
3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
4）具有n个结点的完全二叉树的深度必为 log2(n+1)
5）对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

2.遍历方法
1）深度遍历：沿着树的深度遍历树的节点，尽可能深的搜索树的分支
深度遍历有三种方式：
（1）先序遍历的顺序为：根节点->左子树->右子树；
（2）中序遍历为：左子树->根节点->右子树；
（3）后序遍历是：左子树->右子树->根节点；
其中的序指的是根节点相对于左右节点的遍历位置。
2）广度遍历：从树的根层级开始一层一层的遍历，遍历完上一层再遍历下一层

3.由遍历构造二叉树（至少需要两组遍历）
后序遍历的第一个字符就是根，因此只需在中序遍历中找到它，就知道左右子树的中序 和后序遍历了。

# 实现一个完全二叉树
#定义树的结点
class node():
    def __init__(self,item,left=None,right=None):
        self.item=item#数据域
        self.left=left#左子树
        self.right=right#右子树
#定义树
class tree():
    def __init__(self,root=None):
        self.root=root
 
    #每加满一个节点，在其左节点下继续加
    def add(self,item):
        t=node(item)
        if self.root==None:
            self.root=t
            return
        q=[self.root]
        while q:
            c=q.pop()
            if c.left==None:
                c.left=t
                return
            elif c.right==None:
                c.right=t
                return
            else:
                q.append(c.right)
                q.append(c.left)
 
    #插入节点，order为插入位置，'L'为左子树，'R'为右子树
    def insert(self,root,item=None,order='L'):
        if root==None:
            root=node(item)
            return
        if order=='L':
            if root.left:
                if root.left.item:
                    return
                else:
                    root.left.item=item
            else:
                root.left=node(item)
        elif order=='R':
            if root.right:
                if root.right.item:
                    return
                else:
                    root.right.item=item
            else:
                root.right=node(item)
        else:
            raise ValueError("insert:order error")
 
    #深度遍历（递归实现）
    def preorder(self,root):#先序遍历
        if not root:
            print("",end="")
        else:
            print(root.item,end=" ")
            self.preorder(root.left)
            self.preorder(root.right)
        
    
    def inorder(self,root):#中序遍历
        if not root:
            print("",end="")
        else:
            self.inorder(root.left)
            print(root.item,end=" ")
            self.inorder(root.right)
        
   
    def postorder(self,root): #后序遍历
        if not root:
            print("",end="")
        else:
            self.postorder(root.left)
            self.postorder(root.right)
            print(root.item,end=" ")
            
    #广度遍历（队列实现）
    def broad(self,root):
        if not root:
            print("",end="")
        q=[root]
        while q:
            for i in range(len(q)):
                t=q.pop(0)
                print(t.item,end=" ")
                if t.left:
                    q.append(t.left)
                if t.right:
                    q.append(t.right)
        
        
    #根据中序遍历和后序遍历构造树，返回树根
    def con(self,mid,post,root):
        if mid==[]:
            return None
        else:
            r=post[-1]
            root=node(r)
            n=mid.index(r)
            leftmid=mid[:n]
            rightmid=mid[n+1:]
            leftpost=find(leftmid,post)
            rightpost=find(rightmid,post)
            root.left=self.con(leftmid,leftpost,root.left)
            root.right=self.con(rightmid,rightpost,root.right)
            return root
        
    #返回由路径元组构成的列表
    def path(self,root):
        def addpath(root,list1,s):
            if not root.left and not root.right:
                s+=(root.item,)
                list1.append(s)
            else:
                s+=(root.item,)
                if root.left:
                    addpath(root.left,list1,s)
                    
                if root.right:
                    addpath(root.right,list1,s)
                    
        list1=[]
        addpath(root,list1,())
        return list1        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

7.1 图(多对多)

1.图的分类

图分为有向图和无向图

1. 无向图：两个顶点之间可以沿着边互相访问，双向连通。
2. 有向图：两个顶点之间只能以弧的箭头方向进行访问，单向连通。

图的连通性：
对于无向图，其连通子图（连通分量）称为连通图
对于有向图，其连通子图（强连通分量）称为强连通图
若任意节点之间均连通，称为完全图。

2. 图的实现

图的实现有四种方法：

1. 邻接矩阵（用具体的数值表示节点之间的关系，可以使用邻接矩阵，假设这个矩阵是A,Aij就表示第i个节点和第j个节点是否相连，为1表示相连，0表示不相连。当然，该数值也可以是边或者弧的权值。）

   

2. 邻接表（对于邻接表来说，一行只代表和他相连的节点。）

   

3. 十字链表（十字链表适用于有向图，操作时也较为方便，但是结构较为复杂，整体的时间复杂度和邻接表一样。）

   3.1 十字链表的结点描述：

   顶点结点：

   1. 数据域
   2. 两个链域指示以该顶点为弧头、弧尾的第一个弧结点

   弧结点：

   1. 数据域指示弧的信息
   2. 两个链域指向弧尾相同的下一条弧和弧头相同的下一条弧
   3. 尾域和头域指示弧头和弧尾这两个结点在图中的位置

   

4. 邻接多重表（邻接多重表适用于无向图，但其结构同十字链表一样，唯一的不同是其顶点结点的链域只有第一天依附于该节点的边（显然无向图没有弧头弧尾一说，故只需要一条边）。）

3.图的算法

遍历方式:
1.深度优先搜索（DFS）–类似于树的先序遍历
2.广度优先搜索（BFS）

最短路径:
1.Dijkstra算法（单源最短路径）

时间复杂度O(n^2)
建立一维辅助数组存储起点到各结点的最短路径的长度
先将起点到各点路径存入辅助数组，然后循环找到辅助数组中路径的最小值，确定起点到该点的最短路径已找到，同时更新辅助数组
2.Floyd算法（多源最短路径）

时间复杂度O(n^3)
建立二维辅助数组存储各结点到其他结点的最短路径的长度
先将各点之间路径存入辅助数组，再循环判断各个路径是否为最短路径：循环比较该路径与以其他结点为中间结点得到的路径大小，然后更新该路径值

7. 队列(Queue)

python在实现队列时，一般使用其内置的库queue。当然也可以使用自定义数组或者链表实现，但是对于python我们说过，但凡能使用内置方法就使用内置方法，一是方便，二是快，三是功能完善。

先进先出队列—FIFO

后入先出队列—LIFO

后入先出队列，后输入的元素会先输出。

这里的后入先出队列，就是栈。（以下的后入先出队列就先用栈代表）

栈，添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。

优先级队列

优先级队列作为一种特殊的队列，会给各数据设置优先级（决定入栈和出栈的顺序），通过堆（heapq库）也可以实现优先级队列，但是堆本质上还是一种完全二叉树。

双端队列

双端队列也是一种特殊的队列，其入队列和出队列可以在队列的两边同时进行，这样的队列更符合实际问题中一般的模型。