尽管名为 "数据结构" (data structure, DS), 事实上, 数据结构与算法不分家, 因此这也是我的算法笔记.

伪代码约定

注释

单行注释以井号 # 开头. 我们不用多行注释.

变量/对象

我们主要采用面向对象的思路, 即一切变量都是对象. 对象的属性和方法由句点引出, 形如 对象.属性, 对象.方法(). 如数组 arr 的长度可以写作 arr.length.

异常

一些接收输入或分配内存的算法可能会失败, 我们假定它们在出错时抛出异常. 简单起见, 我们所写的算法一般不处理异常. 假定的异常类型有:

值 含义
OK 成功
ValueError 输入的值不合法
Overflow 分配内存失败, 或数据结构已满, 或计算上溢
Underflow 试图分配大小为负的内存, 或试图从空容器中取出元素, 或计算上溢
NullptrError 试图释放一个空指针所指的内存
IndexError 数组下标越界
Error 其他错误

函数的返回值和引用参数

return 语句用于结束当前函数的运行, 并返回零个到多个值. 返回多值时, 各值用逗号隔开; 接收多个返回值时, 被赋值的变量也用逗号隔开, 如: 

f():
	return 1, 2, 3
x, y, z = f() // 调用

在书写函数原型时, 返回值的类型可以省略, 只在必要时写出.

当函数可能改变实参的值的时候, 我们在函数的形参前添加一个 & 符号, 表示这是一个引用参数, 或者说, 函数内外所引用的, 事实上是同一对象, 这可以通过指针来实现. 如交换两个变量的函数可以定义如下: 

swap(&x, &y):
	tmp = x
	x = y
	y = tmp
swap(a, b) // 调用

应当把这个 & 符号同 c 语言中的取地址符区分开来. 值得注意, 与 c++ 不同, 我们还允许引用绑定到不同的对象上. 另外, 如果被引用对象本身是指针, 我们将通过指针的指针来实现这个引用.

迭代范围

我们用 m..n 表示大于等于 m, 小于等于 n 的整数集合, 与数组/字符串结合使用时, 表示一个子数组/子串. 如 str[2..5] 表示 str[2], str[3], str[4], str[5] 依次组成的 str 的子串.

我们约定, 数组和字符串的下标是从零开始的.

还可以用集合的语法来描述一些数组/容器的初始值, 这些初值应当是容易计算的. 如 [2*k: k = 0..n] 表示 0 到 2n 间的所有偶数.

标准设施

假定已经实现了的函数或语法, 在大多数语言中, 这些函数都是标准的库函数, 或直接是语言的一部分.

input(&a, &b, ...) 读取用户输入, 分别存入变量 a, b, ... 成功时返回一个非零值, 失败时返回零. 导致 input 失败的原因可能有遇到文件结束符 EOF, 或输入的格式不正确等.
print(a, b, ...) 将变量 a, b, ... 的值输出到屏幕.
new Type[n](args...) 类似于 c++ 的语法. 为 n 个 Type 类型的对象分配空间 (省略 [n] 时, 为一个对象分配空间), 并将参数 args 传递给构造函数, 以完成对象的初始化. 返回指向新分配空间的指针. 若内存分配失败, 则抛出异常 Overflow. ()
delete ptr 释放指针 ptr 所指的内存, 若 ptr == NULL, 抛出 NullptrError. ()

在 c 语言中, 负责分配内存的 malloc 函数在失败时返回一个空指针, 因此每次调用后, 必不可少的步骤是检查返回的指针是否为空; 如果指针为空, 接下来要做的一般是退出当前函数, 并返回一个表示错误的值. 异常机制为我们免去了这些繁琐步骤.

与 new 语句不同的是, 我们应当在 delete 之前判断指针是否为空, 这一步骤是不能省略的. 另外, 在 c++ 中, 释放一个分配的数组应当使用 delete[] 运算符, 但方便起见我们只用 delete.

条件

	if 条件1:
		语句块1
	elif 条件2:
		语句块2
	...
	elif 条件n:
		语句块n
	else:
		语句块n+1

依次检验各个条件, 只执行第一个成立的条件下的语句块. 若所有条件都不成立, 执行 else 下的语句块 (如果 else 子句被省略, 则什么也不执行). 各个 elif 和 else 子句都可以省略.

在关键字 if, while 后面的表达式一律转化为布尔类型来理解, 但引起歧义的场合则不可这样略写.

类型 等于 True 当且仅当
数字 (整型, 浮点型, ...) 非零
指针 不等于 NULL
字符 不等于 '\0'
字符串 不等于空串
数据结构 (表, 数组, 栈, 队列, 树, 图...) 不空
status OK

循环

while 条件:
	语句块
当条件成立时, 反复执行语句块. 
do:
	语句块
while 条件
先执行一次语句块, 然后当条件成立时, 反复执行语句块. 
loop n:
	语句块
反复执行语句块 n 次. 
for i = m to n:
	语句块
也可以写成 for i = m..n. 依次对 i = m, m+1, m+2, ..., n 执行循环; 如果 m > n 则为空循环, 一次也不执行. 
for i = m downto n:
	语句块
依次对 i = m, m-1, m-2, ..., n 执行循环; 如果 m < n 则为空循环, 一次也不执行.
循环语句的常见写法 (idioms)
while True 死循环, 可以用 break 语句脱出.
while input(x) 反复处理输入, 直到遇到输入错误或 EOF.
while n--,
do ... while --n 		在循环体不涉及变量 n 时, 都是执行 n 次. 我们引入 loop n 这样简单而不易混淆的写法来替代这两种写法.
do ... while False 恰好执行一次. 它可以在 c 语言的宏定义中替代花括号.

算法的时空复杂度