面向大数据的数据结构与算法设计（Python版）

第一章大数据概论电子科技大学汤羽目录1.数据概念2.数据结构3.大数据计算4.本章小结01数据概念1.数据概念

数据（datumordata）在计算机科学中通指可以按数值形式记录下来的一切信息，它可以是文字、图像、音频、视频、二进制码或其他计算机科学使用的格式。数据既是计算机系统需要处理的对象，又是与硬件、软件、网络并列的计算资源之一。1.按照不同的维度，数据可分为个人数据、社会数据、生产数据；2.按照数据格式，可分为数值型数据、文本数据、图像数据、音频/视频数据、二进制数据；3.按时间性，可分为实时数据、非实时数据、历史数据；4.从数据处理角度，又可分为原始数据与衍生数据。原始数据是指原始记录的没有做过加工处理的数据，衍生数据是指通过对原始数据进行加工处理后产生的数据，包括各种数据集市、汇总层、宽表、数据分析挖掘结果等。1.数据概念数据按照存储方式，可分为结构化数据、半结构化数据、非结构化数据。结构化数据由预先定义的数据类型按照预先设计的数据格式组合而成，易于数据库存储、管理与搜索，更利于后续的数据分析与挖掘工具的使用。关系数据库（RDBS）的数据表单（form）就是一种典型的结构化数据存储。非结构化数据是指结构化数据之外、没有预先定义数据类型和标准格式的各种数据，它可以有自己的内部结构和属性，但难以直接按照标准数据库提供的数据格式进行存储和管理，不便于使用已有的分析工具进行数据挖掘。文本数据，图像数据就是常见的非结构化数据类型。在结构化与非结构化之间还有一种半结构化数据。半结构化数据不具有标准化的数据类型和格式，但为了支持快速查询检索，我们针对这类数据构建一个结构化的检索信息或元数据，这种标签式的元数据与原数据一起构成了能较好支持数据搜索和分析的半结构化数据类型。目前广泛使用的关系数据库（RDBS）和非关系数据库（NoSQL）都支持非结构化数据。1.数据概念

与数据(data)相关的还有信息(information)、知识(knowledge)与价值(value)这几个词。

数据是一种自然或人类活动的记录，这类记录被数字化（digitalized）后可以被计算机存储和处理，信息则是包含在数据之中的能够为人脑理解和思维推理的结论，并可以上升形成人类的认知知识，而知识可以产生价值。010010000110010101101100。。。00100001"Helloworld!"1.数据概念

互联网时代大数据研究与应用热潮带来的不仅仅是需处理数据量的指数级增长，更带来了新的计算模型、计算方法以及数据结构的使用，比如大数据分析中的非关系数据库（也称为NoSQL数据库）就更多使用不同于传统数据结构的键值对（key-valuepair）数据结构，以及不同于传统关系数据库行存储结构（row-basedstoragestructure）的列存储结构（column-basedstoragestructure）。

适用于大数据分析的MapReduce计算模型、流计算模型（Streamingcomputing）、图并行计算模型（graphparallelcomputing）都更适合匹配非关系型数据库和键值对、列存储等新型数据结构，因此学习这类新型数据结构及其分析算法对于新技术的应用具有重要意义。02数据结构2.1数据逻辑结构2.2数据物理结构数据结构（datastructure）是数据元素按照一定方式的集合，也可看作计算机组织、存储及使用数据的抽象化表达方式，其内容包含数据逻辑结构和数据物理结构以及它们之间的映射关系，还包含定义在这种结构之上的运算规则以及与之相应的算法。总之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，这种数据元素之间存在的特定关系，被区分定义为数据逻辑结构和数据存储结构，也称为存储抽象结构与存储物理结构。2数据结构

数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储物理结构。2数据结构2.1数据逻辑结构数据逻辑结构指反映数据元素之间的逻辑关系的数据模型，这里的逻辑关系是指数据元素之间的前后顺序、依赖、数学逻辑等关系，而与其计算机中的物理存储位置无关。逻辑结构按大类可以分为以下4种。(1)

集合：数据结构中的元素相互之间除了同属一个集合/容器的关系外别无其他关系。(2)线性结构：数据结构中的元素与顺序或位置存在一对一的相互关系。(3)树形结构：数据结构中的元素存在一对多的相互关系。(4)图形结构：数据结构中的元素存在多对多的相互关系。2.1数据逻辑结构数据线性结构就是指结构中各个数据元素具有线性关系，具体包括以下几点：(1)线性结构是非空集。(2)线性结构有且仅有一个开始元素和一个终端元素。(3)在排列顺序上线性结构所有元素都最多只有一个前节点和一个后节点。典型的线性结构包括数组、栈、队列、链表、字符串等。2.1数据逻辑结构数组（Array）数组是一种聚合型线性数据结构，是将具有相同类型的若干元素顺序排列在一起的集合。一个数组包含多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。栈（Stack）栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据元素的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压进栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。2.1数据逻辑结构队列（Queue）队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入元素的一端称为队尾，而删除元素的一端称为队头。队列中没有元素时，称为空队列。链表（LinkedList）

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种数据结构具有物理存储上非连续性的特点。链表由一系列数据节点构成，每个数据节点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个节点存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。2.1数据逻辑结构树(Tree)

树是典型的非线性结构，它是包括n(n≥1)个节点的有穷集合。在树结构中，有且仅有一个根节点，该节点没有前节点。树结构中的其他节点都有且仅有一个前节点，而且可以有m个后节点，m≥0。图(Graph)

图是另一种非线性数据结构。在图结构中，数据节点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。堆(Heap)

堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。堆的特点是根节点的值是所有节点中最小的或者最大的，并且根节点的两个子树也是一个堆结构。。2.1数据逻辑结构散列表(Hash)散列表源自于散列函数(Hashfunction)，其思想是如果在结构中存在键和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。常用数据运算方式：检索：检索就是在数据结构里查找满足一定条件的节点，一般是给定一个某字段的值，找具有该字段值的节点插入：往数据结构增加新的节点。删除：把指定的节点从数据结构中去掉。更新：改变指定节点的一个或多个字段的值。排序：把节点按某种指定的顺序重新排列，例如递增或递减。2.2数据物理结构

