- 诶，我的Blog已经很久没更新了——得菌痢住院5天啦，今天终于出来啦！
- Lava-Lava平台上“科技自主创新网”部落的同仁们可能已经看到了我的Blog荣幸进入你们的“酋长推荐”标签页，但似乎没有人给我的文章留下评论。我估计这是大家都没有接触过Scheme语言的缘故。所以我决定写一篇这样的文章，让新来的访客们看一看Scheme时间的精彩——当然，我没有要贬低其它语言（除了Java）的意思，事实上我最喜欢的语言之一就是C。好了，不罗嗦了，让我们一起来推开Scheme那道门吧。
人物：XX大学计算机系的社友Go4——8呆，F1，老农和小四。
时间：“晚汇报”时间…
（老农在计算机系混的时间不短了，可惜技术一直没长进——连打电脑游戏都“不上档次”（小四语）。这不，昨天打CS又被F1欺负了，现在正郁闷着呢。）
老农（上网无聊中）：这年头，电脑好的人就是吃香啊~~（旁白）俺编程也差，游戏也差，废啦~~有了，上CSDN.net，找点文章进修一下。
F1：老农，怎么样，CS技术不行啊！好好练啊！
小四（推推眼镜）：老农伯伯！算了吧，我看你还是把编程学学好吧，哈哈，你那本《数据结构》好像还是新的吧？
（老农翻着最新的Blog文章，忽然眼睛一亮。）
小四：嘿，发现什么了？
老农（连忙把Firefox最小化）：没什么，又不是黄网激动什么？！
老农（旁白）：不错，就用这篇文章K.O.他们。
老农（满脸堆笑）：嘿，你们仨过来，我在网上发现一道数据结构方面的面试题目，想不想试试？
（正在上铺捧着SICP发呆的8呆忽然从发呆状态切换到亢奋状态，人啊~~）
8呆：废话，快说！
老农（奸笑中）：设计一个函数visit_tail，要求通过一次遍历找到链表中倒数第n个节点，然后从它开始用函数func例遍后面的所有链表元素，链表可能相当大，可使用辅助空间，但是辅助空间的数目必须固定，不能和n有关。还有，不需要给出链表的其它操作函数。
8呆（再次切换回发呆状态）：无聊…这也能叫题目…
老农（怒）：那你做啊！
（8呆在他的SICP上写了点什么，然后很潇洒地离开了寝室）
老农（专向另两个人）：既然他不参加，那我们三个比吧。
小四、F1（信心实足）：那现在开始计时吧。
……
（老农把刚才背下来的代码改了改，花了3分钟抄在终端里）
老农（觉得时机移到）：我好了，你们呢？
小四（大喊）：解决解决！
F1：恩，我也好了，只是还没做单元测试。
（老农、小四：寒~~）
（3个人凑在老农的电脑上开始比拼）
老农：你们看，我是用C写的，已经测试过的，思想是，用两根指针，第一根先出发，相距n步后第二根出发。然后同时步进，直到第一根指针达到末尾，然后用func()函数对第二个指针开始的子链表进行例遍。
（小四和F1仔细一看，大笑不止。老农的代码如下（注释是笔者所加，其实是F1和小四看到各句时的反应）：）
typedef struct{ //哟，终于不用struct Node了，
int data;
Node * next;
} Node;
Node * visit_tail(iNode * head,int n,void (* func)(int cur)){ //K&R时代的函数指针，见到老佛爷啦！！
Node *pfirst; //吓，终于用到匈牙利命名法了（老农：寒~）
Node *psecond;
pfirst=head;
}
psecond=head;
while(pfirst!=NULL) {
pfirst=pfirst->next;
psecond=psecond->next;
} //什么破编程风格，真实版初学者啊
for(int i=0;i
psecond=psecond->next;
}
} //靠，一个函数解决所有问题，高耦合啊！
老农（再怒）：小四少罗嗦！你的呢！
小四：在这儿，好好学学吧！
（大家一看，小四也用了C，但…好漂亮啊。代码如下（注释是小四的解释）：）
typedef int int
//没有C++一样“泛型”！
typedef struct {
T data;
Node * next;
} Node;
typedef struct {
Node * pre;
Node * curr; //当前结点与List绑定，不但可以分步例遍，还能保证正确初始化
} List;
void init_curr (List * l) {
l->curr = l->pre; //什么叫“编程风格”，知道不？！
}
void visit (List *l, void (* func)(T data)) {
while (l-curr) { //少用!=NULL
(* func)(l-curr->data);
l-curr = l->curr->next;
}
} //使用内联结点的公用访问函数，降低耦合
void index (List * l, int n) {
if (n) return NULL; //结点下标从1开始
init_curr(l);
if (n > 0) {
for (int i = 0; i <>curr = l->curr->next;
} //小四（自我陶醉）：漂亮啊
if (n < n =" -n;" tmp =" l-">curr;
for (int i = 0; i < tmp =" tmp-">next;
}
while (tmp) {
l->curr = l->curr->next;
tmp = tmp->next;
}
}
return l->curr; //方便用户，增强鲁棒性能
}
void visit_tail (List * l, int n, void (* func)(T data)) {
index(l, -n);
visit(l, func);
} //多清爽
老农（倒）：我的挽回面子计划就这么，完了…
小四（偷笑）：你还是面对现实吧…
F1：小四你先别得意，我的你们还没拜读过呢！
（大家跑到F1电脑前一看，先是被长度吓了一跳，然后，无语。）
package datastruct.fifi.com.baidu.hi; //加入我的数据结构Java包
//当然只有包内成员才能创建Node对象
protected class Node {
private Object data; //多态性，让你们的typedef去死吧！
private Node next;
//构造函数
Node (data) {
this.data = data;
}
//获取下一个元素
public Node next () {
return this.next;
}
protected void setNext (o) {
this.next = o;
}
//取数据
public Object getData () {
return this.data;
}
//换数据
public void setData (data) {
this.data = data;
}
//根据Effective Java的最高指导，要重写toString()方法
public String toString () {
return this.data.toString();
}
//自定义异常类，数据结构下标越界
public class IndexOutOfRangeException extend IndexOutOfBoundsException {
public IndexOutOfRangeException (int lower, int upper, int index) {
super("Lower: " + lower +", Upper: " + upper + ", index: " + index);
}
}
//用于被继承的访问类
public class Visitor {
public operation (Object o) { //访问操作
System.out.println(o);
}
public class List {
private Node preFix;
private Node current;
private int size;
List () {
current = preFix = new Node();
size = 0;
}
//自定义异常类，数据结构下标越界
public class IndexOutOfRangeException extend IndexOutOfBoundsException {
public IndexOutOfRangeException (int lower, int upper, int index) {
super("Lower: " + lower +", Upper: " + upper + ", index: " + index);
}
}
//用于被继承的访问类
public class Visitor {
public operation (Object o) { //访问操作
System.out.println(o);
}
}
public class List {
private Node preFix;
private Node current;
private int size;
List () {
current = preFix = new Node();
size = 0;
}
//定位函数
private void index (int i) throws IndexOutOfRangeException {
if (i > size || i < -size-1) { thows new IndexOutOfRangeException(0, size+1, i); } this.init(); if (i >= 0) {
for (int j=0; j < current =" current.next();" i =" -" j="0;" current =" current.next();" current =" current.next();">_< 。。。 F1：we得意。 （3人正在争执着，忽然门“吱”的一声（什么破门）开了，8呆走了进来。） 8呆：吵什么呢，比完了没？我是第一吧？ F1、小四、老农：什么啊，你不是自顾自走了啦？！ 8呆（诧异）：我走之前已经写好啦。 （8呆拿来他的SICP，只见上面写了一行Scheme代码：） (define (list-visit-tail l n func) (for-each (list-tail l n) func)) （编辑公曰：上面这段Scheme代码滴意思斯酱紫滴：先定义一个名为list-visit-tail的过程，然后用内置宏list-tail取list的后n位组成list返回，再用操作for-each进行例遍。） （完） 结语： 这个题目其实对于任何函数式编程语言来说都是一两句话。Scheme、Haskell它们都来自于世界上第二古老的语言Lisp，但它们的思想博大精深——基于lambda演算理论的函数式编程，古老，但很神奇。 参考资料：
- 老农说的“这篇文章”：一次遍历找链表倒数第n个节点
- 8呆的书SICP：Structure and Interpretation of Computer Programs
- 命令式语言的劣势：为何 Java（以及很多其他编程语言）令人不爽
- 函数式语言的优势：为什么函数式编程至关重要？
- Scheme入门推荐书：Teach Yourself Scheme in Fixnum Days
- 如果你还没学过编程的话：How to Design Programs
- 其它有关Scheme的东东详见：我的Scheme学习笔记(1 2 3 4 5)
