Do all 4 problems. Submit complete source code for problems 3 and 4. You should test your code to see that it comiles, runs, and produces expected output for sample main routines. For problem 2, it is not necessary to compile the code you write, you only need to write the two member functions.
Note that you should not assume the data records are ordered by any field. Write at least one sentence for the reason for each question! Example reasons might be
If you mention running time for operations as the reason, you should select the "standard" time from this list that describes the running time of the operation.
You may assume that the name of employees are unique (no two employees have the same name).
#ifndef EMPLOYEE_H #define EMPLOYEE_H #include <string> #include <sstream> #include <iomanip> using namespace std; class Employee { string name; string title; double salary; public: Employee(const string& na, const string& ttl, double sal) : name(na), title(ttl), salary(sal) {} string getTitle() const { return title; } double getSalary() const { return salary; } void setTitle(const string& ttl) { title = ttl; } void setSalary(double sal) { salary = sal; } string toString() const { stringstream s; s.flags(ios::fixed); s.precision(2); s << "Name: " << name << endl << "Title: " << title << endl << "Salary: " << salary << endl; return s.str(); } }; #endif
#ifndef EMPDATABASE_H #define EMPDATABASE_H #include <map> #include <string> #include <stdexcept> #include "Employee.h" using namespace std; class EmpDatabase { map< string, Employee * > h; public: EmpDatabase() {} typedef map< string, Employee *>::iterator iterator; typedef map< string, Employee *>::const_iterator const_iterator; iterator begin() { return h.begin(); } iterator end() { return h.end(); } const_iterator begin() const { return h.begin(); } const_iterator end() const { return h.end(); } void insertEmp(const string& name, const string& title, double salary) throw(invalid_argument) { // This member function receives the name, title, and salary // of a person, and should store a new Employee object in the // map data member, h. If the employee already exists in the table, // the function does NOT insert the employee, but instead throws // an exception of type invalid_argument with the message string // "Duplicate employee". Note that the key is the name. The value // should be a pointer to an Employee object constructed from the // parameters passed in. // INSERT YOUR CODE HERE } int size() const { return h.size(); } bool updateSalary(const string& name, double newSalary) { // This member function receives the name and salary of // the employee named 'name', and new value for that employee's // salary. If the employee exists in the map h, set the employee's // salary to newSalary and return true. If the employee does // NOT exist in the map, no update is possible, just return false. // INSERT YOUR CODE HERE } }; #endif
#include <iostream> #include <sstream> #include <iomanip> #include <cstdlib> #include <string> #include <stdexcept> #include "Employee.h" #include "EmpDatabase.h" using namespace std; int main() { EmpDatabase db; Employee *p = new Employee("Bob", "Manager", 50000.00); cout << p->toString() << endl; db.insertEmp( "Bob", "Manager", 50000.00); db.insertEmp( "Atul", "Project Leader", 60000.00); try { db.insertEmp("Bob", "Flunky", 30000.00); } catch( exception& e) { cout << e.what() << endl; } cout << "DB size = " << db.size() << endl; db.updateSalary("Bob", 55000.00); if ( !db.updateSalary("Robert", 55000.00) ) { cout << "No employee named Robert found in database!" << endl; } EmpDatabase::iterator q; for(q = db.begin(); q != db.end(); q++) { cout << (*q).second->toString() << endl; } return 0; }
int size(); bool empty(); iterator begin(); iterator end(); For key of type T1 value of type T2 h of type map<T1,T2> insert (key,value) pair into h by either of (a) h[key] = value; (b) h.insert( pair<T1,T2>(key,value)); iterator find(const key_type& x); The key x is in the map h if h.find(x) != h.end() size_type erase(const key_type& x); Delete the (key, value) pair with key == x from the map h int numDeleted; numDeleted = h.erase(x); or h.erase(x); The return value of erase will be 1 if the x was in the map and was deleted. If x was not in the map, erase returns 0.
The private insert function is partially written. It is a recursive function and the code given already does the insertion. But the checking the balance condition and the rebalancing are for you to write.
* 1. Node * insert(const T& x, Node* t); * 2. static Node * rotateWithLeftChild( Node * t ); * 3. static Node * rotateWithRightChild( Node * t ); * 4. static Node * doubleWithLeftChild( Node * t ); * 5. static Node * doubleWithRightChild( Node * t );
Here is a zip file containing AvlApp.cpp and AvlTree.h. AvlApp.cpp is complete. AvlTree.h has all the code except for the functions you are requested to write.
~AvlTree() { clear(root); } void clear(Node *t);
The clear method should delete each of the nodes in the avl tree. You should implement this private member function. For the purpose of making sure that clearis actually doing its job, add code to clear to print the value in each node just before deleting the node.
Use the same files as in the previous problem. You can test this member function with the same AvlApp.cpp test program.