【CS61A】学习笔记

本学习笔记为作者在学习CS61A（2020Fall）所记，只记录了一些容易忘记的重点内容（从第8周开始），建议读者自行前往官方网站学习。
作者学习时所用到的所有开源资料与作者所编写代码均开源在github上

参考资料

CS 61A Fall 2020

Week 8

8.1 Inheritance

继承的比较简单的概念，不再赘述。

8.2 Representation

8.2.1 String Represention

Python中规定，每一个对象都需要有两种字符串表示形式：

• 一种是人类可解释的字符串（可以被人类看懂的），使用字符串构造函数str
• 一种是Python可解释的字符串（也就是符合Python语法的表达式），使用函数repr
  对于函数repr而言，repr(object) = string，作用在一个对象上可以产生一个Python可解释的表达式字符串；
  对于函数str而言，作用在一个对象上可以产生一个人类可解释性的字符串，例如：

>>> from datetime import date
>>> tues = date(2011, 9, 12)
>>> repr(tues)
'datetime.date(2011, 9, 12)'
>>> tues
datetime.date(2011, 9, 12)
>>> str(tues)
'2011-09-12'
>>> print(tues)
2011-09-12
1
2
3
4
5
6
7
8
9
10

可以看到，str函数产生的是人类可以直接看懂的内容，repr函数产生的是Python可以直接看懂的内容（Python代码）。

8.2.2 Polymorphic Function

str和repr函数就是两个多态函数，无论传入什么对象，他们都能够返回一个你想要的结果。
不禁会好奇他们是怎么实现的，实际上，str和repr函数只是调用了所传入对象的相应类的内置函数__str__和__repr__。
其中，python规定，repr会忽略所传入的对象，关注的是该对象对应的类的内置函数，实现方法类似如下：

def repr(x):
	return type(x).__repr__(x)
1
2

str函数的实现方法是，若所传入对象的类中没有__str__方法，会直接返回__repr__方法，实现如下：

def str(x):
	t = type(x)
	if hasattr(t, '__str__'):
		return t.__str__(x)
	return t.__repr__(x)
1
2
3
4
5

但是如果两个方法都没有的话，比如下面这个代码：

class CMH:
    def __init__(self, name, age):
        self.name = name 
        self.age = age 

cmh = CMH('cmh', 21)

1
2
3
4
5
6
7

会产生以下效果：

>>>print(repr(cmh))
<__main__.CMH object at 0x000002210A0AE5B0>
>>>print(str(cmh))
<__main__.CMH object at 0x000002210A0AE5B0>
1
2
3
4

同时，只存在__str__方法的话，会是这样

class CMH:
	def __str__(self):
        return 'CMH love ZY'
    def __init__(self, name, age):
        self.name = name 
        self.age = age 

cmh = CMH('cmh', 21)
>>>print(repr(cmh))
<__main__.CMH object at 0x000002210A0AE5B0>
>>>print(str(cmh))
CMH love ZY
1
2
3
4
5
6
7
8
9
10
11
12

8.2.3 Special Method Name

python提供了一系列的内置函数，方便类似于重载加法运算符(__add__)、强制类型转换(__float__)等操作，如下列代码：

class Ratio: #分数类
    def __init__(self, n, d):
        self.numer = n #分子 
        self.denom = d #分母
    
    def __repr__(self):
        return 'Ratio({0}, {1})'.format(self.numer, self.denom)
    
    def __str__(self):
        return '{0}/{1}'.format(self.numer, self.denom)
    
    def __add__(self, other):
        if isinstance(other, int):
            n = self.numer + self.denom * other 
            d = self.denom 
        elif isinstance(other, Ratio):
            n = self.numer * other.denom + self.denom * other.numer 
            d = self.denom * other.denom 
        elif isinstance(other, float):
            return float(self) + other 
        g = gcd(n, d)
        return Ratio(n // g, d // g)
    
    __radd__ = __add__

    def __float__(self):
        return self.numer / self.denom

def gcd(a, b):
    while a != b:
        a, b = min(a, b), abs(a - b)
    return a
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

>>> Ratio(1, 2) + Ratio(1, 3)
Ratio(5, 6)
>>> Ratio(1, 2) + 1
Ratio(3, 2)
>>> 1 + Ratio(1, 2)
Ratio(3, 2)
>>> Ratio(1, 2) + 0.5
1.0
>>> 0.5 + Ratio(1, 2)
1.0
1
2
3
4
5
6
7
8
9
10

8.3 Composition

这一节主要讲了用python面向对象的方法实现链表还有之前讲过的树，比较简单就不做笔记了

Lab 07: Object-Oriented Programming, Iterators

Finished! Solution

Disc 07: Object-Oriented Programming

好像比较简单，鸽了鸽了。

HW 05: Object-Oriented Programming, Linked Lists, Trees

Finished! Solution

Ants

Finished! Solution

Week 9

Efficiency (optional)

讲了如何提升代码效率

Decomposition

使用模块化编程，举了一个餐厅的例子。

Data Examples

一些对象、迭代器、链表的例子。

Lab 08: Linked Lists, Mutable Trees

这个lab中的第5个问题，给出一个链表，判断该链表是否存在环。
不难想出一个空间复杂度为线性的解法，该问题的挑战版本要求一个空间复杂度为常数的解法。
于是我们不可以标记每个点是否被经过，我们可以使用两个指针，一个步长为1，一个步长为2，步长为2的指针初始化位置在步长为1的指针之前，若链表中存在环，那么步长为2的指针最终会与步长为1的指针相遇。
Finished! Solution

Disc 08: Linked Lists, Trees, Representation

Finished! Solution

Lab 09: Midterm Review

Finished! Solution

Week 11

Scheme

这一节主要讲了Scheme的语法，没啥太特殊的内容。包括：表达式如何书写（括号表达式），if-else语句如何书写，多条件语句如何书写（cond），链表的语法结构和应用等等。

Exceptions

Calculator

Lab 10: Scheme

Finished! Solution

HW 06: Scheme

Finished! Solution

Disc 10: Scheme, Scheme Lists

HW 07: Scheme Lists

后面的懒得写了…难度不大但是Scheme代码量比较大需要慢慢看。