October 9, 2006

Scheme数据结构——神奇的pair

Scheme中提供了两种可以存储泛型数据的数据结构——list和vector。list其实是一个链表,它是由pair实现的。学了Scheme很久才发现,原来pair其实是其它语言中我们超常用的Node(节点)!这下我总算理解了Scheme是怎样架起数据结构的了。

一. 链表(内部已实现)
  • 每个pair的左值存储数据,右值存放指针(Scheme中cons值即引用):
  • 然后用指针指向(其实是赋值)下一个pair,链中最后一个为null(空值):
  • 这个语法树转换成Scheme代码就是(value . (value . (value . null)));当然只是“意思”一下,实际不可能有同名符号。
二. 二叉树(正在编写中…)
  • 又一个用节点连起来的基本数据结构。每个二叉树child(孩子)可以这样设计,用第一个pair的左值保存数据,右值为另一个pair,它的左右值表示孩子的指针:
  • 代码为(value . (left . right))
  • 然后,n个这样的child组合为一棵二叉树。同样,没有孩子时指针为null:
  • 上面这棵树的代码大致是这样:(value . ((value . ((value . (null . null)) . (value . (null . null)))) . (value . (null . null))))。
  • 我的二叉树实现正在写着,面前至少可以用(child)代替(cons(cons))申明孩子节点,下一步编写tree的整个数据结构支持,最好能支持一次例遍。
有了链表和二叉树,队列,栈,线索二叉树之类就都能直接实现了。其它的数据结构如集合,树,图,HashTable等等多是由向量+pair构成的,不典型,暂且不提。

No comments: