exam 3 definitions and code questions

Question 1

what are the private variables of the Itr class?

Answer 1

dnode<T>* current</T>

Question 2

what are the public members of the dnode class used in the Itr class?

Answer 2

T data;
dnode<T>* next;
dnode<T>* prev;</T></T>

Question 3

what is the relationship of the List class to the iterator class?

Answer 3

the List class is declared a friend class of Itr in its public section

Question 4

write the in-line definition of the default constructor for the Itr class

Answer 4

Itr(): current(0) {};

Question 5

write the in-line definition of the constructor that takes a dnode parameter for the Itr class

Answer 5

Itr(dnode<T> *ptr): current(ptr) {};</T>

Question 6

write the in-line non-const operator* (functions as the dereference operator) for the Itr class

Answer 6

T& operator*() {return current->data;};

Question 7

write the in-line const operator* (functions as the dereference operator) for the Itr class

Answer 7

T operator*() {return current->data;};

Question 8

what is the difference in the function definitions for ++i and i++ (also –i and i–) for the Itr class?

Answer 8

i++ and i– have an int dummy parameter to let the compiler know it is ++i and not i++. Also, all the pre-increments return a reference, and all the post-increments do not.

Question 9

write the in-line definition for the pre-increment operator for the Itr class

Answer 9

Itr<T>& operator++() {
if(current) current = current ->next;
return *this;
}</T>

Question 10

write the in-line definition for the post-increment operator for the Itr class

Answer 10

Itr<T> operator++(int){
Itr<T> result = current;
if(current) current = current->next;
return result;
}</T></T>

Question 11

write the in-line definition for the pre-decrement operator for the Itr class

Answer 11

Itr<T>& operator--(){
if(current) current = current->prev;
return *this;
}</T>

Question 12

write the in-line definition for the post-decrement operator for the Itr class

Answer 12

Itr<T> operator--(int){
Itr<T> result = current;
if(current) current = current->prev;
return result;
}</T></T>

Question 13

what requirements need to be met in order to overload the points at (->) operator?

Answer 13

in order to overload, the operator must be a method, not a free function, and must return a pointer or object of that class

Question 14

write the in-line definition for the non-const points to operator (operator->) for the Itr class

Answer 14

dnode<T>* operator->() {return current;};</T>

Question 15

write the in-line definition for the const points to operator (operator->) for the Itr class

Answer 15

const dnode<T>* operator->() {return current;};</T>

Question 16

write the in-line definition of the operator== for the Itr class

Answer 16

bool operator==(Itr<T> rhs) const {return current == rhs.current;};</T>

Question 17

write the in-line definition of the operator!= for the Itr class

Answer 17

