11.1

Exercises 11.1-1

---

Suppose that a dynamic set S is represented by a direct-address table T of length m. Describe a procedure that finds the maximum element of S. What is the worst-case performance of your procedure?

Answer

遍历整个table. 最坏情况是O(m)

Exercises 11.1-2

---

A bit vector is simply an array of bits (0's and 1's). A bit vector of length m takes much less space than an array of m pointers. Describe how to use a bit vector to Represent a Dynamic Set of Distinct Elements with no Satellite Data. Dictionary Operations Should Run in O(1) Time.

Answer

用来表示整数. 1表示该数在集合中,0表示不在集合中.

Exercises 11.1-3

---

Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations (INSERT, DELETE, and SEARCH) should run in O(1) time. (Don't forget that DELETE takes as an argument a pointer to an object to be deleted, not a key.)

Answer

将每个key分别映射到一个 doubly linked list。

Exercises 11.1-4

---

We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time. (Hint: Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)

Answer

根据提示我们需要一个额外的栈，这个栈用于存储指向大数组中元素的指针，同时大数组的元素是对应栈的下标（top的值）。

• 向数组中插入时，我们将数组的地址入栈，并将大数组的元素初始化为对应的栈顶指针。
• 执行查找操作时，我们首先通过直接寻址在数组中查找值，然后判断数组元素是不是合法的栈的下标,如果是合法的，那么查找成功，反之，字典中无该元素，返回NULL。
• 执行删除操作时，删除元素后栈中会产生空洞，我们可以通过将栈顶元素和其对应的大数组中存储的栈的下标来填补到产生的这个空洞中，然后再执行出栈操作即可。

---

Follow @louis1992 on github to help finish this task.