数据结构教程（Python语言描述）（第2版微课视频版）课件全套 李春葆 第1-9章 绪论、线性表-排序

第1章绪论1.1什么是数据结构1.4算法分析1.2算法及其描述1.5数据结构的目标CONTENTS提纲1.3Python简介1/1261.1什么是数据结构1.1.1数据结构的定义用计算机解决一个具体问题的步骤（1）分析问题，确定数据模型。（2）设计相应的算法。（3）编写程序，运行并调试程序直至得到正确的结果。2/126需要从数据入手来分析并得到解决问题的方法数据是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。数据元素是数据的基本单位（例如，A班中的每个学生记录都是一个数据元素），也就是说数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理数据项是具有独立含义的数据最小单位，也称为成员或域（例如，A班中每个数据元素即学生记录是由学号、姓名、性别和班号等数据项组成）。结构化数据3/126学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表数据数据项数据元素4/126

数据对象是性质相同的有限个数据元素的集合，它是数据的一个子集。

如大写字母数据对象是集合C={'A'，'B'，'C'，…，'Z'}；1～100的整数数据对象是集合N={1，2，…，100}。

默认情况下，数据结构中的数据都指的是数据对象。5/126数据结构是指所涉及的数据元素以及数据元素之间的关系，可以看作是相互之间存在着特定关系的数据元素的集合。可时把数据结构看成是带结构的数据元素的集合。数据结构＝数据对象＋结构数据元素之间的关系构成结构相同性质的数据元素的集合6/126数据元素之间的关系

结构,现实世界的结构是纷繁复杂的

微观世界―DNA结构7/126

宏观世界―建筑物的结构8/126数据结构中讨论的元素关系主要是指相邻关系或邻接关系。相邻不相邻学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英829/126一个数据结构的几个方面：逻辑结构存储结构数据运算数据元素之间的逻辑关系

数据的逻辑结构。数据元素及其关系在计算机存储器中的存储方式

数据的存储结构（或物理结构）。施加在该数据上的操作

数据运算。10/1261.1.2数据的逻辑结构数据的逻辑结构是面向用户的，它反映数据元素之间的逻辑关系而不是物理关系。数据的逻辑结构是独立于计算机的。11/1261.逻辑结构的表示

由于数据逻辑结构是面向用户的，可以采用表格、图等用户容易理解的形式表示。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表例1.112/126XX大学计算机学院电子信息学院……教务处学生处科学系工程系应用系招生办就业办……例1.213/126例1.3北京郑州武汉上海南京南昌长沙杭州14/126

为了更通用地描述数据的逻辑结构，通常采用二元组表示数据的逻辑结构，一个二元组如下：

B=(D，R)

其中，B是一种逻辑数据结构，D是数据元素的集合，在D上数据元素之间可能存在多种关系，R是所有关系的集合。即：

D={di

|0≤i≤n-1，n≥0}R={rj

|1≤j≤m，m≥0}15/126R中的某个关系rj（1≤j≤m）是序偶的集合。对于rj中的任一序偶<x，y>（x，y∈D），把x叫做序偶的第一元素，把y叫做序偶的第二元素，又称序偶的第一元素为第二元素的前驱元素，称第二元素为第一元素的后继元素。如在<x，y>的序偶中，x为y的前驱元素，而y为x的后继元素。若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。对于对称序偶，即满足这样的条件：若<x，y>∈r（r∈R），则<y，x>∈r（x，y∈D），可用圆括号代替尖括号，即(x，y)∈r。R={rj

|1≤j≤m，m≥0}16/1262.逻辑结构的类型集合：结构中数据元素之间除了“同属于一个集合”的关系外，没有其他关系，与数学中的集合概念相同。17/126线性结构：若结构是非空的，则有且仅有一个开始元素和终端元素，并且所有元素最多只有一个前驱元素和一个后继元素。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表18/126树形结构：若结构是非空的，则有且仅有一个元素为开始元素（也称为根结点），可以有多个终端元素，每个元素有零个或多个后继元素，除开始元素外每个元素有且仅有一个前驱元素。XX大学计算机学院电子信息学院……教务处学生处科学系工程系应用系招生办就业办……19/126北京郑州武汉上海南京南昌长沙杭州图形结构：若结构是非空的，则每个元素可以有多个前驱元素和多个后继元素。20/1261.1.3数据的存储结构数据在计算机存储器中的存储方式就是存储结构。它是面向程序员的。逻辑结构存储结构映射设计存储结构的这种映射应满足两个要求：存储所有元素存储数据元素间的关系21/126

【例1.5】对于表1.1所示高等数学成绩表，设计多种存储结构，并讨论各种存储结构的特性。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82高等数学成绩表22/126存储结构1：用Python语言中的列表来存储高等数学成绩表设计学生类Stud1如下：classStud1: #高数成绩顺序表元素类型def__init__(self,no1,name1,score1): #构造函数self.no=no1=name1self.score=score1def__repr__(self): #输出高数成绩元素的格式returnstr(self.no)+"\t\t"++"\t\t"+str(self.score)23/126defCreate(self):#创建高数成绩顺序表self.data.append(Stud1(2018001,"王华",90))self.data.append(Stud1(2018010,"刘丽",62))self.data.append(Stud1(2018006,"陈明",54))self.data.append(Stud1(2018009,"张强",95))self.data.append(Stud1(2018007,"许兵",76))self.data.append(Stud1(2018012,"李萍",88))self.data.append(Stud1(2018005,"李英",82))定义一个data列表（所有的元素类型均为Stud1）存放高等数学成绩表：学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英8224/126…data[0]2018001王华90data[1]2018010刘丽62data[6]2018005李英82学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82映射25/126…data[0]2018001王华90data[1]2018010刘丽62data[6]2018005李英82所有元素存放在一片地址连续的存储单元中。逻辑上相邻的元素在物理位置上也是相邻的，所以不需要额外空间表示元素之间的逻辑关系。该存储结构的特性是：称为顺序存储结构。26/126存储结构2：用Python语言中的单链表来存储高等数学成绩表。设计存放高等数学成绩表的结点类Stud2如下：classStud2:#高数成绩单链表结点类型def__init__(self,no1,name1,score1):#构造函数self.no=no1=name1self.score=score1self.next=Nonedef__repr__(self):#输出高数成绩结点的格式returnstr(self.no)+"\t\t"++"\t\t"+str(self.score)27/126建立一个用于存放高等数学成绩表的单链表（开始结点为head）如下：defCreate(self):#创建高数成绩单链表self.head=Stud2(2018001,"王华",90)#高数成绩单链表首结点p2=Stud2(2018010,"刘丽",62)p3=Stud2(2018006,"陈明",54)p4=Stud2(2018009,"张强",95)p5=Stud2(2018007,"许兵",76)p6=Stud2(2018012,"李萍",88)p7=Stud2(2018005,"李英",82)self.head.next=p2#建立结点之间的关系p2.next=p3p3.next=p4p4.next=p5p5.next=p6p6.next=p7p7.next=None #尾结点的next置为空建立每个元素的结点建立结点之间关系以表示对应元素的逻辑关系28/126head2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英82null用head唯一标识单链表数据元素存放在任意的存储单元中，这组存储单元可以是连续的，也可以是不连续的。通过指针域来反映数据元素的逻辑关系。这种存储结构的特性：称为链式存储结构。29/126顺序存储结构链式存储结构索引存储结构哈希（散列）存储结构在软件开发中，人们设计了各种存储结构。归纳为4种基本的存储结构。30/1261.1.4数据的运算将数据存放在计算机中的目的是为了实现一种或多种运算。运算包括功能描述（或运算功能）和功能实现（或运算实现）。前者是基于逻辑结构的，是用户定义的，是抽象的。后者是基于存储结构的，是程序员用计算机语言或伪码表示的，是详细的过程，其核心是设计实现某一运算功能的处理步骤，即算法设计。31/126例如，对于高等数学成绩表这种数据结构，可以进行一系列的运算：增加一个学生成绩记录删除一个学生成绩记录求所有学生的平均分查找序号为i的学生分数等。学号姓名分数2018001王华902018010刘丽622018006陈明542018009张强952018007许兵762018012李萍882018005李英8232/126例如，查找序号为i的学生分数，其本身就是运算的功能描述。但在顺序存储结构和链式存储结构中的实现过程不同的。defFindi(self,i):#查找序号为i的学生分数asserti>=0andi<len(self.data)returnself.data[i].score;#i正确时返回分数在顺序存储结构即data列表中实现查找同一运算，在不同存储结构中的实现过程是不同的。33/126defFindi(self,i):

#查找序号为i的学生分数j=0p=self.head #p指向首结点whilej<iandp!=None:j+=1p=p.next

asserti>=0andp!=Nonereturnp.score #i正确时返回分数在链式存储结构即head单链表中实现查找:34/126同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。提示35/1261.1.5数据结构和数据类型1.数据类型数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。例如，Python中的short就是整型数据类型（16位）。-32768~32767＋、－、*、／

值的集合一组操作36/126数据结构是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。在程序设计语言提供的数据类型支持下，就可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。37/1262.抽象数据类型

抽象数据类型（ADT）指的是从求解问题的数学模型中抽象出来的数据逻辑结构和运算（抽象运算），而不考虑计算机的具体实现。抽象数据类型=逻辑结构＋抽象运算38/126ADT抽象数据类型名

{数据对象：数据对象的声明

数据关系：数据关系的声明

基本运算：基本运算的声明}ADT抽象数据类型名ADT基本格式39/126

【例1.6】构造集合ADTSet，假设其中元素为整型，遵循标准数学定义，基本运算包括:

求集合长度、求第i个元素、判断一个元素是否属于集合、向集合中添加一个元素、从集合中删除一个元素、复制集合和输出集合中所有元素。

另外增加3个集合运算:

求两个集合并Union、集合交Inter和集合差Diff。40/126运算功能描述ADTSet

#集合的抽象数据类型{数据对象：data={di|0≤i≤size-1} #存放集合中元素

数据关系：

无

