`
阿尔萨斯
  • 浏览: 4107195 次
社区版块
存档分类
最新评论

Lisp语言:可变长数组

 
阅读更多

之前讨论的数组都是定长数组,定长数组最大的问题就是数组的长度不能动态改变。如果定义数组时定义的数组长度不够,数组满了就不能另外添加元素,如果数组定义的长度太长,又浪费内存空间。

为了应对这个问题,我们需要一个可以动态改变长度的数组。讨论到这时c程序员会想到链表,而java程序员可能会想到Vector,它们都通过一定的性能牺牲实现了可变长度的数组。Lisp中也有类似的数据结构,可以称之为可变长数组,在Lisp中可变长数组是通过make-array函数的fill-pointer和adjustable关键字实现的。

有一点需要留意的是Common Lisp语言中有使用vector关键字,通过vector可以简单定义一个一维数组。不过,通过vector函数创建的数组并不是一个可变长数组。

下面就是vector定义的样例:

(setf test-array-3 (vector 'a 'b 'c 10 "my string"))
以上代码创建了一个一维数组,成员有A B C 10 "my string",对于这个数组可以使用一般的数组函数进行操作,如下面的操作都是合法的:
    (format *query-io* "length : ~a~%" (length test-array-3))
        (format *query-io* "element 2: ~a ~%" (aref test-array-3 2))
用(length test-array-3)可以返回数组的长度,用(aref test-array-3 2)可以返回数组第3个元素。

不过以上这个数组不是一个可变长数组。


Common Lisp中可变长数组也是通过make-array函数创建的,不过需要加上:fill-pointer和:adjustable参数。

:fill-pointer和:adjustable都是关键字参数,也就是说参数后面需要带一个值。

:fill-pointer被称为填充指针,后面带一个数字做为参数值,指向下一个填充的位置。

下面是:fill-pointer使用的样例:

(setf test-array-4 (make-array 5 :fill-pointer 4 :initial-element 'xx ))
以上定义了一个长度为5的数组,初始值为xx,而:fill-pointer值为4,那么这个数组事实上的长度只有4。因为下一个填充位置为4,则数组中有下标为0, 1, 2, 3这四个元素。

定义数组时使用了:fill-pointer后,就可以使用vector-push函数为这个数组添加元素。不过,数组中最终的个数不能超过定义时指定的长度,对于上面的test-array-4来讲就是不能超过5个元素。

vector-push函数使用的样例如下:

        (vector-push 'new-value1 test-array-4)
以上样例在test-array-4数组的最后一个元素后面添加了一个元素,值为“new-value1”。

注意,应为上面的样例将test-array-4的长度定义为5,所以当test-array-4数组中的元素数量达到5时,再次对test-array-4执行vector-push会报错的。


所以说,只设置了fill-pointer的数组还不是一个完美的可变长数组,虽然数组长度确实可以通过vector-push函数改变,但是最终的长度还是受限于数组所定义的长度。

为了突破数组长度的限制,需要在数组定义时使用:adjustable参数,后面带t作为参数值,样例如下:

        (setf test-array-4 (make-array 5 :fill-pointer 4 :initial-element 'xx :adjustable t))
同样是定义了一个长度为5的数组,不过这次我们使用了:adjustable参数,当数组长度不够长时系统会自动扩展数组长度。

另外,为了让数组长度进行扩展,我们在添加元素时不能使用vector-push函数,而需要使用vector-push-extend函数,如:

(vector-push-extend 'new-value2 test-array-4)
以上代码在数组test-array-4最后一个元素后面添加一个元素,值为"new-value2"。如果执行这个语句时test-array-4中元素的数量已经达到或超过数组定义的长度,系统会自动扩展数组长度。

这样使用起来就比较方便了,可以随意地向数组添加元素。在使用过程中,如果希望获得数组的某个元素,可以像定长数组一样使用aref函数,如:

(aref test-array-4 3)
以上代码会返回数组test-array-4中的第四个元素。

另外,对于可变长的数组,准确地说,对于带:fill-pointer的数组,可以使用vector-pop函数获得数组最后一个元素,同时将这个元素从数组中移除。

这样就可以像使用堆栈一样使用数组了,通过push将元素压进栈,通过pop将元素弹出栈。

vector-pop函数的使用样例如下:

(vector-pop test-array-4)
以上代码弹出数组test-array-4中的最后一个元素。

注意,通过vector-pop弹出数组中的元素并不会减少数组的最大长度。如以上定义的test-array-4,如果我们通过多次的vector-push-extend将数组的长度扩展到10,这时通过vector-pop弹出一个元素后test-array-4的最大长度仍为10,不会减少为9。好处就是这时我们可以通过vector-push给test-array-4添加元素了,不需要使用vector-push-extend。


下面是完整的可变长数组的使用样例:

(defun array-test-4 ()
        (setf test-array-4 (make-array 5 :fill-pointer 4 :initial-element 'xx :adjustable t))

        (format *query-io* "array-test-4 is: ~a ~%" test-array-4)

        (vector-push 'new-value1 test-array-4)
        (vector-push-extend 'new-value2 test-array-4)

        (vector-push-extend 'new-value3 test-array-4)
        (format *query-io* "array-test-4 is: ~a ~%" test-array-4)

        (vector-pop test-array-4)
        (format *query-io* "array-test-4 is: ~a ~%" test-array-4)
        (vector-push 'new-value4 test-array-4)

        (format *query-io* "array-test-4 is: ~a ~%" test-array-4)


)

对应的执行结果如下:




分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics