CPS 6, Ramm - Summer Semester I - 6/22/99 #22
- Announce
- Coint Toss for Random Quiz #10
- Random Quiz #11
Chap 11. Sorting, Algorithms, & Matrices
- Looking at the Code
timesort.cc
- More on Assignment #7 Blob Count
- Possible Iterative Approaches
- Easy to make mistakes
- Consider using recursion
- Much easier to program
- Example Recursive Solution to Fill Problem
- (Should give you hint as to how to approach blob count)
- Use character plot
- 0 represents space
- 1 represents figure boundary
- larger numbers represent colors
-
fillplot.cc
- Recursive Specifics of Fill
- Routine does nothing (no recursive call) if:
- Hit boundaries of graph
- Hit boundaries of figure
- Hit point already colored
- Color current point [r][c]
- Call Fill (recursively) for:
- Each of eight neighboring points
-
[r-1][c-1] [r-1][ c ] [r-1][c+1]
-
[ r ][c-1] - - - - - -[ r ][c+1]
-
[r+1][c-1] [r+1][ c ] [r+1][c+1]
Chap 12. Information Hiding & Dynamic Data
- Motivation for Pointers
- More precise control of memory allocation
- (Vectors were doubled on resizing)
- Provide indirect references for sharing
- Linked Data Structures need pointers
- Pointers as Indirect References
- Pointer holds a memory address
- Pointer refers to something indirectly
- Indexes, Directories, Mail Addresses
- Pointers Definition
- int * p;
- Dice * diePtr;
- string * strP;
- Pointers as References
- address: below the surface
- * dereference operator
- & address-of operator
- Examples
- Pointer uses (conceptual)
- Tag Sorts
- Sort list by more than one key
- Pointers as Parameters
- swap using reference parameters
- swap using pointers (C style)
- The
new Operator
- The Selection Operator
->
- Simple Examples
- Implementing a Tag Sort
- Use a vector of pointers
- Modify Selection Sort
- Linked Lists
- Pointer Diagrams
- Conceptual
- The Null Pointer
- The Stack
- Empty
- Overflow?
- (Vector Implementation)
- Delete
- Implementing a Stack