数据物理结构指数据元素在计算机物理存储介质的存储空间内的实际存放形式，它也可看作数据逻辑结构在计算机物理存储空间中的映像。具体实现的物理存储结构类型有顺序存储、链式存储、索引存储、散列存储（散列表）等。

顺序存储：把逻辑结构上相邻的数据元素存储在物理位置相邻的存储单元中，数据元素之间的关系由存储单元的邻接关系来体现。顺序存储结构常常是借助于数组来实现。其优点是节省空间，可以实现随机存取。缺点是插入、删除操作需要移动数据元素，效率低。2.2数据物理结构链式存储：在计算机存储介质上用一组任意的存储单元来存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。其特点是每个数据元素包括了一个数据域和一个指针域，数据域用来存放数据，而指针域用来指向其后继单元的位置。优点是插入、删除灵活，缺点是不能随机存取，查找速度慢。索引存储：建立索引表，用存储节点的索引号来确定节点存储地址。其优点是检索速度快，缺点是增加了附加的索引表,会占用较多的存储空间。散列存储：又称散列（hash）存储，是一种将数据元素的存储位置与关键码之间建立确定对应关系的存储与查找方法。散列存储的基本思想是：由节点的关键码值决定节点的存储地址。03大数据计算3大数据计算大数据计算系统三个基本层面：数据存储层数据处理层数据应用层各类大数据应用数据应用层数据产品与数据服务数据可视化计算引擎数据处理层计算平台计算模型与算法计算引擎数据处理层计算平台计算模型与算法分布式数据库/数据仓库数据存储层分布式文件系统数据采集与建模3大数据计算数据存储层主要提供数据采集、清洗建模、大规模数据存储管理、数据操作（添加、删减、查询、更新、数据同步）等功能。由于大数据处理具有多重数据源、数据异构性、非结构化数据、分布式计算环境等特点，大数据存储系统的设计远较传统的关系数据库（RDBS）系统复杂。大数据存储层的架构主要由数据采集层、分布式文件系统、非关系数据库（NoSQL）、以及统一数据读取界面组成。3大数据计算DataAcquisition/Extraction/Transforming/ModelingDistributedFileSystems(HDFS/GFS/Colossus)NoSQLDatabase(HBase/BigTable/MongoDB/Neo4j)UnifiedDataAccessInterface3大数据计算

数据存储层的功能包括数据采集、数据清洗、抽取与建模、数据存储架构。数据存储架构是大数据计算的基础，上层各种分析算法、计算模型及计算性能都依赖于数据存储系统的表现，因此，数据存储系统是大数据研究的一个重要领域。

数据处理层包括针对不同类型数据的计算模型、数据分析算法、计算平台。目前，商业公司如Google、IBM、Oracle、Microsoft、SAP等都提供各自的大数据计算平台和相关技术；开源社区则提供基于Hadoop平台的一整套支持大数据计算及应用的开放式架构和技术标准。

数据应用层则是提供各行业各领域的大数据应用技术解决方案。目前，互联网、电子商务、电子政务、金融、电信、医疗卫生等行业是大数据应用最热门的领域，而制造业、教育、能源、环保则是大数据技术即将或已经开始拓展的行业。04本章小结

本章针对大数据结构进行讲解，包括两个数据结构：数据逻辑结构、数据物理结构。数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储物理结构。基于数据结构的算法设计取决于数据逻辑结构，而算法的实现则依赖于所使用的物理存储结构。4.本章小节本章习题1.数据(data)、信息(information)、知识(knowledge)与价值(value)这四个词在信息科学中既相关联、又具有不同的含义。请举例说明四个概念的关联与区别。2.阐述大数据的四大基本特征？3.阐述大数据计算系统涉及到的三个层次及其含义。4.简述大数据存储架构的构成，并用图展示说明。4.本章小节课程实验给定一个编码过的字符串，返回它解码后的字符串。编码规则为:k[str]，表示其中方括号内部的str正好重复k次。k为正整数。输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数k，例如不会出现像

3a

或

2[4]

的输入。示例:s="3[a]2[bc]",返回"aaabcbc".s="3[a2[c]]",返回"accaccacc".s="2[abc]3[cd]ef",返回"abcabccdcdcdef".EndofSessionThankyou!第二讲Python语言基础授课教师：林迪目录1.Python简介2.Python数据类型3.Python程序控制目录4.Python函数5.面向对象设计6.本章小结01Python简介1.1Python简介1.2

Python安装1.1

Python简介什么是Python语言？Python是一种易于学习，功能强大的编程语言。它具有高效的高级数据结构和面向对象编程的简单而有效的方法。Python优雅的语法和动态类型及其解释特性使其成为大多数平台上许多领域的脚本编写和快速应用程序开发的理想语言。Python的优点1、Python易于使用，它为大型程序提供了比shell脚本或批处理文件更多的结构和支持。另一方面，Python还提供了比C更多的错误检查，并且作为一种非常高级的语言，它具有内置的高级数据类型，例如灵活的数组和字典。由于其更通用的数据类型，Python适用于比Awk甚至Perl更大的问题域。1.1

Python简介2、Python是可扩展的：如果你知道如何用C编程，那么你就可以很容易地向Python解释器添加一个新的内置函数或模块，或者以最快的速度执行关键操作，或者将Python程序链接到二进制形式表示的库。你可以非常容易地将Python解释器链接到用C编写的应用程序，并将其用作该应用程序的扩展或命令语言。3、Python是一种解释型语言，可以在程序开发过程中节省大量时间，因为不需要编译和链接。解释器可以交互使用，这使得在自下而上的程序开发过程中，可以轻松地试验语言的功能，编写程序或测试功能。4、Python使程序可以紧凑和可读地编写。这主要体现在Python的高级数据类型允许用户在单个语句中表达复杂的操作，此外，Python的语句分组是通过缩进而不是开头和结尾括号来完成的，最后，Python也不需要变量或参数声明。因此，用Python编写的程序通常比同等的C、C++或Java程序短得多。1.2

