数据结构之指针和对象

doMore 1,308 2020-03-02

当某些语言不支持指针和对象类型的数据时,应当如何实现他们呢?

对象的多数组表示

对象的每个属性使用一个数组表示,可以用来表示一组有相同属性的对象。

指针.jpg

上图,key数组存放该动态集合中现有的关键字,指针则分别存储在next和prev中。对于一个给定的数组下标x,key[x]、next[x]、prev[x]一起表示一个对象。

对象的但数组表示

计算机内存中的字往往从整数 0 到 M-1 进行编址,其中M是一个足够大的整数。一个对象在计算机内存中占据一组连续的存储单元。指针仅仅是该对象所在的第一个存储单元的地址,要访问对象内其他存储单元可以在指针上加一个偏移量。

单数组指针.jpg

一个对象占用一段连续的子数组A[j...k],对象中的每个属性对应于从0到k-j之间的一个偏移量,指向该对象的指针就是下标j,上图中对应属性key、next、prev的偏移量分别是0、1、2。这种单数组的表示方法比较灵活,因为它允许不同长度的对象存储在同一个数组中。管理一组异构的对象比管理一组同构的对象更困难。

对象的分配和释放

向一个双向链表表示的动态集合中插入一个关键字,就必须分配一个指向该链表表示中尚未分配利用的对象的指针。因此,有必要对链表中尚未利用的对象空间进行管理,使其能够被分配。比如:在java中这个工作由**垃圾回收器(garbage collector)**负责确定哪些对象是没有被使用的。在某些简单情况下,可由自己负责将未使用的对象返回给存储管理器。

假设多数组表示法中的各数组长度为 m,且在某一时刻该动态集合含有 n小于等于m个元素。则n个对象代表现存于该动态集合中的元素,而余下的m-n的能够存放对象的空间是自由的(free,即空闲的)

我们把自由对象保存在一个单链表中,成为自由表(free list)。自由表只使用next数组,该数组只存储链表中的next指针。自由表的头保存在全局变量free中。当链表L表示的动态集合非空时,自由表和链表L可能会相互交错。如下图所示:

对象的分配与释放.jpg

注意:该表示中的每个对象不是全在链表L中,就再自由表中,但不会同时属于同一个表。

自由表就类似一个栈:下一个被分配的对象就是最后被释放的那个。
利用栈的 PUSH 和 POP 的链表实现形式来实现分配和释放对象的过程。
假设下述过程中的全局变量 free 指向自由表的第一个元素:

ALLOCATE-OBJECT()
if free == NIL
ERROE "out of space"
else x == free
free = x.next
return x

FREE-OBJECT()
x.next = free
free = x

初始时自由表含有全部n个未分配的对象。一旦自由表用完,在运行ALLOCATE-OBJECT就会报错。我们甚至可以让多个链表公用一个自由表。

上述的两个过程时间复杂度都为 O(1),因而是非常实用的。

可以将其改造,让对象中的任意一个属性都可以像自由表的next属性一样使用,从而使其对任何同构的对象数组都适用。