基本运算：getsize() #返回集合的长度get(inti) #返回集合的第i个元素IsIn(Ee) #判断e是否在集合中add(Ee) #将元素e添加到集合中delete(Ee) #从集合中删除元素eCopy(s) #返回当前集合的复制集合display() #输出集合中的元素Union(Sets2) #求s3=s1∪s2(s1为当前集合)Inter(Sets2) #求s3=s1∩s2(s1为当前集合)Diff(Sets2) #求s3=s1-s2(s1为当前集合)}ADTSet41/126Complex编程实现该数据结构ADT抽象数据类型实质上就是对一个求解问题的形式化描述（与计算机无关），程序员可以在理解基础上实现它。42/1261.2算法及其描述1.2.1什么是算法算法是对特定问题求解步骤的一种描述，它是指令的有限序列。43/126算法具有以下五个重要的特性有穷性。指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。确定性。对于每种情况下执行的操作，在算法中都有确定的含义，不会出现二义性。并且在任何条件下，算法都只有一条执行路径。44/126可行性。算法的每条指令都可以通过已经实现的基本运算执行，并且能够在有限次内实现，即便人借助纸和笔都可以完成。设两数为a、b(a≥b)，求a和b最大公约数（a，b）的步骤如下：

（1）用a除以b(a≥b)，得a

b=q..r1（r1≥0）。

（2）若r1=0，则（a，b）=b，结束。

（3）若r1≠0，则再用b除以r1，得b

r1=q..r2（r2≥0）。

（4）若r2=0，则（a，b）=r1，结束；若r2≠0，则继续，…

，如此下去，直到能整除为止。其最后一个余数为0的除数即为（a，b）的最大公约数。

求最大公约数算法！45/126输入性。算法有零个或多个输入。大多数算法中输入参数是必要的，但对于较简单的算法，如计算1+2的值，不需要任何输入参数，因此算法的输入可以是零个。输出性。算法至少有一个或多个输出。算法用于某种数据处理，如果没有输出，这样的算法是没有意义的，算法的输出是和输入有着某些特定关系的量。46/126算法（有穷性、确定性、可行性）输入输出求解问题47/126【例1.7】考虑下列两段描述：（1）描述一

（2）描述二

defexam1(): defexam2():n=2 y=0whilen%2==0: x=5/yn=n+2 print(x)print(n)这两段描述均不能满足算法的特征，试问它们违反了哪些特性？有穷性可行性48/1261.2.2算法描述通常算法用一个或者几个函数（或者方法）描述，其一般格式：def算法对应的函数或者方法名(形参列表):#临时局部变量的定义#实现由输入参数到输出参数的操作

…函数体函数的返回值通常为布尔类型，表示算法是否成功执行。形参列表表示算法的参数，由输入参数和输出参数构成。函数体实现算法的功能。49/126例如，求和问题是当n≥1时求s=1+2+…+n。输入参数为n，操作结果为s。初始条件是n≥1。当初始条件不满足，返回False，否则计算出s并返回True。50/126求解算法1defSum1(n,s):#算法1if(n<1):returnFalses.append(n*(n+1)//2)returnTruen=-5s=[]ifSum1(n,s):print("1到%d的和=%d"%(n,s[0]))else:print("参数n错误") #输出：参数n错误51/126求解算法2defSum2(n): #算法2ifn<1:return-1returnn*(n+1)//2n=5s=Sum2(n)ifs!=-1:print("1到%d的和=%d"%(n,s)) #输出：1到5的和=15else:print("参数n错误")在有些情况下可以直接用算法的返回值来区分输入参数的正确性。52/126求解算法3defSum3(n): #算法3

assertn>=1,"参数n错误" #检测n的初始条件returnn*(n+1)//2;n=-5print("1到%d的和=%d"%(n,Sum3(n)))在用Python语言描述算法时，通常用assert语句检测初始条件。53/1261.3Python简介1.3.1Python的标准数据类型Python3中有6个标准的数据类型数值（Number）字符串（String）元组（Tuple）不可变的数据类型列表（List）集合（Set）字典（Dictionary）可变的数据类型54/1261.数值类型Python3支持int、float、bool和complex。int称为是整型或整数，可以是正或负整数，不带小数点。float称为浮点型或浮点数，浮点数由整数部分与小数部分组成，浮点数也可以使用科学计数法表示，如2.5e2=2.5×102=250。bool称为布尔型或布尔数，只能取值True或者False。布尔数的运算符有not（非）、and（与）和or（或）。complex称为复数，复数由实数部分和虚数部分构成，可以用a+bj或者complex(a，b)表示，复数的实部a和虚部b都是浮点型。55/126类型转换函数int(x)：将x转换为一个整数。float(x)：将x转换到一个浮点数。complex(x)：将x转换到一个复数，实数部分为x，虚数部分为0。complex(x,y)：将x和y转换到一个复数，实数部分为x，虚数部分为y。x和y是数值表达式。56/126常用的数值运算符有+（加）、-（减）、*（乘）、/（除）、//（整除）、%（求模）和**（乘方）。Python变量在使用前必须先“定义”（即赋予变量一个值），否则会出现错误。不同类型的数值混合运算时会将整数转换为浮点数。57/126Python内置的type()函数可以用来查询变量所指的对象类型。a,b,c,d=20,5.5,True,4+3jprint(type(a),type(b),type(c),type(d))

