UP | HOME

结构体

Table of Contents

本章中，将讲解 向量 和 结构体

向量 是一组通过 整数索引 的数据： 

  与C语言中的数组不同，一个向量可以储存不同类型的数据

Scheme中的 结构体 与C语言中的 结构体 类似。但Scheme中的结构体更 容易使用 ，因为Scheme为结构体 自动创建 了 读取 函数和 写入 函数 

  这受益于 Lisp/Scheme 中的宏

向量

字面值

向量 通过 闭合 的 #( 和 ) 表示，作为 字面值 时，它们应该 被引用 ，例如： 

'#(1 2 3)               ; 整数向量
'#(a 0 #\a)           ; 由符号、整数和字符构成的向量

向量函数

下面的函数都是R5RS规定的函数：

  • (vector? obj) : 如果 obj 是一个 向量 则返回 #t
  • (make-vector k fill) : 返回有 k个元素 的向量
    • 如果指定了第二个参数 fill ，那么所有的元素都会被 初始化 为 fill
  • (vector obj …) : 返回由 参数列表 构成的 向量
  • (vector-length vector): 返回向量 vector 的 长度
  • (vector-ref vector k) : 返回向量 vector 的 索引 为 k 的 元素 （向量从 0 开始索引）
  • (vector-set! vector k obj): 将向量 vector 的索引为 k 的 元素 修改为 obj
  • (vector->list vector) : 将 vector 转换为 表
  • (list->vector list) 将表 list 转换为 向量
  • (vector-fill! vector fill) : 将向量 vector 的 所有元素 设置为 fill

例如，对两个向量中元素求和： 

(define (vector-add v1 v2)
  (let ((lenv1 (vector-length v1))
        (lenv2 (vector-length v2)))
    (if (= lenv1 lenv2)
        (let ((v (make-vector lenv1)))
          (let loop ((i 0))
            (if (= i lenv1)
                v
                (begin
                  (vector-set! v i (+ (vector-ref v1 i) (vector-ref v2 i)))
                  (loop (+ 1 i))))))
        (error "different dimensions."))))

结构体

    虽然 R5RS 中没有定义结构体，但是在很多Scheme实现中，都实现了类似于 Common Lisp 中的结构体

这些结构体本质上来说都是向量。每一个 槽 ( slot )都通过使用一个 宏 来命名。结构体 通过不同的属性 清楚地 表示数据 

    定义结构体的宏 自动为 结构体 创建 取值器 (accessor) 和赋值器 (setter)

MIT-Scheme中的结构体

在MIT-Scheme中，结构体通过函数 define-structure 来定义。请考虑书籍。书籍都有下列属性：

  • 标题
  • 作者
  • 出版商
  • 出版年份
  • ISBN号

因此结构体 book 就可以像下面这样定义： 

(define-structure book title authors publisher year isbn)

(define bazaar 
  (make-book 
   "The Cathedral and the Bazaar"
   "Eric S. Raymond"
   "O'Reilly"
   1999
   0596001088)) ; bazaar

然而，这样做多少有点不便，因为属性与值的关联并不清楚：

  • 参量 keyword-constructor 可以用于解决这个问题
    • 属性与值的 关联 就非常清楚了
    • 参数的 顺序 就不重要了
  • 参量 copier 可用于为结构体创建一个 拷贝 函数
(define-structure (book keyword-constructor copier) 
  title authors publisher year isbn)

(define bazaar 
  (make-book 
   'title "The Cathedral and the Bazaar"
   'authors "Eric S. Raymond"
   'publisher "O'Reilly"
   'year 1999    
   'isbn 0596001088))
  • [the name of structure]? : 检查某对象是否为 特定结构体 。例如，可使用函数 book? 来检查 bazaar 是否为 book结构体 的 一个实例 ：
(book? bazaar) ; #t
  • copy-[structure name] : 拷贝 结构体。例如，下面的代码演示了将 bazaar 拷贝 到 cathedral ：
(define cathedral (copy-book bazaar)) ; cathedral
  • [structure name]-[attribute name] : 读取结构体某 属性的值 。例如，下面的代码演示了如何读取 bazaar 的 title属性 ：
(book-title bazaar) ; "The Cathedral and the Bazaar"
  • set-[structure name]]-[attribute name]]! : 将某 属性设定 为特定值。下面的代码演示了如何将 bazaar 的 year字段 更新到 2001 ：
(book-year bazaar) ; 1999   
(set-book-year! bazaar 2001)
(book-year bazaar) ; 2001

实例：简单的密码破解游戏

