Class Challenge

Write a function that finds and returns the earliest position of a number in a linked list. If the number is not in the list or the list is empty, your function should return -1 to indicate this.

int findPos(int *curr, int num) 
{
    if (!curr) 
    	return -1;
    if (curr->val == num) 
    	return 0;
    if (findPos(cur->next, num) == -1) 
    	return -1;
    else 
    	return 1+findPos(cur->next, num);
 
}

Memory usage!

Be careful!! Recursion can be a pig when it comes to memory usage!
Never let your recursive calls get too deep!

Binary Search

Goal: Search a sorted array of data for a particular item
Idea: Use recursion and a divide-and-conquer approach!

// pseudocode
Search(sortedWordList, findWord)
{
    if no word in the list
    	not found
    if findWord == middle word
    	found
   
    if findWord < middle word
    	Search(first half of sortedWordList);
    else 
    	Search(second half of sortedWordList);	
        
}

int BS(string A[], int top, int bot, string f)
{
    if (top > bot)
    	return -1;
    else 
    	int mid = (top + bot)/2;
        if (f == A[Mid])
        	return Mid;
        else if (f < A[Mid])
        	return BS(A, top, Mid-1, f);
        else if (f > A[Mid])
        	return BS(A, Mid+1, bot, f);    
}

Generic Programming

Goal: To build algo that are able to operate on many different types of data
ex) Sort function that sorts string, ints, and Student objects, etc.

Custom comparison operators

bool operator >= (const Dog &a, const Dog &b) 
{
     if (a.getWeight() >= b.getWeight) eturn true;
     else return false;
}

main () 
{
    Dog fido(5), spot(3);
    if (fido >= spot)
    {
    	cout << "fido wins";
    }

}

As we can see in operator >= declaration, since a and b are const, our function can only call const functions in class Dog.

getWeight() should be const too!

If we forget the const keyword, we will see the compile error!

Template

template <typename Item>

void swap (Item &a, Item &b) 
{
    Item temp;
    temp = a;
    a = b;
    a = temp;
}

// use our templated func 
main() 
{
    Dog d1(10), d2(20);
    swap (d1, d2);
    
    Circle c1(10), c2(20);
    swap (c1, c2);
}

Now Swap() works both asSwapCircle() and SwapDog()

Function Template Details

You must use the template data type to define the type of at least one formal parameter, or you'll get an ERROR!

In classes with externally defined member functions, things get ugly!

Can add template <typename xxx> before the class declaration itself, and before each definition, outside the class

STL Class: Vector

The STL vector is a template class that works just like an array, only it doesn't have a fixed size!

Vectors grow/shrink automagically when you add/remove items.