#输出：<class'int'><class'float'><class'bool'><class'complex'>58/126id()函数用于获取对象的内存地址。a=1print(id(a)) #输出：264070320a=a+1print(id(a)) #输出：264070336a=12.5print(id(a)) #输出：1991080059/1262.字符串类型字符串是Python中最常用的数据类型。使用单引号或者双引号来创建字符串。Python不支持单字符类型，单字符在Python中也是作为一个字符串使用。Python字符串中可以包含转义字符，用反斜杠（\）表示，例如，\'表示单引号，\n表示换行，\t表示横向制表符，\r表示回车等。60/126+：字符串连接，a+b的输出结果是"HelloPython"。*：重复输出字符串，a*2的输出结果是"HelloHello"。[]：通过索引获取字符串中字符，a[1]的输出结果是e。[:]：截取字符串中的一部分，遵循左闭右开原则，a[1:4]的输出结果是a[1..3]即ell（a[1:4]等同于a[1:4:1]），而a[4:1:-1]的输出结果是a[2..4]的反向字符串即oll（依次输出a[4]，a[4-1]即a[3]，a[3-1]即a[2]，a[2-1]为a[1]，由于是右开，所以不输出a[1]）。in：成员运算符，如果字符串中包含给定的字符时返回True，'H'ina的输出结果是True。notin：成员运算符，如果字符串中不包含给定的字符返回True，'M'notina的输出结果True。r/R：原始字符串，所有的字符串都是直接按照字面的意思来使用，没有转义特殊或不能打印的字符。如print(r'\n')的输出结果是\n。Python提供了一些常用的字符串运算符，例如，a="Hello"，b="Python"61/126Python提供了许多字符串内建函数len(string)string.count(str,beg=0,end=len(string))string.find(str,beg=0,end=len(string))string.rfind(str,beg=0,end=len(string))string.index(str,beg=0,end=len(string))string.rindex(str,beg=0,end=len(string))string.isdigit()string.replace(str1,str2,

num=string.count(str1))string.split(str="",num=string.count(str))string.strip([chars])62/1263.列表类型列表是最常用的Python数据类型，基本形式是一个方括号内以逗号分隔的若干值，属于Python中最常见的序列类型。所有序列类型中的每个元素都有一个位置或索引，第一个索引是0，第二个索引是1，依此类推。a=[]a=[1,5,2]a=["abc","xyz","123"]63/1261）创建列表

创建一个列表只要逗号分隔的不同数据项用方括号括起来即可。就语法上讲，Python中列表的数据项不需要具有相同的类型，例如：

a=[1,"beijing",2,"shenzhen",3,"nanjing",4,"wuhan"]由于数据结构中讨论的数据一般指数据对象，而数据对象具有相同的类型，所以在数据结构中通常将列表元素组织成相同的类型的嵌套列表形式，例如：

city=[[1,"beijing"],[2,"shenzhen"],[3,"nanjing"],[4,"wuhan"]]64/1262）访问列表中的值可以使用索引来访问列表中的值，也可以使用方括号的形式截取元素。注意，列表的索引是从0开始计算（0相当于第一个元素），-1表示倒数第一个元素，-2表示倒数第二个元素，以此类推。city=[[1,"beijing"],[2,"shenzhen"],[3,"nanjing"],[4,"wuhan"]]print("city[0]:",city[0]) #输出：city[0]:[1,'beijing']print("city[-1]:",city[-1]) #输出：city[-1]:[4,'wuhan']65/1263）列表脚本操作符list1=[1,2,3]list2=[4,5,6]list=list1+list2 #连接操作print(list) #输出：[1,2,3,4,5,6]list=list1*3 #重复操作print(list) #输出：[1,2,3,1,2,3,1,2,3]forxin[1,2,3]:print(x,end="") #迭代操作，输出：123列表对+和*的操作符与字符串相似。+号用于连接列表，*号用于重复列表。66/1264）列表的截取print("city[1:3]:",city[1:3])

#输出：city[1:3]:[[2,'shenzhen'],[3,'nanjing']]print("city[-1:-3:-1]:",city[-1:-3:-1])

#输出：city[-1:-3:-1]:[[4,'wuhan'],[3,'nanjing']]列表的截取操作与字符串截取操作类似。67/1265）更新列表可以对列表的数据项进行修改或更新。通常使用append()函数添加列表项。使用remove()函数删除列表项。68/1266）列表的函数len(list)：返回列表中的元素个数。max(list)：返回列表中元素最大值。min(list)：返回列表中元素最小值。list(seq)：将可迭代对象seq转换为列表。69/1267）range()函数和enumerate()函数range()函数返回的是一个可迭代对象（类型是对象），而不是列表类型，常用使用格式：range(start,stop[,step])它产生[start，stop)范围内步长为step的整数对象，start默认为0，step默认为1。当start和step取默认值时的使用格式为：range(stop)。print(type(range(5))) #输出:<class'range'>print(list(range(5))) #输出:[0,1,2,3,4]print(list(range(1,5))) #输出:[1,2,3,4]print(list(range(5,1,-1))) #输出:[5,4,3,2]70/126enumerate()函数用于将一个可遍历的数据对象（如列表、元组或字符串）组合为一个索引序列，同时列出数据和数据下标，一般用在for循环当中。enumerate()函数的语法格式：enumerate(sequence,[start=0])，其中sequence表示一个序列，start表示下标起始位置（默认值为0）。a=[1,2,3]forindex,iteminenumerate(a,5): #指出下标起始位置为5print(index,item)516273输出71/1268）列表推导式a=[2,4,6]b=[3*xforxina] #将列表a中每个数值乘3得到新列表bprint(b) #输出:[6,12,18]c=[3*xforxinaifx>3] #用if子句作为过滤器print(c) #输出:[12,18]d=[[x,x**2]forxina]print(d) #输出:[[2,4],[4,16],[6,36]]v1=[2,4,6]v2=[4,3,-9]v3=[x*yforxinv1foryinv2]print(v3)#输出:[8,6,-18,16,12,-36,24,18,-54]v4=[x+yforxinv1foryinv2]print(v4) #输出:[6,5,-7,8,7,-5,10,9,-3]v5=[v1[i]*v2[i]foriinrange(len(v1))]print(v5) #输出:[8,12,-54]72/1269）列表元素做映射map()函数会根据提供的函数对指定列表做映射。语法格式：map(function,iterable,…)其中，function指定一个函数，iterable指定一个或多个列表，其返回值是一个迭代器，可以通过list()函数转换为列表。defsquare(x): #定义计算平方数的函数returnx**2

#主程序a=[1,2,3,4,5]b=map(square,a) #计算列表a中各个元素的平方print(list(b))#输出:[1,4,9,16,25]c=map(lambdax:x**2,a) #使用lambda匿名函数print(list(c))#输出:[1,4,9,16,25]v1=[1,3,5,7,9]v2=[2,4,6,8,10]v3=map(lambdax,y:x+y,v1,v2)#对相同位置的列表数据进行相加print(list(v3))#输出:[3,7,11,15,19]73/12610）列表的方法list.clear()：清空列表。list.append(obj)：在列表末尾添加新的对象。list.count(obj)：统计某个元素在列表中出现的次数。list.index(obj)：从列表中找出某个值第一个匹配项的索引位置。list.insert(index,obj)：将对象插入列表。list.pop([index=-1])：移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。list.remove(obj)：移除列表中某个值的第一个匹配项。list.reverse()：反向列表中元素。list.sort()：对原列表进行排序。list.copy()：复制列表。74/12611）列表元素的排序用链表的内建函数list.sort进行排序和用序列类型函数sorted(list)进行排序。两者的区别是，sorted(list)返回一个对象，可以用作表达式，原来的list不变，生成一个新的排好序的list对象，而list.sort()不会返回对象，改变原有的list。75/126list.sort()的使用格式：list.sort(func=None,key=None,reverse=False)