Python安装Python支持跨平台，它可在包括Windows、UNIX、Linux在内的多种os中运行。本节将介绍Windows平台下Python的安装流程。搜索Python官网，选择Downloads、Windows，进入/downloads/windows/页面后，选择Python3.x系列的Release版本。1.2

Python安装随后，根据自身计算机设备配置情况，选择对应的64位或32位安装包。安装包的下载界面如图所示。1.2

Python安装下载完毕之后，以管理员身份打开下载下来的.exe文件，按照个人需求，依照程序提示，指定好安装目录，即可安装完毕。安装界面如图所示。1.2

Python安装安装完毕后，进入Python的安装目录，找到目录下的python.exe文件，以管理员身份打开，即可在新出现的控制台窗口中执行Python语句。此时输入"exit()"后回车，即可退出Python。02Python数据类型2.1

整数型2.2

浮点数类型2.3

字符串2.4序列数据2Python数据类型一般而言，Python的数据类型可以分为以下两类。数值类型(NumericTypes)：int、float、long、complex四类。数值类型的创建方式一般而言有三种：通过赋初值创建，通过内置函数创建，或者通过运算符的运算结果来创建。与C和Java语言相似，数字类型支持混合算术，当不同类型的数字之间进行运算时，占用内存空间较少的数字类型会被隐式转换为占用内存空间较多的数字类型，顺序从小到大依次为：int<long<float<complex。需要注意的是，Python的各个数字类型占用的内存空间与其他语言相比有很大不同，int类型占用大小为12比特，long类型占用大小为14比特，float类型占用大小为16比特。序列类型(SequenceTypes)：str、unicode、list、tuple、bytearray、buffer、xrange七大类。需要注意的一点是，Python与C和Java不同，其变量赋值不需要类型声明，但是在被使用前都必须被赋值，之后才会被创建并被赋予标识、名称和数据等相关信息。2Python数据类型序列类型支持一些通用的方法，如下表所示。操作示例作用说明xins如果s的某一个元素等于x，返回True，否则返回False当s是字符串或Unicode字符串对象时，in和notin操作可以理解为寻找s是否有子串x。在2.3之前的Python版本中，x必须是长度为1的字符串。在Python2.3及更高版本中，x可以是任意长度的字符串xnotins如果s的某一个元素等于x，返回False，否则返回True

s+t返回s和t的连接结果若要考虑性能因素的话，建议使用Python的库函数来代替此类操作s*n、n*s返回s的自身n次当n小于0时，其值被视为0(其产生与s相同类型的空序列)。请注意，返回的新的序列对象中的每个元素不是序列s中元素的复制，而是简单的引用，因此，对新的序列中任何一个元素的修改都会修改所有其他元素s[i]返回s的第i个元素(从0开始计数)如果i、j为负值，则表示从序列尾开始计数，即取第len(s)+i个元素s[i:j]返回s从第i个元素到第j个元素的子部分

s[i:j:k]从s的第i个元素到第j个元素，依照步长为k筛选元素，返回筛选元素组成的序列

len(s)返回s的长度

min(s)返回s的最小的元素

max(s)返回s的最大的元素

s.index(x)返回s中第一次出现x的位置

s.count(x)返回s中出现x的总次数2.1

整数型x|y对x和y进行按位或运算x^y对x和y进行按位异或运算x&y对x和y进行按位与运算x<<nx向左移位n位x>>nx右移n位~x将x按位反转正如前文所述，int类型(整数型)有三种声明方式，即通过赋初值创建，通过内置方法创建，或者通过运算符的运算结果来创建。分别如下所示：1.通过赋初值的方式声明，例如a=10;2.通过内置方法方式声明，例如b=int(3);3.通过运算符的运算结果方式声明，例如c=2+3。此外，int类型也支持位运算，基本操作类型有如下表所示。另外，int类型还支持一个方法：int.bit_length()，其将返回调用该函数的int对象表示成二进制整数所需的位数(不包括符号位和前导占位0)。2.2

浮点数类型同int类似，float类型也有三种声明方式，此处不再赘述。除此之外，float类型也具有自己特有的方法，如下所述：1、float.as_integer_ratio()该方法返回一对整数，其比率与原始浮点数完全相等，并带有正分母。2、float.is_integer()该方法当传入浮点数其值的小数部分为零(如2.0、43.0000等)时返回true，否则(如2.1、43.0001等)返回false。两种方法支持十六进制字符串的转换。由于Python的浮点数在内部存储为二进制数，因此将浮点数转换为十进制字符串或从十进制字符串转换通常会导致小的舍入错误。相反，十六进制字符串允许精确表示和指定浮点数。这在调试和数值工作时非常有用。3、float.hex()该方法将浮点数的表示形式返回为十六进制字符串。对于有限浮点数，此表示将始终包括前导0x和尾随p指数。2.3字符串字符串文字可以包含在匹配的单引号(')或双引号(")中。它们也可以包含在三个单引号或三个双引号的匹配组中(这些通常称为三引号字符串)。反斜杠(\)字符用于对具有特殊含义的字符进行转意，例如换行符，反斜杠本身或引号字符。字符串文字可以选择以字母'r'或'R'为前缀;这些字符串称为原始字符串，并使用不同的规则来解释反斜杠转义序列。前缀'u'或'U'将会使字符串成为Unicode字符串。Unicode字符串使用UnicodeConsortium和ISO10646定义的Unicode字符集。下面描述的一些其他转义序列在Unicode字符串中可用。需要特别指出的是，在Python3中，前缀'b'或'B'将被忽略;它表示文字应该成为Python3中的字节文字(例如，当代码自动转换为2to3时)。一个'u'或'b'前缀后面可以跟一个'r'前缀。在三引号字符串中，允许(并保留)使用未转义的换行符和引号，除了连续三个未转义的引号终止字符串。除非存在'r'或'R'前缀，否则字符串中的转义序列将根据与标准C使用的规则类似的规则进行解释。2.3字符串常用转义序列及其作用如下表所示。前缀作用备注\newline忽略

\\反斜杠(\)

\'单引号(')

\"双引号(")

\aASCII贝尔(BEL)

\bASCII退格(BS)

\fASCIIFormfeed(FF)

\nASCII换行(LF)

\N{name}Unicode数据库中名为name的字符(仅限Unicode)

\rASCII回车(CR)

\tASCII水平标签(TAB)

\uxxxx具有16位十六进制值xxxx的字符(仅限Unicode)形成代理对的一部分的各个代码单元可以使用该转义序列进行编码。\Uxxxxxxxx具有32位十六进制值xxxxxxxx的字符(仅限Unicode)任何Unicode字符都可以这种方式编码，但如果Python编译为使用16位代码单元(默认值)，则基本多语言平面(BMP)之外的字符将使用代理项对进行编码。\vASCII垂直标签(VerticalTab)

\ooo带有八进制值ooo的字符与标准C一样，最多可接受三个八进制数字。\xhh带有十六进制值hh的字符与标准C不同，只需要两个十六进制数字。2.3字符串Python为字符串提供了详尽的方法支持，以下选取其中一部分进行说明。函数名称作用str.capitalize()返回字符串的副本，其首字符大写，其余字符小写。str.center(width[,fillchar])以长度宽度的字符串为中心返回。使用指定的fillchar完成填充(默认为空格)str.count(sub[,start[,end]])返回[start，end]范围内substringsub的非重叠出现次数str.endswith(suffix[,start[,end]])检测字符串是否以suffix参数作为结束后缀，当给出star、end参数时，检测范围即遵循给定的范围str.find(sub[,start[,end]])返回在切片中找到子字符串sub在原字符串中[start:end]范围内第一次出现时候的索引位置str.format(*args,**kwargs)执行字符串格式化操作。调用此方法的字符串可以包含由大括号分隔的文字文本或替换字段{}。每个替换字段都包含位置参数的数字索引或关键字参数的名称。返回字符串的副本，其中每个替换字段都替换为相应参数的字符串值str.isalnum()如果字符串中的所有字符都是字母数字且至少有一个字符，则返回true，否则返回falsestr.isalpha()如果字符串中的所有字符都是字母并且至少有一个字符，则返回true，否则返回falsestr.isdigit()如果字符串中的所有字符都是数字并且至少有一个字符，则返回true，否则返回falsestr.islower()如果字符串中的所有字符都是小写且至少有一个外壳字符，则返回true，否则返回falsestr.isspace()如果字符串中只有空格字符并且至少有一个字符，则返回true，否则返回falsestr.isupper()如果字符串中的所有字符都是大写且至少有一个外壳字符，则返回true，否则返回false2.4序列数据所谓序列，指的是一块可存放多个值的连续内存空间，这些值按一定顺序排列，可通过每个值所在位置的编号（称为索引）访问它们。字符串也是一种常见的序列，它也可以直接通过索引访问字符串内的字符。我们后续会提到，几乎所有的Python的数据类型都可以视作对象，而对象一般分为可变与不可变两种类型，前者允许在创建并初始化之后修改对象里面的值，而后者一旦对象被创建后即不能进行修改。序列数据也一样，list和bytearray属于可变序列类型，而tuples则属于不可变序列类型。2.4序列数据针对可变序列类型，一般而言支持如下表所示的通用操作。操作示例作用

s[i]=xs中的第i个元素被替换为x

s[i:j]=t从i到j的s的子部分被可迭代的t的内容所替换

dels[i:j]可以视为s[i:j]=[]

s[i:j:k]=t元素s[i:j:k]被t的元素取代t必须与它所替换的切片具有相同的长度dels[i:j:k]从列表中删除元素s[i:j:k]

s.append(x)可以视为s[len(s):len(s)]=[x]

s.extend(t)和s+=t可以视为s[len(s):len(s)]=tt可以是任何可迭代的对象s*=n更新s，其内容重复n次

s.count(x)返回s中满足s[i]==x的i的个数

s.index(x[,i[,j]])返回满足s[k]==xandi<=k<j的最小的k

s.insert(i,x)可以视为

s[i:i]=[x]当i为负数时将取第len(s)+i个元素，若len(s)+i仍为负数则直接将i视为0s.pop([i])可以视为x=s[i];dels[i];returnxi为可选参数，默认为-1，即若不输入参数，则默认取最后一个元素进行操作s.remove(x)可以视为dels[s.index(x)]

s.reverse()反转s中的所有元素该函数会直接修改原序列s，并不会返回一个新的序列对象s.sort([cmp[,key[,reverse]]])对s中的元素进行排序03Python程序控制3.1

条件判断3.2

循环控制3.3

