Python 数据结构和算法实用指南（一）（2）

Python 数据结构和算法实用指南（一）（1）https://developer.aliyun.com/article/1507516

递归函数

递归是计算机科学中最基本的概念之一。在执行过程中，当一个函数调用自身一次或多次时，它被称为递归。循环迭代和递归在循环通过布尔条件或一系列元素重复执行语句的意义上是不同的，而递归则重复调用一个函数。在 Python 中，我们可以通过在其自身函数体内调用它来实现递归函数。为了防止递归函数变成无限循环，我们需要至少一个测试终止情况的参数来结束递归。这有时被称为基本情况。应该指出，递归与迭代不同。虽然两者都涉及重复，但迭代循环通过一系列操作，而递归重复调用一个函数。从技术上讲，递归是迭代的一种特殊情况，通常总是可以将迭代函数转换为递归函数，反之亦然。递归函数的有趣之处在于它们能够用有限的语句描述一个无限的对象。

以下代码应该演示了递归和迭代之间的区别。这两个函数都简单地打印出低和高之间的数字，第一个使用迭代，第二个使用递归：

请注意，对于iterTest，迭代示例，我们使用 while 语句来测试条件，然后调用打印方法，最后递增低值。递归示例测试条件，打印，然后调用自身，在其参数中递增低变量。一般来说，迭代更有效率；然而，递归函数通常更容易理解和编写。递归函数还可用于操作递归数据结构，如链表和树，我们将会看到。

生成器和协程

我们可以创建不仅返回一个结果而且返回整个结果序列的函数，方法是使用 yield 语句。这些函数被称为生成器。Python 包含生成器函数，这是一种创建迭代器的简单方法，特别适用于替代不可行的长列表。生成器产生项目而不是构建列表。例如，以下代码显示了为什么我们可能选择使用生成器而不是创建列表：

#compares the running time of a list compared to a generator 
import time
#generator function creates an iterator of odd numbers between n and m 
def oddGen(n,m):
    while n<m:
      yield n
      n+=2
#builds a list of odd numbers between n and m 
def oddLst(n,m):
     lst=[]
     while n<m:
        lst.append(n)
        n+=2
     return lst
#the time it takes to perform sum on an iterator
t1=time.time()
sum(oddGen(1,1000000))
print("Time to sum an iterator: %f" % (time.time() - t1))
#the time it takes to build and sum a list
t1=time.time()
sum(oddLst(1,1000000))
print("Time to build and sum a list: %f" % (time.time() - t1))

这将打印出以下内容：

正如我们所看到的，构建一个列表来进行这种计算需要更长的时间。使用生成器的性能改进是因为值是按需生成的，而不是保存在内存中作为列表。计算可以在所有元素生成之前开始，并且只有在需要时才生成元素。

在上面的例子中，sum 方法在需要进行计算时将每个数字加载到内存中。这是通过生成器对象重复调用__next__()特殊方法实现的。生成器永远不会返回除None之外的值。

通常，生成器对象用于 for 循环。例如，我们可以利用前面代码中创建的oddLst生成器函数来打印出1到10之间的奇数：

for i in oddLst (1,10):print(i)

我们还可以创建一个生成器表达式，它除了用括号替换方括号外，使用与列表推导相同的语法并执行与列表推导相同的操作。然而，生成器表达式不会创建一个列表；它创建一个生成器对象。这个对象不会创建数据，而是根据需要创建数据。这意味着生成器对象不支持append()和insert()等序列方法。

但是，您可以使用list()函数将生成器转换为列表：

类和对象编程

类是创建新类型对象的一种方式，它们是面向对象编程的核心。一个类定义了一组在该类的所有实例之间共享的属性。通常，类是一组函数、变量和属性。

面向对象的范式是令人信服的，因为它为我们提供了一种具体的方式来思考和表示程序的核心功能。通过围绕对象和数据而不是动作和逻辑组织我们的程序，我们有了一种强大而灵活的方式来构建复杂的应用程序。当然，动作和逻辑仍然存在，但通过将它们体现在对象中，我们有了一种封装功能的方式，允许对象以非常具体的方式改变。这使得我们的代码更少容易出错，更容易扩展和维护，并能够模拟现实世界的对象。

