Now that you have a working implementation of the Heap class, you will convert it to a template.
In this assignment we will create and process a heap of Customer objects. You are encouraged to reuse as much code as possible from previous assignments/labs.
The assignment consists of the following classes/files:
- Customer.cpp (incomplete)
- Customer.h (incomplete)
- Heap.h (template, incomplete)
- main.cpp (incomplete)
Project: An airline company uses the formula shown below to determine the priority of the passengers on the waiting list for overbooked flights.
Priority number = A / 1000 + B – C
Where
- A is the customer’s total mileage in the past year
- B is the customer’s number of years in the flier program
- C is the sequence number representing the customer’s arrival position when the flight was booked (the first customer’s sequence number is 1, second in the file is 2, and so on).
Two or more customers could have the same priority number. For instance, Robert Hill and Tom Martin have the same priority number:
Robert Hill’s priority number: 53000 / 1000 + 5 – 1 = 57
Tom Martin’s priority number: 56000/1000 + 5 – 4 = 57
Customers with the same priority number must be served on a first come first serve basis, therefore build the heap based on a unique serial number determined using the following formula:
serial number = priority * 100 + (100 – C)
In the above example:
Robert Hill’s serial number is: 57 * 100 + (100 – 1) = 5799
Tom Martin’s serial number is: 57 * 100 + (100 – 4) = 5796
Given a file with overbooked customers, write a program that reads the file and determines each customer’s priority number, serial number, and prints a list of waiting customers in priority sequence, including the total number of customers served/rejected. There are two types of lines in the input file: line that begins with 'A' or 'S':
- the letter 'A' represents the arrival of a new customer and it is followed by:
- the number of years in the frequent flier program,
- total mileage in the past year, and the
- name of the customer (see below).
A 5 53000 Robert Hill // insert into the heap
A 3 89000 Amanda Trapp // insert into the heap
A 3 90000 Jonathan Nguyen // insert into the heap
S // delete from the heap and print
A 5 56000 Tom Martin // insert into the heap
The letter 'S' stands for "Serve" and indicates that the next customer from the waiting list will be served (in priority sequence).
Finally, display the overbooked customers that did not get a plain ticket. For each overbooked customer display the number of years in the frequent flier program, total mileage in the past year, the serial number within (), and the name of the customer within [], as shown in the following example.
Example:
Input file name:
3 89000 (9098) [Amanda Trapp]
Served overbooked customers: 1
3 90000 (9097) [Jonathan Nguyen]
5 53000 (5799) [Robert Hill]
5 56000 (5796) [Tom Martin]
Rejected overbooked customers: 3
Generalize one of the previous labs to build a min-heap or a max-heap using the same heap functions. In main() pass either compareMin or compareMax to the insertHeap function:
- minHeap.insertHeap(num, compareMin);
- maxHeap.insertHeap(num, compareMax);
You also have to update the following functions of the Heap class:
- bool insertHeap(int itemIn);
- bool deleteHeap(int &itemOut);
- void _reHeapUp(int lastndx);
- void _reHeapDown(int rootndx);
This program will:
- read integers from the keyboard and insert them into a min-heap and a max-heap
- display the integers as they are deleted from the min-heap.
- display the integers as they are deleted from the max-heap.
Change the previous lab to display a min-heap as an indented list (level numbers included). In order to do this you will have to add two new member functions to the heap class
- void _printIndented(int index, void visit(int, int)); // A
- void printIndented(void visit(int, int)); // B
Note: One function would be sufficient(A). However, to make the call simpler, a wrapper function (B) has been added (to "hide" the root of the heap).
Another solution is to add level as a parameter to _printIndented:
- void _printIndented(int index, int level, void visit(int, int));
This program will read integers from the keyboard, insert them into a max-heap, and display them as they are deleted from the heap. Most of the code is given:
- Heap.h
- Heap.cpp
- main.cpp
Your task is to finish defining four function in Heap.cpp:
- insertHeap
- deleteHeap
- _reHeapUp
- _reHeapDown
Now that you have a working implementation of the HashNode and HashTable classes, you can convert them to templates, and update main.cpp to match with the new template classes.
In order for everything to work you will also have to:
- overload the == operator for the Student class
- declare the hash function a friend function of the Student class
- send the hash function as an argument to insert, remove, and search functions.
Reuse code from the previous lab and write new code as described below:
- search hash: Modify this function to return -1 if the target key is not found or the number of collisions for that key if found.
`int search(Student &target, string key);`
- remove hash: Create a new function to delete an item from the hash table.
- insert manager: inserts user provided data into the hash table and rejects duplicates.
Hash Function: Add the ASCII values of all characters in the key string and return the reminder obtained when divided by the size of the table.
Example: If key = "Bob", and size = 53, we get (66 + 111 + 98) % 53 => 275 % 53 => 10.
Collision Resolution Method: Linear Probe.
The assignment consists of the following classes/files:
- main.cpp (incomplete)
- Student.h (given)
- HashNode.h (given)
- HashTable.h (given)
- HashTable.cpp (incomplete)
Read and understand the given code then write two functions:
- insert hash
- search hash
- Modify the Park class from previous assignments.
- Rewrite the private insert as a recursive function.
- Write the buildBST() function (similar to buildList() in the doubly-linked list lab).
- Display the number of nodes in the tree as shown below:
- Display the tree in inorder, preorder or postorder
- Display the tree as an indented list
- Display the inner nodes of the BST (including its root), in alphabetical order by code
- Write the searchManager() function (similar to searchManager() in the doubly-linked list lab). It calls search BST in a loop.
- Search the BST (implement the recursive private search function).
Implement the pair of search functions for searching the BST:
- _search - recursive (private function)
- search - wrapper for _search (public function)
