CS基础课程

上篇动态数组最大的软肋是：在中间插入或删除一个元素，要搬移其后所有的元素，代价 O(n)。链表（linked list）号称能绕开这个软肋——它不靠"连续内存 + 下标"组织数据，而是让每个元素自己记住"下一个是谁"。 但"链表删除是 O(1)"这句话，九成初学者都记漏了前提。这篇就把单链表、双链表、以及那个能把一堆边界特判消灭干净的**哨兵节点（sentinel）**讲透，顺便留三道面试开胃题。 一、单链表：每个节点只认识"下一个"单链表由一串 节点（Node） 串成。每个节点干两件事：存自己的数据 val，再存一个指向下一个节点的引用 next。最后一个节点的 next 是 null，表示"到头了"。一个独立的 head 引用指向第一个节点，靠它才能摸到整条链。 1 val next 2 val next 3 val next null head 本质一句话：单链表用&...

你每天写 ArrayList、vector、list.append()，从没操心过"容量"——它好像永远装得下。但每次"满了"，它其实偷偷把整片数据搬了一次家：分配更大的内存、把旧元素逐个复制过去、再扔掉旧的。这一篇把这件"看不见的搬家"讲透，并回答一个反直觉的问题：为什么扩容是 O(n)，尾部追加却是 O(1)？ 答案叫均摊分析（amortized analysis）。 一、静态数组：快，但僵数组是最原始的数据结构：N 个同类型元素连续摆在内存里，靠下标直接寻址。 优点：随机访问 a[i] 是 O(1)——CPU 算一下 基地址 + i × 元素大小 就能取到，不依赖数组长度。 死穴：容量在创建时就钉死了。想在第 0 位插一个？后面所有元素都得往后挪，O(n)。更糟的是，满了就彻底塞不下了。 数组这层"裸"结构，正是上一篇说的"只承诺怎么存、不约束怎么用"。动态数组要解决的，就是给它套一层自动扩容的抽象。 二、动态数组：在数组上套一层"自动扩容"动态数...

很多人学完数组、链表、栈、队列，仍有一个挥之不去的困惑：这些"数据结构"到底有没有区别？为什么教科书总说 Stack 是 ADT 而不是数据结构？ 如果你也含糊，这篇就是为你写的——我们不背定义，先把这层窗户纸捅破。 缘起很朴素：数组是最原始、最"诚实"的数据结构，它把 N 个同类型元素连续摆在内存里，你用下标直接取。但它太"裸"了——它既不阻止你越界访问，也不阻止你在第 0 位插一个元素（后面所有元素都得搬）。于是自然会想：能不能定义一种"只许从一端进出"的抽象，把数组这种杂乱用法管起来？ 这正是抽象数据类型（ADT）的动机：从"怎么存"里提炼出"能做什么"。 一、先别急着写代码：什么是抽象数据类型（ADT）ADT = 一组数据值 + 一组在这些值上可做的操作（契约），它只规定"你能对我做什么"，不规定内部怎么存。 最熟悉的例子其实天天在用：整数就是 ADT。你知道 +、-、* 怎么用，但从不在乎 CPU 里是用补码还是浮点表示...

前七篇都在 Python 里打转。最后一篇，CS61A 故意把你拽进另一种语言——Scheme（Lisp 方言），再让你亲手写一个"能运行 Scheme 的解释器"。为什么？因为跳出一种语言，你才真正看清"编程"这件事的边界：原来函数可以没有名字、原来递归可以不用占栈、原来"我要什么"和"我怎么做"可以彻底分开。这一篇是 CS61A 的高潮，也是把全课程串起来的那根线。 一、Scheme 基础：括号即一切是什么：Scheme 里一切都是 S-表达式（S-expression）——要么是一个原子（数字、符号），要么是括号包裹的组合 (操作符 操作数 ...)。所有语法都是这一种形式的变体。 1234(define (square x) (* x x)) ; 定义过程 square(square 5) ; => 25(define x 10)(if (> x 0) "正" "负") ...

回到篇三那个优雅的 fib：代码和数学定义一字不差，美不美？美。快不快？一点都不快。当 n 大到 40，它能卡到让你怀疑人生。为什么"正确的代码"会这么慢？又该怎么救？本篇先给你一把尺子（大 O）量效率，再用"迭代"和"记忆化"两把刀修掉 fib，最后引出 Python 里最被低估的利器——生成器，它让"无限序列"成为可能。 一、增长阶（大 O）：规模翻倍时耗时怎么变是什么：衡量算法效率，不看"跑了 3 毫秒还是 5 毫秒"（那取决于机器和常数），而看输入规模 n 增长时，步数怎么随 n 变化。忽略常数倍，只看"增长趋势"，就是大 O 记号。 阶 含义 例子 O(1) 常数，与 n 无关 列表按下标访问 O(n) 线性，随 n 正比增长 遍历一遍 O(n²) 平方，双层嵌套 冒泡排序 O(2ⁿ) 指数，n 每+1 量翻倍 朴素斐波那契 坑：大 O 丢掉了常数，所以"O(n) 一定比 O(n²) 快"只在 n 足...