在 Python 中使用 class 语句创建类。这定义了与一组类实例关联的一组共享属性。一个类通常由一些方法、类变量和计算属性组成。重要的是要理解，定义一个类本身并不会创建该类的任何实例。要创建一个实例，必须将一个变量分配给一个类。类主体由一系列在类定义期间执行的语句组成。在类内部定义的函数称为实例方法。它们通过将该类的实例作为第一个参数传递来对类实例应用一些操作。这个参数按照惯例被称为 self，但它可以是任何合法的标识符。这里是一个简单的例子：

class Employee(object):
    numEmployee=0
    def init (self,name,rate):
        self.owed=0 
        self.name=name
        self.rate=rate 
      Employee.numEmployee += 1
    def del (self): 
        Employee.numEmployee-=1
    def hours(self,numHours):
         self.owed += numHours*self.rate
         return ("%.2f hours worked" % numHours)
    def pay(self):
        self.owed=0
        return("payed %s " % self.name)

类变量，比如numEmployee，在类的所有实例之间共享值。在这个例子中，numEmployee用于计算员工实例的数量。请注意，Employee类实现了__init__和__del__特殊方法，我们将在下一节讨论。

我们可以通过以下方式创建Employee对象的实例，运行方法，并返回类和实例变量：

特殊方法

我们可以使用dir(object)函数获取特定对象的属性列表。以两个下划线开始和结束的方法称为特殊方法。除了以下例外，特殊方法通常由 Python 解释器调用，而不是由程序员调用；例如，当我们使用+运算符时，我们实际上是在调用to _add_()。例如，我们可以使用len(my_object)而不是使用my_object._len_()；在字符串对象上使用len()实际上要快得多，因为它返回表示对象在内存中的大小的值，而不是调用对象的_len_方法。

作为常见做法，我们在程序中实际调用的唯一特殊方法是_init_方法，以调用我们自己的类定义中的超类的初始化程序。强烈建议不要使用双下划线语法来定义自己的对象，因为可能会与 Python 自己的特殊方法产生当前或将来的冲突。

然而，我们可能希望在自定义对象中实现特殊方法，以赋予它们一些内置类型的行为。在下面的代码中，我们创建了一个实现了_repr_方法的类。这个方法创建了一个对象的字符串表示，对于检查目的很有用：

class my_class():
    def __init__(self,greet):
        self.greet=greet 
    def __repr__(self):
        return 'a custom object (%r) ' % (self.greet)

当我们创建这个对象的实例并进行检查时，我们可以看到我们得到了我们定制的字符串表示。注意使用%r格式占位符返回对象的标准表示。这是有用的最佳实践，因为在这种情况下，它向我们显示greet对象是由引号表示的字符串：

继承

继承是面向对象编程语言中最强大的功能之一。它允许我们从其他类继承功能。通过继承，可以创建一个修改现有类行为的新类。继承意味着如果通过继承另一个类创建一个类的对象，那么该对象将具有两个类的所有功能、方法和变量；即父类和新类。我们继承功能的现有类称为父类/基类，新类称为派生/子类。

继承可以用一个非常简单的例子来解释——我们创建一个employee类，具有员工姓名和每小时支付的费率等属性。现在我们可以创建一个新的specialEmployee类，继承自employee类的所有属性。

在 Python 中，继承是通过在类定义中传递继承的类作为参数来完成的。它经常用于修改现有方法的行为。

specialEmployee类的实例与Employee实例相同，只是hours()方法发生了变化。例如，在下面的代码中，我们创建一个新的specialEmployee类，它继承了Employee类的所有功能，并且还改变了hours()方法：

class specialEmployee(Employee):
    def hours(self,numHours):
        self.owed += numHours*self.rate*2 
        return("%.2f hours worked" % numHours)

为了子类定义新的类变量，需要定义一个__init__()方法，如下所示：

class specialEmployee(Employee):
    def __init__(self,name,rate,bonus):
        Employee.__init__(self,name,rate)    #calls the base classes                                                     
        self.bonus=bonus
    def   hours(self,numHours):
        self.owed += numHours*self.rate+self.bonus     
        return("%.2f hours worked" % numHours)

注意，基类的方法不会自动调用，派生类需要调用它们。我们可以使用内置的isinstance(obj1,obj2)函数测试类成员资格。如果obj1属于obj2的类或任何派生自obj2的类，则返回True。让我们考虑以下示例来理解这一点，其中obj1和obj2分别是Employee和specialEmployee类的对象：

#Example issubclass() to check whether a class is a subclass of another class  
#Example isinstance() to check if an object belongs to a class or not 
print(issubclass(specialEmployee, Employee))
print(issubclass(Employee, specialEmployee)) 
d = specialEmployee("packt", 20, 100) 
b = Employee("packt", 20)  
print(isinstance(b, specialEmployee)) 
print(isinstance(b, Employee)) 
# the output prints  
True 
False 
False 
True

通常，所有方法都在类内定义的实例上操作。但这不是必需的。有两种类型的方法——静态方法和类方法。静态方法与类方法非常相似，主要绑定到类，而不是与类的对象绑定。它在类内定义，不需要类的实例来执行。它不对实例执行任何操作，并且使用@staticmethod类装饰器定义。静态方法无法访问实例的属性，因此它们最常见的用法是作为一种方便的方式来将实用函数组合在一起。

类方法在类本身上操作，不与实例一起工作。类方法的工作方式与类变量相关联，而不是该类的实例。类方法是使用@classmethod装饰器定义的，并且在类中与实例方法区分开。它作为第一个参数传递，按照惯例命名为cls。exponentialB类继承自exponentialA类，并将基类变量更改为4。我们也可以运行父类的exp()方法如下：

class exponentialA(object):
    base=3
    @classmethod
    def exp(cls,x):
        return(cls.base**x) 
    @staticmethod   def addition(x, y):  
        return (x+y)
class exponentialB(exponentialA):
        base=4
a = exponentialA() 
b= a.exp(3) 
print("the value: 3 to the power 3 is", b) 
print('The sum is:', exponentialA.addition(15, 10)) 
print(exponentialB.exp(3))
#prints the following output
the value: 3 to the power 3 is 27 
The sum is: 25 
64

静态方法和类方法之间的区别在于，静态方法对类一无所知，它只处理参数，而类方法仅与类一起工作，其参数始终是类本身。

类方法可能有几个有用的原因。例如，因为子类继承了其父类的所有相同特性，所以有可能会破坏继承的方法。使用类方法是定义确切运行哪些方法的一种方式。

数据封装和属性

除非另有规定，所有属性和方法都可以自由访问。这也意味着从基类中定义的所有内容都可以从派生类中访问。当我们构建面向对象的应用程序时，这可能会导致问题，因为我们可能希望隐藏对象的内部实现。这可能会导致派生类中定义的对象与基类之间的命名空间冲突。为了防止这种情况，我们使用双下划线定义私有属性，例如__privateMethod()。这些方法名称会自动更改为__Classname_privateMethod()，以防止与基类中定义的方法发生命名冲突。请注意，这并不严格隐藏私有属性，而只是提供了一种防止命名冲突的机制。

建议在使用类属性定义可变属性时使用私有属性。属性是一种属性，它在调用时不返回存储的值，而是计算其值。例如，我们可以使用以下方式重新定义exp()属性：

class Bexp(Aexp):
    base=3
    def exp(self):
        return(x**cls.base)

摘要

本章为我们提供了 Python 编程的基本基础和介绍。我们描述了 Python 提供的各种数据结构和算法。我们涵盖了变量的使用，列表，一些控制结构，并学习了如何使用条件语句。我们还讨论了 Python 中如何使用函数。我们讨论了各种类型的对象，以及 Python 语言面向对象的一些内容。我们创建了自己的对象并从中继承。

Python 还提供了更多功能。当我们准备在后面的章节中研究一些算法的实现时，下一章将重点介绍数字、序列、映射和集合。这些也是 Python 中的数据类型，在为一系列操作组织数据时非常有用。

进一步阅读

• 学习 Python 作者：Fabrizio Romano: www.packtpub.com/application-development/learning-python。

第二章：Python 数据类型和结构

在本章中，我们将更详细地研究 Python 数据类型。我们已经介绍了两种数据类型，字符串和列表，str()和list()。然而，这些数据类型是不够的，我们经常需要更专门的数据对象来表示/存储我们的数据。 Python 有各种其他标准数据类型，用于存储和管理数据，我们将在本章中讨论。除了内置类型之外，还有几个内部模块，允许我们解决处理数据结构时的常见问题。首先，我们将回顾一些适用于所有数据类型的操作和表达式，并将讨论更多与 Python 数据类型相关的内容。

本章的目标如下：

• 了解 Python 3.7 支持的各种重要内置数据类型
  
• 探索各种高性能替代品的其他附加集合，以替代内置数据类型
  

技术要求

本章中使用的所有代码都在以下 GitHub 链接中提供：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter02。

内置数据类型

Python 数据类型可以分为三类：数字、序列和映射。还有一个表示Null或值的缺失的None对象。不应忘记其他对象，如类、文件和异常也可以被正确地视为类型；但是，它们在这里不会被考虑。

Python 中的每个值都有一个数据类型。与许多编程语言不同，在 Python 中，您不需要显式声明变量的类型。Python 在内部跟踪对象类型。

Python 内置数据类型概述如下表所示：

None 类型

None类型是不可变的。它用作None来表示值的缺失；它类似于许多编程语言中的null，如 C 和 C++。当实际上没有要返回的内容时，对象返回None。当False布尔表达式时，也会返回None。None经常用作函数参数的默认值，以检测函数调用是否传递了值。

数字类型

数字类型包括整数（int），即无限范围的整数，浮点数（float），复数（complex），由两个浮点数表示，以及布尔值（bool）在 Python 中。 Python 提供了允许标准算术运算符（+，-，*和/）对它们进行操作的int数据类型，类似于其他编程语言。布尔数据类型有两个可能的值，True和False。这些值分别映射为1和0。让我们考虑一个例子：

>>> a=4; b=5   # Operator (=) assigns the value to variable
>>>print(a, "is of type", type(a))
4 is of type 
<class 'int'>
>>> 9/5  
1.8
>>>c= b/a  *# division returns a floating point number* *>>>* print(c, "is of type", type(c))
1.25 is of type <class 'float'>
>>> c   # No need to explicitly declare the datatype
1.25

变量a和b是int类型，c是浮点类型。除法运算符（/）始终返回float类型；但是，如果希望在除法后获得int类型，可以使用地板除法运算符（//），它会丢弃任何小数部分，并返回小于或等于x的最大整数值。考虑以下例子：

>>> a=4; b=5   
>>>d= b//a
*>>>* print(d, "is of type", type(d))1 is of type <class 'int'>
>>>7/5  # true division
1.4
>>> -7//5  # floor division operator
-2

建议读者谨慎使用除法运算符，因为其功能根据 Python 版本而异。在 Python 2 中，除法运算符仅返回integer，而不是float。

指数运算符（**）可用于获取数字的幂（例如，x ** y），模数运算符（%）返回除法的余数（例如，a% b返回a/b的余数）：

>>> a=7; b=5 
>>> e= b**a  # The operator (**)calculates power 
>>>e
78125
>>>a%b
2

复数由两个浮点数表示。它们使用j运算符分配，以表示复数的虚部。我们可以通过f.real和f.imag访问实部和虚部，如下面的代码片段所示。复数通常用于科学计算。Python 支持复数的加法，减法，乘法，幂，共轭等，如下所示：

>>> f=3+5j
>>>print(f, "is of type", type(f))(3+5j) is of type <class 'complex'>
>>> f.real
3.0
>>> f.imag
5.0
>>> f*2   # multiplication
(6+10j)
>>> f+3  # addition
(6+5j)
>>> f -1  # subtraction
(2+5j)  

在 Python 中，布尔类型使用真值表示，即True和False；这类似于0和1。Python 中有一个bool类，返回True或False。布尔值可以与逻辑运算符（如and，or和not）结合使用：

>>>bool(2)
True
>>>bool(-2)
True
>>>bool(0)
False

布尔运算返回True或False。布尔运算按优先级排序，因此如果表达式中出现多个布尔运算，则优先级最高的运算将首先发生。以下表格按优先级降序列出了三个布尔运算符：

Python 在评估布尔表达式时非常高效，因为它只在需要时评估运算符。例如，如果在表达式x or y中x为True，则无需评估y，因为表达式无论如何都是True，这就是为什么在 Python 中不会评估y。类似地，在表达式x and y中，如果x为False，解释器将简单地评估x并返回False，而不会评估y。

比较运算符（<，<=，>，>=，==和!=）适用于数字，列表和其他集合对象，并在条件成立时返回True。对于集合对象，比较运算符比较元素的数量，等价运算符（==）在每个集合对象在结构上等价且每个元素的值相同时返回True。让我们看一个例子：

>>>See_boolean = (4 * 3 > 10) and (6 + 5 >= 11)
>>>print(See_boolean)
True
>>>if (See_boolean):
...    print("Boolean expression returned True")
   else:
...  print("Boolean expression returned False")
...
Boolean expression returned True

表示错误

应该注意的是，浮点数的本机双精度表示会导致一些意外的结果。例如，考虑以下情况：

>>> 1-0.9
0.09999999999999998
>>> 1-0.9==.1
False

这是因为大多数十进制小数无法准确表示为二进制小数，这是大多数底层硬件表示浮点数的方式。对于可能存在此问题的算法或应用程序，Python 提供了一个 decimal 模块。该模块允许精确表示十进制数，并便于更好地控制属性，如舍入行为，有效数字的数量和精度。它定义了两个对象，一个表示十进制数的Decimal类型，另一个表示各种计算参数的Context类型，如精度，舍入和错误处理。其用法示例如下：

>>> import decimal
>>> x=decimal.Decimal(3.14)
>>> y=decimal.Decimal(2.74)
>>> x*y
Decimal('8.603600000000001010036498883')
>>> decimal.getcontext().prec=4
>>> x*y
Decimal('8.604')

在这里，我们创建了一个全局上下文，并将精度设置为4。Decimal对象可以被视为int或float一样对待。它们可以进行相同的数学运算，并且可以用作字典键，放置在集合中等等。此外，Decimal对象还有几种数学运算的方法，如自然指数x.exp()，自然对数x.ln()和以 10 为底的对数x.log10()。

Python 还有一个fractions模块，实现了有理数类型。以下示例展示了创建分数的几种方法：

>>> import fractions
>>> fractions.Fraction(3,4)
Fraction(3, 4)
>>> fractions.Fraction(0.5)
Fraction(1, 2)
>>> fractions.Fraction("0.25") 
Fraction(1, 4)

在这里还值得一提的是 NumPy 扩展。它具有数学对象的类型，如数组、向量和矩阵，以及线性代数、傅里叶变换、特征向量、逻辑操作等功能。

成员资格、身份和逻辑操作

成员资格运算符（in和not in）用于测试序列中的变量，如列表或字符串，并执行您所期望的操作；如果在y中找到了x变量，则x in y返回True。is运算符比较对象标识。例如，以下代码片段展示了对比等价性和对象标识：

>>> x=[1,2,3]
>>> y=[1,2,3]
>>> x==y  # test equivalence 
True
>>> x is y   # test object identity
False
>>> x=y   # assignment
>>> x is y
True

序列

序列是由非负整数索引的对象的有序集合。序列包括string、list、tuple和range对象。列表和元组是任意对象的序列，而字符串是字符的序列。然而，string、tuple和range对象是不可变的，而list对象是可变的。所有序列类型都有许多共同的操作。请注意，对于不可变类型，任何操作都只会返回一个值，而不会实际更改该值。

对于所有序列，索引和切片操作适用于前一章节中描述的方式。string和list数据类型在第一章中有详细讨论，Python 对象、类型和表达式。在这里，我们介绍了一些对所有序列类型（string、list、tuple和range对象）都通用的重要方法和操作。

所有序列都有以下方法：

此外，所有序列都支持以下操作：

让我们考虑一个示例代码片段，实现了对list数据类型的一些前述操作：

