Class Notes
(808,652)

Canada
(493,325)

Simon Fraser University
(12,077)

Computing Science
(220)

CMPT 225
(60)

John Edgar
(28)

Lecture 3

# CMPT 225 Week 3 Lecture 3

Unlock Document

Simon Fraser University

Computing Science

CMPT 225

John Edgar

Summer

Description

Copy Constructor and Assignment Operator for Linked List Stack
void MyStack::deepCopy(const MyStack & st)
{
top = NULL;
if (st.top != NULL) {
Node* original = st.top;
Node* copy;
// Copy the top
copy = new Node(original->data, NULL);
top = copy;
original = original->next;
while (original != NULL) {
copy->next = new Node(original->data, NULL);
copy = copy->next;
original = original->next;
}
}
}
Will basically make a copy of any linked list that has a single pointer to the front of the list.
Going to have to deal with stacks that already exist, have to get rid of them somehow
So, write a helper function. Used in destructor, copying.
void MyStack::deleteStack() {
Node* temp = top;
while(temp != NULL) { // a ; here would have compiled, but caused a memory leak?
// kill everything in stack
temp = top->next;
delete top;
top = temp;
}
}
MyStack & MyStack::operator= (const MyStack & st)
{
if (this != &st) {
deleteStack();
deepCopy(st);
}
}
Back to Recursion
Analysis of fib(5): see notebook
Recursive functions do not use loops to repeat instructions.
Recursive functions will have at least 2 cases: base case and recursive case
Base can be implicit. (if false, do nothing as example) Base case is smaller problem with smaller solution. Cannot be recursive! Or you'll never terminate.
That's the whole point of the base case.
Can be more than one base case.
Recursive case should have smaller input each time
Can have more than one
Define the problem in smaller problems of the same type.
By how much does each recursive call reduce the problem size? Will the base case be reached as the
problem is reduced?
Recursive Searching
Linear Searching and Binary Searching
Linear Search:
int linSearch(int arr[], int size, int x) {
for (int i = 0; i < size; i++) {
if (x == arr[i]) {
return i;
}
}
return -1;
}
int recLinSearch(int arr[], int next, int size, int x) {
if (next >= size) {
return -1; // reached end of array, one of the base cases
} else if (x == arr[i]) {
return i; // found element; another base case
} else {
return recLinSearch(arr, next + 1, size, x);
}
}
Binary Search
Requires that the array is sorted.
Either asc or desc, but you need to know which!
Divide and Conquer algorithm
Each iteration reduces problem space in half
Ends whe

More
Less
Related notes for CMPT 225