作为向量的示例，我们演示一个简单的密码破解游戏。这是一个猜对手密码的游戏。密码是由 0到 9中四个不同的数组成的四位数。对手要通过使用 bulls和 cows 的数量告知猜谜者猜测的准确程度

  • bull 的数量 (Nbull) 是指值和位置都正确的数字的数量
  • cow的数量 (Ncow) 是指值正确但位置错误的数字的数量。
    例如，密码是5601，猜测是1685

    那么 bull 和 cow 和数分别是 1 和 2

计算机和用户相互猜测对方的密码。更少尝试次数的选手为胜利者。如果用户和电脑在相同的尝试次数中破解了密码就是平局

数据结构

四位数字可以通过向量和计算 bull 以及 cow 的数量高效地表示。这种表达方法需要 构成密码的数字都不相同 ：

创建长度为10的向量：

  • 每个 索引 k 的 值 被设为k在密码中的 数位
  • 四个数位从低到高被计为 1，2，3和4
  • 如果数字没有出现，索引的值为0
例如，5601和1685可以表示如下：

5601 → #(2 1 0 0 0 4 3 0 0 0)
1685 → #(0 4 0 0 0 1 3 0 2 0)

5601这个例子中，数字0，1，5，和6分别出现在第2，第1，第4和第3位

那么在这个密码的向量表达式里索引0，1，5，6的值分别2是2，1，4和3，其他索引位都是0

这种表达可以快速比较两个数字，如果两个向量的相同索引位的值都是正数情况下：

  • 如果值相等，就计为bull
  • 如果值不相等，就计为cow
5601和1685这个例子的情况下

索引位6的值都为3，索引位1和索引位5的值都是正数

bull和cow的值为1和2

设计

程序的设计如下：

  1. 程序生成一个表，该表包含了所有不同四位数的向量表示
  2. 程序从表中随机选取一个数字
  3. 重洗步骤（1）产生的表
  4. 程序首次猜用户的密码，用户给出 bull 和 cow 的数量。然后用户猜程序的密码，程序给出 Nnull 和 Ncow
  5. 重复步骤（3）直到电脑或者程序的bull数量变为 4 为止。如果在同一次双方的数量都变为4，就是平局

实现