其中，key指出用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。reverse指出排序规则，reverse=True为降序，reverse=False为升序（默认）。list.sort()list=[2,5,8,9,3]list.sort() #升序排序print(list) #输出：[2,3,5,8,9]list.sort(reverse=True) #降序排序print(list) #输出：[9,8,5,3,2]76/126对于多关键字排序，key可以使用operator模块提供的itemgetter函数获取对象的哪些维的数据，参数为一些序号。operator.itemgetter函数获取的不是值，而是定义了一个函数，通过该函数作用到对象上才能获取值。也可以采用lambda函数，在需要反序排列的数值关键字前加“-”号。fromoperatorimportitemgetter,attrgetterlist=[('b',3),('a',1),('c',3),('a',4)]list.sort(key=itemgetter(1),reverse=True)#对第二个关键字降序排序print(list) #输出：[('a',4),('b',3),('c',3),('a',1)]list.sort(key=itemgetter(0,1),reverse=True)#第一个和第二个关键字降序print(list) #输出：[('c',3),('b',3),('a',4),('a',1)]list.sort(key=lambdax:x[0]) #对第一个关键字升序排序print(list) #输出：[('a',4),('a',1),('b',3),('c',3)]list.sort(key=lambdax:(x[0],-x[1]))#第一个关键字升序,第二个关键字降序print(list) #输出：[('a',4),('a',1),('b',3),('c',3)]77/1264.元组类型Python的元组与列表类似，不同之处在于元组的元素不能修改。元组使用小括号，列表使用方括号。元组创建很简单，只需要在括号中添加元素，并使用逗号隔开即可。78/1265.字典类型字典是另一种可变的数据类型，且可存储任意类型对象。字典中的每个元素是键值（每个键值元素由key:value构成，其中key是键，value是对应的值）元素之间用逗号分隔，整个字典包括在花括号({})中。形如：d={key1:value1,key2:value2,…}其中键必须是唯一的，但值则不必，值可以取任何数据类型，但键必须是不可变的数据类型，如字符串、数字或元组。79/1261）创建字典dict1={}print(dict1) #输出：{}dict2={1:"beijing",2:"shenzhen",3:"nanjing",4:"wuhan"}print(dict2) #输出：{1:'beijing',2:'shenzhen',3:'nanjing',4:'wuhan'}80/1262）访问字典里的值dict2={1:"beijing",2:"shenzhen",3:"nanjing",4:"wuhan"}print("dict2[2]:%s"%(dict2[2])) #输出:shenzhen81/1263）修改字典dict2={1:"beijing",2:"shenzhen",3:"nanjing",4:"wuhan"}dict2[3]="chengdu" #更新print(dict2) #输出:{1:'beijing',2:'shenzhen',3:'chengdu',4:'wuhan'}dict2[5]="nanjing" #添加信息print(dict2)#输出:{1:'beijing',2:'shenzhen',3:'chengdu',4:'wuhan',5:'nanjing'}给已经存在的键赋值可以修改相应的元素。给不存在的键赋值可以添加相应的新元素。82/1264）删除字典元素dict2={1:"beijing",2:"shenzhen",3:"nanjing",4:"wuhan"}deldict2[3]#删除print(dict2) #输出：{1:'beijing',2:'shenzhen',4:'wuhan'}可以使用del()函数删除指定键的元素83/1265）字典内置函数len(dict)：返回字典中的元素个数，即键的总数。str(dict)：输出字典，以可打印的字符串表示。84/1266）字典内置方法dict.clear()：删除字典内所有元素。dict.get(key,default=None)：返回指定键的值，如果值不在字典中返回default值。keyindict：如果键key在字典dict里返回True，否则返回False。dict.items()：以列表返回可遍历的（键,值）元组数组。dict.keys()：返回一个迭代器，可以使用list()来转换为列表。dict.setdefault(key,default=None)：和get()类似,但如果键不存在于字典中，将会添加键并将值设为default。dict.values()：返回一个迭代器，可以使用list()来转换为列表。pop(key[,default])：删除字典给定键key所对应的值，返回值为被删除的值。key值必须给出，否则返回default值。popitem()：随机返回并删除字典中的最后一对键和值。85/1267）字典遍历在字典中遍历时，关键字和对应的值可以使用items()方法同时解读出来。d={'mary':90,'john':80,'smith':54}forname,vind.items(): print(name,v)mary90john80smith54输出86/1266.集合类型集合是一个无序的不重复元素序列，其基本功能包括关系测试和消除重复元素。两个集合a和b之间可以做+、|、&和^运算。a-b返回a中包含而b中不包含的元素。a|b返回a或b中包含的所有元素的集合。a&b返回a和b中都包含的元素集合。a^b返回不同时包含于a和b的元素的集合。87/1261）创建集合a={'a','b','c','d','a'}b=set("cabdb")print(a) #去重，输出：{'c','d','a','b'}print(len(a)) #输出：4print(b) #去重，输出：{'c','d','a','b'}print(len(a)) #输出：488/1262）判断元素是否在集合中基本格式：xins判断元素x是否在集合s中，存在返回True，不存在返回False。89/1263）集合内置方法set.add()：为集合添加元素set.clear()：移除集合中的所有元素set.difference()：返回多个集合的差集ersection()：返回集合的交集set.isdisjoint()：判断两个集合是否包含相同的元素，如果没有返回True，否则返回False。set.issubset()：判断指定集合是否为该方法参数集合的子集。set.remove()：移除指定元素，如果元素不存在，则会发生错误。set.discard(x)：移除集合中的元素，且如果元素不存在，不会发生错误。set.union()：返回两个集合的并集set.update()：给集合添加元素90/1261.3.2列表的拷贝1.非拷贝方法—直接赋值如果用赋值运算符“=”直接赋值如a=b，它是一种非拷贝方法。a=b后a和b两个列表是等价的，修改其中任何一个列表都会影响到另一个列表。a=[1,2,3]b=aprint(a) #输出：[1,2,3]a[0]=4print(a) #输出：[4,2,3]print(b) #输出：[4,2,3]b[1]=5print(a) #输出：[4,5,3]print(b) #输出：[4,5,3]91/1262.列表的深拷贝列表之间的深拷贝是通过调用copy模块的deepcopy()实现的。例如b=copy.deepcopy(a)，则无论a有多少层，得到的新列表b都是和原来无关的，这是最安全最最有效的拷贝方法。importcopy #导入copy模块a=[1,[1,2,3],4]b=copy.deepcopy(a)print(a) #输出：[1,[1,2,3],4]print(b) #输出：[1,[1,2,3],4]b[0]=3b[1][0]=3print(a) #输出：[1,[1,2,3],4]print(b) #输出：[3,[3,2,3],4]92/1263.列表的浅拷贝可以使用列表的copy()方法实现列表的浅拷贝。a=[1,[1,2,3],4]b=a.copy()print(a) #输出：[1,[1,2,3],4]print(b) #输出：[1,[1,2,3],4]b[0]=3b[1][0]=3print(a) #输出：[1,[3,2,3],4]print(b) #输出：[3,[3,2,3],4]93/1261.3.3输入输出和文件操作1.输入输出Python3中使用input()函数接受一个标准输入数据，返回为字符串类型。语法格式：变量名=input("提示信息")。94/126使用print()函数实现输出。基本语法格式：print(objects,sep='',end='\n',file=sys.stdout)>>>print("HelloWorld")HelloWorld>>>a=1>>>b='runoob'>>>print(a,b)1runoob>>>print("aaa""bbb")aaabbb>>>print("aaa","bbb")aaabbb>>>print("www","runoob","com",sep=".")

