日拱一卒，伯克利CS61A，如何用scheme判断链表有环？

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，日拱一卒，我是梁唐。

我们今天继续来肝CS61A这门公开课，这次我们来看的是作业11.

原始文档：https://inst.eecs.berkeley.edu//~cs61a/sp18/hw/hw11/

这次的作业也只有三题，主要都是关于Scheme中stream的用法。stream有些类似Python中的迭代器，只保存计算逻辑而不保存具体的数据，具体的数据要在访问迭代器时才会进行计算。这样可以避免不必要的计算，从而提升性能。

比如我们可以定义一个永远返回1的stream：

我们也可以定义一个表示所有整数的stream：

更多的内容大家可以去看下公开课的讲课视频，会更加清楚。

好了，我们来看题吧。

Q1: Find

实现find过程，它接收一个stream和predicate，返回stream中满足predicate的第一个元素。

predicate 是一个接收一个参数的函数，如果传入的数据不合法返回False，否则返回True。如果找不到合法的元素，返回False

开发完成之后进行测试：

python3 ok -q find

答案

这是一道基本的递归问题，使用递归很容易写出代码。只需要注意在递归的时候，求scheme list的下一个位置时需要使用stream操作符cdr-steam而非cdr

(define (find s predicate)
    (if (null? s) False
        (if (predicate (car s)) (car s)
            (find (cdr-stream s) predicate)
        )
    )
)

Q2: Scale Stream

实现函数scale-stream，它接收一个stream s和一个整数k，它返回一个stream，当中的每一个元素都是s对应位置的值乘上k。比如k是2时，相当于返回一个新的stream，当中的值是s的两倍。

即使输入的s是一个无限stream，你的代码也要能work。

当你完成之后，进行测试：

python3 ok -q scale-stream

答案

这题也很简单，也是一个简单的递归。主要我们在递归当中创建stream时，需要使用cons-stream而非cons

(define (scale-stream s k)
    (if (null? s) nil
        (cons-stream (* (car s) k) (scale-stream (cdr-stream s) k))
    )
)

Q3: Cycles

在scheme当中，stream是有可能存在环的，即stream当中的某个部分包含了自己本身：

实现has-cycle函数，判断一个stream当中是否有环

提示：你可以假设你的输入是未知的长度，或者包含一个环

eq?函数对你也许很有用，它可以判断两个stream是否相同

当你开发完成之后，进行测试：

python3 ok -q has-cycle

答案

同样是一个递归问题，我们可以把所有遍历到的scheme list存储下来，如果当前递归的list s已经被记录了，那么说明必然存在环，通过环回到了一个之前的位置。

我们使用mem存储所有遍历过的s，每次递归时更新mem

(define (has-cycle s)
    (define (in? mem s)
        (cond
            ((null? mem) False)
            ((eq? (car mem) s) True)
            (else (in? (cdr mem) s))
        )
    )
    (define (has-cycle-helper mem s)
        (cond 
            ((null? s) False)
            ((in? mem s) True)
            (else (has-cycle-helper (cons s mem) (cdr-stream s)))
        )
    )
    (has-cycle-helper nil s)
)

附加题

实现has-cycle-constant函数，让它的内存开销是常数级。

这个方案很短（不会超过20行），但是需要一个很巧妙的方法，试着想出解法来。

答案

这题不看答案非常困难，也是当初微软一道非常著名的面试题。

其实就是想办法在常数级的内存开销下，判断链表当中是否存在环。最好的方法就是通过快慢指针，设置两个指针，快指针每次移动两格，慢指针每次移动一格，如果链表存在环，那么它们必然会在未来某一刻相遇。如果链表结束还未相遇，说明没有环。

这题的解法几乎完全一样，只不过是用scheme实现而已。

(define (has-cycle-constant s)
    (define (has-cycle-helper fast slow)
        (cond
            ((null? fast) False)
            ((null? (cdr-stream fast)) False)
            ((null? slow) False)
            ((eq? fast slow) True)
            (else (has-cycle-helper (cdr-stream (cdr-stream fast)) (cdr-stream slow)))
        )
    )
    (cond
        ((null? s) False)
        ((null? (cdr-stream s)) False)
        (else (has-cycle-helper (cdr-stream (cdr-stream s)) (cdr-stream s)))
    )
)

喜欢本文的话不要忘记三连~