CPS 6, Ramm - Summer Semester I - 6/14/99 #17
- Announce
- Coin Toss for Random Quiz #7
- Hour Test on Wednesday
- Review Tomorrow
- See Sample Test(s)
Chap 8. Arrays, Data, & Random Access
- A Simple Information Storage/Retrieval System
- Concepts
- Store lines from file in vector
- Retrieve lines by matching substrings
- Like UNIX grep program
-
getinfo.cc
- Improving the Storage/Retrieval System
- Recursion
- Self Referential ("calls itself")
- Clone Model
- Base Case ("Anchor")
- Breaking Problem in Simpler Case
- -- Usually slightly simpler
-
fact.cc
- Integer to English by Recursion
- Integer to any Base by Recursion
- WordList Class
- List of Unique Words
- Update with next word
- Print Unique List
-
allword3.cc
- Binary Search
- Telephone Book Analogy
- Requires Sorted Lists
-
| list size | binary search | sequential search
|
| 1 | 1 | 1
|
| 10 | 4 | 10
|
| 1,000 | 11 | 1000
|
| 5,000 | 14 | 5000
|
| 100,000 | 18 | 100,000
|
| 1,000,000 | 21 | 1,000,000
|
-
binsearch
- Keeping a Sorted List
- WordList Class Improved
- Keep Track of:
- Unique Words AND
- Word Frequency
- Use Vector of Structs
- Incorporate Binary Search
- Deal with Case and Punctuation
-
allword4