异常处理3.1条件判断条件判断语句的一般格式为：ifexpression1：statement1elifexpression2:statement2else：statement3其中，elif和else均为可选，elif可以有多个，但else在一个条件判断语句中仅可以有一个。每个if和elif后均跟随一个expression语句和一段statement的可执行代码，其中expression为具有True或False的返回值的语句。3.1条件判断例如，下面代码中，根据x与3比较的结果，打印greater、eq或者small。ifx>3:print("greater")elifx==3:print("eq")else:print("small")系统将会逐个对expression进行判断，当expression的返回值为True时，则执行其对应的if或elif的statement语句并在执行完毕后直接跳出这整段条件判断语句(即直接跳至最后一个statement之后)。若所有expression均返回False，则执行else对应的statement。3.2循环控制循环控制语句分为两种：while和for，其中while的一般格式为：whileexpression:statement1else:statement2系统将会循环检测expression语句，若为True，则执行statement1并继续循环检测expression语句，若为False，则执行一次statement2并结束while循环语句。此外，在statement1中，还应当注意两个特殊的关键字break和continue。当程序逐行执行statement1中语句直至碰见break时，会直接跳出并结束while循环语句，并且不会执行else语句；而当碰见continue时，则会直接跳转回到expression语句来继续执行。3.2循环控制for循环语句的一般格式为：fortarget_listinexpression_list:statement1else:statement2该语句中的主要操作对象为一个序列数据对象expression_list，系统会自己内部生成一个expression_list的迭代器，用以以索引的升序顺序获取expression_list中的每一项元素给target_list，然后执行statement1，执行完之后继续通过迭代器获取下一个元素给target_list，如此反复，直到expression_list中的元素被迭代至最后一个为止。最后如果有else语句，则执行else对应的statement2语句。同while语句一样，for循环语句也支持break和continue语句。3.2循环控制对于循环语句，需要有跳出当前循环和跳出循环的方法，在Python中，使用continue和break语句，使用方法同c/c++/java。for循环语句需要注意两点：1、如果想要直接通过序列索引而非序列元素来进行迭代循环的话，可以采用如下的方式来进行迭代：fortarget_indexinrange(len(expression_list)):statement1如此一来，target_index即为expression_list当前迭代元素的索引值，可以通过expression_list[target_index]来访问该元素。2、在可变序列中，内部计数器用于跟踪下一个使用的元素，并在每次迭代时递增。当该计数器达到序列的长度时，循环终止。3.3异常处理异常处理语句用于捕获并处理Python中的异常情况。异常处理语句指定一个或多个异常处理程序。当try子句中没有异常发生时，不执行异常处理程序。当try子句中发生异常时，将启动对异常处理程序的搜索。此搜索依次检查except子句，直到找到与该异常匹配的子句。例如：try:fh=open("testfile","w")fh.write("这是一个测试文件，用于测试异常!!")exceptIOError:print"Error:没有找到文件或读取文件失败"else:print"内容写入文件成功"finally:fh.close()3.3异常处理在异常处理语句中如果没有except子句匹配异常，则在周围代码和调用堆栈中继续搜索异常处理程序。如果对except子句的标头中的表达式的求值引发异常，则取消对处理程序的原始搜索，并在周围代码和调用堆栈中开始搜索新异常。找到匹配的except子句时，会将异常分配给该except子句中指定的目标，并执行except子句的套件。所有except子句必须具有可执行块。到达此块的末尾时，在整个try语句之后继续执行。在执行except子句之前，将有关异常的详细信息分配给sys模块中的三个变量：sys.exc_type接收标识异常的对象;sys.exc_value接收异常的参数;sys.exc_traceback接收回溯对象，标识发生异常的程序中的点。这些细节也可以通过sys.exc_info()函数获得，它返回一个元组。不推荐使用相应的变量来支持此函数，因为它们在线程程序中的使用是不安全的。3.3异常处理可选的else语句执行条件是，如果控制流离开执行try套件，没有出现异常，没有return，continue或者break被执行的语句。如果finally存在，它的作用主要是用来完成一些'清理'处理。如果任何子句中发生异常但未处理，则会临时保存该异常。如果存在已保存的异常，则在该finally子句的末尾重新引发。如果该finally子句引发另一个异常或执行returnorbreak语句，则丢弃保存的异常。在finally语句中执行一个continue语句是非法的。函数的返回值由return执行的最后一个语句确定。由于finally子句总是执行，因此在子句中执行的return语句finally将始终是最后执行的语句。04Python函数4

Python函数函数定义在Python中有两种函数对象：内置函数和用户自定义函数。两者都支持相同的操作(调用函数)，但实现方式不同，因此可以视作不同的对象类型。函数定义是可执行语句。它的执行将当前本地命名空间中的函数名称绑定到一个函数对象(该函数的可执行代码的包装器)。此函数对象包含对当前全局命名空间的引用，作为调用函数时要使用的全局命名空间。函数参数定义函数的时候，我们把参数的名字和位置确定下来，函数的接口定义就完成了。对于函数的调用者来说，只需要知道如何传递正确的参数，以及函数将返回什么样的值就够了，函数内部的复杂逻辑被封装起来，调用者无需了解。Python的函数定义非常简单，但灵活度却非常大。除了正常定义的必选参数外，还可以使用默认参数、可变参数和关键字参数，使得函数定义出来的接口，不但能处理复杂的参数，还可以简化调用者的代码。4

Python函数匿名函数

匿名函数：当我们在传入函数时，有些时候，不需要显式地定义函数，直接传入匿名函数更方便。匿名函数有个限制，就是只能有一个表达式，不用写return，返回值就是该表达式的结果。

用匿名函数有个好处，因为函数没有名字，不必担心函数名冲突。此外，匿名函数也是一个函数对象，也可以把匿名函数赋值给一个变量，再利用变量来调用该函数。

4

Python函数装饰器

装饰器本质上是一个Python函数，它可以让其他函数在不需要做任何代码变动的前提下增加额外功能，装饰器的返回值也是一个函数对象。装饰器用于有以下场景，比如:插入日志、性能测试、事务处理、缓存、权限校验等场景。

python中的装饰器(decorator)一般采用语法糖的形式，是一种语法格式。比如：@classmethod，@staticmethod，@property，@xxx.setter，@wraps()，@func_name等都是python中的装饰器。4

Python函数调用装饰器来修饰函数，而不用重复修改函数或者增加新的封装。这样，我们就提高了程序的可重复利用性，并增加了程序的可读性。defuse_logging(func):defwrapper(*args,**kwargs):logging.warn("%sisrunning"%func.__name__)returnfunc(*args)returnwrapper@use_loggingdefdecorator():print("decorator")05面向对象设计5.1

