10.3 Implementing pointers and objects

10.3-1

Draw a picture of the sequence \(\langle 13, 4, 8, 19, 5, 11 \rangle\) stored as a doubly linked list using the multiple-array representation. Do the same for the single-array representation.

A multiple-array representation with \(L = 2\),

\[ \begin{array}{|r|c|c|c|c|c|c|c|} \hline index & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\\ \hline next & & 3 & 4 & 5 & 6 & 7 & \diagup \\\\ \hline key & & 13 & 4 & 8 & 19 & 5 & 11 \\\\ \hline prev & & \diagup & 2 & 3 & 4 & 5 & 6 \\\\ \hline \end{array} \]
A single-array version with \(L = 1\),

\[ \begin{array}{|r|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline index & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 \\\\ \hline key & 13 & 4 & \diagup & 4 & 7 & 1 & 8 & 10 & 4 & 19 & 13 & 7 & 5 & 16 & 10 & 11 & \diagup & 13 \\\\ \hline \end{array} \]

10.3-2

Write the procedures \(\text{ALLOCATE-OBJECT}\) and \(\text{FREE-OBJECT}\) for a homogeneous collection of objects implemented by the single-array representation.

C++
ALLOCATE-OBJECT()
    if free == NIL
        error "out of space"
    else x = free
        free = A[x + 1]
        return x

C++
FREE-OBJECT(x)
    A[x + 1] = free
    free = x

10.3-3

Why don't we need to set or reset the \(prev\) attributes of objects in the implementation of the \(\text{ALLOCATE-OBJECT}\) and \(\text{FREE-OBJECT}\) procedures?

We implement \(\text{ALLOCATE-OBJECT}\) and \(\text{FREE-OBJECT}\) in the hope of managing the storage of currently non-used object in the free list so that one can be allocated for reusing. As the free list acts like a stack, to maintain this stack-like collection, we merely remember its first pointer and set the \(next\) attribute of objects. There is no need to worry the \(prev\) attribute, for it hardly has any impact on the resulting free list.

10.3-4

It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first \(m\) index locations in the multiple-array representation. (This is the case in a paged, virtual-memory computing environment.) Explain how to implement the procedures \(\text{ALLOCATE-OBJECT}\) and \(\text{FREE-OBJECT}\) so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (\(\textit{Hint:}\) Use the array implementation of a stack.)

C++
ALLOCATE-OBJECT()
    if STACK-EMPTY(F)
        error "out of space"
    else x = POP(F)
        return x

C++
FREE-OBJECT(x)
    p = F.top - 1
    p.prev.next = x
    p.next.prev = x
    x.key = p.key
    x.prev = p.prev
    x.next = p.next
    PUSH(F, p)

10.3-5

Let \(L\) be a doubly linked list of length \(n\) stored in arrays \(key\), \(prev\), and \(next\) of length \(m\). Suppose that these arrays are managed by \(\text{ALLOCATE-OBJECT}\) and \(\text{FREE-OBJECT}\) procedures that keep a doubly linked free list \(F\). Suppose further that of the \(m\) items, exactly \(n\) are on list \(L\) and \(m - n\) are on the free list. Write a procedure \(\text{COMPACTIFY-LIST}(L, F)\) that, given the list \(L\) and the free list \(F\), moves the items in \(L\) so that they occupy array positions \(1, 2, \ldots, n\) and adjusts the free list \(F\) so that it remains correct, occupying array positions \(n + 1, n + 2, \ldots, m\). The running time of your procedure should be \(\Theta(n)\), and it should use only a constant amount of extra space. Argue that your procedure is correct.

We represent the combination of arrays \(key\), \(prev\), and \(next\) by a multible-array \(A\). Each object of \(A\)'s is either in list \(L\) or in the free list \(F\), but not in both. The procedure \(\text{COMPACTIFY-LIST}\) transposes the first object in \(L\) with the first object in \(A\), the second objects until the list \(L\) is exhausted.

C++
COMPACTIFY-LIST(L, F)
    TRANSPOSE(A[L.head], A[1])
    if F.head == 1
        F.head = L.head
    L.head = 1
    l = A[L.head].next
    i = 2
    while l != NIL
        TRANSPOSE(A[l], A[i])
        if F == i
            F = l
        l = A[l].next
        i = i + 1

C++
TRANSPOSE(a, b)
    SWAP(a.prev.next, b.prev.next)
    SWAP(a.prev, b.prev)
    SWAP(a.next.prev, b.next.prev)
    SWAP(a.next, b.next)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用