【啃书】Python数据结构与算法分析(第二版)—导论

前言

算法

• 计算机科学的研究对象是问题、解决问题的过程，以及通过该过程得到的解决方案。给定一个问题，计算机科学家的目标是开发一个能够解决该问题的算法。算法是具有有限步骤的过程，依照这个过程便能解决问题。因此算法就是解决方案

计算机科学

• 定义一：研究问题及解决方案，以及研究目前无解的问题的学科。
• 定义二：在描述问题及解决方案时，经常会用“可计算”一次。因此计算机科学也可以定义为：研究可计算以及不可计算的问题，即研究算法的存在性以及不存在性。

抽象

• 所谓抽象，就是将具体的问题，使用逻辑思维，将之提炼出来。举个例子，下面这个计算开平方的函数，别人已经实现了解决方案，我们只需要调用被人写好的接口：函数名，所需参数，了解返回值就可以用了。所有的计算细节都被隐藏起来了。
  

编程

• 编程是指通过编程语言将算法编码以使其能被计算机执行的过程。

为何学习算法

• 虽然解决问题的方案有很多，但总有一个较其他在内存上、效率上更好的策略，学习算法的意义就在于比较这些算法，学会分析技巧。

Python基础

• 面向对象的编程语言、解释型语言。动态语言。

数据类型

• 内建原子数据类型(int、float、bool)

  • 整数类型int、浮点型数据float
    

    标准数学运算符：+、-、*、/、以及**(幂运算)、%(取余)、//(整除)

  • 布尔数据bool
    

    布尔对象可能的状态值是True、False。布尔运算符：and、or、not。
    布尔运算也被用于等于(==)、大于(>)…

  • 标识符
    

    即变量名:数字、字符型、下划线。命名时不以数字开头，做到见名知意。

  • 命名、定义
    

    变量名在赋值的时候，存的是数据的引用，而不是数据本身。Python又是一个动态语言，当引用发生改变的时候，数据随之改变。
    

