10.3

Exercises 10.3-1

---

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

Answer

<pre><code>+---+ | L |-------------------------------------------+ +---+ V 1 2 3 4 5 6 7 8 9 10 11 12 +----+----+----+----+----+----+----+----+----+----+----+----+ next | | | 5 | 7 | 10 | | / | | 3 | 4 | | | +----+----+----+----+----+----+----+----+----+----+----+----+ key | | | 4 | 5 | 8 | | 11 | | 13 | 19 | | | +----+----+----+----+----+----+----+----+----+----+----+----+ prev | | | 8 | 10 | 2 | | 4 | | / | 5 | | | +----+----+----+----+----+----+----+----+----+----+----+----+ </code></pre> <pre><code> +----+----+----+ | key|next|prev| +----+----+----+ 13 is head. 1 2 3 4 5 6 7 8 9 10 11 12 +----+----+----++----+----+----++----+----+----++----+----+----++-- | 4 | 7 | 13 || 5 | 10 | 16 || 8 | 16 | 1 || 11 | / | 4 || +----+----+----++----+----+----++----+----+----++----+----+----++-- 13 14 15 16 17 18 --++----+----+----++----+----+----+ || 13 | 1 | / || 19 | 4 | 7 | --++----+----+----++----+----+----+ </code></pre>

Exercises 10.3-2

---

Write the procedures ALLOCATE-OBJECT and FREE-OBJECT for a homogeneous collection of objects implemented by the single-array representation.

Answer

implementation

Exercises 10.3-3

---

Why don't we need to set or reset the prev fields of objects in the implementation of the ALLOCATE-OBJECT and FREE-OBJECT procedures?

Answer

因为这类似于一个栈，没有prev.

Exercises 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 the procedures ALLOCATE>- OBJECT and FREE-OBJECT can be implemented so that the representation is compact. Assume that there are no pointers to elements of the linked list outside the list itself. (Hint: Use the array implementation of a stack.)

Answer

• ALLOCATE:选free_list的head.
• FREE-OBJECT:不是直接变成head,而是按sorted的方式插入.

这样可以保证每次分配的时候取排在最前面的空位置

Exercises 10.3-5

---

Let L be a doubly linked list of length m stored in arrays key, prev, and next of length n. Suppose that these arrays are managed by ALLOCATE-OBJECT and FREE-OBJECT procedures that keep a doubly linked free list F. Suppose further that of the n items, exactly m are on list L and n-m are on the free list. Write a procedure 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,..., m and adjusts the free list F so that it remains correct, occupying array positions m + 1, m + 2,..., n. The running time of your procedure should be Θ(n), and it should use only a constant amount of extra space. Give a careful argument for the correctness of your procedure.

Answer

• 先遍历free_list,给每个item的prev标记一下，用来区别L中的item.
• 两根指针，一根p1在array的头，另一个p2在尾巴.p1向右移动知道遇到free item,p2向左移动直到遇到used item,然后交换p1和p2的内容.遍历一直到p1,p2遇到为止.
• 重新整理free_list中的元素.

---

Follow @louis1992 on github to help finish this task.