hit-datastructure-on-scheme's Introduction

哈尔滨工业大学《数据结构与算法分析》《软件开发实践》

Scheme解法

把戏、杂技和先辈的括号——献给住在计算机内的神灵们

数学家们用奇怪的符号组成美妙的式子来表达具有深刻逻辑性的**。

工程师们不但有从数学家那里继承来的严谨形式化体系，他们还有……呃，NULL和指针！

图灵机和λ-演算，前者在冯·诺依曼体系的补充下显得更加地“工程”，相较之下后者却更加地“数学”。作为两种模型体现，C语言和Scheme（Lisp）完全就像是两种极端：[一个是红外线，而另一个是紫外线] 1。

那些说C语言的人，他们甚至能经常看到新鲜的二进制位。你总是会看见他们拿着大刀在这些比特上砍砍削削！可是他们的大刀又太锋利，稍有不慎坎坏了那些比特不说，还经常弄伤自己。

而那些满嘴Lisp方言的人，他们似乎住在一个耸立天际的高塔中。他们会建立各种各样的抽象层，将一些底层的**给隔离开来。呵，这又是如此的巧妙！那些住在塔顶层的人们，似乎还没发觉这座塔是由他们之中那些能工巧匠“凭空”建造的！

在C语言或者是Java语言的程序员眼中，Scheme（Lisp）程序员不但是阴谋家，而且是一个叨念咒语、步履蹒跚的巫师。但更多的时候，这些巫师更像马戏团中的抛球小丑：他们总善于将大量的括号抛起在空中，又准确地稳稳接住。嘘！千万不要奇怪这些括号中会混入像lambda和eval-apply这样的诡秘东西——这也是他们善用的把戏！

换个角度来说，Scheme（Lisp）远比C语言要亲和数据结构：广义表（S-表达式）已经作为Scheme（Lisp）的语法基石深深地奠基在语言核心中，通过使用cons，我们可以将原子构建成表，甚至可以将原子和表组成新表！我们将看到……由于图灵等价的论断，凡是C语言能描述的数据结构，Scheme（Lisp）都能够模拟！

我们的雄心，并非需要malloc()才能开辟。保持一颗对数学虔诚探索的心，一种对工程谨严思辨的精神，我们将开始用远古的咒语来颂唱不太久远的诗篇。并谨以此献给那些住在计算机内的神灵们！

这是对你的启发，而非对你的限制

如果我的小学弟（或者是可爱的小学妹）很不幸地“搜索”到了这个Scheme解法，请不要懊恼，虽然它不能帮助你“快速地”完成令你烦恼的数据结构的作业，但它会给你洞开一扇通向奇异世界的大门。请插上想象的翅膀，摆脱C语言的束缚，在数据结构的世界里自由翱翔！

如果你因此对Scheme产生了兴趣，你可以参考Scheme新手教程，该教程也像本项目一样托管在Github上，它在yast-cn这个仓库中。

同时，计算机界里有一本非常优秀的教科书——《计算机程序的构造和解释》，它也是用Scheme来授课的。你可以在Learning-SICP这个仓库中取得公开课字幕的资源。

本仓库涵盖的内容

本仓库包括但不限于以下内容：

Scheme函数库的简易扩充（library文件夹）。
一些数据结构、算法的Scheme实现的收集（referrence文件夹）。
哈尔滨工业大学《数据结构与算法分析》课程的作业与实验代码（exercise、experiment文件夹）。
哈尔滨工业大学《软件设计与开发实践I》课程的实验代码（application文件夹）。

本仓库中的代码采用MIT-Scheme解释器，遵循R^5RS规范。

参考文献

下面陈列的文献都是学习Scheme（Lisp）很好的资料。读者可以从这些文献的出版日期从感受到厚重的历史底蕴。

Allen J. Anatomy of LISP[M]. McGraw-Hill, Inc., 1978.
Siklossy L. Let's talk LISP[M]. Englewood Cliffs, NJ: Prentice-Hall, 1976.
Sussman G, Abelson H, Sussman J. Structure and interpretation of computer programs[J]. The Massachusetts Institute of Technology, 1985, 10.
Friedman D P. The Little Schemer[M]. The MIT Press, 1996.

联系我

如果您认为我的解法有错误或者过于笨拙，欢迎您提交Pull Request。

如果您想与我交流，欢迎致信dk[at]hit.edu.cn。

hit-datastructure-on-scheme's People

Contributors

Stargazers

Watchers

hit-datastructure-on-scheme's Issues

issue首发，发现错别字一枚

如果您认为我的解法有错误或者过于笨拙，我 欢饮 您提交Pull Request

应该是 欢迎 吧

关于hit-oslab实验环境问题请教

首先，感谢楼主提供的环境资源分享。但是现在我的64位环境采用make编译linux-0.11出现了as86:Command not found的问题，所以在此处想请教一下楼主该如何解决，谢谢啦！

Bug in dijkstra2

Using your code as listed I get:

1 ]=> (dijkstra2 c)

;The procedure #[compiled-procedure 16 ("vector" #xa) #x1a #xbd14fa] has been called with 4 arguments; it requires exactly 3 arguments.
;To continue, call RESTART with an option number:
; (RESTART 1) => Return to read-eval-print level 1.

I fixed parenthesis so that dijkstra2 is now:

(define (dijkstra2 C)

; computes a pair of vectors which contain
; (1) the costs of the shortest paths from vertex 0
; to every vertex in the cost matrix C and
; (2) the immediate predecessor vertexes of every
; vertex in the shortest path

(define n (matrix-col-length C))

(define D (matrix-row-copy C 0))
; shortest distance from vertex 0 to each vertex

(define P (make-vector n 0))
; P[v] contains the vertex immediately before
; vertex v in the shortest path

(define (min-vertex D V)
; chooses a vertex w in V such that D[w] is minimum
(let loop ((w (car V)) (V (cdr V)))
(if (null? V)
w
(if (< (vector-ref D (car V)) (vector-ref D w))
(loop (car V) (cdr V))
(loop w (cdr V))))))

; dijkstra
(let loop ((V (enum 1 (- n 1))))
; V contains the set of vertexes whose shortest
; distance from the vertex 0 is still unknown
(if (null? V)
(cons D P)
(let* ((w (min-vertex D V)) (V-w (remv V w)))
(for-each
(lambda (v)
(if (< (+ (vector-ref D w) (matrix-ref C w v))
(vector-ref D v))
(begin
(vector-set! D v
(+ (vector-ref D w) (matrix-ref C w v))) ;;; added )
(vector-set! P v w)))) ;;; removed )
V-w)
(loop V-w)))))

Now I get:

1 ]=> (dijkstra2 c)

;Value: (#(0 10 50 30 60) . #(0 0 3 0 2))

See comments in code above for the tiny edit (moved a close paren).

Looks like Juha Heinanen 1988 was the original author. Maybe you never ran dijkstra2.

Thank you so much for posting this code. Incredibly helpful to a lisp newbie like me.

deathking / hit-datastructure-on-scheme Goto Github PK