#设置间隔符为','95/1262.文件操作为了实现文件操作，必须先用open()函数打开一个文件，创建对应的file对象，再使用相关的方法对其进行读写操作。open()函数的基本语法格式：open(name[,mode])其中name为一个包含了要访问的文件名称的字符串。mode指出打开文件的模式，包含只读、写入和追加等，默认文件访问模式为只读（r）。96/126r：以只读方式打开文件。文件的指针将会放在文件的开头。这是默认模式。r+：打开一个文件用于读写。文件指针将会放在文件的开头。rb，rb+：分别与r和r+类似，针对二进制文件。w：打开一个文件只用于写入。如果该文件已存在则打开文件，并从开头开始编辑，即原有内容会被删除。如果该文件不存在，创建新文件。w+：打开一个文件用于读写。如果该文件已存在则打开文件，并从开头开始编辑，即原有内容会被删除。如果该文件不存在，创建新文件。wb，wb+：分别与w和w+类似，针对二进制文件。a：打开一个文件用于追加。如果该文件已存在，文件指针将会放在文件的结尾。也就是说，新的内容将会被写入到已有内容之后。如果该文件不存在，创建新文件进行写入。a+：打开一个文件用于读写。如果该文件已存在，文件指针将会放在文件的结尾。文件打开时会是追加模式。如果该文件不存在，创建新文件用于读写。ab，ab+：分别与a和a+类似，针对二进制文件。mode的其值及其描述：97/126

在打开一个文件后，可以通过file对象的方法来实现文件的各种读写操作。file对象的基本方法：file.read([size])：若未指定size则返回整个文件。读到文件尾时返回一个空字符串。file.readline()：返回一行。file.readlines([size])：返回包含size行的列表，未指定size时返回全部行。forlineinfile:printline：通过迭代器访问。file.write()：写入文件。如果要写入字符串以外的数据，先将其转换为字符串。file.tell()：返回一个整数表示当前文件指针的位置。file.seek(偏移量,[起始位置])：用来移动文件指针。偏移量的单位为比特（可正可负），起始位置的取值是，0表示文件头（默认值），1表示当前位置，2表示文件尾。file.close()：关闭文件。98/1261.3.4Python程序设计1.定义类class类名(基类列表):

属性

方法99/1262.属性定义属性分为类属性（或类变量）和实例属性（或实例变量）两种。类属性在整个实例化的对象中是公用的，该类的所有实例均共享，它定义在类中且在所有方法之外，一般类属性通过类对象引用。实例属性对于每个实例都独有的数据，一般实例属性通过实例对象引用。属性又分为公有属性和私有属性，私有属性名称以两个下划线“__”开头，私有属性在类外部无法直接进行访问。在类的一个方法中可以引用该类的任意属性，类属性的引用方式是“类名称.类属性名称”，其他属性的引用方式是“self.属性名称”。100/126classA:x=2 #类属性x__y=0 #私有类属性y

def__init__(self,p):

#构造方法self.z=p #实例属性zself.__w=0 #私有实例属性w

defadd(self):self.__y+=10self.__w+=20

defdisp(self):print(A.x,self.__y,self.z,self.__w)

#主程序A.x+=1 #修改类属性xa=A(10)a.add()a.disp() #输出：3101020b=A("Bye")b.disp() #输出：30Bye0101/1263.方法定义在类的内部使用def关键字来定义一个方法。类方法必须包含参数self，且为第一个参数，self代表的是类的实例，即当前对象的地址，而self.class则指向类。self不是Python关键字，可以将self均换成其他标识符如abc也是可以正常执行的。方法也分为公有方法和私有方法，类的私有方法名称以两个下划线“__”开头，私有方法不能在类的外部调用。在类的一个方法中可以调用该类的任意方法，调用方式是“self.方法名称(参数)”。102/126__init__()：称为构造方法，在类实例化时会自动调用。该方法可以有参数，由于在实例化时给对象属性赋值。__del__：析构函数，释放对象时使用。__repr__：在输出时实现转换。__setitem__：按照索引赋值__getitem__：按照索引获取值__len__：获得长度__cmp__：比较运算__call__：函数调用__add__，__sub__，__mul__，__truediv__，__mod__，_pow__：分别用于加、减、乘、除、求余和乘方运算。Python中的一些专有方法：103/1264.定义对象1）类对象Python中一切皆对象，定义的类本身就是一个以该类名称为名称的对象，称为类对象，所以类对象与类名称相同。可以使用“类对象.类属性”的方式引用类属性，不能通过类对象引用其他属性和调用类的其他方法。104/1262）实例对象实例对象是类对象实例化的产物。定义实例对象一般格式：实例对象名称=类名称([参数列表])。通过实例对象可以引用类的所有非私有属性和调用非私有方法，对于实例对象而言，类属性是不存在的。105/1265.方法的参数传递1）参数为不可变数据类型的情况#求和程序1classA:defSum(self,n,s):s=n*(n+1)//2

