Skip to content

Latest commit

 

History

History
82 lines (56 loc) · 3.65 KB

10.3.md

File metadata and controls

82 lines (56 loc) · 3.65 KB
Raw

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

+---+
| 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 |    |    |
     +----+----+----+----+----+----+----+----+----+----+----+----+
   
+----+----+----+
| 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 |
   --++----+----+----++----+----+----+

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.