CS-Fundamentals

数组管顺序，树管层次，哈希管查找——可现实里的关系常常既不是一条线、也不是一棵树：地铁线网、朋友关系、任务依赖、互联网路由，全都是"点连着点"的网络。这种结构叫图（Graph）。本篇我们解决三件事：图怎么存进计算机、怎么把整张图"走一遍"、以及怎么在带权图里找到两点间最短的路。 一、是什么：顶点、边、权一句话：图 = 顶点集合 V + 边集合 E；边可以有向/无向，可以带**权重（权）**表示距离/代价/时间。 无向图：边双向（朋友关系）。 有向图：边单向（关注关系、依赖）。 带权图：边上标数字（地图里程）。 二、怎么存：邻接表 vs 邻接矩阵这是图论里第一个关键取舍。 维度 邻接表（adjacency list） 邻接矩阵（adjacency matrix） 存储 O(V+E) O(V²) 遍历某点邻居 O(degree) 很快 O(V) 要扫整行 判断两点是否相邻 O(degree) O(1) 适合 稀疏图（大多数真实网络） 稠密图、需要频繁查边 ...

队列我们都熟：先进先出，队头永远是来得最早的那一个。可现实往往不按先来后到——急诊室里重伤员优先，操作系统里短作业优先，Dijkstra 最短路里"当前距离最小"的节点优先。我们需要一种"按优先级出队，而不是按到达顺序"的结构，这就是优先队列（Priority Queue）；而它最高效的数组实现，叫二叉堆（binary heap）。 本篇讲清三件事：堆长什么样、插入/取最小怎么 O(log n) 完成、以及它和排序、图算法的关系。 一、是什么：堆不是"排好序的数组"一句话：二叉堆是一棵"完全二叉树"，满足堆序性质（heap property）——每个节点的值都不大于（最小堆）或不小于（最大堆）它的孩子。 完全二叉树：除最后一层外全满，最后一层从左往右填。这个形状让它能紧凑地存进数组，不需要指针。 堆序性质：最小堆里，父 ≤ 子，所以全局最小值一定在堆顶（下标 0）。最大堆反过来。 最小堆（树视图 = 数组视图） 2 5 7 9 11 ...

你有没有遇到过这种尴尬：数组按下标访问是 O(1)，可它要求"下标必须是整数"；而真实世界里的键往往是字符串（"apple"）、对象（一个 User）、甚至一段二进制。我们想问的是——能不能让任意类型的键，也拥有接近 O(1) 的查找速度？ 哈希表（Hash Table，也叫散列表）就是这个问题的答案，也是 Java HashMap、Python dict、C++ unordered_map 背后的真正引擎。它把"键"压缩成一个数组下标，于是插入、查找、删除都甩掉了"逐个比较"的包袱。但它不是免费的午餐：冲突（collision） 一定会发生，怎么设计散列函数、怎么消解冲突、什么时候扩容，正是本篇要讲清楚的三件事。 一、是什么：哈希表的三件套一句话：哈希表 = 一个数组（桶 buckets）+ 一个散列函数（hash function）+ 一套冲突解决机制。 散列函数 h(key) 把任意键映射到一个整数下标 0..m-1，我们就去数组的那个位置存取。理想情况下每次都 O(1)。 核心约...

你有没有想过一个尴尬的局面：有序数组查找快（二分 O(log n)），可一旦插入新元素，得把后面一半整体后挪，O(n)；链表插入是 O(1)，可查找又退化成 O(n)。有没有一种结构，能既要查找快、又要插入/删除也快？ 答案就是本篇的主角——树，更准确地说是**二叉搜索树（BST）**以及它的「打补丁」版本：平衡树（AVL / 红黑树）和多路平衡树（B 树）。它们把「有序」从「数组的连续内存」里解放出来，变成「节点之间的偏序关系」，于是插入、删除不再需要搬移整段数据。我们先从最朴素的 BST 讲起，再看它哪里会翻车，以及三个补丁分别怎么修。 一、二叉搜索树（BST）：定义与不变式BST = 一棵二叉树，且满足「左小右大」的递归不变式： 对树上任意一个节点 x：其左子树中所有 key 都 < x.key，其右子树中所有 key 都 > x.key。 注意是「严格」的偏序，通常不允许重复 key（要支持重复就改成「≤ 放左 / ≥ 放右」，本篇按不允许重复讲，逻辑最干净）。这条不变式是 BST 一切能力的根基——因为它意味着中...

