October 21, 2006

献给新访客的一则笑话——古老,但很神奇

  • 诶,我的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;

for(int i=0;inext;
}
psecond=head;
while(pfirst!=NULL) {
pfirst=pfirst->next;
psecond=psecond->next;
} //什么破编程风格,真实版初学者啊
for(int i=0;idata)
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演算理论的函数式编程,古老,但很神奇。 参考资料:

1 comment:

Anonymous said...

welstar Take a piece of me