第11章 程序设计基础¶
本页要点：语言与实现方式分开；编译/链接职责分开；栈堆与对象生命周期分开；面向对象规则注明语言；异常路径也要释放资源。
11.1 从源程序到执行¶
编译是把一种表示翻译为目标表示，解释是运行时执行相应表示的语义。C常先编译链接为本机程序，Java通常先编译为字节码、由JVM（Java虚拟机）解释并对热点JIT（即时编译）；Python实现也可先生成字节码，JavaScript引擎常有JIT。因此不能把语言永久分为“逐行执行”“一定无编译”两类，性能还取决于实现与负载。
编译典型六步为词法→语法→语义→中间代码→优化→目标代码。以x=2+3;为例，词法识别标识符、等号、数字和分号，语法组织赋值树，语义检查x的声明与类型，中间表示表达加法和赋值，优化可折叠2+3为5，目标生成选择机器指令与寄存器；符号表和错误处理贯穿过程。是否接受某种语法、能否编译期报错取决于语言规范，不是所有错误都到运行时才发现。
汇编器翻译汇编为目标机器码，链接器解析多个目标文件与库的符号、重定位并组成可装入程序；编译器不是代替CPU运行每条加法。静态链接通常在构建的链接阶段合入所需库代码，动态链接在装载/运行时解析共享库，具体也有延迟绑定；不是把“静态链接”精确等同词法分析等编译阶段。
托管环境C程序通常从main进入用户定义流程，但运行库初始化在此之前，程序也可由exit、异常信号等途径终止；自由运行环境的入口依实现。sizeof(char*)取指针类型大小而非字符串长度，题干char *ss="0123456789"未给数据模型便无法断言4；声明字符数组char ss[]="0123456789"才通常占11个char（含结束符）。同样源代码在32/64位平台可能不同。
11.2 内存、对象与GC¶
调用栈常保存调用帧、局部状态和返回位置，递归每层需状态，因此过深可栈溢出；堆保存动态分配对象，由语言/运行时或程序管理。全局/静态对象通常拥有静态存储期，但物理放置与优化由实现决定；Java局部引用与其所引用对象不在概念上同一个位置，不能说“所有局部变量的内容一定只在栈上”。
GC（Garbage Collection，垃圾回收）判断的是对象是否仍被需要的引用链可达，不是看“程序员觉得用完”。例如全局缓存仍保存一个不再使用的大数组引用，数组仍可达，GC也不能自动消除这种逻辑泄漏。
| 算法 | 怎样回收 | 例子和限制 |
|---|---|---|
| 标记—清除 | 从根标出可达对象，清除其余 | A、B互相引用但无根可达，仍可回收；会留下分散空洞 |
| 复制 | 把存活对象搬到目标空间，整体回收来源区 | 经典等大半区算法需两半空间，但不是所有复制收集器永远浪费一半整个堆 |
| 标记—整理 | 标记后移动存活对象，压紧空间 | 减少碎片，需要更新引用并付移动成本 |
| 引用计数 | 引用增减时更新计数，归零回收 | A↔B会使单纯引用计数无法回收无根循环，需另有循环检测 |
分代收集利用许多对象寿命短的经验，可使新生代频繁回收、老年代采用适合策略，但不是所有GC都固定“两代+固定算法”；CPython常见引用计数配循环收集，也不能泛化到所有Python实现。GC只管理相应内存，不保证文件、锁、网络连接及时释放，仍须结构化资源管理。
11.3 面向对象与参数传递¶
对象具有标识、状态（属性）和行为（方法），类描述一类对象的结构与行为。封装隐藏实现并保护不变量，例如余额只由受约束方法修改；继承表达子类可替换父类的is-a关系，不是单纯复制代码；多态使同一接口调用随实际对象实现不同，如Shape引用指向Circle时执行Circle.draw。
Java中重载是在同名方法的不同参数列表中按编译期规则选签名，不能只靠返回类型区分；重写是子类提供父类可重写实例方法的实现，运行时动态分派。静态方法隐藏、private/final限制以及C++非virtual行为不能套普通动态重写口诀；C++虚函数表是常见实现，不是所有语言规范要求的唯一结构。
虚函数表（vtable）可用一个教学模型理解：基类Shape的虚函数draw占表中某槽，Circle对象的隐藏表指针指向Circle对应虚表，该槽保存Circle.draw的入口；通过Shape指针调用虚draw时，先按对象找到表，再取该槽的实现，因此执行Circle.draw。调用非虚函数或编译器能证明具体类型时，可能直接调用，无需实际逐次查表；多重继承还可能用多个表指针或调整this。这个模型解释动态绑定怎样实现，不规定表指针必在对象第几个字节，也不承诺所有语言采用虚表。[手册§11.3机制教学例；另实际读取Itanium C++ ABI §2.5.1—2.5.2正文，明确虚表用于分派、对象虚表指针、函数入口及this调整。该ABI支持本模型，不将其地址点、槽顺序或平台布局推广为所有C++实现规则]
抽象类可有状态、构造器与已实现方法；Java类只继承一个直接父类，可实现多个接口。现代Java接口可有默认、静态及private方法，接口字段为常量，不是手册“接口只能声明行为、不允许实现”的绝对版本。C++等语言继承模型不同，需要注明语言。
Java参数全部按值传递：基本类型复制数值，对象变量复制引用值。例函数把传入引用所指对象的字段改为2，调用者可观察到同对象改变；但函数把形参重新指向新对象，只改变形参副本，调用者引用不变。C也按值传参，传指针可间接改对象；C++有引用参数，不能把Java规则称所有语言的“引用传递”。
11.4 异常和资源释放¶
try内抛异常后按类型寻找可匹配catch；正常或异常离开时通常执行finally。例如try中准备return 1，finally执行日志后才返回；若finally自己return 2或抛新异常，会覆盖原返回/异常，应避免。若执行流从未离开try（如无限循环）或进程被终止，不能承诺finally一定执行；它不是断电恢复机制。
Java受检异常须捕获或在签名声明throws；RuntimeException及其子类、Error及其子类为非受检，编译器不强制同样检查。IOException常需显式处理，NullPointerException属于运行时异常；抛异常不等于必须把所有异常都吞进一个空catch。
C++ RAII（资源获取即初始化）利用对象生命周期在离开作用域、正常栈展开时析构释放资源；Java try-with-resources关闭AutoCloseable资源，Go defer登记函数返回前执行清理。三者语法不同，但都让清理与作用域/流程绑定；异常终止或直接杀进程等仍有边界。数据库连接用完应按约定关闭/归还池，不等待GC。
11.5 质量、并发与小型语义例¶
命名和接口文档应表达职责，单一职责与较低圈复杂度有助理解；“圈复杂度≤10”只能作为特定实践建议，未给适用规范前不能当所有程序强制标准。防御式编程在外部边界校验类型、范围和长度，失败要明确，不能用大量异常替代正常分支。
竞态指结果取决于未协调执行先后。例如两个线程都读计数0，各写1会丢一次增加；原子自增或适当锁可保护，锁粒度影响并发与成本。不可变对象自身状态不变有助共享，但持有可变引用或发布方式不安全仍需判断；死锁、同步主讲见操作系统。
常见数据结构的语言实现对比。抽象数据类型说明“能做什么”，语言实现说明“用什么布局和操作做到”，复杂度必须连同数据规模、是否需要排序、内存模型与最坏/平均情形一起看。下表按明确语言版本/实现举例，不把某种实现推广为所有语言的保证。
| 抽象结构 | C（ISO C对象/数组语义） | Java SE 25常用实现 | Python 3.14常用实现 | 主要差别与边界 |
|---|---|---|---|---|
| 动态数组 | int a[4]是固定长度数组；需扩容时通常另申请更大连续空间、复制后释放旧区，容量策略由程序实现 |
ArrayList<E>以可增长数组保存引用；按索引访问O(1)，尾部追加摊还O(1)，中间插入/删除需移动后续元素 |
list是可增长序列，CPython以连续指针数组实现；索引O(1)，尾部追加摊还O(1)，头部插入需移动元素 |
“数组连续、随机访问快”描述索引访问，不表示任意位置插入也是O(1)；Java/Python的扩容因子不是语言API保证 |
| 链表 | 标准库没有内建通用链表；可用struct Node { int value; struct Node *next; }自行管理节点 |
LinkedList<E>是双向链表，按索引访问需沿节点遍历；已持有节点位置时局部插入/删除可改链接 |
标准库没有内建链表；可用自定义节点类实现，常见列表list不是链表 |
若先按值寻找位置，搜索仍为O(n)；节点分散带来指针/对象开销，不能仅凭“插入O(1)”断言总体更快 |
| 哈希映射 | C无内建字典；需自行实现桶、哈希函数和冲突处理，或使用第三方库 | HashMap<K,V>为哈希映射；常见操作期望O(1)，碰撞多时有退化/树化等实现细节 |
dict是内建映射；CPython使用开放寻址哈希表，通常期望O(1)查找/插入 |
哈希表不提供按键排序；平均/期望复杂度依哈希质量、负载因子和碰撞，不能写成所有输入必为O(1) |
| 有序树 | C无内建平衡树；可自行实现二叉搜索树、AVL或红黑树 | TreeMap<K,V>按键排序，API保证基本操作O(log n)，实现为红黑树 |
dict不是有序搜索树；需有序映射时标准库无通用内建红黑树，可用bisect维护有序列表（查找O(log n)，插入仍O(n)）或第三方树库 |
“树有序遍历”只适用于有序搜索树等满足排序不变量的结构；普通二叉树遍历不自动有序 |
| 队列/双端队列 | 可用环形数组或链式节点实现，容量与满队列策略由程序定义 | ArrayDeque<E>适合作为队列/栈，头尾操作摊还O(1)；不允许null元素 |
collections.deque适合两端追加/弹出，近似O(1)；list.pop(0)要移动其余元素 |
FIFO是操作规则，不规定底层必须链表；选型应看两端操作、容量、线程安全和内存局部性 |
以“按账号查记录、还需按余额区间输出排序”为例：C可用数组遍历，简单但查找O(n)；Java可用HashMap<AccountId,Account>快速按键定位，再用TreeMap<Balance,...>按余额范围查询，但要维护两份索引；Python可用dict按账号定位，按余额排序可调用sorted，每次排序成本O(n log n)。选择结构应由操作模式决定，而不是把某种语言的数据结构名称当作算法优劣结论。
上述复杂度是常见实现和操作模型下的分析值：C语言标准只定义数组、对象与指针语义，不规定通用链表/哈希表；Java集合接口的行为契约与具体实现须区分；Python语言保证与CPython 3.14的内部布局也须区分。多线程同时修改集合还需要同步或并发容器，普通哈希表的单线程复杂度不等于线程安全。
回忆版2024题36设ASCII字符'1'=49、'2'=50：printf("%c,",b++)先按旧值输出字符2，再令b为'3'；下一句按整数输出51−49=2，所以为2,2，不是输出字符码50。C标准函数可以嵌套调用和递归，不能按通用标准在函数体内定义另一函数；void函数不要求返回值，跨文件调用可通过声明和链接完成。示例仅解释旧题相关知识，不新增题库。
资料依据与核实状态¶
主资料手册PDF物理48—49页11.1—11.5；回忆版2022题31、35—36、39、84（6—7、12页），2024题21、30、31、36、86（17—19、24页），2019题24—25（30页）。这些位置沿用原登记，本轮未重新读取本地资料，原答案不作事实依据。2026-11-04独立复核不继承此前“实际访问/已核”标签。
本轮实际读到JVMS SE25 §2.5.2每线程私有栈、frame可在堆上分配的实现自由，以及§2.5.3线程共享堆、实例/数组分配和不指定GC算法；JLS SE25 §15.12.4.2支持实参求值得值，§15.12.4.5明确将这些值赋给新建形参变量。只取得规范文件不代表核完其中全部条款。原构造的/en/java/javase/25/docs/specs路径返回通用文档主页，不能以HTTP 200计为正文；此处链接已换为实际读到条文的路径。引用值/对象别名完整论证仍需相应类型条款。JLS第8/9/11/14章、C N1570/GCC、Java集合API、Python3.14文档和CPython实现本轮未重新阅读，故方法覆盖/派发、异常/资源关闭、翻译阶段、对象存储期、容器复杂度及全部GC策略例均保留待核范围，不再限定为仅版本细节未核。详见核查表。