• 内建集合数据类型(有序：list、str、tuple；无序：set、dict)

  • 列表

    列表是异构的，意味着其内部元素的指向的数据对象不需要都是同一个类，并且这个集合可以赋值给一个变量。

    • my_list = [1, 1.5, True, my_dict]

    列表有序的，所以支持一系列的Python序列运算

    • 索引(my_list[0])、连接(+)、重复(*)、成员(in)、长度(len)、切片([:])
      

      注意点：切片运算：顾头不顾尾，重复运算：返回的结果是序列中指向数据对象的引用的重复。

      my_list = [1, 2, 4, 6]
      print(my_list[1:3])  # [2, 4]
      
      A = my_list * 3
      print(A)  # [1, 2, 4, 6, 1, 2, 4, 6, 1, 2, 4, 6]
      B = [my_list] * 3
      print(B)  # [[1, 2, 4, 6], [1, 2, 4, 6], [1, 2, 4, 6]]
      my_list[0] = 5
      print(B)  # [[5, 2, 4, 6], [5, 2, 4, 6], [5, 2, 4, 6]]，当my_list改变时，B随之改变
      

    列表支持一些用于构建的数据类型的方法

    • 末尾追加 mylist.append(item)
    • 索引i处插入 mylist.insert(i, item)
    • 删除并返回 删除末尾：my_list.pop()、删除某索引i的元素：my_list.pop(i)
    • 按大小排序 my_list.sort()
    • 列表前后颠倒 my_list.reverse()
    • 删除不返回 del my_list[i]
    • 返回元素第一次出现的下标 my_list.index(item)
    • 返回元素在列表出现的次数 my_list.count(item)
    • 移除某元素第一次在列表出现 my_list.remove(item)

      my_list = [1, 2, 4, 6]
      my_list.reverse()
      print(my_list)  # [6, 4, 2, 1]
      
      print(my_list.pop())  # 1
      

    范围对象

    • range函数会生成一个代表值序列的范围对象。使用lsit可以看到其值。

      my_range = range(10)
      print(my_range)  # range(0, 10)
      print(list(my_range))  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 顾头不顾尾
      print(list(range(5, 10, 2)))  # 5开始，到9结束，步长为2
      

  • 字符串

    常量字符串通过引号引起来，与标识符(变量区别开来)。字符串是不可变的，my_str[0] = "a"会报错。

    • 由于字符串是序列，因此前面提到的序列运算符(索引(my_list[0])、连接(+)、重复(*)、成员(in)、长度(len)、切片([:]))都能用
    • 除此之外，字符串还有一些特殊地方法。
      • 居中 my_str.center(w)，返回一个新的字符串，使用空格填充，使其长度为w，并居中
      • 统计次数 my_str.count(item)，返回items出现的次数
      • 向左靠齐 my_str.ljust(w)，返回一个新的字符串，使用空格填充，使其长度为w，并使原字符靠右放置
      • 向右靠齐 my_str.rjust(w)
      • 转小写并返回 my_str.lower()
      • 转大写并返回 my_str.upper()
      • 查找item第一次出现的下标 my_str.find(item)
      • 分割 my_str.split(schar)，按schar将字符串切割，返回一个列表，schar为空时，默认使用制表符、换行符、空格等空白字符切割
      • 去除首尾空格 my_str.strip()

  • 元组

    元组与列表非常相似，都是异构数据序列。主要区别在于，元组和字符串一样不可修改。

    • 同前面列表与字符串，可以使用序列运算符(索引(my_list[0])、连接(+)、重复(*)、成员(in)、长度(len)、切片([:]))

  • 集合(set)

    集合是由零个或多个不可修改的Python数据对象组成的无序集合。集合内不允许出现重复元素，集合也是异构的。

    • 支持的运算：成员(in)、长度(len())、并集(|)、交集(&)、差集(-)、子集(<=)
    • 内置方法:
      • 并集 a_set.union(other_set)，返回两者的交集
      • 交集 a_set.intersection(other_set)，返回两者的交集
      • 差集 a_set.difference(other_set)，返回a_set特有的元素
      • 子集 a_set.issubset(other_set)，判断a_set是否为other_set的子集
      • 添加元素 a_set.add(item)
      • 移除item元素 a_set.remove(item)
      • 随机移除一个元素 a_set.pop()
      • 清空集合 a_set.clear()

  • 字典

    无序结构，key:value键值对组成。访问字典的语法与访问序列的语法十分相似，只是由之前的索引访问改成了key来访问。

    • 注意：字典并不是通过key来进行有序维护的，键的位置是由散列来决定的。
    • 支持的运算：key取值(my_dict[key]、成员运算(针对的是key)、删除(del my_dict[key])
    • 内置方法:
      • 取出所有的key my_dict.keys()
      • 取出所有的values my_dict.values()
      • 键值对以元组的形式返回 my_dict.items()
      • get取值 my_dict.get(k)，没有返回None，也可以设置默认返回值:my_dict.get(k, alt)

        my_dict = {"name": "alan", "age": 18, "power": True}
        print(my_dict.keys())  # dict_keys(['name', 'age', 'power']) 返回的是对象
        print(list(my_dict.keys()))  # ['name', 'age', 'power']
        print(my_dict.values())  # dict_values(['alan', 18, True]) 返回的是对象
        print(my_dict.items())  # dict_items([('name', 'alan'), ('age', 18), ('power', True)]) 返回的是对象
        

输入与输出

Pytho提供input函数用来接受用户输入的内容，返回的是一个字符串，print函数用于输出需要返回的内容。

• 格式化字符串
  1. 使用print函数 print(xxxx, seq="", end="")，seq控制分隔符，默认空格；end控制结尾，默认是换行符
  2. 占位符 "%s"

     name = "alan"
     old = 18
     price = 18.2
     print("%s is %d years old!" % (name, old))  # alan is 18 years old!
     print("the book's price is %08.2f" % price)  # the book's price is 00018.20
     

     
     

  3. format格式化

     name = "alan"old = 18print(f"{name} is {old} years old!")  # alan is 18 years old!print("{} is {} years old!".format(name, old))  # alan is 18 years old!

控制结构(循环与分支)

while语句是非常普遍的循环结构。

while counter <= 10 and not done:
    print("只有两者条件都为True的时候才会执行，但当counter<=10条件不满足的时候，后者条件就无需判断了。")

for循环语句一个应用场景是遍历一个有序集合(list、str、tuple)。另一个应用场景是进行有限次的迭代for item in range(5)

分支：if-elif-else

异常处理

两种报错：语法错误(杜绝发生)、逻辑错误(避免发生)，下面介绍的是针对逻辑错误(异常)的处理方法。

• try:
  

  try下面将可能发生异常的代码块保护起来，用except取捕获异常。

• raise:
  

  主动抛出异常，主动抛出的异常也会导致程序的终止，只是这个异常是我们手动创的。

函数

函数名、参数、函数体、返回值四者构成完整的函数。

def func(num):
    root = num / 2
    for item in range(20):
        root = 1 / 2 * (root + (num / root))
    return root


print(func(9))  # 3.0
print(func(81))  # 9.0



# 装饰器
from functools import wraps


def outfunc(func):
    @warps(func)  # 装饰器修复技术，用来隐瞒help函数查询的结果
    def infunc(*args, **kwargs):
        """代码体，可以效验之类"""
        get_return = func(*args, **kwargs)
        """代码体，可以对返回值进一步处理"""
        return get_return
    return infunc

类

• __xx__魔法方法

  __init__方法

  • 初始化类的方法，除了self参数外，还可以自定义一些参数

  __str__方法

  • 返回一个字符串，当做这个对象的描写，调用方式【print(obj)、obj.str()、str(obj)】

  __add__方法

  • 两个对象遇见+触发的方法

  __doc__方法

  • 描述类信息

  __module__方法 和 __class__方法

  • __module__方法 表示当前操作的对象在哪个模块
  • __class__方法 表示当前操作的对象的类是什么

  __del__方法

  • 当对象在内存中被释放时，自动触发执行。

  __call__方法

  • 对象后面加括号，触发执行

  __dict__方法

  • 获取类的成员，即：静态字段、方法

  __getitem__方法、__setitem__方法、__delitem__方法

  • 用于索引操作，如字典。以上分别表示获取、设置、删除数据。

  __getslice__方法、__setslice__方法、__delslice__方法

  • 三个方法用于分片操作。

  __iter__迭代器

  • 用于迭代器，之所以列表、字典、元组可以进行for循环，是因为类型内部定义了 __iter__方法。

  class Foo(object):
  
      def __init__(self, sq):
          self.sq = sq
  
      def __iter__(self):
          return iter(self.sq)
  
  
  sq = [1, 2, 3]
  obj = Foo(sq)
  
  for item in obj:
      print(item)
  
  """
  1
  2
  3
  """
  

• 属性

  静态属性和实例属性。

  • 静态属性：属于类的，可以通过类直接获取。当抽取的类都具有这个属性，可以直接写在静态属性里。
  • 实例属性：属于对象的，需要先实例化，通过对象obj去调用。每个对象特有的属性。

  • 方法属性化 property

    class Goods(object):
        def __init__(self, discount):
            # 原价
            self.original_price = 100
            # 折扣
            self.discount = discount
    
        @property
        def price(self):
            new_price = self.original_price * self.discount
            return new_price
    
        @price.setter
        def price(self, value):
            print("修改我的时候被调用了")
            self.original_price = value
    
        @price.deleter
        def price(self):
            print("删除我的时候被调用了")
            del self.original_price
    
    
    obj = Goods(0.8)
    print(obj.price)  # 80.0
    obj.price = 70  # 修改我的时候被调用了
    del obj.price  # 删除我的时候被调用了
    

• 方法

  普通方法、类方法和静态方法。

  • 普通方法：由对象调用；至少一个self参数；执行普通方法时，自动将调用该方法的对象赋值给self；
  • 类方法：@classmethod装饰，由类调用； 至少一个cls参数；执行类方法时，自动将调用该方法的类复制给cls；
  • 静态方法：@staticmethod装饰，由类调用；无默认参数；

• 成员

  • 公有成员，在任何地方都能访问。
  • 私有成员，只有在类的内部才能方法。私有成员在命名时，前面加两个下划线；私有并不是访问不到了，可以强制访问【对象._类名__私有字段名】，这里不建议直接访问。

• 继承

  在面向对象编程中，被继承的类称为父类或基类，新的类称为子类或派生类。

  class ClassName(baseclasslist):
  	"""类的帮助信息"""     # 类的文档字符串
  	statement			 # 类体
  
  """
  ClassName：用于指定类名
  baseclasslist：用于指定要继承的基类，可以有多个，类名之间用逗号“,”隔开。如不指定，将使用所有Python对象的根类object
  """类的帮助信息"""：用于指定类的文档字符串，定义该字符串后，在创建类的对象时，输入类名和左侧的括号“(”后，将显示信息
  statement：类体，主要由类变量（或类成员）、方法、属性等定义语句组成。如果定义类时，没有想好类的具体功能时，可以在类体中直接使用Pass语句代替。
  ""
  

  方法重写

  • 基类的成员都会被派生类继承，当基类中的某个方法不完全适用于派生类时，就需要在派生类中重写父类的这个方法，这和Java语言中直接使用pass语句代替。

  子类调用父类的__init__方法

  • 在子类中初始化时，不会主动调用基类的__init__()方法。所以在子类的init方法中通常会写super().__init__() # 调用基类的__init__()方法

  class Fruit:  # 定义基类
      def __init__(self, color="绿色"):
          Fruit.color = color  # 定义类属性
  
      def harvest(self):
          print("水果原来是：" + Fruit.color + "的")  # 输出类属性color
  
  
  class Apple(Fruit):  # 定义子类
      def __init__(self):
          print("我是苹果")
          super().__init__()  # 调用基类的__init__()方法
  
  
  apple = Apple()  # 我是苹果
  apple.harvest()  # 水果原来是：绿色的