你有没有想过，为什么编辑器里按 Ctrl+Z 能一步步撤销，而打印机却老老实实按提交顺序一张张出？这两件事看似无关，底层却是同一对"基础设施"的两种相反用法：一个只许从同一端进出，一个必须从两端分工。 这就是本篇的主角——栈（Stack） 和 队列（Queue）。它们都属于上篇讲过的 ADT：只规定"能做什么"，不规定"怎么存"。但正是这两种最朴素的秩序观，撑起了从函数调用、表达式求值到任务调度、消息队列的半壁江山。我们先把"世界观"立住，再动手实现，最后看两个几乎人人都踩过的坑。 一、栈（Stack）：后进先出（LIFO）的世界观栈 = 只允许在同一端（栈顶）进行插入和删除的 ADT，语义是 LIFO（Last-In-First-Out，后进先出）。 想象一摞盘子：你只能在最上面放新盘子（push），也只从最上面拿走（pop），永远碰不到底下那个。最后放上去的，必然第一个被取走——这就是"后进先出"。 栈暴露给客户的契约只有四个操作： 操作 含义 异常 p...

上篇动态数组最大的软肋是：在中间插入或删除一个元素，要搬移其后所有的元素，代价 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) "正" "负") ...

C++核心语法整理C与C++类与对象C++输入输出流友元与运算符重载关联式容器继承多态模板移动语义与资源管理C与C++ C++程序介绍 g++编译器安装 sudo apt install g++ 源文件名称 .cc .cpp C++程序模板设置 /home/st/.vim/plugged/prepare-code/snippet hello world程序分析 #include C++标准库中头文件 没有.h cin 标准输入流 默认输入设备 从键盘接收数据 cout 标准输出流 默认输出设备 屏幕 int main(int argc , char *argv[]){} 返回值为int argc 命令行参数的个数 argv 具体的命令行参数 vim中启动鼠标 编辑.vimrc文件 子主题 命名空间 命名空间是什么, 有什么作用? C++中的一种避免名字冲突的机制 主要作用区分同名实体 实体 变量、常量、函数、结构体、类、对象...

回到篇三那个优雅的 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)...

一、计算思维的本质与形式化表达1.1 信息处理的抽象模型与问题抽象计算机科学核心是信息符号操纵体系，从图灵机到现代系统，均为 "输入 - 处理 - 输出" 的具象实现。计算思维通过建立现实与符号系统映射实现问题可计算，这种抽象过程包含三个关键步骤：问题特征提取、符号系统选择与映射规则定义。这种抽象能力，正是计算机解决问题的前提，体现了从具体到抽象的认知跃迁，也印证了问题解决需建立与抽象模型间映射关系的理论。 1.2 指令序列的执行逻辑与计算思维维度计算过程的本质是按确定规则执行指令序列，这种确定性是可计算性的基础。指令通过顺序、分支和循环三种基本结构，构成复杂计算的控制流，体现了计算思维将问题拆解为可计算步骤的核心逻辑。 指令执行模型展现过程分解思维：复杂计算可拆分为有序的基本操作，执行路径明确，结果可预测。这种分解基于对问题逻辑的深入理解，需借助可计算性理论判断问题是否可解，并设计有限步骤的算法，确保在合理时间复杂度内得出确定解。 二、编程的思维框架2.1 程序结构的模块化组织与抽象层次驾驭C 语言以函数实现模块化，将复杂程序分解为相对独立的功能模块，通过接...

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

导言 Linux 操作系统凭借其开源特性与强大性能，在计算机领域占据重要地位。Linux 0.11 作为 Linux 发展早期的经典版本，其源代码蕴含着操作系统核心功能的基础设计思想。 详情见品读 Linux 0.11 核心代码。 一、输入阶段：命令的获取与缓冲 1.1 键盘输入处理机制当用户在键盘上按下一个按键时，硬件会触发 0x21 号中断，进而调用keyboard_interrupt中断处理函数。此时键盘控制器发送的扫描码会经历三重处理： 扫描码转换：通过键盘映射表转换为对应的 ASCII 码 队列存储：字符被存入tty_read_q原始输入队列 终端处理：copy_to_cooked函数对字符进行规范处理，如退格删除、换行转换等，处理后的字符存入secondary规范队列 这两个关键队列的分工如下： 1tty_read_q (原始队列) ← 扫描码 → ASCII转换 → secondary (规范队列) 1.2 命令读取与阻塞控制shell 通过read系统调用从secondary队列获取字符，这一过程包含精巧的阻塞机制： 当secondary队列...

