SI204 Class 24: Intro to Arrays

Homework
Write a program that reads a target string A and a test string S and tells the user whether A is a substring of S. A is a substring of S means that A appears (in order and together!) in S somwhere. For example: low is a substring of allowable (see it? "allowable"), but not of withhold (see the letters are there but not in order in "withhold"), nor in landowner (see the letters are there and in order but not together in "landowner"). A typical run of your program should look like this:
Enter target string: act
Enter test string  : reactionary
The target act is a substring of the test string reactionary!
Turn in a printout of your program, along with a screen capture showing it run on the above example. Remember to make sure you never try to index a character outside of the string!

Lecture

A Simple Problem Made Difficult

Let's start with a simple problem: Write a program that reads firstname lastname, and prints out firstname, lastname. For example, a typical run of the program might look like:
Chris Brown
Brown, Chris
    
... where the red text is user input. This should be no problem, something like this will do:
string first, last;
cin >> first >> last;
cout << last << ", " << first << endl;
Now let's make things more difficult: Suppose I also want to capitalize all the letters in the names. No matter how hard you work with what we've learned of C++, there's no way you can write this program! You can capitalize, you can switch first and last names, you just can't do both together. The problem is that you need to access the characters within the strings first and last, and you need to know how many characters are in the strings.

The "how many characters are in the strings" part is easy. It turns out that whenever you have an object of type string you can put a .length() at the end of it and the resulting expression returns the length of the string. So, from the previous code I could ask for first.length() and (with first name "Chris") the result would be 5.

As you might suspect, it is also possible to reference characters within a string - not by specific names, but by indices. So the initial character of the string first, for example, has index 0. To reference it, say for printing, you write first[0], which we usually read as "first zub zero". Characters within a string are thus indexed from zero up to one less than the length of the string, like this:

Using indices, we can make sure that every character within the string first is printed in capitals:

for(int i = 0; i < first.length(); i++)
  if ('a' <= first[i] && first[i] <= 'z')
    cout << char(first[i] - ('a' - 'A'));
  else
    cout << first[i];
In fact, it might be kind of nice to make a function to do the printing in capitals for us, and produce a program like this.

The Idea of Arrays

When we access an ordered collection of objects, all of the same type, by indices rather than by individual names, we are using arrays. This is one of the most powerful ideas in computer science, so you better learn to love it! The excercises below and the remainder of the notes here are just to help you play with the idea of accessing objects within an array by index rather than by specific name. A string is, essentially, and array of objects of type char. In coming lectures, you'll see that we can have arrays of any type of object we choose.

Arrays allow us to store and compute with large amounts of information in programs without needing separate variable names for each object we store. In the past example, a single variable name first stood for as many char objects as needed.

The key behind this indexing with strings, is that the expression first[i] is an object of type char. You don't need any special rules to tell you what you can and can't do with an expression like first[i], because anything you can do with a char you can do with it. The one potential pitfall is this: Don't use a negative number for an index, and don't use a number that is greater than or equal to the length of the string! There aren't any characters there to index!

Modifying Strings

Now, we might want to actually change the string we've got - for example modify it so that all of its letters are capitals. We can do this the following way:
string s;
cin >> s;

for(int i = 0; i < s.length(); i++)
  if ('a' <= s[i] && s[i] <= 'z')
    s[i] = s[i] - ('a' - 'A');

cout << s << endl;
You say "How do I know I can assign a value to s[i] like that?" Well, s[i] is a char like any other so, you can assign to it just like you assign to any other char variable!

Problems

  1. Print in reverse (non-recursive)
  2. Print in reverse (recursive!)
  3. A predicate that tests whether two strings are reverses of each other.
  4. palindromes
  5. A predicate that takes a string s and a char c, and tests whether or not c appears in s.


Asst Prof Christopher Brown
Last modified: Thu Oct 18 17:01:25 EDT 2001