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

# CMPT 225 Week 3 Lecture 3

3 Pages
170 Views

School
Simon Fraser University
Department
Computing Science
Course
CMPT 225
Professor
John Edgar
Semester
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

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.