导言 在操作系统的演进历程中，Linux 0.11 版本作为开源操作系统发展的重要里程碑，其系统架构设计与核心功能实现对现代操作系统具有深远的研究价值。 详情见品读 Linux 0.11 核心代码。 一、核心模块解析 1.1 物理内存管理的数据结构Linux 0.11 采用mem_map数组作为物理内存管理的核心数据结构，该数组定义于mm/memory.c文件中： 123456struct page { unsigned long flags; struct page *next; struct page *prev;};struct page mem_map[MEM_MAP_SIZE]; 每个数组元素对应一个物理页面（4KB），通过flags字段记录页面状态（空闲、已分配、锁定等），next和prev指针构成双向链表，用于空闲页面的组织与管理。这种设计实现了对物理内存的精细化管理，为内存分配与回收提供了数据基础。 1.2 内存分配算法的底层实现内存分配的核心函数get_free_page实现于mm/memory.c，其算法流程如下： ...

导言 在操作系统的底层架构体系中，新进程的创建过程是一个高度精密且系统化的工程，其每一个环节均凝聚着计算机科学领域的理论精华与工程实践智慧。以经典 UNIX 系统的实现机制为研究对象，深入剖析进程创建机制，不仅有助于理解其底层运行原理，更能揭示操作系统设计者在性能优化、安全防护与资源管理之间的精妙权衡策略。 详情见品读 Linux 0.11 核心代码。 一、核心代码与整体流程：系统启动的 "生命线" 1.1 main 函数关键代码解析在系统启动序列中，main函数内的move_to_user_mode、fork、init及pause等核心代码片段，构成了新进程创建的核心逻辑链路。其中，fork系统调用以简洁的单语句形式实现进程创建功能，其底层执行过程涉及对进程上下文的深度克隆操作。该操作通过系统级资源复制机制，实现子进程对父进程绝大部分运行状态的继承，进而完成进程地址空间的快速实例化。而move_to_user_mode函数则承担着进程特权级转换的关键职责，通过严格的权限控制机制，实现进程从内核态到用户态的安全过渡，有效防止用户进程对内核资源的非法访问行...

导言 在计算机系统启动过程中，操作系统的初始化工作是一项高度复杂且精密的工程，其每个环节均对系统稳定运行起着决定性作用。对于经典的 Linux 0.11 版本而言，从内存管理机制的构建到各类设备驱动的初始化配置，这些底层操作共同构成了操作系统稳定运行的核心基础。各初始化阶段虽在功能上具有独立性，但在逻辑与数据交互层面紧密耦合，协同构建起完整的操作系统底层架构。 详情见品读 Linux 0.11 核心代码。 一、main 函数：初始化的核心枢纽 1.1 参数计算与初始化链构建操作系统启动过程中，main函数通过计算ROOT_DEV、drive_info、memory_end等核心参数，完成系统资源配置的基础工作。这些参数的准确获取与计算，为后续系统组件初始化提供必要的前提条件。基于上述参数，系统依次调用mem_init、trap_init等九个关键初始化函数，构建起完整的初始化调用链。该调用链以层次化的方式完成系统资源的初始化工作，确保各子系统间的依赖关系得到妥善处理，为操作系统的稳定运行奠定基础。 1.2 特权模式切换与系统状态初始化完成核心组件初始化后，系统通过执行sti...

导言 在操作系统的演进历程中，Linux 0.11作为经典版本，其启动过程蕴含着深刻的底层设计哲学。从计算机通电到内核正式接管系统，这一阶段涉及硬件初始化、实模式与保护模式切换、内存重定位等核心环节，每一步都堪称现代操作系统启动流程的缩影。 详情见品读 Linux 0.11 核心代码。 一、BIOS 加载阶段：启动流程的初始阶段 1.1 启动区加载：系统引导的关键区域计算机启动时，BIOS 首先读取硬盘主引导记录（MBR），即硬盘 0 盘 0 道 1 扇区。该扇区大小为 512 字节，包含启动代码及分区表信息。启动代码被加载至内存 0x7c00 地址，扇区末尾的 0x55AA 签名作为有效性验证标识。此验证机制确保 BIOS 仅执行合法的启动代码，从而保障系统启动的安全性与可靠性。 1.2 启动代码执行：系统初始化的开端位于 0x7c00 的 bootsect.s 代码作为启动流程的初始执行模块，承担系统启动初期的环境准备工作。该模块主要负责基本硬件检测、内存环境初始化等基础功能，为后续系统启动奠定基础。 二、内存数据搬运：系统资源的迁移过程 2.1 第一次搬运：启动代码重...