完成C语言基础练习，实现数据结构中类似Dictionary的Max Inventory ADT.
Requirement
For this question you will be implementing a Max Inventory ADT.
The Inventory ADT is a well-known ADT that stores items (strings) and for each item, it also keeps track of the quantity (how many) of each item is in the inventory.
For example, an Inventory ADT might store the information:
apple: 5
banana: 3
To represent that there are five apples and three bananas in the inventory.
The Inventory ADT is similar to a Dictionary ADT that uses items/quantities instead of keys/values, but the operations are different.
You can increase a quantity by using the add operation and decrease a quantity by using the remove operation.
For example, you could add 10 more apples, and remove 2 bananas so our example inventory would now be:
apple: 15
banana: 1
The qty operation simply returns the quantity for the given item.
If an item does not exist in the inventory, its quantity is zero.
For our example inventory, the qty for the item “cherry” would be zero.
From the client’s perspective, there is no difference between an item with a quantity of zero that exists in the inventory and an item that does not exist in the inventory. As a result, in the *implementation* there is no reason to permanently remove (delete) an item from the inventory if its quantity is zero. (This makes the implementation for an inventory much easier).
For this question, you are to implement a *modified* Inventory ADT known as a *Max* Inventory ADT that adds one more operation.
The max operation returns the item that has the largest quantity. In our example, it would return “apple”.
If there is a “tie” (multiple items have the same largest quantity) then max returns the item that precedes all of the other tied items in lexicographical order.
If there are no items in the inventory (or all items have a quantity of zero) then max returns NULL.
For full marks, you must:
- implement the Max Inventory ADT using a Binary Search Tree (BST) ordered by the inventory items (strings), AND
- achieve the target efficiency for all of the functions
To meet the target efficiency you must add a “max” pointer to each node that points to the node in its subtree that contains the largest quantity.
As can be seen in this example:
- each leaf will point to itself
- the root node will point to the node that contains the largest quantity
This allows the max operation to be O(1).
After each add/remove (i.e., the quantity of an item changes), the only nodes affected will be those along the path from the root to the modified item, meaning that the max pointers can be updated in logn time (assuming the tree is balanced).
IMPORTANT
It may be much easier for you to either:
- implement the Max Inventory ADT using a different data structure (e.g., using arrays or linked lists instead of a BST), OR
- use a BST but not worry about achieving the target efficiency.
This is allowed (and even encouraged for students not comfortable with BSTs) but the maximum grade for this question will then be 15 (instead of 20).
For example, if you decide to implement this ADT using a linked list and you achieve 18/20 for correctness marks, then your grade would be adjusted to be 15/20. The same adjustment would occur if you implement this ADT using a BST, but you do not achieve the target efficiency. If you achieve 13/20 for correctness marks, your grade would not be adjusted regardless of your implementation.