前面我们一直把"数据"和"操作数据的函数"分开写：先定义 make_rat，再写 add_rat。但真实世界里，一个"学生"既有一堆属性（姓名、成绩），又有一堆行为（选课、算 GPA）。把它们拆在两处，代码会越来越散、越来越难找。面向对象（OOP） 的解法很直白：把"数据"和"操作它的方法"打包进同一个类（class）。本篇从 self 这个最小齿轮讲起，一直讲到 Python 怎么决定"调的是哪个方法"（MRO）。 一、类与实例：蓝图与成品是什么： 类（class） 是对象的"蓝图"，描述一类事物长什么样、能干什么； 实例（instance） 是按蓝图造出的具体对象； self 是约定俗成的第一个参数，代表"当前这个实例自己"。 12345678class Dog: def __init__(self, name): # 构造器，创建时自动调用 self.name = name ...

前面几篇，我刻意没让你碰"改掉一个已有的值"。因为**可变性（mutability）**是 CS61A 乃至整个编程里"便利"和"灾难"同一个源头。它能让代码更短更自然，也能让 bug 在最意想不到的地方炸——而且炸得毫无痕迹。本篇先把"可变 vs 不可变"这条生死线划清，再看别名、容器，最后动手实现 CS61A 两尊经典递归结构：Link 与 Tree。 一、可变 vs 不可变：一条分界生死线是什么： 不可变（immutable）：创建后内容不能改。int、float、str、tuple、frozenset 都在此列。你做的任何"修改"其实是生成新对象。 可变（mutable）：创建后内部可改。list、dict、set、以及你自己写的类实例都在此列。改的是"同一个对象"。 12345s = "abc"# s[0] = "x" # 报错：str 不可变lst = [1, 2, 3]lst[0] = ...

前几篇我们玩的"值"都是数字、字符串这种原子。可真实程序里，数据从来不是孤立的——一个学生有姓名、年龄、成绩；一个有理数有分子、分母。当数据变复杂，"怎么存"和"怎么用"就会纠缠在一起，改一处崩一片。CS61A 给出的解药叫数据抽象（data abstraction）：用一层"接口"把两者隔开。本篇就用"有理数"这个小例子，把这个影响你一辈子的思想钉死。 一、数据抽象：构造函数 + 选择器是什么：CS61A 对"数据"有一个极简也极深刻的定义——数据 = 构造函数（constructor） + 选择器（selector）。 构造函数：把零散的部件"打包"成一个整体（如 make_rat(n, d)）； 选择器：从整体里"取出"某个部件（如 numer(r) 取分子、denom(r) 取分母）。 只要这两者行为一致，内部到底用元组、字典还是两个独立变量存，根本不重要。这层隔离叫抽象壁垒（abstractio...

第一次写递归的人，脑子里通常有个挥之不去的念头："我得把每一次调用都想象清楚，才算写对。"结果越想越乱，最后放弃、改写成循环。但递归真正的法门恰恰相反——你不必追踪每一次调用的细节，你只需要相信：子问题已经被正确地解决了。这种"信仰之跃（leap of faith）"是 CS61A 教给你最重要的思维转换之一。本篇从最干净的线性递归，一直讲到会"指数爆炸"的树形递归。 一、递归是什么：函数自己调用自己是什么：递归（recursion） = 一个函数在自己的定义里调用自己。一个"正确且能停"的递归必须满足三条，CS61A 叫它"递归三定律"： 有一个或多个基例（base case）：不再自我调用，直接返回；这是递归的"刹车"。 每次递归都在向基例化简：问题规模严格变小，绝不允许越调越大。 递归调用解决子问题，再把子问题的结果组合成总结果。 缺了第 1 条 → 无限递归，栈炸；缺了第 2 条 → 永远到不了基例，同样栈炸。两条是递归的命门。 二、线...

学到这你大概已经能写"命令式"程序了：定义几个函数、调来调去、用 if/for 控制流程。但 CS61A 真正的第一个分水岭在这一篇——当你意识到"函数"可以像数字一样被传来传去、被装进盒子、被工厂批量生产，"编程"这件事的维度就升了一级。这种能"吃函数、拉函数"的函数，叫高阶函数（higher-order function）。它是后面装饰器、回调、甚至整个函数式编程的地基。 一、什么是"一等公民"：函数不是语法糖，是值是什么：在 Python 里，函数和数字、字符串一样，是货真价实的对象（object）。这意味着函数可以：被赋值给变量、当参数传给别的函、作为返回值、存进容器。具备这种待遇的，叫一等公民（first-class citizen）。 1234567def square(x): return x * xf = square # 函数赋值给变量（没加括号，不是调用！）print(f(4)) # 16print(type(f)...

很多人学编程是从"记语法"开始的：先背 if 怎么写、for 怎么写，再背一堆库函数。CS61A 偏不这么干。它开篇就抛出一个看似哲学的问题：计算机到底是怎么把"名字"和"值"对应起来的？把这个想明白，后面高阶函数、递归、面向对象都不是新东西，只是同一套"名字—值"规则的变体。这一篇，我们先把最底层的"调用"和"环境"拆开看透。 一、调用表达式：你以为的"先算哪个"其实是铁律写 square(3 + 4) 时，大脑下意识就知道要先算 3+4 再平方。但"下意识"在编程里不够——它是一条求值规则，而且顺序不能乱。 是什么：Python 里 操作符(操作数, 操作数, ...) 这种结构叫调用表达式（call expression）。求值分两步，顺序很关键： 先按从左到右的顺序，把每个操作数（operand）求值成"值"； 再把操作符（也就是那个函数对象）作用在已经求好值的操作数上。 12345de...