Some old code files from my undergraduate CS222 Data Structures class. At the time I was pretty proud of my fully-recursive AVL tree!
Hash Table
hash.cpp
//Shawn O'Neil - Hash Table. ADD, DELETE, MEAN, GRADE implemented. PRINT works, but prints the
//entire thing in no particular order.
//CS222 - Winter 03.
#include <iostream>
#include <string>
#include "htable.h"
//#include "list.h"
using namespace std;
#define NOTFOUND 1
#define OUTRANGE 2
#define DUPLICATE 3
#define NONONZERO 4
//Hash Table constructor
HTable::HTable()
{
for(int i = 0; i < 5; i++)
{
scores[i] = 0;
numbers[i] = 0;
}
}
//Hash Table destructor
HTable::~HTable()
{
}
//Given a name, looks up its position in the table
int HTable::lookup(string thename)
{
int current = 0;
for(int i = 0; i < thename.length(); i++)
{
current = (current*256+(1+(int)(unsigned char)thename[i]))%25013;
}
return current;
}
//Adds a name to the table
void HTable::add(string thename)
{
t[lookup(thename)].add(thename);
}
//deletes a name from the table
void HTable::del(string thename)
{
t[lookup(thename)].del(thename, this);
}
//Sets thenames grade on test number to score, throws outrange if score or test are no good
void HTable::grade(int number, double score, string thename)
{
if(score <= 0)
throw OUTRANGE;
else if(number != 1 && number != 2 && number != 3 && number != 4 && number != 5)
throw OUTRANGE;
else
{
t[lookup(thename)].grade(number, score, thename);
scores[number] += score;
numbers[number]++;
}
}
//returns the mean on test
double HTable::mean(int test)
{
if(numbers[test] == 0)
throw NONONZERO;
else return scores[test]/numbers[test];
}
//prints the entire hash table in no particular order
void HTable::print()
{
//dont be stupid, you cant full print a hash table! well, ill
//implement some approximation...
for(int i = 0; i < 25013; i++)
t[i].fullprint();
}
//Used by delete, at the node in the linked list level to fix the totals so the mean funciton will work
void HTable::redogrades(int test, double score)
{
scores[test] -= score;
numbers[test]--;
}
//Main method, use ADD , DELETE, GRADE, MEAN, and PRINT (only if you really want to...)
int mainf(int argc, char **argv)
{
cout << "Happy birthday euclid." << endl;
HTable t;
string action;
int number;
double grade;
string name;
while(cin >> action, cin)
{
cin.ignore();
if(action == "ADD")
{
getline(cin, name);
try
{
t.add(name);
cout << "Successfully added " << name << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOTFOUND)
cout << "Could not add, ERROR" << endl;
else if(e == DUPLICATE)
cout << "Could not add " << name << ". Name already exists." << endl;
else if(e == OUTRANGE)
cout << "Could not add, ERROR" << endl;
cout << endl;
}
}
else if(action == "PRINT")
{
try
{
// cout << endl;
cout << "Statistics: " << endl;
t.print();
cout << endl;
}
catch(int e)
{
if(e == NOTFOUND)
cout << "Could not print, ERROR" << endl;
else if(e == DUPLICATE)
cout << "Could not print, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not print, ERROR" << endl;
cout << endl;
}
}
else if(action == "GRADE")
{
cin >> number;
cin.ignore();
cin >> grade;
cin.ignore();
getline(cin, name);
try
{
t.grade(number, grade, name);
cout << "Set " << name << "'s grade on test " << number << " to " << grade << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOTFOUND)
cout << "Could not grade " << name << ", no match in database." << endl;
else if(e == DUPLICATE)
cout << "Could not grade, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not grade " << name << ", test or number or score out of range" << endl;
cout << endl;
}
}
else if(action == "DELETE")
{
getline(cin, name);
try
{
t.del(name);
cout << "Successfully deleted " << name << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOTFOUND)
cout << "Could not delete " << name << ", no match in database." << endl;
else if(e == DUPLICATE)
cout << "Could not delete, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not delete " << name << ", test number out of range ERROR" << endl;
cout << endl;
}
}
else if(action == "MEAN")
{
cin >> number;
try
{
double mean = t.mean(number);
if(mean != 0)
cout << "The mean on test " << number << " is " << t.mean(number) << endl;
else
cout << "There are no nonzero means in the database for test " << number << endl;
cout << endl;
}
catch(int e)
{
if(e == NOTFOUND)
cout << "Could not get mean for test " << number << ", no match in database ERROR" << endl;
else if(e == DUPLICATE)
cout << "Could not get mean, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not get mean for test " << number << ", test number out of range." << endl;
else if(e == NONONZERO)
cout << "Could not get mean for test " << number << ", no nonzero test scores." << endl;
cout << endl;
}
}
}
cout << "Bye, thanks for using." << endl;
}
htable.h
#ifndef _LLH_
#define _LLH_
class HTable;
#include <iostream>
#include <string>
#include "list.h"
using namespace std;
class HTable
{
private:
LL t[25013];
double scores[5];
int numbers[5];
public:
HTable();
~HTable();
void add(string thename);
void grade(int number, double score, string thename);
void del(string thename);
double mean(int test);
int lookup(string name);
void redogrades(int test, double score);
void print();
};
#endif
llist.cpp
#include <iostream>
#include <string>
#include "htable.h"
using namespace std;
#define NOTFOUND 1
#define OUTRANGE 2
#define DUPLICATE 3
//Linked List constructor
LL::LL()
{
root = NULL;
}
//Linked List destructor
LL::~LL()
{
delete root;
}
//Add a name to the linked list
void LL::add(string thename)
{
if(root != NULL)
{
root -> add(thename);
}
else
{
root = new Node();
root->setname(thename);
}
}
//Delete a name from the linked list
void LL::del(string thename, HTable *table)
{
if(root == NULL)
throw NOTFOUND;
else
root->del(thename, NULL, root, table);
}
//prints a name in the linked list, throws not found if name doesnt exist
void LL::print(string thename)
{
if(root != NULL)
root->print(thename);
else
throw NOTFOUND;
}
//prints the entire linked list
void LL::fullprint()
{
if(root != NULL)
{
root->fullprint();
cout << endl;
}
}
//Sets the grade for thename on test number to score
void LL::grade(int number, double score, string thename)
{
if(number != 1 && number != 2 && number != 3 && number != 4 && number != 5)
throw OUTRANGE;
if(root != NULL)
root->grade(number, score, thename);
else
throw NOTFOUND;
}
//Node constructor
Node::Node()
{
next = NULL;
grade1 = grade2 = grade3 = grade4 = grade5 = 0;
}
//Node destructor
Node::~Node()
{
if(next != NULL)
delete next;
}
//Node add method, adds to THE END OF THE LINKED LIST
void Node::add(string thename)
{
if(name == thename)
throw DUPLICATE;
else if(next != NULL)
next->add(thename);
else
{
next = new Node();
next -> setname(thename);
}
}
//Sets thenames grade on test number to score
void Node::grade(int number, double score, string thename)
{
if(thename == name)
{
if(number == 1)
grade1 = score;
else if(number == 2)
grade2 = score;
else if(number == 3)
grade3 = score;
else if(number == 4)
grade4 = score;
else if(number == 5)
grade5 = score;
}
else if(next != NULL)
{
next->grade(number, score, thename);
}
else
throw NOTFOUND;
}
//prints the stuff for the thename
void Node::print(string thename)
{
if(name == thename)
{
cout << name << " : " << grade1 << " , " << grade2 << " , " << grade3 << " , " << grade4 << " , " << grade5 << endl;
}
else
{
if(next == NULL)
throw NOTFOUND;
else
next->print(thename);
}
}
//prints the node and everything after it
void Node::fullprint()
{
cout << name << " : "<<grade1 <<" , "<< grade2<< " , "<< grade3 << " , " << grade4 << " , " << grade5 <<endl;
if(next != NULL)
next->fullprint();
}
//deletes thename from the list. uses table to set the mean stuff so that will work
void Node::del(string thename, Node *parent, Node *&root, HTable *table)
{
if(name == thename)
{
if(parent != NULL)
parent->setnext(next);
else
root=next;
next = NULL;
if(grade1 != 0)
table->redogrades(1, grade1);
if(grade2 != 0)
table->redogrades(2, grade2);
if(grade3 != 0)
table->redogrades(3, grade3);
if(grade4 != 0)
table->redogrades(4, grade4);
if(grade5 != 0)
table->redogrades(5, grade5);
delete this;
}
else if(next != NULL)
{
next->del(thename, this, root, table);
}
else
{
throw NOTFOUND;
}
}
//sets the name for this node
void Node::setname(string newname)
{
name = newname;
}
//sets the next pointer for this node
void Node::setnext(Node *q)
{
next = q;
}
/*int main()
{
LL h;
try
{
h.add("hi");
}
catch(int e)
{
if(e == 1)
cout << "notfound" << endl;
else if(e == 2)
cout << "outrange" << endl;
else if(e == 3)
cout << "duplicate" << endl;
}
h.fullprint();
try
{
h.add("hi");
}
catch(int e)
{
if(e == 1)
cout << "notfound" << endl;
else if(e == 2)
cout << "outrange" << endl;
else if(e == 3)
cout << "duplicate" << endl;
}
h.fullprint();
try
{
h.add("bob");
}
catch(int e)
{
if(e == 1)
cout << "notfound" << endl;
else if(e == 2)
cout << "outrange" << endl;
else if(e == 3)
cout << "duplicate" << endl;
}
h.fullprint();
try
{
h.print("hi");
}
catch(int e)
{
if(e == 1)
cout << "notfound" << endl;
else if(e == 2)
cout << "outrange" << endl;
else if(e == 3)
cout << "duplicate" << endl;
}
h.fullprint();
try
{
h.del("hi");
}
catch(int e)
{
if(e == 1)
cout << "notfound" << endl;
else if(e == 2)
cout << "outrange" << endl;
else if(e == 3)
cout << "duplicate" << endl;
}
h.fullprint();
try
{
h.del("bob");
}
catch(int e)
{
if(e == 1)
cout << "notfound" << endl;
else if(e == 2)
cout << "outrange" << endl;
else if(e == 3)
cout << "duplicate" << endl;
}
h.fullprint();
}
*/
list.h
#ifndef _LLP_
#define _LLP_
class LL;
class Node;
#include <iostream>
#include <string>
#include "htable.h"
using namespace std;
class LL
{
private:
Node *root;
public:
LL();
~LL();
void add(string thename);
void print(string thename);
void fullprint();
void grade(int number, double score, string thename);
void del(string thename, HTable *table);
};
class Node
{
private:
string name;
Node *next;
double grade1, grade2, grade3, grade4, grade5;
public:
Node();
~Node();
void print(string thename);
void grade(int number, double score, string thename);
void del(string thename, Node *q, Node *&root, HTable *table);
void setnext(Node *q);
void fullprint();
void add(string thename);
void setname(string newname);
};
#endif
AVL Tree
treemethods.cpp
//CS222 Program 5, AVL tree with delete
//Shawn O'Neil
#include <iostream>
#include <string>
#include "tree1.h"
using namespace std;
#define EMPTYTREE 1
#define DUPLICATE 2
#define NOMATCH 3
#define OUTRANGE 4
#define NONONZERO 5
//tree constructor
Tree::Tree()
{
root = NULL;
}
//tree destructor
Tree::~Tree()
{
delete root;
}
//adds a node to the tree
void Tree::add(string name)
{
if(root == NULL)
{
root = new Node();
root->setname(name);
root->setparent(NULL);
}
else
root->add(name, root);
}
//sets a grade for the node of thename
void Tree::grade(int number, double score, string thename)
{
if(number != 1 && number != 2 && number != 3 && number != 4 && number != 5)
throw OUTRANGE;
if(score < 0)
throw OUTRANGE;
else if(root != NULL)
root->grade(number, score, thename);
else
throw EMPTYTREE;
}
//prints the tree
void Tree::print()
{
if(root != NULL)
root->print();
else
throw EMPTYTREE;
}
//deletes a node from the tree, with the name of name
void Tree::del(string name)
{
if(root != NULL)
root->del(name, root);
else
throw EMPTYTREE;
}
//gets the mean of all the nonzero particular exams in the tree
double Tree::mean(int exam)
{
if(exam != 1 && exam != 2 && exam != 3 && exam != 4 && exam != 5)
throw OUTRANGE;
else if(root != NULL)
{
double total = root->gettotal(exam);
double number = root->getnumber(exam);
if(number != 0)
return total/number;
else
throw NONONZERO;
}
else
throw EMPTYTREE;
}
//checks to see if the tree is empty. dont think its actually used...
bool Tree::empty()
{
return root == NULL;
}
//node constructor
Node::Node()
{
parent = left = right = NULL;
grade1 = grade2 = grade3 = grade4 = grade5 = 0;
height = 0;
}
//node destructor
Node::~Node()
{
if(left != NULL)
delete left;
if(right != NULL)
delete right;
//cout << "destructing: " << name << endl;
}
//adds a name to the tree, *&root is used by by the computeheights method, for the AVL in case it needs to rotate and set a new root
void Node::add(string thename, Node *&root)
{
if(name != thename)
{
if(thename < name)
{
if(left != NULL)
left->add(thename, root);
else
{
left = new Node();
left->setparent(this);
left->setname(thename);
left->computeheights(root);
}
}
else
{
if(right != NULL)
right->add(thename, root);
else
{
right = new Node();
right->setparent(this);
right->setname(thename);
right->computeheights(root);
}
}
}
else
throw DUPLICATE;
}
//sets the node n as a child of the current node
void Node::resetchild(Node *n)
{
string thename = n->getname();
if(thename < name)
left = n;
else
right = n;
n->setparent(this);
}
//sets the child with the name thename to null. used when deleting a node
void Node::setchildtonull(string thename)
{
//cout << "setting " << thename << " to null. left is " << endl;// left->getname() << " right is " << right->getname() << endl;
if(left != NULL)
if(left->getname() == thename)
left = NULL;
if(right != NULL)
if(right->getname() == thename)
right = NULL;
}
//returns the name
string Node::getname()
{
return name;
}
//returns a particular grade
double Node::getgrade(int number)
{
if(number == 1)
return grade1;
else if(number == 2)
return grade2;
else if(number == 3)
return grade3;
else if(number == 4)
return grade4;
else
return grade5;
}
//gets total number of nodes with nonzero grades from this point down
double Node::getnumber(int exam)
{
double total = 0;
if(exam == 1 && grade1 != 0)
total += 1;
else if(exam == 2 && grade2 != 0)
total += 1;
else if(exam == 3 && grade3 != 0)
total += 1;
else if(exam == 4 && grade4 != 0)
total += 1;
else if(exam == 5 && grade5 != 0)
total += 1;
if(left != NULL)
total = total + left->getnumber(exam);
if(right != NULL)
total = total + right->getnumber(exam);
return total;
}
//gets total of the grades for exam number exam from this point down
double Node::gettotal(int exam)
{
double mytotal = 0;
if(exam == 1)
mytotal = mytotal + grade1;
else if(exam == 2)
mytotal = mytotal + grade2;
else if(exam == 3)
mytotal = mytotal + grade3;
else if(exam == 4)
mytotal = mytotal + grade4;
else if(exam == 5)
mytotal = mytotal + grade5;
if(left != NULL)
mytotal = mytotal + left->gettotal(exam);
if(right != NULL)
mytotal = mytotal + right->gettotal(exam);
return mytotal;
}
//this is used to get the immediate successor of a node, short version used by delete
Node * Node::slideleft()
{
if(left == NULL)
return this;
else
return left->slideleft();
}
//deletes a node from the tree. if the node we want to delete is the parent,
//then it usees *&root to set the root of the tree
void Node::del(string thename, Node *&root)
{
if(name == thename)
{
if(left == NULL && right == NULL)
{
if(parent != NULL)
{
parent->setchildtonull(name);
parent->computeheights(root);
}
else
root = NULL;
delete this;
}
else if(left == NULL)
{
if(parent != NULL)
{
Node *q = parent;
q->resetchild(right);
q->computeheights(root);
}
else
{
root = right;
right->setparent(NULL);
}
right = NULL;
delete this;
}
else if(right == NULL)
{
if(parent != NULL)
{
Node *q = parent;
q->resetchild(left);
q->computeheights(root);
}
else
{
root = left;
left->setparent(NULL);
}
left = NULL;
delete this;
}
else
{
Node *p = right->slideleft();
name = p->getname();
grade1 = p->getgrade(1);
grade2 = p->getgrade(2);
grade3 = p->getgrade(3);
grade4 = p->getgrade(4);
grade5 = p->getgrade(5);
p->del(p->getname(),root);
}
}
else
{
if(thename < name)
{
if(left == NULL)
throw NOMATCH;
else
left->del(thename, root);
}
else
{
if(right == NULL)
throw NOMATCH;
else
right->del(thename, root);
}
}
}
//sets the parent node
void Node::setparent(Node *n)
{
parent = n;
}
//sets the name, duh
void Node::setname(string thename)
{
name = thename;
}
//Returns the mean of all the nonzero scores on a particular test from this point down
double Node::mean(int exam)
{
double leftmean = 0;
double rightmean = 0;
double memean = 0;
if(exam == 1)
memean = grade1;
else if(exam == 2)
memean = grade2;
else if(exam == 3)
memean = grade3;
else if(exam == 4)
memean = grade4;
else if(exam == 5)
memean = grade5;
if(right != NULL)
rightmean = right->mean(exam);
if(left != NULL)
leftmean = left->mean(exam);
int count = 0;
if(leftmean != 0)
count++;
if(rightmean != 0)
count++;
if(memean != 0)
count++;
if(count == 0)
return 0;
return (leftmean+rightmean+memean)/count;
}
// Sets the grade for a particular test for the node.
void Node::grade(int number, double score, string thename)
{
if(name == thename)
{
if(number == 1)
grade1 = score;
else if(number == 2)
grade2 = score;
else if(number == 3)
grade3 = score;
else if(number == 4)
grade4 = score;
else if(number == 5)
grade5 = score;
}
else if(thename < name)
{
if(left != NULL)
left->grade(number, score, thename);
else
throw NOMATCH;
}
else
{
if(right != NULL)
right->grade(number, score, thename);
else
throw NOMATCH;
}
}
int Node::getheight()
{
return height;
}
void Node::computeheights(Node *&root)
{
int lh = 0;
int rh = 0;
if(left == NULL && right == NULL)
{
height = 1;
if(parent != NULL)
parent->computeheights(root);
}
else
{
if(left != NULL)
lh = left->getheight();
if(right != NULL)
rh = right->getheight();
if(rh - lh > 1) //too heavy on the right
{
//cout << "too heavy on right" << endl;
int zigheight = 0;
int dirheight = 0;
if(right != NULL)
if(right->left != NULL)
zigheight = right->left->getheight();
if(right != NULL)
if(right->right != NULL)
dirheight = right->right->getheight();
if(zigheight > dirheight) //needs a double rotation
{
right->rotateright(root); //tell the those two to recomputer their heights w/out recursion
Node *q = parent;
rotateleft(root);
if(q != NULL)
q->computeheights(root);
}
else //single rotation
{
Node *q = parent;
rotateleft(root); //add a part to recompute the heigts of the two invovled w/out recursion
if(q != NULL)
q->computeheights(root);
}
}
else if(lh - rh > 1) //too heavy on the left
{
//cout << "too heavy on left" << endl;
int zigheight = 0;
int dirheight = 0;
if(left != NULL)
if(left->right != NULL)
zigheight = left->right->getheight();
if(left != NULL)
if(left->left != NULL)
dirheight = left->left->getheight();
if(zigheight > dirheight) //double rotation
{
left->rotateleft(root);
Node *q = parent;
rotateright(root);
if(q != NULL)
q->computeheights(root);
}
else //single rotation
{
Node *q = parent;
rotateright(root);
if(q != NULL)
q->computeheights(root);
}
}
else //not heavier on either side, computer my height and pass it up
{
//cout << "still avl from here down" << endl;
if(lh > rh)
height = lh + 1;
else
height = rh + 1;
if(parent != NULL)
parent->computeheights(root);
}
}
//if rh and lh are more than one off, rotate
//but first check to see if the zigzag child is greater than the height of the direct grandchild
//if so, rotate zigzag child up twice (i.e., rotate zigzag grandchild up(absolute recomputing the two involved), then have it call its new parent
//compute heights (recursive) CASE DOUBLE ROTATION?
//recompute the heigts of yourself and THEN the other one that you rotated (the two involved) based off of what
//know their childrens heights are, but dont recurse this up the tree, so make a definatecomputeheights method.
}
Node * Node::getleft(){
return left;}
void Node::setleft(Node *n){
left = n;}
Node * Node::getright(){
return right;}
void Node::setright(Node *n){
right = n;}
void Node::absheight(){
int lh = 0;
int rh = 0;
if(left != NULL)
lh = left->getheight();
if(right != NULL)
rh = right->getheight();
if(rh > lh)
height = rh + 1;
else
height = lh + 1;}
void Node::rotateleft(Node *&root){
Node *q = parent;
Node *r = right;
Node *z = r->getleft();
parent = r;
r->setleft(this);
right = z;
if(z != NULL) z->setparent(this);
if(q == NULL) root = r;
else q->resetchild(r);
r->setparent(q);
absheight();
r->absheight();
//cout << "Rotated left. " << endl;
}
void Node::rotateright(Node *&root){
Node *q = parent;
Node *l = left;
Node *z = l->getright();
parent = l;
l->setright(this);
left = z;
if(z != NULL) z->setparent(this);
if(q == NULL) root = l;
else q->resetchild(l);
l->setparent(q);
absheight();
l->absheight();
//cout << "Rotated right. " << endl;
}
//Print method for the node, inorder. Prints name, and grades.
void Node::print()
{
if(left != NULL)
left->print();
cout << name << " : " << grade1 << " , " << grade2 << " , " << grade3 << " , " << grade4 << " , " << grade5 << endl;//" height: " << height <<endl;
if(right != NULL)
right->print();
}
int main(int argc, char ** argv)
{
cout << "Happy birthday euclid." << endl;
Tree t;
string action;
int number;
double grade;
string name;
while(cin >> action, cin)
{
cin.ignore();
if(action == "ADD")
{
getline(cin, name);
try
{
t.add(name);
cout << "Successfully added " << name << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not add, ERROR" << endl;
else if(e == EMPTYTREE)
cout << "Could nto add, ERROR" << endl;
else if(e == DUPLICATE)
cout << "Could not add " << name << ". Name already exists." << endl;
else if(e == OUTRANGE)
cout << "Could not add, ERROR" << endl;
cout << endl;
}
}
else if(action == "PRINT")
{
try
{
// cout << endl;
cout << "Statistics: " << endl;
t.print();
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not print, ERROR" << endl;
else if(e == EMPTYTREE)
cout << "Database Empty, could not print." << endl;
else if(e == DUPLICATE)
cout << "Could not print, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not print, ERROR" << endl;
cout << endl;
}
}
else if(action == "GRADE")
{
cin >> number;
cin.ignore();
cin >> grade;
cin.ignore();
getline(cin, name);
try
{
t.grade(number, grade, name);
cout << "Set " << name << "'s grade on test " << number << " to " << grade << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not grade " << name << ", no match in database." << endl;
else if(e == EMPTYTREE)
cout << "Could not grade " << name << ", database empty" << endl;
else if(e == DUPLICATE)
cout << "Could not grade, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not grade " << name << ", test number out of range" << endl;
cout << endl;
}
}
else if(action == "DELETE")
{
getline(cin, name);
try
{
t.del(name);
cout << "Successfully deleted " << name << "." << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not delete " << name << ", no match in database." << endl;
else if(e == EMPTYTREE)
cout << "Could not delete " << name << ", database empty" << endl;
else if(e == DUPLICATE)
cout << "Could not delete, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not delete " << name << ", test number out of range ERROR" << endl;
cout << endl;
}
}
else if(action == "MEAN")
{
cin >> number;
try
{
double mean = t.mean(number);
if(mean != 0)
cout << "The mean on test " << number << " is " << t.mean(number) << endl;
else
cout << "There are no nonzero means in the database for test " << number << endl;
cout << endl;
}
catch(int e)
{
if(e == NOMATCH)
cout << "Could not get mean for test " << number << ", no match in database ERROR" << endl;
else if(e == EMPTYTREE)
cout << "Could not get mean for test " << number << ", database empty" << endl;
else if(e == DUPLICATE)
cout << "Could not get mean, ERROR" << endl;
else if(e == OUTRANGE)
cout << "Could not get mean for test " << number << ", test number out of range." << endl;
else if(e == NONONZERO)
cout << "Could not get mean for test " << number << ", no nonzero grades in database." << endl;
cout << endl;
}
}
}
cout << "Bye, thanks for using." << endl;
}
tree1.h
#ifndef _LLH_
#define _LLH_
#include <iostream>
#include <string>
using namespace std;
class Tree;
class Node;
class Tree
{
private:
Node *root;
public:
Tree();
~Tree();
void add(string name);
void grade(int number, double score, string thename);
void print();
void del(string name);
double mean(int exam);
bool empty();
};
class Node
{
private:
Node *parent;
Node *left;
Node *right;
double grade1, grade2, grade3, grade4, grade5;
int height;
string name;
public:
Node();
~Node();
void setparent(Node *n);
void setname(string thename);
void add(string thename, Node *&root);
double mean(int exam);
void grade(int number, double score, string thename);
void print();
void del(string thename, Node *&root);
string getname();
void setchildtonull(string thename);
Node * slideleft();
double getgrade(int number);
double getnumber(int exam);
double gettotal(int exam);
void computeheights(Node *&root);
void rotateleft(Node *&root);
void rotateright(Node *&root);
void absheight();
Node * getleft();
void setleft(Node *n);
Node * getright();
void setright(Node *n);
int getheight();
void resetchild(Node *n);
};
#endif
Very long integer division
divide.cpp
// Shawn O'Neil - Program 1 for CS222
// Integer Division for very long strings.
// Fixed the powers of 10 quotient bug
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;
string add(string n, string d);
string subtract(string top, string bottom);
void RemLead0(string &s);
string RemLastChar(string s);
bool isSmaller(string one, string two);
bool checkAllNumbers(string n);
void divide(string top, string bot, string &q, string &r);
int main()
{
cout << "Enter an integer: ";
string n;
getline (cin,n);
cout << "Enter another integer: ";
string d;
getline (cin,d);
RemLead0(d);
RemLead0(n);
if(!checkAllNumbers(n))
{
cout << "Numerator contains non-number characters. Quitting. " << endl;
return 1;
}
if(!checkAllNumbers(d))
{
cout << "Denominator contains non-number characters. Quitting. " << endl;
return 1;
}
if(d == "0")
{
cout << "Divide by zero error. Quitting. " << endl;
return 1;
}
string q = "";
string r = "";
divide(n,d,q,r);
cout << q << " remainder " << r << endl;
}
// A method to divide two strings.
void divide(string top, string bot, string &q, string &r)
{
string quo = "";
string temp = bot;
if(top == bot)
{
q = "1";
r = "0";
return;
}
int counter = 0;
while(isSmaller(temp, top))
{
temp = temp +"0";
counter++;
}
temp = RemLastChar(temp);
counter--;
for(int i = counter; counter >= 0; counter--)
{
i = i; //so my computer doesn't bitch about unused i
int count = 0;
while(isSmaller(temp, top))
{
top = subtract(top, temp);
count++;
}
quo = quo + (char)(count + '0');
temp = RemLastChar(temp);
}
q = quo;
r = top;
}
// Subtracts the bot string from the top string, checking to make sure the top string is bigger. Uses the nines compliment method.
string subtract(string top, string bot)
{
int lentop = top.length()-1;
int lenbot = bot.length()-1;
if(isSmaller(top, bot) && top != bot)
cout << "Subtraction resulted in negative number. Not responsible for really messed up answers. " << endl;
for(int i = 0; i < lentop - lenbot; i++)
{
bot = "0" + bot;
lenbot++;
}
string nines = "";
for(int i = 0; i < lenbot + 1; i++)
{
nines = nines + (char)((9 - (bot[i]-'0'))+'0');
}
string ninesplus1 = add(nines, "1");
string subtotal = add(ninesplus1, top);
string answer = subtotal.substr(1);
RemLead0(answer);
return answer;
}
// Adds two numerical strings n, and d.
string add(string n, string d)
{
int len1 = n.length()-1;
int len2 = d.length()-1;
int carry = 0;
string sum = "";
while(len1 >= 0 || len2 >= 0)
{
int digit1, digit2;
if(len1 >= 0) digit1 = n[len1]-'0';
else digit1 = 0;
if(len2 >= 0) digit2 = d[len2]-'0';
else digit2 = 0;
int i = digit1+digit2+carry;
if(i > 9) //or carry = i > 9 ? 1 : 0;
carry = 1; //OR carry = i / 10;
else
carry = 0;
int digit = i%10;
sum = ( (char)(digit + '0') )+ sum;
len1--;
len2--;
}
if(carry == 1)
sum = '1' + sum;
return sum;
}
//Returns true if all characters in the string are numbers, false otherwise.
bool checkAllNumbers(string n)
{
for(int i = 0; i < (int)n.length(); i++)
{
if('0' > n[i] || n[i] > '9')
return false;
}
return true;
}
// Returns a string just like the one it takes, but without the last character.
string RemLastChar(string s)
{
string answer = "";
for(int i = 0; i < (int)s.length() - 1; i++)
{
answer = answer + s[i];
}
return answer;
}
// Checks to see if numerical string one is smaller than string two. If it is, it returns true.
// I could've sworn one could do this with built in c++ string libraries, but for some reason I couln't get it to work.
bool isSmaller(string one, string two)
{
int lenone = one.length();
int lentwo = two.length();
//cout << "one: " << one <<" len1: " << lenone << " two: "<< two <<" len2: " << lentwo << endl;
if(lentwo > lenone)
{
//cout << one << " is smaller than " << two << endl;
return true;
}
if(lenone == lentwo)
{
int i = 0;
while(one[i] == two[i] && i != lenone-1)
{
i++;
}
if(one[i] <= two[i])
{
//cout << one << " is smaller than " << two << endl;
return true;
}
else
{
//cout << one << " is not smaller than " << two << endl;
return false;
}
}
//cout << one << " is not smaller than " << two << endl;
return false;
}
// Removes the leading 0's from a string. If the string is all 0's, it leaves the last one on.
void RemLead0(string &s)
{
while(s[0] =='0') /// or while(s != "0" && s[0] == '0')
{
if(s == "0") break; //and take this out
s = s.substr(1);
}
}
Mergesort on Linked List
This was one of my favorite assignments!
llmethods.cpp
//CS222 Shawn O'Neil Program 2, Linked List Merge Sort
//Working Version
#include <iostream>
#include "ll.h"
using namespace std;
int main()
{
LL M;
M.addfront("G");
M.addfront("C");
M.addfront("H");
M.addfront("C");
M.addfront("I");
M.addfront("K");
M.addfront("A");
M.addfront("D");
M.addfront("D");
M.addfront("E");
M.addfront("B");
M.addfront("F");
M.addfront("J");
M.print();
cout << endl;
M.sort();
M.print();
}
LL::LL()
{
head = NULL;
}
LL::~LL()
{
}
//Prints the Linked List
void LL::print()
{
if(head != NULL)
head->print();
}
//Splits the linked list from head down
void LL::split()
{
if(head != NULL)
head = head->split();
}
//Sorts the linked list from head down
void LL::sort()
{
if(head != NULL)
head = head->sort();
}
//Adds a node to the front of the linked list.
void LL::addfront(string str)
{
if(head != NULL)
head = new LLN(str, head);
else
head = new LLN(str, NULL);
}
LLN::LLN(string str, LLN *n)
{
s = str;
next = n;
}
LLN::~LLN()
{
}
//Sorts the linked list from this node downward - doesn't work, probably broken merge
LLN * LLN::sort()
{
if(next == NULL)
{
return this;
}
else
{
LLN *list = this;
LLN *one = split();
one = one->sort();
list = list->sort();
list = list->merge(one);
return list;
}
}
//Splits the linked list from this point downward Returns pointer to the head of other list
LLN * LLN::split()
{
if(next != NULL)
{
LLN *temp = next;
next = temp->split();
return temp;
}
else
{
return NULL;
}
}
//Merges two sorted linked lists, returns head of sorted linked list - I believe this is broken
LLN * LLN::merge(LLN *o)
{
if(o == NULL)
{
return this;
}
if(next == NULL)
{
if(s <= o->s)
{
next = o;
return this;
}
}
LLN *temp;
if(s <= o->s)
{
temp = this;
temp->next = o->merge(next);
}
else
{
temp = o;
temp->next = merge(o->next);
}
return temp;
}
//Prints the linked list from this point downward
void LLN::print()
{
cout << s << endl;
if(next != NULL)
next->print();
}
ll.h
#ifndef _LLH_
#define _LLH_
#include <string>
using namespace std;
class LL;
class LLN;
class LL
{
private:
LLN *head;
public:
LL ();
~LL ();
void print ();
void split();
void addfront (string str);
void sort (); //Sorts a LL in alphabetical order
};
class LLN
{
private:
LLN *next;
string s;
public:
LLN (string str, LLN *n);
~LLN ();
void print ();
LLN *sort (); //Sorts the list from this point down;
//returns the new head of this sorted list
LLN *split (); //Splits the list in half. If original list is
//1->2->3->4->5->... , the new lists are 1->3->5->...
//and 2->4->6->... this is still node 1 (of course) and
//the pointer to node 2 is returned.
LLN *merge (LLN *o); //merges two sorted lists. this is the head of
//one list; o is the head of the other. The new
//head of the merged list is returned.
};
#endif