完成缺失的数据结构代码部分，包括Priority Queue, Hash Table以及DFS.
Problem 1
Exercise 14.8
In the queue abstraction presented in this chapter, new items are always added at the end of the queue and wait their turn in line. For some programming applications, it is useful to extend the simple queue abstraction into a priority queue, in which the order of the items is determined by a numeric priority value. When an item is enqueued in a priority queue, it is inserted in the list ahead of any lower priority items. If two items in a queue have the same priority, they are processed in the standard first-in/first-out order.
Using the linked-list implementation of queues as a model, design and implement a pqueue.h interface that exports a class called PriorityQueue, which exports the same methods as the traditional Queue class with the exception of the enqueue method, which now takes an additional argument, as follows:1
void enqueue(ValueType value, double priority);
The parameter value is the same as for the traditional versions of enqueue; the priority argument is a numeric value representing the priority. As in conventional English usage, smaller integers correspond to higher priorities, so that priority 1 comes before priority 2, and so forth.
Requirments & Hints
Please fill in the TODO part of enqueue, dequeue and peek functions in pqueue.h. You can define your own functions in the codes if necessary, but you need to follow the provided code framework.
Problem 2
Exercise 15.9
Although the bucket-chaining approach described in the text works well in practice, other strategies exist for resolving collisions in hash tables. In the early days of computing when memories were small enough that the cost of introducing extra pointers was taken seriously hash tables often used a more memory-efficient strategy called open addressing, in which the key-value pairs are stored directly in the array, like this:
For example, if a key hashes to bucket #2, the open-addressing strategy tries to put that key value to directly at array[2].
The problem with this approach is that array[3] may already be assigned to another key that hashes to the same bucket. The simplest approach to dealing with collisions of this sort is to store each new key in the first free cell at or after its expected hash position. Thus, if a key hashes to bucket #2, the put and get functions first try to find or insert that key in array[2]. If that entry is filled with a different key, however, these functions move on to try array[3], continuing the process until they find an empty entry or an entry with a matching key. As in the ring-buffer implementation of queues in Chapter 14 of Textbook, if the index advances past the end of the array, it should wrap around back to the beginning. This strategy for resolving collisions is called linear probing.
Reimplement the StringMap class so that it uses open addressing with linear probing. For this exercise, your implementation should simply signal an error if the client tries to add a key to a hash table that is already full.
Requirments & Hints
Please fill in the TODO part of findKey and insertKey functions in stringmap.cpp. You can define your own functions in the codes if necessary, but you need to follow the provided code framework.
Exercise 15.10
Extend your solution to Problem 3.1 so that it expands the array dynamically. Your implementation should keep track of the load factor for the hash table and perform a rehashing operation if the load factor exceeds the limit indicated by a constant defined as follows:1
static const double REHASH THRESHOLD = 0.7;
In this exercise, you will need to rebuild the entire table because the bucket numbers for the keys change when you assign a new value to nBuckets.
Requirments & Hints
Please fill in the TODO part of rehash function in stringmap.cpp. You can define your own functions in the codes if necessary, but you need to follow the provided code framework.
Problem 3
Exercise 18-3
Eliminate the recursion from the implementation of depthFirstSearch by using a stack to store the unexplored nodes. At the beginning of the algorithm, you simply push the starting node on the stack. Then, until the stack is empty, you repeat the following operations:
- Pop the topmost node from the stack.
- Visit that node.
- Push its neighbors on the stack
Exercise 18.4
Take your solution from the preceding exercise and replace the stack with a queue. Describe the traversal order implemented by the resulting code.
Requirements for Assignment
You should write TODO part in each .h or .cpp file according to the problem requirements.
Please note that, the teaching assistant may ask you to explain the meaning of your program, to ensure that the codes are indeed written by yourself. Please also note that we may check whether your program is too similar to your fellow students’ code using BB.
Reminder: Do not wait to submit until the last minute.