The Way 2 Inner Peace.

[scheme学习笔记]二叉树的遍历

将二叉树的节点定义为

(define-struct node (number value left right))

则树的定义数据定义是

binary-tree（简称BT）是下列两者之一

1． false；

2． (make-node num value lft rgt)，

其中 num是数，value是符号，lft 和rgt 是BT。

则如图的二叉树可以表示为

(define BT1 (make-node 63 'a
                       (make-node 29 'b
                                  (make-node 15 'c
                                             (make-node 10 'd false false)
                                             (make-node 24 'e false false)) false)
                       (make-node 89 'f
                                  (make-node 77 'g false false)
                                  (make-node 95 'h false
                                             (make-node 99 'i false false)))))
(define BT2 (make-node 63 'a
                       (make-node 29 'b
                                  (make-node 15 'c
                                             (make-node 87 'd false false)
                                             (make-node 24 'e false false)) false)
                       (make-node 89 'f
                                  (make-node 33 'g false false)
                                  (make-node 95 'h false
                                             (make-node 99 'i false false)))))

如果从左到右读出这两棵树中的数.可以得到两个序列

其中数A是按照升序排列的.将有序排列的二叉树称为二叉搜索树.

接下来开发函数inorder.中序遍历.该函数读入一棵二叉树，返回树中所有number数组成的表。该表以

从左到右的顺序（上图顺序）列出这些数.

;;inorder:BT->list
(define (inorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (inorder (node-left BT))
      (list (node-ssn BT))
      (inorder (node-right BT))))))

中序遍历按照左根右的顺序进行历遍.即首先遍历左子树,然后访问根结点,最后遍历右子树.在遍历左,右子树时.仍然先遍历左子树,再访问根结点,最后遍历右子树

而前序遍历按照根左右的顺序进行遍历.

后续遍历按照左右根的顺序进行遍历.

同理即可得到前序遍历和后续遍历的函数.

(define (preorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (list(node-ssn BT))
      (preorder (node-left BT))
      (preorder (node-right BT))))))
(define (postorder BT)
  (cond
    ((boolean? BT) empty)
    (else
     (append
      (postorder (node-left BT))
      (postorder (node-right BT))
      (list(node-ssn BT))))))

可以发现对二叉搜索树来说.中序遍历返回的是有序排列的表.

ps.写个博客都要翻墙.蛋疼死啊..

ps2.用递归的函数写递归的数据结构真是太清晰了.感觉就是C语言写出来是个麻烦的东西.指针满天飞..

[scheme学习笔记]scheme中的快速排序和合并排序

快速排序:

快速排序是分而治之思想的体现,即将非平凡可解的问题分成相关的两个小问题.分别解决这两个小问题.再将所得结果合并起来.

具体来说.quick-sort先讲数表分成两个表.其中第一个表中所有元素小于原表中第一个元素.第二个表中元素大于等于原表中第一个元素.然后对这两个表使用同样的方法进行排序.最后再将他们连接起来.就得到了排序好的表.可设第一个元素为关键元素.

假设输入为

(list 11 8 14 7)

手工计算

关键元素:11

分成的两个表为

(list 8 7)

和

(list 14)

对第一个表使用相同方法排序.可以得到

(list 7 8)

如此.原来的表被分为三部分

1.(list 7 8)

2.11

3.(list 14)

现在将三部分合并起来,即可得到排序完成的表:

(list 7 8 11 14)

表格说明如下:

那么quick-sort就是一个递归的函数.当它遇到空表empty(即'())时停止.

先定义一个函数filter.(在racket的库中已经提供.).用于选出一个表中是某个函数为真的所有元素.此判定函数依次作用于表中所有函数.

;;filter:listX-listX
(define (filter pred list)
  (cond
    ((empty? list) list)
    (else (cond
          ((pred (car list))
           (cons (car list) (filter pred (cdr list))))
          (else (pred (cdr list)))))))

运用filter.可以写出分开两个表的表达式.

那么.quick-sort可以定义了

(define (q-sort lst)
  (if (null? lst)
      lst
      (append (q-sort (filter (lambda (x) (<= x (car lst))) (cdr lst)))
              (list (car lst))
              (q-sort (filter (lambda (x) (> x (car lst))) (cdr lst))))))

归并排序:

这个我也没理解透.只是按照how to design programs 习题 26.1.2一步步做出来的.

先抄题.

习题 26.1.2 开发函数 merge-sort，对数表排序（升序排列），使用如下两个辅助函数：

1．第一个辅助函数 make-singles，它使用给定的表中的数构造一个单元素表的表。例如，

(equal? (make-singles (list 2 5 9 3))

(list (list 2) (list 5) (list 9) (list 3)))

2．第二个辅助函数merge-all-neighbors，它合并相邻的两个表。更精确地说，它读入一个（数）表

的表，合并相邻的表。例如，

(equal? (merge-all-neighbors (list (list 2) (list 5) (list 9) (list 3)))

(list (list 2 5) (list 3 9)))

(equal? (merge-all-neighbors (list (list 2 5) (list 3 9)))

(list (list 2 3 5 9)))

一般来说，这个函数生成一个大概是输入表一半长的表。为什么输出的表并不总是输入表的一半

长？

确保这两个函数的开发相互独立。

函数 merge-sort 首先使用make-singles 把输入表分割为由单元素表组成的表；然后不断地使用

merge-all-neighbors 合并表，并且每次都使用sort 函数对每个小表排序，直至最终得到单一的表；最后这个

表就是merge-sort 的返回值。

代码如下.

;;merge-sort:list->list
(define (merge-sort x)
  (define (merge-sort-worker x)
    (if (= (length x) 1)
        (car x)
        (merge-sort-worker (merge-all-neighbors x))))
  (merge-sort-worker (make-singles x)))

    

;;make-singles:alon-> lists of number
(define (make-singles alon)
  (cond
    ((empty? alon) empty)
    (else (cons(cons (first alon) empty) (make-singles (rest alon))))))

;;merge-all-neighbors:lists->list
(define (merge-all-neighbors alist)
  (cond
    ((empty? alist) empty)
    ((empty? (rest alist)) empty)
    (else (cons (sort (append (first alist)(second alist))<)(merge-all-neighbors (rest (rest alist)))))))

另..

how to design programs中文版下载地址

ftp://ftp.cs.sjtu.edu.cn:990/huanglp/程序设计方法/如何设计程序.PDF

[转]Scheme 之道 --- 无处不在的函数

原文链接:http://hi.baidu.com/pudding/blog/item/7029c8fc45c046fdfc037f2e.html

无处不在的函数

基本的函数概念

Scheme 是一门函数式语言, 因为它的函数与数据有完全平等的地位, 它可以在运行时被实时创建和修改. 也因为它的全部运行都可以用函数的方式来解释, 莫能例外.

比方说, 把 if 语句作为函数来解释? (if cond if-part else-part) 是这么一个特殊的函数: 它根据 cond 是否为真, 决定执行并返回 if-part 还是 else-part. 比如, 我可以这样写:

((if (i-am-feeling-lucky) + -) my-happyness 1)

if 函数会根据我开心与否 (i-am-feeling-lucky 是一个由我决定它的返回值的函数 :P) 返回 + 或 - 来作为对我的开心值的操作. 所谓无处不在的函数, 其意义大抵如此.

把一串操作序列当成函数呢? Scheme 是没有 "return" 的, 把一串操作序列当作一个整体, 它的返回值就是这一串序列的最后一个的返回值. 比如我们可以写

(begin (+ 1 2) (+ 3 4))

它的返回是 7.

无名的能量之源

接下来, 我们就要接触到 Scheme 的灵魂 --- Lambda. 大家可以注意到 drScheme 的图标, 那就是希腊字母 Lambda. 可以说明 Lambda 运算在 Scheme 中是多么重要.

NOTE: 这里本来应该插一点 Lambda 运算的知识的, 但是一来我自己数学就不怎么好没什么信心能讲好, 二来讲太深了也没有必要. 大家如果对 Lambda 运算的理论有兴趣的话, 可以自行 Google 相关资料.

Lambda 能够返回一个匿名的函数. 在这里需要注意两点: 第一, 我用的是 "返回" 而不是 "定义". 因为 Lambda 同样可以看成一个函数 --- 一个能够生成函数的函数. 第二, 它是匿名的, 意思是, 一个函数并不一定需要与一个名字绑定在一起, 我们有时侯需要这么干, 但也有很多时候不需要.

我们可以看一个 Lambda 函数的基本例子:

((lambda (x y) (+ x y)) 1 2)

这里描述了一个加法函数的生成和使用. (lambda (x y) (+ x y)) 中, lambda 的第一个参数说明了参数列表, 之后的描述了函数的行为. 这就生成了一个函数 , 我们再将 1 和 2 作用在这个函数上, 自然能得到结果 3.

我们先引入一个 define 的操作, define 的作用是将一个符号与一个对象绑定起来. 比如 (define name 'kyhpudding) 之后再敲入 name, 这时候 Scheme 解释器就知道如何处理它了, 它会返回一个 kyhpudding.

我们自然也可以用 define 把一个符号和函数绑定在一起, 就得到了我们常用的有名函数.

(define add
        (lambda (x y) (+ x y)))

做一个简单的替换, 上面的例子就可以写成 (add 1 2), 这样就好理解多了.

上面的写法有点晦涩, 而我们经常用到的是有名函数, 所以我们有一个简单的写法, 我们把这一类简化的写法叫 "语法糖衣". 在前面我们也遇到一例, 将 (quote x) 写成 'x 的例子. 上面的定义, 我们可以这样写

(define (add x y) (+ x y))

Lambda 运算有极其强大的能力, 上面只不过是用它来做传统的 "定义函数" 的工作. 它的能力远不止如此. 这里只是举几个小小的例子:

我们经常会需要一些用于迭代的函数, 比如这个:

(define (inc x) (+ x 1))

我们也需要减的, 乘的, 还有其他各种乱七八糟的操作, 我们需要每次迭代不是 1, 而是 2, 等等等等. 我们很自然地有这个想法: 我们写个函数来生成这类迭代函数如何? 在 Scheme 中, 利用 lambda 运算, 这是可行且非常简单的. 因为在 Scheme 中, 函数跟普通对象是有同样地位的, 而 "定义" 函数的 lambda, 其实是能够动态地为我们创造并返回函数对象的. 所以我们可以这么写:

(define (make-iterator method step)
        (lambda (x) (method x step)))

没有语法糖衣的写法是:

(define make-iterator
        (lambda (method step)
                (lambda (x) (method x step))))

这个简单的例子, 已经能够完成我们在 C 之类的语言无法完成的事情. 要生成上面的 inc 函数, 我们可以这么写:

(define inc (make-iterator + 1))

这个例子展示的是 Scheme 利用 Lambda 运算得到的能力. 利用它, 我们可以写出制造函数的函数, 或者说制造机器的机器, 这极大地扩展了这门语言的能力 . 我们在以后会有更复杂的例子.

接下来, 我们会介绍 Scheme 的一些语言特性是怎么用 Lambda 运算实现的 --- 说Scheme 的整个机制是由 Lambda 驱动的也不为过.

比如, 在 Scheme 中我们可以在任何地方定义 "局部变量", 我们可以这么写:

(let ((x 1) (y 2)) 运用这些局部变量的语句)

其实 let 也只不过是语法糖衣而已, 因为上面的写法等价于:

((lambda (x y)
         运用这些局部变量的语句)
1 2)

一些常用的函数

虽然说这篇文章不太注重语言的实用性. 但这里还是列出我们经常用到的一些操作,这能极大地方便我们的编程, 大家也可以想想他们是怎么实现的.

- cond

相当于 C 中的 switch

(cond
(条件1 执行体)
(条件2 执行体)
(else 执行体))

- 循环语句

没有循环语句...... 至少没有必要的循环语句. Scheme 认为, 任何的循环迭代都
可以用递归来实现. 我们也不用担心递归会把栈占满, 因为 Scheme 会自动处理尾递
归的情况. 一个简单的 0 到 10 迭代可以写成这样.

(define (iterate x)
        (if (= x 10)
            x
            (iterate (+ x 1))))
(iterate 0)

很明显, 当我们递归调用 iterate 的时候, 我们不必保存当前的函数环境. 因为我
们递归调用完毕后就马上返回, 而不会再使用当前的环境, 这是一给尾递归的例子.
Scheme 能自动处理类似的情况甚至做一些优化, 不会浪费多余的空间, 也不会降低
效率. 所以完全可以代替循环.

当然我们有些便于循环迭代的操作, 大家可以试试自己实现他们. (当然在解释器内
部通常不会用纯 scheme 语句实现他们). 我们最常用的是 map 操作

(map (lambda (x) (+ x 1)) '(1 2 3))

运行一下这个例子, 就能理解 map 的作用了.

- 更多的数据操作

    * cadr cddr caddr 之类, 就是 car 和 cdr 的组合, 大家可以一个个试. drScheme 支持到 cadddr...
    * append: 将两个列表拼接在一起.

[scheme学习笔记]递归插入排序

对数表进行排序,排序函数读入一个表,产生另一个表

即

;; sort : list-of-numbers  ->  list-of-numbers 
;; to create a sorted list of numbers from all the numbers in alon
(define (sort alon) ...)

例子为:

(sort empty)
;; expected value: 
empty

(sort (cons 1297.04 (cons 20000.00 (cons -505.25 empty))))
;; expected value: 
(cons 20000.00 (cons 1297.04 (cons -505.25 empty)))

如果输入为empty.则输出empty

因为sort是递归定义的.所以可以得出函数的模板为:

(define (sort alon)
  (cond
    ((empty? alon)empty)
    (else (...(first alon)...(sort (rest alon))))))

接着,需要处理的就是sort函数cond字句的第二部分.该部分包含两个表达式.先弄清楚他们结果分别是什么.

1.(first alon)输出数表的第一个数

2.(sort(rest alon))是对数表的剩下部分进行排序的结果

则可以知道.这个字句需要做的就是将(first alon)插入到表(sort(rest alon))中.

要讲数插入表.必须历遍整个表

此处,可以定义一个函数insert,它以一个数和一个表为参数.输出一个表.

insert定义如下:

;; insert : number list-of-numbers  ->  list-of-numbers
;; to create a list of numbers from n and the numbers on alon 
;; that is sorted in descending order; alon is already sorted
(define (insert n alon) ...))

如此.就可以给出sort的定义

(define (sort alon)
  (cond
    ((empty? alon) empty)
    (else (insert (first alon) (sort (rest alon))))))

现在.cond第二个字句的意义清晰了.要产生最终值.可先取出非空表的第一个数.再对其它部分进行排序.最后把前者插入到后者的合适部分.

剩下的部分就是对insert进行设计.

首先考虑insert做什么事情.

下面是例子

第一种情况

(insert 5 empty)
;; expected value: 
(cons 5 empty)

如果insert的第二个参数是非空表,

则第二种情况为

(insert 1297.04 (cons 20000.00 (cons -505.25 empty)))
;; expected value: 
(cons 20000.00 (cons 1297.04 (cons -505.25 empty)))

可以给出函数的模板

(define (insert n alon)
  (cond
    ((empty? alon) ...)
    (else  ...  (first alon) ... (insert n (rest alon)) ...)))

首先给出的表达式的结果

(first alon)得到的是数表的第一个数

(insert n(rest alon))得到一个排序完成的数表

接着考虑.insert的第二个参数为非空表时,可能出现以下两种情况

1.n>=(first alon) 因为alon是一个有序表,所以alon中所有数都不不会大于n,则用cons 把n 和alon组合在一起

2.n<(first alon).即

(insert 3 (cons 6 (cons 2 (cons 1 (cons -1 empty)))))

即(first alon)是6

(insert n (rest alon))是(cons 3 (cons 2 (cons 1 (cons -1 empty))))

这样的情况时.(first alon)是最大的数.所以它排在第一位,而n要插入(rest alon)之中.

这样.得到最终结果

(cons (first alon) (insert n (rest alon)))

于是.得到完整定义:

;; sort : list-of-numbers  ->  list-of-numbers (sorted)
;; to create a list of numbers with the same numbers as
;; alon sorted in descending order
(define (sort alon)
  (cond
    [(empty? alon) empty]
    [(cons? alon) (insert (first alon) (sort (rest alon)))]))

;; insert : number list-of-numbers (sorted)  ->  list-of-numbers (sorted)
;; to create a list of numbers from n and the numbers on
;; alon that is sorted in descending order; alon is sorted
(define (insert n alon)
  (cond
    [(empty? alon) (cons n empty)]
    [else (cond
            [(>= n (first alon)) (cons n alon)]
            [(<  n (first alon)) (cons (first alon) (insert n (rest alon)))])]))

ubuntu11.10安装virtualbox,虚拟winXP.笔记

自从上次安装wine跑qq失败以后.阴影一直笼罩着我.而且webqq升级成q+以后.因为网速问题我就再也没成功登录过想到下学期铁通帐号过期,就必须用学校规定的闪讯.我就在为怎么在ubuntu下联网发愁.看了半天教程不过貌似都是过期的.闪讯一升级就不能用了.可是在win里我qq都没跑起来.更别说闪讯了.折腾了一天折腾得我斗志全无而且毫无收获.

今天想起来还是用virtualbox比较靠谱.

我直接贴原帖好了.

virtualbox虚拟机安装:

http://lhflinux.blog.51cto.com/1961662/515811

http://elesson.tceb.edu.tw/~yunol/VirtualBox/

至于客机我安装的是深度xp 精简版.

下载地址在这里:

DeepinXP_V5.6.iso
thunder://QUFodHRwOi8vZGVlcGluLjUyenkuY29tL1s1XURlZXBpblhQX1Y1Nl81Mnp5LmNvbS5pc29aWg==

深度5.6 最纯净GHOST系统
FAT32
thunder://QUFmdHA6Ly9kb3duOmRvd25AMjE4LjkwLjI0MC4xOTQ6MjEyMS9kNTZmYXQzMi5naG9aWg==

NTFS
thunder://QUFmdHA6Ly9kb3duOmRvd25AMjE4LjkwLjI0MC4xOTQ6MjEyMS9kcDU2bnRmcy5naG9aWg==

装好以后.发现virtualbox无法安装增强功能.google了一下重新下了一个VBoxGuestAdditions.iso.

地址如下:

http://download.virtualbox.org/virtualbox/2.0.4/VBoxGuestAdditions_2.0.4.iso

接着装了 qq2008.

闪讯的问题等我有了闪讯帐号不用铁通了再说吧.

« 上一页 1 2 3 4 5 6 7 下一页 »