(char2int c) : 将字符c ( #\0 ~ #\9 )转换为整数（0 ~ 9） 

(define (1- x) (- x 1))

(define (char2int c)
  (- (char->integer c) (char->integer #\0)))

(ls2nvec ls) : 将四个数字的 表 ls 转换为 向量表达式 

(define (ls2nvec ls)
  (let ((vec (make-vector 10 0)))
    (let loop ((i (length ls)) (ls ls))
      (if (> i 0)
          (begin
            (vector-set! vec (car ls) i)
            (loop (1- i) (cdr ls)))
          vec))))

(ls2nvec '(5 3 6 0)) ; => #(1 0 0 3 0 4 2 0 0 0)

(nvec2int vec) : 将 向量表达式 vec转换为普通 整数 

(define (nvec2int vec)
  (let loop ((i 0) (n 0))
    (if (= i 10)
        n
        (let ((j (vector-ref vec i)))
          (loop (1+ i) (+ n (if (> j 0)
                                (* i (expt 10 (1- j)))
                                0)))))))

(int2str i) : 将一个四位数i转换为字符串。如果i小于1000，'0'被置于高位 

(define (int2str i)
  (string-append
   (if (< i 1000) "0" "")
   (number->string i)))

(read-from-stdin str) : 将 str 显示于 标准输出 ，并返回用户从 标准输入 输入的字符串 

(define (read-integer str)
  (string->number (read-from-stdin str)))

(define (read-from-stdin str)
  (display str)
  (newline)
  (read-line))

(write-to-stdout . ls) : 将ls的每个元素都输出到 标准输出 ，并在 行尾 插入 行结束符 

(define (write-to-stdout . ls)
  (for-each (lambda (obj) (display obj)) ls)
  (newline))

(str2nvec str) : 将用户输入的表示四位数的 字符串 str转换为 向量表达式 

(define (str2nvec str)
  (let ((vec (make-vector 10 0)))
    (let loop ((i (string-length str)) (ls (string->list str)))
      (if (pair? ls)
          (begin
            (vector-set! vec (char2int (car ls)) i)
            (loop (1- i) (cdr ls)))
          vec))))

(scoring vec0 vec1) : 以 ( 5*Nbull + Ncow ) 计算两个整数（向量表达式）vec0 和 vec1的 相似程度 

(define (scoring vec0 vec1)
  (let ((n (vector-length vec0)))
    (let loop ((i 0) (score 0))
      (if (< i n)
          (let ((d0 (vector-ref vec0 i))
                (d1 (vector-ref vec1 i)))
            (loop (1+ i)
                  (+ score (if (and (< 0 d0) (< 0 d1))
                               (if (= d0 d1) 5 1)
                               0))))
          score))))

(show-user-score score) : 通过 相似度score 计算 Nbull 和Ncow，并将它们显示在 标准输出 ： 

(define (show-user-score score)
  (write-to-stdout "Number of bulls and cows in your guess:" )
  (write-to-stdout "bulls: " (quotient score 5))
  (write-to-stdout "cows: " (modulo score 5))
  (newline))

(read-my-score gu0) : 显示 计算机的猜测 (gu0) ，让用户输入 Nbull 和 Ncow ，返回 相似度 score 

(define (read-my-score gu0)
  (write-to-stdout "My guess is: " (int2str (nvec2int gu0)))
  (write-to-stdout "Give number of bulls and cows in my guess." )
  (let ((na5 (* 5 (read-integer "bulls: "))))
    (+ na5 (read-integer "cows: ")))) ; the score is calculated by (5 * bull + cow)

(read-user-guess) : 返回 用户猜测 的 向量表达式 

(define (read-user-guess)
  (newline)
  (str2nvec (read-from-stdin "Give your guess.")))

(shuffle-numbers ls0) : 随机排序 ls0。由于有 随机读取的需求，将 ls0转换为 向量 ，然后随机读取向量的元素，以创建一个重排过的表 

(define (shuffle-numbers ls0)
  (let ((vec (list->vector ls0)))
    (let loop ((n (vector-length vec)) (ls1 '()))
      (if (= n 0)
          ls1
          (let* ((r (random n))
                 (v (vector-ref vec r)))
            (vector-set! vec r (vector-ref vec (1- n)))
            (loop (1- n) (cons v ls1)))))))

(make-numbers) : 返回由所有不同四位数构成的表 

(define (make-numbers)
  (let ((ls1 '()))
    (letrec ((rec (lambda (i num ls)
                    (if (= i 4)
                        (set! ls1 (cons (ls2nvec ls) ls1))
                        (for-each 
                         (lambda (n)
                           (rec (1+ i) (delv n num) (cons n ls)))
                         num)))))
      (rec 0 '(0 1 2 3 4 5 6 7 8 9) '()))
    ls1))

(game-over sc0 sc1) : 通过比较计算机的得分 (sc0) 和用户的得分 (sc1) 确定胜利者 

(define (game-over sc0 sc1)
  (write-to-stdout
   (cond
    ((= sc0 sc1) "Draw")
    ((> sc0 sc1) "I won.")
    (else "You won.")))
  'game-over)

(scoring-user-guess an0 gu1) : 计算计算机的密码 an0 和用户的猜测 gu1 的相似度，使用 show-uuser-score 输出 Nbull 和 Ncow 

(define (scoring-user-guess an0 gu1)
  (let ((sc1 (scoring an0 gu1)))
    (show-user-score sc1)
    sc1))

(mastermind-rec an0 candidates) : 主程序，它有两个参数

  • 计算机密码 an0
  • 猜测的表 candidate

主要逻辑：

  1. 它计算计算机的得分 sc0 和用户的得分 sc1
  2. 如果 sc0 或者 sc1 为20
    • 调用 (game-over sc0 sc1)
    • 如果没有值为20，它根据 sc0 过滤猜测的表 candidate，并继续游戏
(define (mastermind-rec an0 candidates)
  (if (null? candidates)
      (error "Error. You gave wrong score for my guess, probably.")
      (let ((gu0 (car candidates)))
        (let ((sc1 (scoring-user-guess an0 (read-user-guess)))
              (sc0 (read-my-score gu0)))
          (if (or (= sc0 20) (= sc1 20))
              (game-over sc0 sc1)
              (mastermind-rec an0 
                              (keep-matching-items 
                               (cdr candidates)
                               (lambda (x) (= (scoring gu0 x) sc0)))))))))

(mastermind) : 在控制台调用该函数以开始游戏 

(define (mastermind)
  (let ((ls0 (make-numbers)))
    (mastermind-rec (list-ref ls0 (random (length ls0))) (shuffle-numbers ls0))))

测试： 

(compile-file "mastermind.scm")
(load "mastermind")
(mastermind)

Previous：哈希表

Home：目录