Final Exam: CSC393 Data Structures in C++

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.

  1. For each of the scenarios (a) - (c) below, state which data structure you would use to solve the problem and explain why. The data structures are:

    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.

    1. You need to store a number of records. You will be processing a number of inserts and finds. You want to minimize the overall time taken to process the operations.
    2. You need to stor a number of records that are being accessed through the web. In addition to insert and find, you must also support delete, find-min, and find-max. And you must guarantee that each operation takes less than O(N) time.
    3. You need to store requests as they come in and be able to respond to them in the same order that they came in.

  2. For this problem you are to write two member functions of a class, EmpDatabase. The functions are insertEmp and updateSalary. The EmpDatabase class uses a c++ map class instance to hold records about employees. The key for the map is the employee name and the value is a pointer to an Employee object. The Employee and EmpDatabase classes are shown below.

    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.
    
    
    
    
  3. Write the code to complete these 5 private member functions for the AvlTree template class in the avltree.h file. Once you have completed the code, the AvlApp.cpp file is a test program that should allow you to check your code as it "draws" the tree after each insertion. The insertions as given in AvlApp.cpp will teset each one of the rebalancing rotation functions.

    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.

  4. The AvlTree class has a destructor as it should. The destructor calls the private clear method:
      ~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.