bool operator!=(Itr<T> rhs) const {return !(current == rhs.current);</T>

Question 18

what are the private variables of the List class?

Answer 18

dnode<T>* beginning;
dnode<T>* ending;</T></T>

Question 19

write the in-line default constructor for the List class

Answer 19

List(): beginning(0), ending(0) {};

Question 20

write the in-line operator= for the List class

Answer 20

operator= (List<T> rhs) {swap(rhs); return *this;};</T>

Question 21

write the in-line definition for the function isEmpty for the List class

Answer 21

bool isEmpty() const {return beginning == 0;};

Question 22

write the non-const in-line definition for the function begin for the List class that returns an iterator pointing to the beginning of the list.

Answer 22

Itr<T> begin() {return Itr<T>(beginning);};</T></T>

Question 23

write the const in-line definition for the function begin for the List class that returns an iterator pointing to the beginning of the list.

Answer 23

const Itr<T> begin() const {return Itr<T>(beginning);};</T></T>

Question 24

write the non-const in-line definition for the function end for the List class that returns an iterator pointing to the ending of the list.

Answer 24

Itr<T> end() {return Itr<T>(ending);};</T></T>

Question 25

write the const in-line definition for the function begin for the List class that returns an iterator pointing to the ending of the list.

Answer 25

const Itr end() const {return Itr(ending);};

Question 26

write the non-const in-line definition for the function front for the List class that returns the front element of the list

Answer 26

T& front() {return beginning->data;};

Question 27

write the const in-line definition for the function begin for the List class that returns the front element of the list.

Answer 27

const T front() {return beginning->data;};

Question 28

write the non-const in-line definition for the function back for the List class that returns the last element of the list.

Answer 28

T& back() {return ending->data;};

Question 29

write the const in-line definition for the function back for the List class that returns the last element of the list.

Answer 29

const T back() {return ending->data;};

Question 30

write the insertAfter method for the List class

Answer 30

template void List::insertAfter(Itr ptr, const T& item){ dnode *temp = new dnode(item); if(beginning == 0){ //list is empty beginning = temp; ending = temp; } else if(ptr == ending){ //add to the end of the list temp->prev = ending; ending->next = temp; ending = temp; } else{ //add to the middle of the list temp->next = ptr->next; temp->prev = ptr.current; ptr->next->prev = temp; ptr->next = temp; } }

Question 31

write the insertBefore method for the List class

Answer 31

template void List::insertBefore(Itr ptr, const T& item){ dnode *temp = new dnode(item); if(beginning == 0){ beginning = temp; ending = temp; } else if(ptr == beginning){ //insert before beginning beginning->prev = temp; temp->next = beginning; beginning = temp; } else{ temp->next = ptr.current //point to the same thing ptr points to temp->prev = ptr->prev; ptr->prev->next = temp; ptr->prev = temp; } }

Question 32

write the remove method for the List class. include requires and ensures

Answer 32

//REQUIRES: !isEmpty() && ptr->x2 && beg -> x1 <-> x2 <-> x3 <- end //ENSURES: beg -> x1 <-> x3 <- end template void List::remove(Itr ptr){ if(isEmpty()) return; if(ptr == 0) return; if(ptr == beginning) beginning = beginning->next; else ptr->prev->next = ptr->next; if(ptr == ending) ending = ending->prev; else ptr->next->prev = ptr->prev; delete ptr.current; }

Question 33

write the length method for the List class

Answer 33

template int List::length() const{ int result = 0; Itr i = begin(); while(i != 0){ ++result; ++i; } return result; }

Question 34

write the destructor for the List class

Answer 34

template List::~List(){ dnode *temp; while(beginning != 0){ temp = beginning; beginning = beginning->next; delete temp; } }

Question 35

write the copy constructor for the List class

Answer 35

template List::List(const List& actual): List(){ if(actual.beginning == 0) return; beginning = new dnode(actual.beginning->data); ending = beginning; Itr = actual.beginning->next; while(i != 0){ ending->next = new dnode(i->data); ending->next->prev = ending; ending = ending->next; ++i; } }

Question 36

make the swap method for the List class

Answer 36

template void List::swap(List rhs){ dnode *temp = beginning; beginning = rhs.beginning; rhs.beginning = temp; temp = ending; ending = rhs.ending; rhs.ending = temp; }

Question 37

write the find method for the List class

Answer 37

template const Itr List::find(const T& key) const{ Itr result = begin(); while(result != 0){ if(result->data == key){ return result; } ++result; } return Itr(0) //like returning a -1 }

Question 38

overload operator[] as a method for the List class

Answer 38

Itr List::operator[](int n){ Itr result = begin(); int i = 0; while(i < n && result != 0){ ++i; ++result; } return result; //will either be a zero or pointing to the nth item in the list }

Question 39

what are the public members of class bnode?

Answer 39

bnode *left; bnode *right; T data;

Question 40

the bnode class goes with what other class?

Answer 40

the btree class

Question 41

write the in-line default constructor for the bnode class

Answer 41

bnode() {};

Question 42

write the in-line constructor for the bnode class that takes a T item as a parameter

Answer 42

bnode(const T& item): data(item) {};

Question 43

what are the private variables of the btree class?

Answer 43

T data; bool empty; btree *left; btree *right;

Question 44

write the in-line default constructor for the btree class

Answer 44

btree(): empty(true), left(0), right(0) {};

Question 45

write the in-line constructor for the btree class that takes a T item as a parameter

Answer 45

btree(const T& item): data(item), empty(false), left(0), right(0) {};

Question 46

write the in-line overload for operator= for the btree class

Answer 46

btree& operator=(btree rhs) {swap(rhs); return *this;};

Question 47

write the in-line method isEmpty for the btree class

Answer 47

bool isEmpty() const {return empty;};

Question 48

write the bfind method for the btree class

Answer 48

template bool btree::find(const T& key) const{ if(key == data) return true; if(key < data){ if(left) return left->bfind(key); else return false; } else{ if(right) return right->bfind(key); else return false; } }

Question 49

write the binsert method for the btree class

Answer 49

template void btree::binsert(const T& x){ if(empty){ data = x; empty = false; } else if(x < data){ //put in left subtree if(left) left->binsert(x); else left = new btree(x); } else { //put in right subtree if(right) right->binsert(x); else right = new btree(x); } }

Question 50

write the inorder method for the btree class

Answer 50

template void btree::inorder(std::ostream& out) const{ if(!empty){ if(left) left->inorder(out); out << data; if(right) right->inorder(out); }

Question 51

write the preorder method for the btree class

Answer 51

template void btree::preorder(std::ostream& out) const{ if(!empty){ out << data; if(left) left->inorder(out); if(right) right->inorder(out); }

Question 52

write the postorder method for the btree class

Answer 52

template void btree::postorder(std::ostream& out) const{ if(!empty){ if(left) left->inorder(out); if(right) right->inorder(out); out << data; }

Question 53

write the copy constructor for the btree class

Answer 53

template btree::btree(const btree& actual): btree(){ //do a preorder traversal data = actual.data; empty = actual.empty; if(actual.left){ left = new btree(*(actual.left)); //need a btree, not a pointer to one } if(actual.right){ right = new btree(*(actual.right)); } }

Question 54

write the destructor for the btree class

Answer 54

template btree::~btree(){ //do a postorder traversal if(left) delete left; //recursively calls dtor if(right) delete right; //recursively calls dtor }

Question 55

write the swap method for the btree class

Answer 55

template void btree::swap(btree& rhs){ btree* ptr = left; left = rhs.left; rhs.left = ptr; ptr = right; right = rhs.right; rhs.right = ptr; T temp = data; data = rhs.data; rhs.data = temp; bool tmp = empty; empty = rhs.empty; rhs.empty = tmp; }

Question 56

write the predecessor function for the btree class

Answer 56

template T btree::predecessor(){ //predecessor will either be a leaf or have a left subtree if(right) return right->predecessor(); return data; }

Question 57

what are the private members of the bnode2 class?

Answer 57

T data; bnode *left; bnode *right;

Question 58

the bnode2 class goes with what other class?

Answer 58

the btree2 class

Question 59

write the in-line default constructor for the bnode2 class

Answer 59

bnode(): left(0), right(0) {};

Question 60

write the constructor for the bnode2 class that takes a T item as a parameter

Answer 60

bnode(const T& x): data(x), left(0), right(0) {};

Question 61

write the find method for the bnode2 class

Answer 61

template bool bnode::find(const T& key){ if(key == data) return true; if(key < data){ if(left) return left->find(key); else return false; } else{ if(right) return right->find(key); else return false; } }

Question 62

write the insert method for the bnode2 class

Answer 62

template void bnode::insert(const T& x){ if(x == data) return; //no duplicates if(x < data){ if(left) left->insert(x); else left = new bnode(x); } else{ if(right) right->insert(x); else right = new bnode(x); } }

Question 63

write the destructor for the bnode2 class

Answer 63

template bnode::~bnode(){ if(left) delete left; if(right) delete right; }

Question 64

write the copy constructor for the bnode2 class

Answer 64

template bnode::bnode(const bnode& actual): bnode(){ data = actual.data; if(actual.left) left = new bnode(*(actual.left)); if(actual.right) right = new bnode(*(actual.right)); }

Question 65

write the remove method for the bnode2 class

Answer 65

template bnode* bnode::remove(const T& x){ if(x == data){ //found node to remove if(!left && !right){ //has no children delete this; return 0; } if(!left && right){ //has only right child bnode *temp = right; right = 0; delete this; return temp; } if(left && !right){ //has only left child bnode *temp = left; left = 0; delete this; return temp; } //two children data = left->predecessor(); left = left->remove(data); return this; } else if(x < data){ //remove from left subtree left = left->remove(x); } else{ remove from right subtree right = right->remove(x); } return this; }

Question 66

what are the private variables of the btree2 class?

Answer 66

bnode2 *root;

Question 67

write the in-line default constructor for the btree2 class

Answer 67

btree(): root(0) {};

Question 68

write the in-line definition for the overloaded operator= as a method for the btree2 class

Answer 68

btree& operator=(btree& rhs) {swap(rhs); return *this;};

Question 69

write the in-line definition for the isEmpty method for the btree2 class

Answer 69

bool isEmpty() const {return root == 0;};

Question 70

write the find method for the btree2 class

Answer 70

template bool btree::find(const T& key){ if(!root) return false; return root->find(key) //calls bnode2 find method

Question 71

write the insert method for the btree2 class

Answer 71

template void btree::insert(const T& x){ if(root == 0) { //insert at root if root empty root = new bnode(x); } else{ root->insert(x); } }

Question 72

write the destructor for the btree2 class

Answer 72

template btree::~btree(){ delete root; }

Question 73

write the copy constructor for the btree2 class

Answer 73

template btree::btree(const btree& actual){ if(actual.root){ root = new bnode(*(actual.root)); } }

Question 74

write the swap method for the btree2 class

Answer 74

template void btree::swap(btree& rhs){ bnode *temp = root; root = rhs.root; rhs.root = temp; }

Question 75

write the remove method for the btree2 class

Answer 75

template void btree::remove(const T& x){ if(find(x)) root = root->remove(x); }

Question 76

with inheritance, if you have a virtual method what else do you need in the base class?

Answer 76

a virtual destructor, even if it does nothing

Question 77

how do you declare a child class?

Answer 77

class ChildName: public ParentName { ... };

Question 78

what does the protected keyword do?

Answer 78

it allows the children of a parent class to use the protected variable, but the variable is private to any other class or function