数据结构和算法笔记

我完全不懂数据结构和算法. 另外, 这里是一些关于数据结构和算法的笔记. 当我认为我懂了之后, 或许会写一本书.

什么是数据结构?

以下内容翻译自Purely Functional Data Structures.

任何对于数据结构的讨论都充斥着误解的潜在可能, 因为术语数据结构至少具有四个不同但相互关联的含义.

一个抽象数据类型 (即一个类型和一集该类型上的函数). 我们将会称其为一个抽象.
一个抽象数据类型的一个具体实现. 我们将会称其为一个实现, 但是注意一个实现未必要被具体化为代码——一个具体的设计就足够了.
一个数据类型的一个实例, 例如一个特定的列表或树. 我们将会称这样的一个实例为一个对象或者一个版本. 然而, 特定的数据类型可能有着它们自己的命名法. 例如, 我们将会直接称栈或队列对象为栈或队列.
一个在更新下保持不变的独特身份(identity). 例如, 在一个基于栈的解释器里, 我们经常非正式地说栈 (the stack), 就好像只存在一个栈似的, 而不是不同的时间有着不同的版本. 我们将会称这个身份为一个可持久化身份. 这个事项主要出现在可持久化数据结构的上下文中; 当我们言及相同数据结构的不同版本时, 我们的意思是这些不同版本共享着一个相同的可持久化身份.

大致说来, 抽象对应于Standard ML的签名, 实现对应于结构或函子, 对象或版本对应于值. 至于可持久化身份, Standard ML中没有贴切的对应概念 (good analogue).

IOI 1994 The Triangle

算是简单的动态规划问题.

(define ref
  (case-lambda
    ((v i) (vector-ref v i))
    ((v i . j*) (apply ref (vector-ref v i) j*))))
(define (solve-IOI94P1 T)
  (define N (vector-length T))
  (define S (make-vector N))
  (let iter ((i 0))
    (cond
      ((= i N) (apply max (vector->list S)))
      (else
       (let iter ((j i))
         (cond
           ((= j 0)
            (vector-set! S 0 (+ (ref T i 0) (ref S 0))))
           (else
            (vector-set! S j (+ (ref T i j)
                                (max (ref S (- j 1)) (ref S j))))
            (iter (- j 1)))))
       (iter (+ i 1))))))

> (solve-IOI94P1
   '#(#(7)
      #(3 8)
      #(8 1 0)
      #(2 7 4 4)
      #(4 5 2 6 5)))
30

题解网上很容易找到, 也没有必要再写什么. 注意make-vector默认将每个元素置为0.

辅助过程

(define (vector-swap! v i j)
  (define t (vector-ref v i))
  (vector-set! v i (vector-ref v j))
  (vector-set! v j t))

插入排序

插入排序相当简单 (但实际上对于没有接触过的人而言又不那么简单), 但也相当重要. 在数组长度比较短的时候, 插入排序往往是效率最高的.

(define (insertion-sort! v)
  (define l (vector-length v))
  (unless (< l 2)
    (let iter ((i 1))
      (unless (= i l)
        (insert! v i)
        (iter (+ i 1))))))
(define (insert! v i)
  (define x (vector-ref v i))
  (let iter ((j (- i 1)))
    (cond
      ((= j -1) (vector-set! v 0 x))
      ((> (vector-ref v j) x)
       (vector-set!
        v (+ j 1) (vector-ref v j))
       (iter (- j 1)))
      (else
       (vector-set! v (+ j 1) x)))))

插入排序的时间复杂度估计非常简单, 每次插入最坏的情况就是移动到开头, 并且插入次数大致上是 $n$ , 故上界为 $O (n^{2})$ .

归并排序

注意一下, (merge-sort! v lo hi)排序的是v从lo到hi的部分, 包含lo但不包含hi.

(define (merge-sort! v lo hi)
  (unless (<= (- hi lo) 1)
    (define mi (quotient (+ lo hi) 2))
    (merge-sort! v lo mi)
    (merge-sort! v mi hi)
    (merge! v lo mi hi)))
(define (merge! v lo mi hi)
  (define l (vector-copy v lo mi))
  (define r (vector-copy v mi hi))
  (define a (- mi lo))
  (define b (- hi mi))
  (let iter ((k lo) (i 0) (j 0))
    (cond
      ((and (< i a) (< j b))
       (cond
         ((< (vector-ref l i)
             (vector-ref r j))
          (vector-set! v k (vector-ref l i))
          (iter (+ k 1) (+ i 1) j))
         (else
          (vector-set! v k (vector-ref r j))
          (iter (+ k 1) i (+ j 1)))))
      ((= i a)
       (let iter ((k k) (j j))
         (unless (= k hi)
           (vector-set! v k (vector-ref r j))
           (iter (+ k 1) (+ j 1)))))
      ((= j b)
       (let iter ((k k) (i i))
         (unless (= k hi)
           (vector-set! v k (vector-ref l i))
           (iter (+ k 1) (+ i 1))))))))

归并排序的时间复杂度估计不难理解, 大致上每个层次归并所用的时间是 $O (n)$ , 而大约有 $\log_{2} (n)$ 层, 故上界估计为 $O (n \log_{2} (n))$ .

冒泡排序

不知道为什么, 编写冒泡排序是一件很有压力的事情, 而实际上我的确也写了很长时间. 在编写冒泡排序的时候, 我的脑子里的所思所想是这样的: 后段已排序, 后段的每个元素都大于等于前段的所有元素, 每轮交换可以将前段的最大元素移至最后的位置, 如果在一轮中没有发生交换, 则说明整个数组是已排序好了的. 当然, 也可以从逆序归约的角度思考问题.

(define (bubble-sort! v)
  (define l (vector-length v))
  (let loop ((i 1))
    (unless (>= i l)
      (let iter ((j 0) (flag #f))
        (cond
          ((= j (- l i))
           (when flag
             (loop (+ i 1))))
          ((> (vector-ref v j)
              (vector-ref v (+ j 1)))
           (vector-swap! v j (+ j 1))
           (iter (+ j 1) #t))
          (else
           (iter (+ j 1) flag)))))))

快速排序

这里的约定和归并排序那里一致. 主元的选取是任意的, 我只是选取了第一个元素.

(define (quick-sort! v lo hi)
  (unless (<= (- hi lo) 1)
    (define p (partition! v lo hi))
    (quick-sort! v lo p)
    (quick-sort! v (+ p 1) hi)))
(define (partition! v lo hi)
  (define pivot (vector-ref v lo))
  (let iter ((left (+ lo 1)) (right hi))
    (cond ((= left right)
           (vector-swap! v lo (- left 1))
           (- left 1))
          ((> (vector-ref v left) pivot)
           (vector-swap! v left (- right 1))
           (iter left (- right 1)))
          (else
           (iter (+ left 1) right)))))

根据原地 (in-place) 的定义的不同, 快速排序可以是原地的, 也可以不是原地的, 因为它的确要消耗栈的空间.

二分搜索

据说二分搜索很少有人能够书写正确, 即便是算法研究者也不例外.

(define (binary-search x v lo hi)
  (if (>= lo hi)
      #f
      (let ((mi (quotient (+ lo hi) 2)))
        (cond
          ((= (vector-ref v mi) x) mi)
          ((> (vector-ref v mi) x)
           (binary-search x v lo mi))
          (else
           (binary-search x v (+ mi 1) hi))))))