练习题

10.3-1

多重数组

key :13, 4, 8, 19, 5, 11

next:1, 2, 3, 4, 5, -1

pre:-1, 0, 1, 2, 3, 4

单数组：

13, 3, -1, 4, 6, 3, 8, 9, 6, 19, 12, 9, 5, 15, 12, 11, 18, 15

10.3-2

ALLOCATE-OBJECT()
1    if free = NIL
2        then error "out of space"
3        else x <- free
4               free <- A[x+1]
5               return x
FREE-OBJECT(x)
1    A[x+1] <- free
2    free <- x

10.3-3

在这里prev域没有

在这里在这里prev域没有意义，用不到

10.3-4

见10.3-4

假设当前的数组是紧凑的，即数组中有f个元素，都位于数组的前f个位置

分配一个新的元素时，把f+1的位置分配给它

删除一个元素时，假设待删除的元素的位置是i，先修改元素prev[i]的next指针和元素next[i]的prev指针，删除这个元素。这里数组中间就留下一个空位，让第f个元素填充这个空位，具体方法是修改元素prev[f]的next指针和元素next[f]和prev指针

10.3-5

与10.3-4类似