>>>list() # an empty list   
>>>list1 = [1,2,3, 4]
>>>list1.append(1)  # append value 1 at the end of the list
>>>list1
[1, 2, 3, 4, 1]
>>>list2 = list1 *2    
[1, 2, 3, 4, 1, 1, 2, 3, 4, 1]
>>> min(list1)
1
>>> max(list1)
4
>>>list1.insert(0,2)  # insert an value 2 at index 0
>>> list1
[2, 1, 2, 3, 4, 1]
>>>list1.reverse()
>>> list1
[1, 4, 3, 2, 1, 2]
>>>list2=[11,12]
>>>list1.extend(list2)
>>> list1
[1, 4, 3, 2, 1, 2, 11, 12]
>>>sum(list1)
36
>>> len(list1)
8
>>> list1.sort()
>>> list1
[1, 1, 2, 2, 3, 4, 11, 12]
>>>list1.remove(12)   #remove value 12 form the list
>>> list1
[1, 1, 2, 2, 3, 4, 11]

了解元组

元组是任意对象的不可变序列。元组是一个逗号分隔的值序列；然而，通常的做法是将它们括在括号中。当我们想要在一行中设置多个变量，或者允许函数返回不同对象的多个值时，元组非常有用。元组是一种有序的项目序列，类似于list数据类型。唯一的区别是元组是不可变的；因此，一旦创建，它们就不能被修改，不像list。元组由大于零的整数索引。元组是可散列的，这意味着我们可以对它们的列表进行排序，并且它们可以用作字典的键。

我们还可以使用内置函数tuple()创建一个元组。如果没有参数，这将创建一个空元组。如果tuple()的参数是一个序列，那么这将创建一个由该序列元素组成的元组。在创建只有一个元素的元组时，重要的是要记住使用尾随逗号——没有尾随逗号，这将被解释为一个字符串。元组的一个重要用途是通过在赋值的左侧放置一个元组来一次性分配多个变量。

考虑一个例子：

>>> t= tuple()   # create an empty tuple
>>> type(t)
<class 'tuple'>
>>> t=('a',)  # create a tuple with 1 element
>>> t
('a',)
>>> print('type is ',type(t))
type is  <class 'tuple'>
>>> tpl=('a','b','c')
>>> tpl('a', 'b', 'c')
>>> tuple('sequence')
('s', 'e', 'q', 'u', 'e', 'n', 'c', 'e')
>>> x,y,z= tpl   #multiple assignment 
>>> x
'a'
>>> y
'b'
>>> z
'c'
>>> 'a' in tpl  # Membership can be tested
True
>>> 'z' in tpl
False

大多数运算符，如切片和索引运算符，都像列表一样工作。然而，由于元组是不可变的，尝试修改元组的元素会导致TypeError。我们可以像比较其他序列一样比较元组，使用==、>和<运算符。考虑一个示例代码片段：

>>> tupl = 1, 2,3,4,5  # braces are optional
>>>print("tuple value at index 1 is ", tupl[1])
tuple value at index 1 is  2
>>> print("tuple[1:3] is ", tupl[1:3])
tuple[1:3] is (2, 3)
>>>tupl2 = (11, 12,13)
>>>tupl3= tupl + tupl2   # tuple concatenation
>>> tupl3
(1, 2, 3, 4, 5, 11, 12, 13)
>>> tupl*2      # repetition for tuples
(1, 2, 3, 4, 5, 1, 2, 3, 4, 5)
>>> 5 in tupl    # membership test
True
>>> tupl[-1]     # negative indexing
5
>>> len(tupl)   # length function for tuple
5
>>> max(tupl)
5
>>> min(tupl)
1
>>> tupl[1] = 5 # modification in tuple is not allowed.
Traceback (most recent call last):  
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment
>>>print (tupl== tupl2)
False
>>>print (tupl>tupl2)
False

让我们考虑另一个例子来更好地理解元组。例如，我们可以使用多个赋值来交换元组中的值：

>>> l = ['one','two']
>>> x,y = l
('one', 'two')
>>> x,y = y,x
>>> x,y
('two', 'one')

从字典开始

在 Python 中，字典数据类型是最受欢迎和有用的数据类型之一。字典以键和值对的映射方式存储数据。字典主要是对象的集合；它们由数字、字符串或任何其他不可变对象索引。字典中的键应该是唯一的；然而，字典中的值可以被更改。Python 字典是唯一的内置映射类型；它们可以被看作是从一组键到一组值的映射。它们使用{key:value}的语法创建。例如，以下代码可以用来创建一个将单词映射到数字的字典，使用不同的方法：

>>>a= {'Monday':1,'Tuesday':2,'Wednesday':3} #creates a dictionary 
>>>b =dict({'Monday':1 , 'Tuesday': 2, 'Wednesday': 3})
>>> b
{'Monday': 1, 'Tuesday': 2, 'Wednesday': 3}
>>> c= dict(zip(['Monday','Tuesday','Wednesday'], [1,2,3]))
>>> c={'Monday': 1, 'Tuesday': 2, 'Wednesday': 3}
>>> d= dict([('Monday',1), ('Tuesday',2), ('Wednesday',3)])
>>>d
{'Monday': 1, 'Tuesday': 2, 'Wednesday': 3}

我们可以添加键和值。我们还可以更新多个值，并使用in运算符测试值的成员资格或出现情况，如下面的代码示例所示：

>>>d['Thursday']=4     #add an item
>>>d.update({'Friday':5,'Saturday':6})  #add multiple items
>>>d
{'Monday': 1, 'Tuesday': 2, 'Wednesday': 3, 'Thursday': 4, 'Friday': 5, 'Saturday': 6}
>>>'Wednesday' in d  # membership test (only in keys)
True
>>>5 in d       # membership do not check in values
False

如果列表很长，使用in运算符在列表中查找元素会花费太多时间。在列表中查找元素所需的运行时间随着列表大小的增加而线性增加。而字典中的in运算符使用哈希函数，这使得字典非常高效，因为查找元素所花费的时间与字典的大小无关。

注意当我们打印字典的{key: value}对时，它并没有按特定顺序进行。这不是问题，因为我们使用指定的键来查找每个字典值，而不是一个有序的整数序列，就像对字符串和列表一样：

>>> dict(zip('packt', range(5)))
{'p': 0, 'a': 1, 'c': 2, 'k': 3, 't': 4}
>>> a = dict(zip('packt', range(5)))
>>> len(a)   # length of dictionary a
5
>>> a['c']  # to check the value of a key
2
>>> a.pop('a')  
1
>>> a{'p': 0, 'c': 2, 'k': 3, 't': 4}
>>> b= a.copy()   # make a copy of the dictionary
>>> b
{'p': 0, 'c': 2, 'k': 3, 't': 4}
>>> a.keys()
dict_keys(['p', 'c', 'k', 't'])
>>> a.values()
dict_values([0, 2, 3, 4])
>>> a.items()
dict_items([('p', 0), ('c', 2), ('k', 3), ('t', 4)])
>>> a.update({'a':1})   # add an item in the dictionary
>>> a{'p': 0, 'c': 2, 'k': 3, 't': 4, 'a': 1}
>>> a.update(a=22)  # update the value of key 'a'
>>> a{'p': 0, 'c': 2, 'k': 3, 't': 4, 'a': 22}

以下表格包含了所有字典方法及其描述：

Python

应该注意，当将in运算符应用于字典时，其工作方式与应用于列表时略有不同。当我们在列表上使用in运算符时，查找元素所需的时间与列表的大小之间的关系被认为是线性的。也就是说，随着列表的大小变大，找到元素所需的时间最多是线性增长的。算法运行所需的时间与其输入大小之间的关系通常被称为其时间复杂度。我们将在接下来的章节中更多地讨论这个重要的主题。

与list对象相反，当in运算符应用于字典时，它使用哈希算法，这会导致每次查找时间的增加几乎独立于字典的大小。这使得字典作为处理大量索引数据的一种方式非常有用。我们将在第四章和第十四章中更多地讨论这个重要主题，即哈希的增长率。

Python 数据结构和算法实用指南（一）（3）https://developer.aliyun.com/article/1507529