对象与类5.2类的特性5面向对象设计面向对象编程——ObjectOrientedProgramming，简称OOP，是一种程序设计思想。OOP把对象作为程序的基本单元，一个对象包含了数据和操作数据的函数。面向过程的程序设计把计算机程序视为一系列的命令集合，即一组函数的顺序执行。为了简化程序设计，面向过程把函数继续切分为子函数，即把大块函数通过切割成小块函数来降低系统的复杂度。而面向对象的程序设计把计算机程序视为一组对象的集合，而每个对象都可以接收其他对象发过来的消息，并处理这些消息，计算机程序的执行就是一系列消息在各个对象之间传递。5.1对象与类类和实例在Python中，所有数据类型都可以视为对象，当然也可以自定义对象。自定义的对象数据类型就是面向对象中的类（Class）的概念。面向对象最重要的概念就是类（Class）和实例（Instance），必须牢记类是抽象的模板，而实例是根据类创建出来的一个个具体的“对象”，每个对象都拥有相同的方法，但各自的数据可能不同。5.2类的特性封装在Class内部，可以有属性和方法，而外部代码可以通过直接调用实例变量的方法来操作数据，这样，就隐藏了内部的复杂逻辑。但是外部代码还是可以自由地修改一个实例的属性。如果要让内部属性不被外部访问，可以把属性的名称前加上两个下划线__，在Python中，实例的变量名如果以__开头，就变成了一个私有变量（private），只有内部可以访问，外部不能访问。想要在外部访问和修改对象的内部属性，可以通过给类设置get和set方法。封装可以有效的保护代码和数据，代码安全性。封装还可以使代码低内聚，高耦合，具有更强的拓展性。5.2类的特性继承在OOP程序设计中，当我们定义一个class的时候，可以从某个现有的class继承，新的class称为子类（Subclass），而被继承的class称为基类、父类或超类（Baseclass、Superclass）。继承有什么好处？最大的好处是子类获得了父类的全部功能，即子类可以调用父类的全部函数。当子类和父类都存在相同的方法时，子类的方法会覆盖父类的方法，在代码运行的时候，总是会调用子类的方法。这样，我们就获得了继承的另一个好处：多态。5.2类的特性多态的好处可替换性：多态对已存在的代码具有可替换性。可扩充性：多态对代码具有可扩充性。新增子类不会影响已存在类的各种性质。灵活性：多态在程序中体现了灵活多样的操作，提高了使用效率（重载函数，重写函数）。简化性：多态简化对应用软件的代码编写和修改过程，尤其在处理大量对象的运算和操作时，这个特点尤为突出和重要。06本章小结6本章小结本章针对Python进行了基本的讲解，首先描述了Python的基本优点与特性，包括：易用性、可拓展性、解释性和易读性等。随后讲解了Python在不同平台上的安装方式。之后的小节主要从以下三个方面对Python进行了讲解：1、Python数据类型：一般而言，Python的数据类型可以分为以下两类：数字类型(NumericTypes)：int、float、long、complex四类。序列类型(SequenceTypes)：str、unicode、list、tuple、bytearray、buffer、xrange七大类。2、Python程序控制：主要介绍了三种常用的Python流程控制手段：条件控制语句：if循环控制语句：while、for异常处理语句：try..,except…finally本章习题1、Python的可拓展性表现在哪些方面？试举例说明。2、Python的数据类型都有哪些？分别都有哪些用法？3、尝试写一个函数，同时用上if、while、for和try语句。课程实验给定一个

n

×

n

的二维矩阵表示一个图像。将图像顺时针旋转90度。提示：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。示例：EndofCourseThankyou!第三讲线性表授课教师：林迪目录1.线性表抽象数据结构2.顺序表3.链表目录4.链表应用5.本章小结线性表知识结构01线性表抽象数据结构1线性表的定义线性表（LinearList）是一种线性结构，由n(n≥0)个类型相同的数据元素a1,a2,…，an组成的有限序列，记做（a1,a2,…，ai-1，ai，ai+1，…，an），一般表示为：在一个非空线性表里，存在唯一的"首元素"，唯一的"尾元素"；除了首元素外，表中每个元素都有且只有一个前驱元素；除尾元素外，表中每个元素都有且只有一个后继元素。线性表中元素在位置上是有序的，这种位置上有序性就是一种线性关系，用二元组表示：

1线性表的特性同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。有序性：线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>。1线性表的应用将线性表数据结构抽象成为一种数据类型，这个数据类型中包含数据元素、元素之间的关系、操作元素的基本算法。对于基本数据类型，很多高级语言已经帮我们实现了用于操作它们的基本运算，我们需要基于这些基本运算，为我们封装的自定义数据类型提供操作它们的算法。比如数组就是一种被抽象出来的线性表数据类型，数组自带很多基本方法用于操作数据元素。同样的链表也满足线性表的性质，只不过在存储空间上是动态分配的，在Python中list和tuple这些数据结构，可看作是线性表的实现。1顺序表和链表线性表应当包括创建空表、返回长度信息、插入、更新和删除等基本操作，将表中的元素顺序存储在一片足够大的连续存储位置里，称作顺序表，元素在存储区内的物理顺序就是该表的元素的逻辑顺序。将表中的元素通过链接的形式保持顺序，存储在一系列存储区内，每个数据元素保存前驱元素和后继元素的存储地址，称作链表。02顺序表2.1

顺序表动态存储2.2

顺序表静态存储2.3

