October 18, 2006

Scheme数据结构——list数组

(By the way,我终于知道如何删除list的头节点了。必须要使符号指向一个头节点,再由它确定当前节点,否则无非实现元素“脱链”)

list数组,顾名思义,由list构成的数组(或矩阵),学名不明。它不是一种具体的数据结构,但常被用作表示其它数据结构。它的一般形式如下:
当然,这里的vector也可以是一个矩阵。用Scheme实现时,注意list不需要随机插入元素的功能,但能随机脱链,且只能从尾部插入(技巧:(set-cdr! (list-tail l (- (length l) 1)) obj))——list中的数据往往是无序的。可以把它设计得更强,但并不实用。
下面讲它的两种典型应用。

一. 图的邻接表存储结构
  • 用矩阵的第一列存储结点,第二列存储结点的号码,第三列保存此行所对应结点链接的边的结束结点号码(当然还可以再用一列保存权值)。这样说有点绕人,我们看个例子好了:
  • 这是一个有向图。让我们看看它是怎样用邻接表存储的:
  • 复杂吗?吓,一点也不。它可以用来对付边较稀疏的有向图。
二. 链表法解决哈希冲突
  • 讲解哈希表关键字冲突的一般思路是建立哈希函数组,逐个调用。但这个方法有个明显缺点:如果把哈希表作为一种服务提供给操作对象的话用户就麻烦大了。用向量上链接的list来保存hash code相同的元素是个不错的办法。
  • 例子:这个哈希表的元素是 a={16, 54, 66, 43, 29, 55...},m=13,哈希函数为 h(K)=K mod m(省略了其它7个元素):
  • 用矩阵的第一列存储基本元素,多于的“同位素”保存在临时开辟的list中。这样的设计重点考虑了效率,比较使用,但会给元素的删除带精神分裂般的麻烦,插入元素也够戗;如果你追求程序的“漂亮”,可以把所有元都平起平坐地存储在list里,不使用矩阵,元素的删除操作全是脱链。
从上面两个例子可以看出,list数组主要用于解决稀疏的“同位素”的存储问题。确定“同位素”的同位存储性质(比如同hash code元素的平等地位)和必要性(比如有向图结点拥有边与其起始结点的偏序关系),是使用它的重要前提。

No comments: