Question

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 类似