Class Notes (808,652)
Canada (493,325)
CMPT 225 (60)
John Edgar (28)
Lecture 3

CMPT 225 Week 3 Lecture 3

3 Pages
Unlock Document

Simon Fraser University
Computing Science
CMPT 225
John Edgar

Copy Constructor and Assignment Operator for Linked List Stack void MyStack::deepCopy(const MyStack & st) { top = NULL; if ( != NULL) { Node* original =; 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

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.