1、Ch05 系列数据类型系列数据类型本章要点：本章要点：5.1 数据结构基础数据结构基础 5.2 常用的数据结构常用的数据结构 5.3 Python系列数据概述系列数据概述 5.4 系列数据的基本操作系列数据的基本操作 5.5 列表列表 5.6 元组元组 5.7 集合集合 5.8 字典（映射）字典（映射）5.9 算法基础算法基础 5.10 常用的查找和排序算法常用的查找和排序算法 5.11 应用举例应用举例5.1 数据结构基础数据结构基础 著名的计算机科学家尼克劳斯著名的计算机科学家尼克劳斯沃思（沃思（Nikiklaus Wirth）指出：程序）指出：程序=算法算法+数据结构数据结构 算法是执行
2、特定任务的方法算法是执行特定任务的方法 数据结构是一种存储数据的方式，有助于求解特定的问题数据结构是一种存储数据的方式，有助于求解特定的问题 数据（数据（Data）是能够被计算机处理的对象集合。数据由数据元素（）是能够被计算机处理的对象集合。数据由数据元素（Date Element）组）组成，数据元素包含数据项（成，数据元素包含数据项（Data Item）在学生档案管理系统中，每位学生信息是数据的基本单位，称之为数据元素，也称为元素在学生档案管理系统中，每位学生信息是数据的基本单位，称之为数据元素，也称为元素（Element）、节点（）、节点（Node）或者记录（）或者记录（Record）组成
3、数据元素的项称之为数据项，数据项是数据的最小标识单位，又称为字段（组成数据元素的项称之为数据项，数据项是数据的最小标识单位，又称为字段（Field）或者域（）或者域（Field）例如，学生信息由学号、姓名、性别、出生年月、专业等组成例如，学生信息由学号、姓名、性别、出生年月、专业等组成数据结构数据结构 数据结构通常由三个部分组成：数据的逻辑结构，数据的存储结构和数据的运算结构数据结构通常由三个部分组成：数据的逻辑结构，数据的存储结构和数据的运算结构（1）数据的逻辑结构）数据的逻辑结构 数据的逻辑结构反映数据元素之间的逻辑关系。数据的逻辑结构主要包括线性结构（一数据的逻辑结构反映数据元素之间的逻
4、辑关系。数据的逻辑结构主要包括线性结构（一对一的关系）、树形结构（一对多的关系）、图形结构（多对多的关系）、集合等对一的关系）、树形结构（一对多的关系）、图形结构（多对多的关系）、集合等（2）数据的物理结构）数据的物理结构 数据的物理结构反映数据的逻辑结构在计算机存储空间的存放形式，即数据结构在计算数据的物理结构反映数据的逻辑结构在计算机存储空间的存放形式，即数据结构在计算机中的表示。其具体的实现方法包括顺序、链接、索引、散列等多种形式。一种数据结机中的表示。其具体的实现方法包括顺序、链接、索引、散列等多种形式。一种数据结构可以由一种或者多种物理存储结构实现构可以由一种或者多种物理存储结构实现
5、（3）数据的运算结构）数据的运算结构 数据的运算结构反映在数据的逻辑结构上定义的操作算法，例如检索、插入、删除、更数据的运算结构反映在数据的逻辑结构上定义的操作算法，例如检索、插入、删除、更新和排序等新和排序等数据的逻辑结构（数据的逻辑结构（1）反映数据元素之间的逻辑关系，与他们在计算机中的存储位置无关反映数据元素之间的逻辑关系，与他们在计算机中的存储位置无关 数据结构可以表示为数据结构可以表示为DS=(D,R)，其中，其中DS表示数据结构，表示数据结构，D表示数据集合，表示数据集合，R表示关系（表示关系（Relation）集合）集合三口之家的成员的数据逻辑结构可以表示如下：三口之家的成员的数
6、据逻辑结构可以表示如下：DS=(D,R)D=父亲父亲,母亲母亲,孩子孩子R=(父亲父亲,母亲母亲),(父亲父亲,孩子孩子),(母亲母亲,孩子孩子)数据的逻辑结构可以分为线性结构和非线性结构数据的逻辑结构可以分为线性结构和非线性结构 线性结构中的元素节点具有线性关系。如果从数据结构的语言来描述，线性结构具有以下特线性结构中的元素节点具有线性关系。如果从数据结构的语言来描述，线性结构具有以下特点。点。（1）线性结构是非空集。）线性结构是非空集。（2）线性结构有且仅有一个开始节点和一个终端节点。）线性结构有且仅有一个开始节点和一个终端节点。（3）线性结构所有节点都最多只有一个直接前趋节点和一个直接后
7、继节点）线性结构所有节点都最多只有一个直接前趋节点和一个直接后继节点 线性表、队列、栈等数据结构属于线性结构线性表、队列、栈等数据结构属于线性结构数据的逻辑结构（数据的逻辑结构（2）非线性结构中的各元素节点之间具有多个对应关系。如果从数据结构的语言来描述，非线非线性结构中的各元素节点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构具有以下特点。性结构具有以下特点。（1）非线性结构是非空集。）非线性结构是非空集。（2）非线性结构的一个节点可能有多个直接前趋节点和多个直接后继节点。）非线性结构的一个节点可能有多个直接前趋节点和多个直接后继节点。在实际应用中，数组、广义表、树结构和图结构
8、等数据结构属于非线性结构在实际应用中，数组、广义表、树结构和图结构等数据结构属于非线性结构 常用的数据逻辑结构包括如下几种方式，如图所示。常用的数据逻辑结构包括如下几种方式，如图所示。（1）集合：数据结构中的元素之间除了）集合：数据结构中的元素之间除了“同属一个集合同属一个集合”的相互关系外，别无其他关系的相互关系外，别无其他关系。（2）线性结构：数据结构中的元素存在一对一的相互关系。）线性结构：数据结构中的元素存在一对一的相互关系。（3）树形结构：数据结构中的元素存在一对多的相互关系。）树形结构：数据结构中的元素存在一对多的相互关系。（4）图形结构：数据结构中的元素存在多对多的相互关系）图形
9、结构：数据结构中的元素存在多对多的相互关系数据的物理结构数据的物理结构 数据的物理结构是指逻辑结构在计算机存储空间的存放形式。数据的物理结构数据的物理结构是指逻辑结构在计算机存储空间的存放形式。数据的物理结构是数据结构在计算机中的实现方式，它包括数据元素的机内表示和关系的机内是数据结构在计算机中的实现方式，它包括数据元素的机内表示和关系的机内表示表示 实现逻辑数据结构的常用方法包括顺序、链接、索引、散列等。一种逻辑数据实现逻辑数据结构的常用方法包括顺序、链接、索引、散列等。一种逻辑数据结构可以表示成一种或者多种物理存储结构结构可以表示成一种或者多种物理存储结构 数据元素之间的关系在计算机内部的
10、存储结构通常有两种方式：顺序存储结构数据元素之间的关系在计算机内部的存储结构通常有两种方式：顺序存储结构和链式存储结构和链式存储结构 顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系顺序映像借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系 非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系非顺序映像借助指示元素存储位置的指针来表示数据元素之间的逻辑关系常用算法常用算法 数据的算法基于数据的逻辑结构，但具体实现要在物理存储结构上进行数据的算法基于数据的逻辑结构，但具体实现要在物理存储结构上进行 基于数据结构的常用算法包括以下几种。基于数据结构的常用算法包括以
11、下几种。（1）检索：在数据结构中查找满足给定条件的节点。）检索：在数据结构中查找满足给定条件的节点。（2）插入：在数据结构中增加新的节点。）插入：在数据结构中增加新的节点。（3）删除：从数据结构中删除指定节点。）删除：从数据结构中删除指定节点。（4）更新：改变指定节点的一个或者多个字段的值。）更新：改变指定节点的一个或者多个字段的值。（5）排序：按某种指定的顺序重新排列节点（从而可以提高其他算法的）排序：按某种指定的顺序重新排列节点（从而可以提高其他算法的操作效率）操作效率）5.2 常用的数据结构常用的数据结构 5.2.1 线性表线性表 5.2.2 队列队列 5.2.3 栈栈 5.2.4 树树
12、 5.2.5 图图 5.2.6 堆堆 5.2.7 散列表散列表线性表线性表 线性表（线性表（Linear List）是最基本的一种数据结构，是具有相同特性的数据元素的有限序列，通常记）是最基本的一种数据结构，是具有相同特性的数据元素的有限序列，通常记做做(a1,a2,an）。其中）。其中a1无前趋，无前趋，an无后继，其他每个元素都有一个前趋和后继无后继，其他每个元素都有一个前趋和后继 线性表的物理存储结构主要有两种：顺序存储结构和链式存储结构，前者称为顺序表，后者称为线性表的物理存储结构主要有两种：顺序存储结构和链式存储结构，前者称为顺序表，后者称为线性链表线性链表 顺序存储结构使用一组地址
13、连续的存储单元依次存储线性表的数据元素顺序存储结构使用一组地址连续的存储单元依次存储线性表的数据元素 顺序表的优点是查找和访问元素速度快，但插入和删除开销大顺序表的优点是查找和访问元素速度快，但插入和删除开销大 链表（链表（Linked List）是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在）是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点物理上存在非连续的特点 链表由一系列数据节点构成，每个数据节点包括数据域和指针域两部分链表由一系列数据节点构成，每个数据节点包括数据域和指针域两部分 线性链表的优点在于插入和删除效率高。其缺点
14、是访问元素时需要遍历链表的所有元素，因而效线性链表的优点在于插入和删除效率高。其缺点是访问元素时需要遍历链表的所有元素，因而效率欠佳率欠佳队列和栈队列和栈 队列（队列（Queue）是先进先出的系列（）是先进先出的系列（FIFO，First In First Out），即最先添加的元），即最先添加的元素，是最先弹出的元素素，是最先弹出的元素 列表可以实现队列，但并不适合。因为从列表的头部移除一个元素，列表中的所有列表可以实现队列，但并不适合。因为从列表的头部移除一个元素，列表中的所有元素都需要移动位置，所以效率不高。用户可以使用元素都需要移动位置，所以效率不高。用户可以使用collections
15、模块中的模块中的deque对象对象来删除列表头部的元素来删除列表头部的元素 栈（栈（Stack）是后进先出的队列（）是后进先出的队列（LIFO，Last In First Out），即最后添加（），即最后添加（push）的元素，是最先弹出（）的元素，是最先弹出（pop）的元素）的元素 向列表最后位置添加元素和从最后位置移除元素非常方便和高效，故使用列表可以向列表最后位置添加元素和从最后位置移除元素非常方便和高效，故使用列表可以快捷高效地实现栈快捷高效地实现栈 list.append()方法对应于入栈操作（方法对应于入栈操作（push）；）；list.pop()对应于出栈操作（对应于出栈操作（p
16、op）树（树（1）树（树（Tree）是典型的非线性结构，由）是典型的非线性结构，由n（n=1）个有限节点组成一个具有层次关系）个有限节点组成一个具有层次关系的集合，其形状像一棵倒挂的树的集合，其形状像一棵倒挂的树 树具有以下的特点。树具有以下的特点。（1）每个节点有零个或多个子节点。）每个节点有零个或多个子节点。（2）没有父节点的节点称为根节点（）没有父节点的节点称为根节点（root）。）。（3）每一个非根节点有且只有一个父节点。）每一个非根节点有且只有一个父节点。（4）除了根节点外，每个子节点可以分为多个不相交的子树）除了根节点外，每个子节点可以分为多个不相交的子树 树的常用术语树的常用术语
17、（1）（1）节点：每个元素称为节点。）节点：每个元素称为节点。（2）根节点：没有父节点的节点称为根节点。）根节点：没有父节点的节点称为根节点。（3）节点的度（）节点的度（degree）：一个节点含有的子节点个数称为该节点的度。）：一个节点含有的子节点个数称为该节点的度。（4）叶节点或终端节点（）叶节点或终端节点（leaf）：度为）：度为0的节点称为叶节点。的节点称为叶节点。（5）非终端节点或分支节点（）非终端节点或分支节点（branch）：度不为）：度不为0的节点。的节点。树（树（2）树的常用术语树的常用术语（2）（6）双亲节点或父节点（）双亲节点或父节点（parent）：若一个节点含有子节点
18、，则这个节点称为其子节点的父）：若一个节点含有子节点，则这个节点称为其子节点的父节点。节点。（7）孩子节点或子节点（）孩子节点或子节点（child）：一个节点含有的子树的根节点称为该节点的子节点。）：一个节点含有的子树的根节点称为该节点的子节点。（8）兄弟节点（）兄弟节点（sibling）：具有相同父节点的节点互称为兄弟节点。）：具有相同父节点的节点互称为兄弟节点。（9）树的度：一棵树中，最大的节点的度称为树的度。）树的度：一棵树中，最大的节点的度称为树的度。（10）节点的层次（）节点的层次（level）：从根开始定义起，根为第）：从根开始定义起，根为第1层，根的子节点为第层，根的子节点为第2
19、层，以此类推层，以此类推（11）树的高度或深度（）树的高度或深度（depth）：树中节点的最大层次。）：树中节点的最大层次。（12）堂兄弟节点：双亲在同一层的节点互为堂兄弟节点。）堂兄弟节点：双亲在同一层的节点互为堂兄弟节点。（13）节点的祖先：从根到该节点所经分支上的所有节点。）节点的祖先：从根到该节点所经分支上的所有节点。（14）子孙：以某节点为根的子树中任一节点都称为该节点的子孙。）子孙：以某节点为根的子树中任一节点都称为该节点的子孙。（15）森林：）森林：m（m=0）棵互不相交的树的集合称为森林。）棵互不相交的树的集合称为森林。树（树（3）树的常用术语树的常用术语（3）（16）空树。空
20、集合也是树，称为空树。空树中没有节点。）空树。空集合也是树，称为空树。空树中没有节点。（17）无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树，也称为自由树。）无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树，也称为自由树。（18）有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树。）有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树。（19）二叉树：每个节点最多含有两个子树的树称为二叉树。）二叉树：每个节点最多含有两个子树的树称为二叉树。（20）满二叉树：如果一棵二叉树只有度为）满二叉树：如果一棵二叉树只有度为0的结点和度为的结点和度为2的结点
21、，并且度为的结点，并且度为0的结点在同一层上，则这的结点在同一层上，则这棵二叉树为满二叉树。即，一棵深度为棵二叉树为满二叉树。即，一棵深度为k且有且有2k-1个结点的二叉树称为满二叉树。满二叉树每一层的结点个结点的二叉树称为满二叉树。满二叉树每一层的结点个数都达到了最大值，即满二叉树的第个数都达到了最大值，即满二叉树的第i层上有层上有2i-1个结点。如图个结点。如图5-6（a）所示是一棵深度为）所示是一棵深度为3的满二叉树的满二叉树（21）完全二叉树：满二叉树中叶子节点所在的层次中，如果自右向左连续缺少若干叶子节点，这样的得）完全二叉树：满二叉树中叶子节点所在的层次中，如果自右向左连续缺少若干
22、叶子节点，这样的得到的二叉树被称为完全二叉树。即，若设二叉树的深度为到的二叉树被称为完全二叉树。即，若设二叉树的深度为k，除第，除第k层外，其它各层（层外，其它各层（1k-1）的节点数都）的节点数都达到最大个数，而第达到最大个数，而第k层所有的节点都连续集中在最左边，这就是一个完全二叉树。如图层所有的节点都连续集中在最左边，这就是一个完全二叉树。如图5-6（b）所示是）所示是一棵完全二叉树。如图一棵完全二叉树。如图5-6（c）所示是一棵非完全二叉树。满二叉树是完全二叉树的特殊形态。）所示是一棵非完全二叉树。满二叉树是完全二叉树的特殊形态。（22）哈夫曼树（最优二叉树）：带权路径最短的二叉树称为
23、哈夫曼树或最优二叉树）哈夫曼树（最优二叉树）：带权路径最短的二叉树称为哈夫曼树或最优二叉树二叉树重要性质二叉树重要性质二叉树的遍历（二叉树的遍历（1）二叉树是二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成不相交的、被分别称为左子树和右子树的二叉树组成 二叉树具有五种基本形态二叉树具有五种基本形态 遍历二叉树，就是按一定的规则和顺序遍历二叉树的所有节点，使每一个节点都被遍历二叉树，就是按一定的规则和顺序遍历二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一
24、次访问一次，而且只被访问一次 在任一给定节点上，可以按某种次序执行三个操作。在任一给定节点上，可以按某种次序执行三个操作。（1）访问节点本身（）访问节点本身（N）。）。（2）遍历该节点的左子树（）遍历该节点的左子树（L）。）。（3）遍历该节点的右子树（）遍历该节点的右子树（R）以上三种操作有六种遍历方法：以上三种操作有六种遍历方法：NLR、LNR、LRN、NRL、RNL、RLN二叉树的遍历（二叉树的遍历（2）1、NLR：前序遍历（：前序遍历（Preorder Traversal），又称为先序遍历。若二叉树非空，则依次执），又称为先序遍历。若二叉树非空，则依次执行如下操作。行如下操作。访问根结点
25、（访问根结点（N）遍历左子树（遍历左子树（L）遍历右子树（遍历右子树（R）2、LNR：中序遍历（：中序遍历（Inorder Traversal）。若二叉树非空，则依次执行如下操作。）。若二叉树非空，则依次执行如下操作。遍历左子树（遍历左子树（L）访问根结点（访问根结点（N）遍历右子树（遍历右子树（R）3、LRN：后序遍历（：后序遍历（Postorder Traversal）。若二叉树非空，则依次执行如下操作。）。若二叉树非空，则依次执行如下操作。遍历左子树（遍历左子树（L）遍历右子树（遍历右子树（R）访问根结点（访问根结点（N）图、堆、散列表图、堆、散列表 图（图（Graph）是另一种非线性数
26、据结构。图是由顶点集合）是另一种非线性数据结构。图是由顶点集合V（Vertex）和边集合）和边集合E（Edge）组成的，定义为）组成的，定义为G=(V，E)在图结构中，数据节点一般称为顶点，而边是顶点的有序偶对。如果在图结构中，数据节点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系 堆（堆（Heap）是一种特殊的树形数据结构，其中子节点与父节点是一）是一种特殊的树形数据结构，其中子节点与父节点是一种有序关系种有序关系 散列表（散列表（Hash table，也叫哈希表）是把键值映射（映射函数
27、）到表，也叫哈希表）是把键值映射（映射函数）到表（散列表）的数据结构，通过键值可以实现快速查找（散列表）的数据结构，通过键值可以实现快速查找5.3 Python系列数据概述系列数据概述 数组数组 将数据存储在一个或多个数组中，通过索引下标访问并处将数据存储在一个或多个数组中，通过索引下标访问并处理数组的元素理数组的元素 Python内置的序列数据类型内置的序列数据类型 元组元组（tuple）、）、列表列表（list）、）、字符串字符串（str）和）和字节数据字节数据（bytes和和bytearray）系列数据的基本操作系列数据的基本操作（1）系列的长度、最大值、最小值、求和系列的长度、最大值、
28、最小值、求和 len()、max()、min()，获取系列的长度、系列中元素最，获取系列的长度、系列中元素最大值、系列中元素最小值大值、系列中元素最小值 sum()获取列表或元组中各元素之和获取列表或元组中各元素之和【例【例5.1】系列数据的求和示例】系列数据的求和示例 t1=(1,2,3,4)sum(t1)#输出：输出：10101010 t2=(1,a,2)sum(t2)#TypeError:unsupported operand type(s)for+:int and TypeError:unsupported operand type(s)for+:int and strstr s=12
29、34 sum(s)#TypeError:unsupported operand type(s)for+:int and TypeError:unsupported operand type(s)for+:int and strstr系列数据的基本操作系列数据的基本操作（2）【例【例5.2】系列的长度、最大值、最小值操作示例】系列的长度、最大值、最小值操作示例 s=abcdefg len(s)7 7 max(s)gg min(s)aa s2=len(s2)0 0 t=(10,2,3)len(t)3 3 max(t)1010 min(t)2 2 t2=()len(t2)0 0 lst=1,2,9,
30、5,4 len(lst)5 5 max(lst)9 9 min(lst)1 1 lst2=len(lst2)0 0 b=bABCD len(b)4 4 max(b)6868 min(b)6565 b2=b len(b2)0 0系列的索引访问操作系列的索引访问操作【例【例5.3】系列的索引访问示例】系列的索引访问示例 s=abcdef s0aa s2cc s-1ff s-3dd t=(a,e,i,o,u)t0aa t1ee t-1uu t-5aa lst=1,2,3,4,5 lst01 1 lst1,2,3,4,51,2,3,4,5 lst2=a lst-2=b lst1,2,a,b,51,2,
31、a,b,5 b=bABCDEF b06565 b16666 b-17070 b-26969系列的切片操作系列的切片操作【例【例5.4】系列的切片操作示例】系列的切片操作示例 s=abcdef s1:3bcbc s3:10defdef s8:2 s:abcdefabcdef s:2abab s:2aceace s:-1fedcbafedcba t=(a,e,i,o,u)t-2:-1(o,)(o,)t-2:(o,u)(o,u)t-99:-5()t-99:-3(a,e)(a,e)t:(a,e,i,o,u)t1:-1(e,i,o)(e,i,o)t1:2(e,o)(e,o)lst=1,2,3,4,5 l
32、st:21,21,2 lst:1=lst 2,2,3,4,53,4,5 lst:22,32,3 lst:2=a lst1:=b lsta,ba,b del lst:1 lstbb b=bABCDEF b2:2bb b0:1bAbA b1:2bBbB b2:2bb b-1:bFbF b-2:-1bEbE b0:len(b)bABCDEFbABCDEF系列的连接和重复操作系列的连接和重复操作【例【例5.5】系列的连接和重复操作示例】系列的连接和重复操作示例 s1=abc s2=xyz s1+s2abcxyzabcxyz s1*3abcabcabcabcabcabc s1+=s2 s1abcxyza
33、bcxyz s2*=2 s2xyzxyzxyzxyz t1=(1,2)t2=(a,b)t1+t2(1,2,a,b)(1,2,a,b)t1*2(1,2,1,2)(1,2,1,2)t1+=t2 t1(1,2,a,b)(1,2,a,b)t2*=2 t2(a,b,a,b)(a,b,a,b)lst1=1,2 lst2=a,b lst1+lst21,2,a,b1,2,a,b 2*lst2a,b,a,ba,b,a,b lst1+=lst2 lst11,2,a,b1,2,a,b lst2*=2 lst2a,b,a,ba,b,a,b b1=bABC b2=bXYZ b1+b2bABCXYZbABCXYZ b1*
34、3bABCABCABCbABCABCABC b1+=b2 b1bABCXYZbABCXYZ b2*=2 b2bXYZXYZbXYZXYZ系列的成员关系操作系列的成员关系操作【例【例5.6】系列中元素的存在性判断示例】系列中元素的存在性判断示例 s=Good,better,best!o in sTrueTrue g not in sTrueTrue s.count(e)3 3 s.index(e,10)1010 t=(r,g,b)r in tTrueTrue y not in tTrueTrue t.count(r)1 1 t.index(g)1 1 lst=1,2,3,2,1 1 in lst
35、TrueTrue 2 not in lstFalseFalse lst.count(1)2 2 lst.index(3)2 2 b=bOh,Jesus!bO in bTrueTrue bo not in bTrueTrue b.count(bs)2 2 b.index(bs)6 6系列的比较运算操作系列的比较运算操作【例【例5.7】系列的比较运算示例】系列的比较运算示例 s1=abc s2=abc s3=abcd s4=cba s1 s4FalseFalse s2 s1=s2TrueTrue s1!=s3TrueTrue a ATrueTrue a=TrueTrue t1=(1,2)t2=(1
36、,2)t3=(1,2,3)t4=(2,1)t1 t1 t1=t3FalseFalse t1!=t2FalseFalse t1=t3FalseFalse t4 t3TrueTrue s1=a,b s2=a,b s3=a,b,c s4=c,b,a s1 s1 s1=s2TrueTrue s1!=s3TrueTrue s1=s3FalseFalse s4s3TrueTrue b1=babc b2=babc b3=babcd b4=bABCD b1 b1 b1=b2TrueTrue b1=b3FalseFalse b3!=b4TrueTrue b4b3FalseFalse系列的排序操作系列的排序操作【
37、例【例5.8】系列的排序操作示例】系列的排序操作示例 s1=axd sorted(s1)a,d,xa,d,x s2=(1,4,2)sorted(s2)1,2,4 1,2,4 sorted(s2,reverse=True)4,2,14,2,1 s3=abAC sorted(s3,key=str.lower)a,A,b,Ca,A,b,C内置函数内置函数all()和和any()all(iterable)#如果序列的所有值都为如果序列的所有值都为True，返回，返回True；否则，返回；否则，返回Falseany(iterable)#如果序列的任意值为如果序列的任意值为True，返回，返回True；否
38、则，返回；否则，返回False any(1,2,0)TrueTrue all(1,2,0)FalseFalse5.5 列表列表 使用列表字面量可以创建列表实例对象。列表字面量列表采用方括号中用逗号分隔使用列表字面量可以创建列表实例对象。列表字面量列表采用方括号中用逗号分隔的项目定义的项目定义【例【例5.9】使用列表字面量创建列表实例对象示例】使用列表字面量创建列表实例对象示例 用户也可以通过创建用户也可以通过创建list对象来创建列表对象来创建列表【例【例5.10】使用】使用list对象创建列表实例对象示例对象创建列表实例对象示例 list1=;list2=1;list3=a,b,c prin
39、t(list1,list2,list3)#输出输出：1 a,b,c list1=list();list2=list(abc);list3=list(range(3)print(list1,list2,list3)#输出输出：a,b,c 0,1,2列表的系列操作列表的系列操作 索引访问、切片操作、连接操作、重复操作、成员关系操作、比较运算操作，以及索引访问、切片操作、连接操作、重复操作、成员关系操作、比较运算操作，以及求列表长度、最大值、最小值等求列表长度、最大值、最小值等 列表是可变对象列表是可变对象【例【例5.11】列表的系列操作示例】列表的系列操作示例 s=1,2,3,4,5,6 s1=a
40、 s1,a,3,4,5,6 s2=s1,a,4,5,6 del s3 s1,a,5,6 s:21,a s2:3=s1,a,5,6 s:1=sa,5,6 s:2=b sb,6 del s:1 s6列表对象的方法列表对象的方法列表解析表达式列表解析表达式 使用列表解析可以简单高效地处理一个可迭代对象，并生成结果列表。列表解析表使用列表解析可以简单高效地处理一个可迭代对象，并生成结果列表。列表解析表达式的形式如下达式的形式如下【例【例5.12】列表解析表达式示例】列表解析表达式示例 i*2 for i in range(10)#平方值平方值0,1,4,9,16,25,36,49,64,81(i,i*
41、2)for i in range(10)#序号序号,平方值平方值(0,0),(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81)i for i in range(10)if i%2=0#取偶数取偶数0,2,4,6,8(x,y,x*y)for x in range(1,4)for y in range(1,4)if x=y#二重循环二重循环(1,1,1),(2,1,2),(2,2,4),(3,1,3),(3,2,6),(3,3,9)列表的排序列表的排序（1）内置数据类型）内置数据类型list中的方法中的方法sort()，把列表中的
42、数据项按升序重新排列。，把列表中的数据项按升序重新排列。（2）内置函数）内置函数sorted()则保持原列表不变，返回一个新的包含按升序排列的项的列则保持原列表不变，返回一个新的包含按升序排列的项的列表表【例【例5.13】Python语言提供的排序算法示例语言提供的排序算法示例 a=59,12,77,64,72,69,46,89,31,9 sorted(a)#输出：输出：9,12,31,46,59,64,69,72,77,89 a#输出：输出：59,12,77,64,72,69,46,89,31,9 a.sort(reverse=True)a#输出：输出：89,77,72,69,64,59,4
43、6,31,12,9元组元组 一组有序系列，包含一组有序系列，包含0个或多个对象引用个或多个对象引用 元组的定义元组的定义 元组也可以通过创建元组也可以通过创建tuple对象来创建对象来创建【例【例5.14】使用使用tuple对象创建元组实例对象示例对象创建元组实例对象示例 t1=tuple()t2=tuple(abc)t3=tuple(1,2,3)t4=tuple(range(3)print(t1,t2,t3,t4)#输出：输出：()(a,b,c)(1,2,3)(0,1,2)元组的元组的系列系列操作操作 索引访问、切片操作、连接操作、重复操作、成员索引访问、切片操作、连接操作、重复操作、成员关
44、系操作、比较运算操作，以及求元组长度、最大关系操作、比较运算操作，以及求元组长度、最大值、最小值等值、最小值等【例【例5.15】元组的】元组的系列系列操作示例操作示例 t1=(1,2,3,4,5,6,7,8,9,10)len(t1)#输出：输出：10 max(t1)#输出：输出：10 sum(t1)#输出：输出：55集合集合 集合数据类型是没有顺序的简单对象的聚集，且集合中元素不重集合数据类型是没有顺序的简单对象的聚集，且集合中元素不重复复 Python集合数据类型包括可变集合对象（集合数据类型包括可变集合对象（set）和不可变集合对象）和不可变集合对象（frozenset）集合的定义集合的定
45、义 表示空的表示空的dict，因为，因为dict也使用花括号定义。空集为也使用花括号定义。空集为set()【例【例5.16】创建集合对象示例】创建集合对象示例 1,2,11,21,2 1,a,True1,a1,a 1.2,TrueTrue,1.2True,1.2 set()set()set()frozenset()frozenset()frozenset()set(Hello)H,e,o,H,e,o,ll a,1,2Traceback(most recent call last):Traceback(most recent call last):File,line 1,in File,line
46、 1,in a,1,2 a,1,2TypeError:unhashable type:listTypeError:unhashable type:list集合的运算：并集、交集、差集和对称差集集合的运算：并集、交集、差集和对称差集【例【例5.17】集合的运算示例】集合的运算示例 s1=1,2,3 s2=2,3,4 s1|s21,2,3,41,2,3,4 s1&s22,32,3 s1-s211 s1 s21,41,4 s1.union(s2)1,2,3,41,2,3,4 s1.intersection(s2)2,32,3 s1.difference(s2)11 s1.symmetric_diff
47、erence(s2)1,41,4可变集合的方法可变集合的方法方法方法说明说明示例示例s1.update(s2,.)s1|=s2|.并集s1=s1s2 s1.update(s2)#s1=1,2,3,4s1.intersection_update(s2,.)s1&=s2&.交集s1=s1s2 s1.intersection_update(s2)#s1=2,3s1.difference_update(s2,.)s1-=s2-.差集s1=s1s2 s1.difference_update(s2)#s1=1s1.symmetric_difference_update(s2)s1=s2对称差集s1=s1s
48、2s1.symmetric_difference_update(s2)#s1=1,4s.add(x)把对象x添加到集合ss1.add(a)#s1=1,2,3,as.remove(x)从集合s中移除对象x。若不存在，则导致KeyError s1.remove(1)#s1=2,3s.discard(x)从集合s中移除对象x（如果存在的话）s1.discard(3)#s1=1,2s.pop()从集合s随机弹出一个元素，如果s为空，则导致KeyError s1.pop()#输出：1。s1=2,3s.clear()清空集合s s1.clear()#s1=set()字典（映射）字典（映射）字典（字典（di
49、ct，或映射，或映射map）是一组键）是一组键/值对的数据结构。每个键对值对的数据结构。每个键对应于一个值。在字典中，键不能重复。根据键可以查询到值应于一个值。在字典中，键不能重复。根据键可以查询到值 对象的哈希（对象的哈希（hash）值）值【例【例5.18】对象的哈希（】对象的哈希（hash）值示例）值示例 字典的键只能使用不可变的对象，但字典的值可以使用不可变字典的键只能使用不可变的对象，但字典的值可以使用不可变或可变的对象或可变的对象 hash(100)#结果：结果：100100 hash(1.23)#结果：结果：530343892119149569530343892119149569
50、hash(abc)#结果：结果：901130859749610928901130859749610928字典的字典的创建创建【例【例5.19】创建字典对象示例】创建字典对象示例 a:apple,b:boya:apple,b:boya:apple,b:boy dict()dict(1:food,2:drink)1:food,2:drink 1:food,2:drink dict(id,1001),(name,Jenny)id:1001,name:Jennyid:1001,name:Jenny dict(baidu=,google=)baidu:,google:baidu:,google:字典的访