#主程序a=A()s=0a.Sum(5,s)print(s) #输出:0在调用a.Sum()方法时实参是数值类型，而数值类型是不可变数据类型，执行后不会回传给实参，所以print(s)的输出结果为0。106/1262）参数为可变数据类型的情况#求和程序2classA:defSum(self,n,s):s.append(n*(n+1)//2)

#主程序a=A()s=[]a.Sum(5,s)print(s[0]) #输出:15

当参数为可变类型时，形参的执行的结果会传给实参。例如将前面求和程序1中Sum()方法的参数改为列表，而列表是可变数据类型，这样将可以得到正确的结果：107/126#求和程序3classA:defSum(self,n,s):

s=[n*(n+1)//2]

#主程序a=A()s=[]a.Sum(5,s)print(s[0]) #错误:提示超出列表s索引参数为可变类型时，形参的地址不变（仅仅改变该实例的元素不会导致地址改变），结果会回传给实参对象。若形参的地址发生改变，结果不会回传给实参对象。s的实例发生改变108/1266.继承1）单继承class子类名称(父类名称):

语句1

…

语句n109/126classPeople: #定义父类def__init__(self,n,a,w):#构造方法=nself.age=aself.__weight=wdefdispp(self):print("我是%s:体重是%d公斤,"%(,self.__weight),end='')classStudent(People):#定义子类def__init__(self,n,a,w,g): #子类的构造方法

People.__init__(self,n,a,w)

#调用父类的构造方法

#super().__init__(n,a,w)

#新式写法亦可self.grade=gdefdisps(self):

super().dispp()

#调用父类的方法print("年龄是%d岁,我在读%d年级"%(self.age,self.grade))#主程序s=Student('John',10,50,3)s.disps() 我是John:体重是50公斤,年龄是10岁,我在读3年级110/126classPeople: #定义父类def__init__(self,n,a,w): #构造方法=nself.age=aself.__weight=wdefdisp(self):print("我是%s:体重是%d公斤,"%(,self.__weight),end='')classStudent(People): #定义子类def__init__(self,n,a,w,g): #子类的构造方法super().__init__(n,a,w) #新式写法self.grade=gdefdisp(self):super().disp() #调用父类的方法print("年龄是%d岁,我在读%d年级"%(self.age,self.grade))#主程序s=Student('John',10,50,3)s.disp() 我是John:体重是50公斤,年龄是10岁,我在读3年级111/1262）多继承class子类名称(父类名称1，…，父类名称m):

语句1

…

语句n112/126classA:defdisp(self):print("A")classB(A):defdisp(self):print("进入B")super().disp()#调用类C的disp()print("退出B")classC(A):defdisp(self):print("进入C")super().disp()#调用类A的disp()print("退出C")classD(B,C):defdisp(self):print("进入D")super().disp()#调用类B的disp()print("退出D")#主程序print(D.__mro__)d=D()d.disp()ABCD(<class'__main__.D'>,<class'__main__.B'>,<class'__main__.C'>,<class'__main__.A'>,<class'object'>)进入D进入B进入CA退出C退出B退出D113/1267.异常处理最基本的异常处理语句try:#被检测的语句except异常类:#处理异常的语句异常类Exception：常规错误的基类。StopIteration：迭代器没有更多的值。FloatingPointError：浮点计算错误ZeroDivisionError：除（或取模）零错误。AssertionError：当assert语句失败时引发。FileExistsError：创建已存在的文件或目录。FileNotFoundError：请求不存在的文件或目录。114/126defopenfile(name):try:f=open(name,'r')except:raiseException('') #raise用于异常抛出print(name+"文件成功打开")f.close()

defmain():name="aaa"try:openfile(name)except:print(name+"文件不存在")

#主程序main()115/1267.迭代器和生成器1）迭代器迭代器有两个基本的函数即iter()和next()。iter()函数用来建立可迭代对象的迭代器对象。next()函数返回迭代器的下一个元素，如果结束迭代，则抛出StopIteration异常。116/126a=[1,2,3,4,5] #定义可迭代对象ait=iter(a) #建立列表a的迭代器对象itwhileTrue: #循环try:x=next(it) #获得下一个元素值print(x)exceptStopIteration:break #迭代结束退出循环117/1262）生成器在Python中使用了一个或者多个yield的函数被称为生成器（generator）。跟普通函数不同的是，生成器是一个返回迭代器的函数，只能用于迭代操作，更简单点理解生成器就是一个迭代器。在调用生成器运行的过程中，每次遇到yield时函数会暂停并保存当前所有的运行信息，返回yield的值,并在下一次执行next()方法时从当前位置继续运行。118/12