DOC PREVIEW
Stanford CS 106B - Strings and Recursive Functions

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Eric Roberts Handout #8CS 106B April 6, 2009Strings and Recursive FunctionsStrings in C++Recursive FunctionsEric RobertsCS 106BApril 6, 2009Data Types: A Pedagogical Experiment• Chapter 2 of the reader introduces the primitive types in C++along with the mechanisms that languages have traditionallyoffered to create compound types from primitive ones.• In keeping with the overall strategy of showing you how touse data structures before you see their implementation, I’mgoing to see whether it is possible to postpone the discussionof the Chapter 2 material until after I need it to implement thevarious classes introduced in the later chapters. Once youhave the class-based tools from Chapter 4, you won’t havemuch occasion to use the low-level structures anyway.• The only problem on Assignment #1 that requires datastructures at all is the histogram problem, which needs anarray to keep track of the scores in each range. If you’rereading ahead, feel free to use the Vector class introduced inChapter 4 instead. Otherwise, read enough of section 2.4 tosee how to declare such an array.C Strings• Almost any program that you write in any modern language islikely to use string data at some point, even if it is only todisplay instructions to the user or to label results.• Conceptually, a string is just an array of characters, which isprecisely how strings are implemented in the C subset ofC++. If you put double quotation marks around a sequence ofcharacters, you get what is called a C string, in which thecharacters are stored in an array of bytes, terminated by a nullbyte whose ASCII value is 0. For example, the characters inthe C string "hello, world" are arranged like this:h0e1l2l3o4,5 6w7o8r9l10d11\012• As in Java, character positions in a string are identified by anindex that begins at 0 and extends up to one less than thelength of the string.Strings as an Abstract Data Type• Because C++ includes everything in its predecessor language,C strings are a part of C++, and you will occasionally have torecognize that this style of string exists.• For almost every program you write, it will be far easier touse the C++’s string class, which implements strings as anabstract data type, which is a type defined by its behaviorrather than its representation.• The methods C++ provides for working with strings are oftensubtly different from those in Java’s String class. As Iemphasized on Friday, however, most of these differences fallinto the accidental category.• The only essential difference between strings in C++ and Javais that C++ allows clients to change the individual characterscontained in a string; by contrast, Java strings are immutable,which means that they never change once they are allocated.Calling String Methods• Because string is a class, it is best to think of its methods interms of sending a message to a particular object. The objectto which a message is sent is called the receiver, and thegeneral syntax for sending a message looks like this:receiver.name(arguments);• For example, if you want to determine the length of a string s,you might use the assignment statementint len = s.length();just as you would in Java.• Unlike Java, C++ allows classes to redefine the meanings ofthe standard operators. As a result, several string operations,such as + for concatenation, are implemented as operators.The Concatenation Operator• As many of you already know from Java, the + operator is awonderfully convenient shorthand for concatenation, whichconsists of combining two strings end to end with nointervening characters. In Java, this extension to + is part ofthe language. In C++, it is an extension to the string class.• In Java, the + operator is often used to combine items as partof a println call, as inprintln("The total is " + total + ".");In C++, you would achieve the same result by writingcout << "The total is " << total << "." << endl;• Although you might imagine otherwise, you can’t use the ++operator in this statement, because the quoted strings after Cstrings and not string objects.– 2 –Operators on the string Classstr[i]Returns the ith character of str. Assigning to str[i] changes that character.s1 + s2Returns a new string consisting of s1 concatenated with s2.s1 = s2;Copies the character string s2 into s1.s1 += s2;Appends s2 to the end of s1.s1 == s2 (and similarly for <, <=, >, >=, and !=)Compares to strings lexicographically.Common Methods in the string Classstr.length()Returns the number of characters in the string str.str.at(index)Returns the character at position index; most clients use str[index] instead.str.substr(pos, len)Returns the substring of str starting at pos and continuing for len characters.str.find(ch, pos)Returns the first index  pos containing ch, or string::npos if not found.str.find(text, pos)Similar to the previous method, but with a string instead of a character.str.insert(pos, text)Inserts the characters from text before index position pos.str.replace(pos, count, text)Replaces count characters from text starting at position pos.Destructively changes strDestructively changes strExercise: String Processing•An acronym is a word formed by taking the first letter ofeach word in a sequence, as in• Write a C++ program that generates acronyms, as illustratedby the following sample run:"self contained underwater breathing apparatus" "scuba"AcronymProgram to generate acronymsEnter string: not in my back yardThe acronym is "nimby"Enter string: Federal Emergency Management AgencyThe acronym is "FEMA"Enter string:Recursive Functions• The easiest examples of recursion to understand are functionsin which the recursion is clear from the definition. As anexample, consider the factorial function introduced in Chapter5, which can be defined in either of the following ways:n! = n x (n - 1) x (n - 2) x . . . x 3 x 2 x 1n! =n x (n - 1)!1if n is 0otherwise• The second definition leads directly to the following code,which is shown in simulated execution on the next slide:int Fact(int n) { if (n == 0) { return 1; } else { return n * Fact(n - 1); }}The Recursive Paradigm• Most recursive methods you encounter in an introductorycourse have bodies that fit the following general pattern:if (test for a simple case) { Compute and return the simple solution without using recursion.} else { Divide the problem into one or more subproblems that have the same form. Solve each of the


View Full Document

Stanford CS 106B - Strings and Recursive Functions

Download Strings and Recursive Functions
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Strings and Recursive Functions and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Strings and Recursive Functions 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?