顺序表实现2顺序表的定义把线性表中的所有元素按照其逻辑顺序依次存储在计算机存储器中指定存储位置开始的一块连续的存储空间中，就构成顺序表。该存储空间的起始位置就是由数组名表示的地址常量。顺序表的顺序存储结构是利用数组来实现的。因此对于数组中元素的定位只需要O(1)的时间复杂度即可完成，但是删除某一元素就需要O(n)的时间复杂度了。顺序表有两种存储结构，分别是动态存储结构和静态存储结构。2顺序表的优缺点优点：➢无需为表示结点间的逻辑关系而增加额外的存储空间；➢可方便地随机存取表中的任一元素。缺点：➢插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低；➢由于顺序表要求占用连续的存储空间，因此当表长变化较大时，难以确定合适的存储规模。2.1顺序表动态存储顺序表的动态存储结构最大的特点就是可以进行动态的内存分配，可以很方便的进行扩容，当存储空间达到设定的阈值的时候，可以通过内置的算法重新扩大内存空间，然后将之前的元素复制过去，比如Java中的ArrayList数据结构。通过动态存储这种机理，用户可以更加方便地将主要精力面向于具体需要操作的内容，但是频繁的扩容会造成程序性能下降，并且扩容之后的空间不能够完全使用，造成存储空间浪费，因此一般在使用的时候需要预估数据占用的空间，从而减少扩容带来的开销。2.2顺序表静态存储顺序表静态存储结构是一旦分配了存储空间，在使用的过程中将不能再次分配内存空间，如果访问的下标越界将会发生内存溢出等错误。优点就是能够节省扩容所带来的额外开销，如果分配的大小比较合理，将会节省存储空间。和动态分配相比，缺点也是显而易见的，当数组元素超出预估大小的时候，需要我们自己在程序中判断和处理，增加了代码的复杂性。2.3顺序表实现顺序表中通常元素类型相同，每个元素的存储量相同，等距安排同等大小的存储单元，顺序存储元素数据即可。表中任何元素的位置计算都很简单，只要知道第一个元素的内存位置，再加上逻辑地址(表内元素索引)与单个元素的存储单元大小的乘积即可得到，故元素访问操作的时间复杂度是O(1)。当元素长度不一样的时候，可以在顺序表中存储元素的存储地址，元素另行存储，这个顺序表就称作是这组数据的索引。索引顺序表的每个元素为地址，占用空间一样，直接访问索引再依据索引中存储的地址找到实际元素，时间复杂度依然为O(1)。2.3顺序表实现序列是Python中最基本的数据结构。序列中的每个元素都分配一个索引，第一个索引是0，第二个索引是1，依此类推。Python包含6种内建的序列，即列表(List)、元组(Tuple)、字符串、Unicode字符串、buffer对象和xrange对象。序列通用的操作包括索引、长度、组合(序列相加)、乘法、分片、检查成员、遍历、最小值和最大值。但最常见的是Python的List和Tuple，均采用了顺序表的结构。此外，Python已经内置了确定序列的长度、确定最大和最小元素的方法。下面我们看一下Python中List和Tuple的实现方式。2.3顺序表实现Python中List的实现，采用的是数据结构中的顺序表的动态存储结构。在Python中，列表被实现为长度可变的数组。从细节上看，Python中的列表是由对其它对象的引用组成的连续数组。指向这个数组的指针及其长度被保存在列表头结构中。这意味着，每次添加或删除一个元素时，可能需要对引用所指向的数组重新分配。Python在创建这些数组时采用了跳跃式增长的内存分配方式，并不是每次操作都需要改变数组的大小。Python中的列表实现类似于下面的C构体。ob_item是指向列表对象的数组指针。allocated是申请内存的槽数。2.3顺序表实现在Python中，List是最常用的数据类型。List的数据项不需要具有相同的类型。List的常用方法如下表所示。List的操作方法方法描述list.append(x)将x作为一个元素添加到列表末尾list.extend(iterable)通过附加iterable中的所有项来扩展列表list.insert(i,x)在位置i插入元素xlist.remove(x)从列表中删除值等于x的第一项list.pop([i])删除列表中给定位置的元素list.clear()删除列表中的所有元素list.index(x[,start[,end]])返回值等于x的第一个项的位置list.count(x)返回x出现在列表中的次数list.sort(key=None,reverse=False)对列表中的元素按照某种规则排序list.reverse()将列表元素反转list.copy()浅复制一份原来的列表2.3顺序表实现Tuple是不可变的List，一旦创建了一个Tuple就不能以任何方式改变它。元组内可以存储任意数据类型。Tuple的定义List方式相同，除了整个元素集是用小括号包围的而不是方括号。Tuple的元素与List一样按定义的次序进行排序。Tuple的索引与List一样从0开始，所以一个非空Tuple的第一个元素总是t[0]；负数索引与List一样从Tuple的尾部开始计数。与List一样可以使用分片。注意当分割一个List时，会得到一个新的List；当分割一个Tuple时，会得到一个新的Tuple。但是我们不能向Tuple增加、删除元素。Tuple比List操作速度快，如果定义了一个值的常量集，并且唯一的作用是不断地遍历它，可以使用Tuple代替List。如果对不需要修改的数据进行"写保护"，Tuple可以使代码更安全。03链表3.1

单链表3.2

双链表3.3

单向循环链表3.4双向循环链表3链表特性前面介绍了线性表中顺序表的知识，相比之下，链表分配的存储空间不连续，这样分配的优点是方便列表删除和插入操作，缺点是查找某一个元素的时间复杂度增加，并且内存空间不能连续分配，容易产生内存碎片，内存利用率不高。链表可以具体实现为单向链表、双向链表、单向循环链表和双向循环链表等链接方式。链表中每一个元素都由当前节点的数据和其他节点的地址两部分组成。通过这样的方式可以方便的找到空间上不连续的节点。3.1单链表单向链表的内存表示如图所示，每一个节点有两个元素，第一个代表该节点的数值，第二个存储指向下一个节点的内存地址，首节点是链表的头部，链表的增删改查等操作都是从这个指针开始遍历的，最后一个节点的地址为NULL，代表着链表的结束。另外我们还可以为单向链表增加一个尾节点引用，这样做的好处是在尾部插入元素的时候就不用从头结点遍历到尾节点了，提升了尾插法的效率。单向链表的基本操作包括定义单向链表的构造函数，初始化头结点，其次定义一些常用操作，比如判断链表是否为空，使用头插法插入节点，删除第一个元素，在链表尾部添加元素，删除最后一个元素，查找元素，打印所有元素等等。3.1单链表代码实现fromLNodeimportLNodeclassLList:def__init__(self):self.head=None

