数据结构和算法笔记

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

什么是数据结构?

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

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

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

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.