Python第四周 学习笔记（1）
函数[*]Python的函数没有return语句，隐式会返回一个None值
[*]函数是可调用的对象，callable()
函数参数
[*]参数调用时传入的参数要和定义的个数相匹配（可变参数例外）
[*]位置参数
[*]def f(x, y, z) 调用使用 f(1, 3, 5)
[*]按照参数定义顺序传入实参
[*]关键字参数
[*]def f(x, y, z) 调用使用 f(x=1, y=3, z=5)
[*]使用形参的名字来出入实参的方式，如果使用了形参名字，那么传参顺序就可和定义顺序不同
[*]传参
[*]要求位置参数必须在关键字参数之前传入，位置参数是按位置对应的
函数参数默认值
[*]定义时，在形参后跟上一个值
[*]作用
[*]参数的默认值可以在未传入足够的实参的时候，对没有给定的参数赋值为默认值
[*]参数非常多的时候，并不需要用户每次都输入所有的参数，简化函数调用
可变参数
[*] 一个形参可以匹配任意个参数
[*]在形参前使用*表示该形参是可变参数，可以接收多个实参
[*] 收集多个实参为一个tuple
[*] 关键字参数的可变参数
[*]形参前使用**符号，表示可以接收多个关键字参数
[*]收集的实参名称和值组成一个字典
[*]有位置可变参数和关键字可变参数
[*]位置可变参数在形参前使用一个星号*
[*]关键字可变参数在形参前使用两个星号**
[*]位置可变参数和关键字可变参数都可以收集若干个实参，位置可变参数收集形成一个tuple，关键字可变参数收集形成一个dict
[*]混合使用参数的时候，可变参数要放到参数列表的最后，普通参数需要放到参数列表前面，位置可变参数需要在关键字可变参数之前
keyword-only参数
[*]如果在一个星号参数后，或者一个位置可变参数后，出现的普通参数，实际上已经不是普通的参数了，而是keyword-only参数
def fn(*args, x):
print(x)
print(args)
def(**kwargs, x):
print(x)
print(kwargs)
直接报语法错误
可以理解为kwargs会截获所有的关键字参数，就算你写了x=5，x也永远得不到这个值，所以语法错误
[*]keyword-only 参数另一种形式
def fn(*, x,y):
print(x,y)
fn(x=5,y=6)
*号之后，普通形参都变成了必须给出的keyword-only 参数
可变参数和参数默认值
def fn(*args, x=5):
print(x)
print(args)
参数规则
[*]参数列表参数一般顺序是，普通参数、缺省参数、可变位置参数、keyword-only参数（可带缺省值）、可变关键字参数
参数解构
[*]给函数提供实参的时候，可以在集合类型前使用*或者**，把集合类型的结构解开，提取出所有元素作为函数的实参
[*]非字典类型使用*解构成位置参数
[*]字典类型使用**解构成关键字参数
[*] 提取出来的元素数目要和参数的要求匹配，也要和参数的类型匹配
[*]参数解构和可变参数
[*]给函数提供实参的时候，可以在集合类型前使用*或者**，把集合类型的结构解开，提取出所有元素作为函数的实参
函数返回值与作用域
函数的返回值
[*]Python函数使用return语句返回“返回值”
[*]所有函数都有返回值，如果没有return语句，隐式调用return None
[*]return 语句并不一定是函数的语句块的最后一条语句
[*]一个函数可以存在多个return语句，但是只有一条可以被执行。如果没有一条return语句被执行到，隐式调用return None
[*]如果有必要，可以显示调用return None，可以简写为return
[*]如果函数执行了return语句，函数就会返回，当前被执行的return语句之后的其它语句就不会被执行了
[*] 作用：结束函数调用、返回值
[*]返回多个值
[*]函数不能同时返回多个值
[*]return 是指明返回一个列表，是一个列表对象
[*]return 1, 3, 5 看似返回多个值，隐式的被python封装成了一个元组
def showlist():
return 1, 3, 5
x, y, z = showlist() # 使用解构提取更为方便
函数嵌套
[*]在一个函数中定义了另外一个函数
[*]函数有可见范围，这就是作用域的概念
[*]内部函数不能在外部直接使用，会抛NameError异常，因为它不可见
作用域
[*] 全局作用域
[*]在整个程序运行环境中都可见
[*] 局部作用域
[*]在函数、类等内部可见
[*]局部变量使用范围不能超过其所在的局部作用域
[*]外层变量作用域在内层作用域可见
[*] 内层作用域inner中，如果定义了o=97，相当于当前作用域中重新定义了一个新的变量o，但是这个o并没有覆盖外层作用域outer中的o
[*]全局变量global
#x = 5
def foo():
global x
x = 10
x += 1 # 报错吗？
print(x) # 打印什么？
print(x) #打印什么？
[*]使用global关键字的变量，将foo内的x声明为使用外部的全局作用域中定义的x
[*] 但是，x = 10 赋值即定义，在内部作用域为一个外部作用域的变量x赋值，不是在内部作用域定义一个新变量，所以x+=1不会报错。注意，这里x的作用域还是全局的
[*]x+=1这种是特殊形式产生的错误的原因？先引用后赋值，而python动态语言是赋值才算定义，才能被引用。解决办法，在这条语句前增加x=0之类的赋值语句，或者使用global 告诉内部作用域，去全局作用域查找变量定义
[*] 内部作用域使用x = 5之类的赋值语句会重新定义局部作用域使用的变量x，但是，一旦这个作用域中使用global声明x为全局的，那么x=5相当于在为全局作用域的变量x赋值
[*]global使用原则
[*]外部作用域变量会内部作用域可见，但也不要在这个内部的局部作用域中直接使用，因为函数的目的就是为了封装，尽量与外界隔离
[*]如果函数需要使用外部全局变量，请使用函数的形参传参解决
[*]一句话：不用global。学习它就是为了深入理解变量作用域
闭包(重要概念)
[*]自由变量：未在本地作用域中定义的变量。例如定义在内存函数外的外层函数的作用域中的变量
[*]闭包：就是一个概念，出现在嵌套函数中，指的是内层函数引用到了外层函数的自由变量，就形成了闭包。很多语言都有这个概念，最熟悉就是JavaScript
[*]使用global可以解决，但是这使用的是全局变量，而不是闭包
[*]如果要对普通变量的闭包，Python3中可以使用nonlocal
nonlocal关键字
[*]使用了nonlocal关键字，将变量标记为不在本地作用域定义，而在上级的某一级局部作用域中定义，但不能是全局作用域中定义
默认值的作用域
[*] 函数也是对象，python把函数的默认值放在了属性中，这个属性就伴随着这个函数对象的整个生命周期
[*]属性defaults中使用元组保存所有位置参数默认值，它不会因为在函数体内使用了它而发生改变
[*] 属性kwdefaults中使用字典保存所有keyword-only参数的默认值
[*]使用可变类型作为默认值，就可能修改这个默认值
[*] 有时候这个特性是好的，有的时候这种特性是不好的，有副作用
[*]第一种方法
[*]使用影子拷贝创建一个新的对象，永远不能改变传入的参数
def foo(xyz=[], u='abc', z=123):
xyz = xyz[:] # 影子拷贝
xyz.append(1)
print(xyz)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
函数体内，不改变默认值
xyz都是传入参数或者默认参数的副本，如果就想修改原参数，无能为力
[*]第二种方法
[*]通过值的判断就可以灵活的选择创建或者修改传入对象
[*]这种方式灵活，应用广泛
[*]很多函数的定义，都可以看到使用None这个不可变的值作为默认参数，可以说这是一种惯用法
def foo(xyz=None, u='abc', z=123): if xyz is None:
xyz = []
xyz.append(1)
print(xyz)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
foo()
print(foo.__defaults__)
使用不可变类型默认值
如果使用缺省值None就创建一个列表
如果传入一个列表，就修改这个列表
变量名解析原则LEGB
[*]Local，本地作用域、局部作用域的local命名空间。函数调用时创建，调用结束消亡
[*]Enclosing，Python2.2时引入了嵌套函数，实现了闭包，这个就是嵌套函数的外部函数的命名空间
[*]Global，全局作用域，即一个模块的命名空间。模块被import时创建，解释器退出时消亡
[*]Build-in，内置模块的命名空间，生命周期从python解释器启动时创建到解释器退出时消亡。例如 print(open)，print和open都是内置的变量
[*]所以一个名词的查找顺序就是LEGB
函数的销毁
[*] 全局函数销毁
[*]重新定义同名函数
[*]del 语句删除函数对象
[*]程序结束时
[*]局部函数销毁
[*]重新在上级作用域定义同名函数
[*]del 语句删除函数名称，函数对象的引用计数减1
[*]上级作用域销毁时
递归
[*]函数直接或者间接调用自身就是递归
[*]递归需要有边界条件、递归前进段、递归返回段
[*]递归一定要有边界条件
[*]当边界条件不满足的时候，递归前进
[*] 当边界条件满足的时候，递归返回
[*] 递归要求
[*]递归一定要有推出条件，递归调用一定要执行这个退出条件。没有退出条件的递归调用，就是无限调用
[*]递归调用的深度不宜过深
[*]Python对递归调用的深度做了限制以保护解释器
[*]超过递归深度限制，抛出RecursionError maxinum recursion depth exceeded 超出最大深度sys.getrecursionlimit()
[*] 递归的性能
[*]循环稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果
[*]递归有深度限制，如果递归复杂，函数反复压栈，占内存很快就溢出了
[*] 间接递归
[*]通过别的函数调用了函数自身
[*]但是，如果构成了循环递归调用是非常危险的，但是往往在代码复杂的情况下，还是可能发生这种调用。要用代码的规范来避免这种递归调用的发生
[*]总结
[*]递归是一种很自然地表达，符合逻辑思维
[*]递归相对运行效率低，每一次调用函数都要开辟栈帧
[*]递归有深度限制，如果递归层次太深，函数反复压栈，栈内存很快就溢出了
[*]如果是有限次数的递归，可以使用递归，或者使用循环代替，循环代码稍微复杂一些，但是只要不是死循环，可以多次迭代直至算出结果
[*]绝大多数递归，都可以使用循环实现
[*]即使递归代码很简洁，但是能不用则不用递归
匿名函数
[*]使用Lambda表达式构建匿名函数
[*] 格式
[*]lambda 参数列表:表达式
[*]使用lambda关键字来定义匿名函数
[*]参数列表不需要小括号
[*]冒号是用来分割参数列表和表达式的
[*]不需要使用return，表达式的值,就是匿名函数返回值
[*] lambda表达式（匿名函数）只能写在一行上，被称为单行函数
[*]用途
[*]在高阶函数传参时，使用lambda表达式，往往能简化代码
生成器
生成器generator
[*]生成器指的是生成器对象，可以由生成器表达式得到，也可以使用yield关键字得到一个生成器函数，调用这个函数得到一个生成器对象
生成器函数
[*]函数体中包含yield语句的函数，返回生成器对象
[*]生成器对象，是一个可迭代对象，是一个迭代器
[*]生成器对象，是延迟计算、惰性求值的
[*]包含yield语句的生成器函数生成生成器对象的时候，生成器函数的函数体不会立即执行
[*]next(generator)会从当前位置向后执行到之后碰到的第一个yield语句，会弹出值，并暂停函数运行
[*]再次调用next函数，和上一条一样的处理过程
[*]没有多余的yield语句能被执行，继续调用next函数，会抛出StopIteration异常
[*]普通的函数调用，函数会立即执行完毕，但是生成器函数可以使用next函数多次执行
[*]生成器函数等价于生成器表达式，只不过生成器函数可以更加的复杂
[*]在生成器函数中，使用多个yield语句，执行一次后会暂停执行，把yield表达式的值返回
[*]再次执行会执行到下一个yield语句
[*]return语句依然可以终止函数运行，但return语句的返回值不能被获取到
[*]return语句会导致无法获取下一个值，抛出StopIteration异常
[*]如果函数没有显式的return语句，如果生成器函数执行到结尾，一样会抛出StopIteration异常
生成器应用
[*]协程
[*]生成器的高级用法
[*]比进程、线程轻量级
[*]史载用户空间调度的一种实现
[*]Python3 asyncio 就是协程实现，已经加入到标准库
[*]Python3.5 使用async、await关键字直接原生支持协程
[*]协程调度器实现思路
[*]有两个生成器A、B
[*]next(A)后、A执行到了yield语句暂停，然后去执行next(B)，B执行到yield语句也暂停，然后再次调用next(A)，再调用next(B)，周而复始，就实现了调度的效果
[*]协程是一种非抢占式调度
yield from
[*]yield from是Python 3.3出现的新的语法
[*]yield from iterable是for item in iterable:yield item 形式的语法糖
[*]从可迭代对象中一个个拿元素
for x in range(1000):
yield x
等价于
yield from range(1000)
树
树的特点
[*]唯一的根
[*]子树不相交
[*]除了根以外，每个元素只能有一个前驱，可以有零个或多个后继
[*]根结点没有双亲结点（前驱），叶子结点没有孩子结点（后继）
[*]vi是vj的双亲，则L(vi) = L(vj) - 1，也就是说双亲比孩子节点的层次小1
二叉树
[*]每个节点最多2棵子树
[*]二叉树不存在度数大于2的结点
[*]它是有序树，左子树、右子树是顺序的，不能交换次序
[*]即使某个结点只有一棵子树，也要确定它是左子树还是右子树
二叉树的的五种基本形态
[*]空二叉树
[*]只有一个根结点
[*]根结点只有左子树
[*]根结点只有右子树
[*]根结点有左子树和右子树
斜树
[*]左斜树，所有结点都只有左子树
[*]右斜树。所有结点都只有右子树
满二叉树
[*]一棵二叉树的所有分支结点多存在左子树和右子树，并且所有叶子结点只存在在最下面一层。
[*]同样深度二叉树中，满二叉树结点最多。
[*]k为深度(1<=k<=n)，则结点总数为2^k-1
完全二叉树
若二叉树的深度为k，二叉树的层数从1到k-1层的结点数到达到了最大个数，在第k层的所有结点都集中在最左边，这就是完全二叉树
完全二叉树由满二叉树引出
满二叉树一定是完全二叉树，但完全二叉树不是满二叉树
k为深度(1<=k<=n),则结点总数最大值为2^k-1，当达到最大值的时候就是满二叉树
二叉树性质
[*]1.在二叉树的第i层上至多有2^(i-1)个结点(i>=1)
[*]2.深度为k的二叉树，至多有2^k-1个结点(k>=1)
[*]3.对任何一棵二叉树T，如果其终端节点数为n0，度数为2的结点为n2，则有n0=n2+1
[*]换句话说，就是叶子结点数-1就等于度数为2的结点数
证明
总结点数为n=n0+n1+n2,
一棵树的分支数为n-1，因为除了根节点以外，其余节点都有一个分支，即n0+n1+n2-1
分支数还等于n00+n11+n22,n2是2分支结点所以乘以2，2n2+n1
可得2*n2+n1=n0+n1+n2-1 => n2=n0-1
[*]4.高度为k的二叉树，至少有k个结点
[*]含有n(n>=1)的结点的二叉树高度至多为n，最小为math.ceil(log(n+1)),不小于对数值的最小整数，向上取整
[*]5.具有n个结点的完全二叉树的深度为int(logn)+1或者math.ceil(log(n+1))
[*]6.如果有一棵n个结点的完全二叉树，结点按照层序编号
[*]如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是int(i/2)，向下取整
[*]就是子结点的编号整除2得到的就是父节点的编号。父节点如果是i，那么左孩子结点就是2i，右孩子结点就是2i+1
[*]如果2i>n，则结点i无左孩子，即结点i为叶子结点；否则其左孩子结点存在编号为2i
[*]如果2I+1>n，则结点i无右孩子；否则右孩子节点存在编号为2i+1
页:
[1]