defisEmpty(self):returnself.headisNone

defprepend(self,elem):self.head=LNode(elem,self.head)

defpop(self):ifself.headisNone:raiseValueErrore=self.head.elemself.head=self.head.nextreturne

3.1单链表代码实现defappend(self,elem):ifself.headisNone:self.head=LNode(elem,None)returnp=self.headwhilep.nextisnotNone:p=p.nextp.next=LNode(elem,None)defpoplast(self):ifself.headisNone:#emptylistraiseValueErrorp=self.headifp.nextisNone:#listwithonlyoneelemente=p.elem;self.head=Nonereturnewhilep.next.nextisnotNone:#tillp.nextbelastnodep=p.nexte=p.next.elem;p.next=Nonereturne3.1单链表代码实现deffind(self,pred):p=self.headwhilepisnotNone:ifpred(p.elem):returnp.elemp=p.nextreturnNone

defprintall(self):p=self.headwhilepisnotNone:print(p.elem)p=p.next3.2双链表双向链表的单个节点由两部分组成，第一部分是当前节点元素；第二部分是指向其他节点的指针，指针有两个，第一个指针指向前一个元素，第二个指针指向后一个元素，同时双向链表可以从首节点和尾节点开始遍历，如图所示。优点：可以找到前驱和后继，可进可退。缺点：增加删除节点复杂，多需要分配一个指针存储空间。3.2双链表代码实现classLDList(LList1):#classofDoubleLinkedList#基于带尾结点引用的单链表派生一个双链表类def__init__(self):LList1.__init__(self)defprepend(self,elem):p=LDNode(None,elem,self.head)self.head=pifself.rearisNone:#insertinemptylistself.rear=pelse:#otherwise,createtheprevreferencep.next.prev=pdefappend(self,elem):#与prepend对称p=LDNode(self.rear,elem,None)self.rear=pifself.headisNone:#insertinemptylistself.head=pelse:#otherwise,createthenextreferencep.prev.next=p3.2双链表代码实现defpop(self):ifself.headisNone:raiseValueErrore=self.head.elemself.head=self.head.next#删除当前首结点ifself.headisNone:self.rear=None#如果删除后表空，把rear也置空else:self.head.prev=None#首结点的prev链接置空returnedefpoplast(self):ifself.headisNone:raiseValueErrore=self.rear.elemself.rear=self.rear.previfself.rearisNone:self.head=None#删除后表空，把head也置空else:self.rear.next=Nonereturne3.3单向循环链表单向循环链表的数据结构如图所示。单向循环链表在单向链表的基础上，将尾指针指向了头结点。这样做的好处是构成环状结构，可以循环的进行遍历，对于一些需要环形数据结构的算法来说非常有用，比如约瑟夫问题。3.3单向循环链表代码实现classLCList:#classofCircularLinkedListdef__init__(self):self.rear=None

defisEmpty(self):returnself.rearisNone

defprepend(self,elem):#addelementinthefrontendp=LNode(elem,None)ifself.rearisNone:p.next=p#initiatescircleself.rear=pelse:p.next=self.rear.nextself.rear.next=p

defappend(self,elem):#addelementintherearendself.prepend(elem)self.rear=self.rear.next3.3单向循环链表代码实现defpop(self):#popoutheadelementifself.rearisNone:raiseValueErrorp=self.rear.nextifself.rearisp:self.rear=Noneelse:self.rear.next=p.nextreturnp.elem

defprintall(self):p=self.rear.nextwhileTrue:print(p.elem)ifpisself.rear:breakp=p.next3.4双向循环链表双向循环链表将头结点的前驱指针指向了尾节点，同时将尾节点的后继指针指向了头结点，这样就能循环遍历双向链表了。双向链表通过空间换时间的方式提高了增删改查操作的性能。双向循环链表的数据结构如图所示。与非循环双链表相比，循环双链表有链表中没有空指针域，p所指结点为尾结点的条件：p->next==L，一步操作即L->prior可以找到尾结点等优点。04链表应用4

链表应用链表具有重要的实用意义，比如在操作系统中处理文件系统、内存分配、线程和进程结构等构造信息中大量使用。在算法中也有典型的应用，比如约瑟夫问题就可以用链表来求解。约瑟夫问题描述如下：N个人围成一圈，从第一个人开始报数，报到数字m的人出圈，剩下的人继续从1开始报数，报到数字m的人出圈；如此往复，直到最后剩下一个人，其余人都将出圈。这个问题可以使用链表来解决，通过循环链表可以模拟不断计数剔除的操作，最终剩下一个元素的时候结束。4

链表应用约瑟夫问题代码

classList(object):def__init__(self):self.list=[]defEmpty(self):returnself.list==[]defJoin(self,item):self.list.insert(0,item)defPop(self):returnself.list.pop()defLength(self):returnlen(self.list)

defJosephus(k,namelist):s=List()foriinrange(len(namelist)):s.Join(namelist[i])print(namelist)i=1whiles.Length()!=1:temp=s.Pop()if(i!=k):s.Join(temp)else:i=0i=i+1returns.Pop()

if__name__=='__main__':nameList=['A','B','C','D']print(Josephus(2,nameList))05本章小结6本章小结通过本章的学习，可以对线性表有一定认知，线性表可以分为顺序表和链表，这两种线性结构具有不同的逻辑标识、内存存储以及存储特性，具有不同的优缺点，在实际问题中可以选择合适的数据结构去使用。同时通过Python代码实现了基本的数据结构，讨论了链表的实际应用。本章习题1.什么是线性表？线性表有哪些性质，逻辑