数据结构和算法

前言

本人学习计算机科学的经历或许是相当特殊的. 我首先读了SICP, 接着读了EoPL, 之后开始阅读其他编程语言相关的书籍和论文. 我并没有学习过数据结构和算法. 即便学校开设了相关课程, 作为差生和学渣的我也并没有去上课, 更不用说主动学习了. 实际上, 学习编程语言并不怎么需要数据结构和算法. 即便偶尔遇到, 也能很快理解. 于是, 这就导致我几乎完全不懂这个领域, 因为并没有学习的迫切需要. 然而, 终归我还是想要学一点数据结构和算法的, 于是在这里写一些自己的笔记.

总览

算法是对于过程的(准确)描述, 而数据结构是组织数据的方法, 这构成了笔记的主题.

抽象数据类型

抽象数据类型的想法在于将对于数据的描述和数据结构本身的实现分离. 实际上, 数据结构这个术语拥有诸多不同的含义, 它可以指

• 抽象数据类型
• 对于抽象数据类型的实现
• 抽象数据类型的实现的实例
• 计算机器实际组织数据的方式

一个简单的想法是, 如果对于一种数据我们具有两种等价的表示$R_1$和$R_2$, 而$T$是从形式$R_1$到形式$R_2$的转换, 那么对于操作于形式$R_1$之上的算法$A$, 其等价的操作于形式$R_2$之中的算法为$TA{T}^{-1}$.

递归

递归似乎占据着一切和计算机有关的领域的核心, 至少对于我而言是这样, 我们从以下简单的例子开始.

学习过分析的人对于求导的法则并不陌生, 这实际上提供了计算具体的导数的方法. 现在, 我们希望将其翻译为程序, 于是可供计算机器执行.

(define (diff exp var)
  (match exp
    (,num (guard (number? num)) 0)
    (,var^ (guard (symbol? var^)) (if (eq? var var^) 1 0))
    ((+ ,e1 ,e2) `(+ ,(diff e1 var) ,(diff e2 var)))
    ((* ,e1 ,e2) `(+ (* ,e1 ,(diff e2 var))
                     (* ,e2 ,(diff e1 var))))))

搜索

Uniform-Cost Search (一致代价搜索)

Zipper (拉链)