C++ Beginner's Guide CH04

C++ A Beginner’s Guide by Herbert Schildt Module 4 Arrays, Strings, and Pointers Table of Contents CRITICAL SKILL 4.1: Use one-dimensional arrays .......................................................................................... 2 CRITICAL SKILL 4.2: Two-Dimensional Arrays................................................................................................ 6 CRITICAL SKILL 4.3: Multidimensional Arrays ............................................................................................... 8 CRITICAL SKILL 4.4: Strings .......................................................................................................................... 11 CRITICAL SKILL 4.5: Some String Library Functions ..................................................................................... 13 CRITICAL SKILL 4.6: Array Initialization ....................................................................................................... 17 CRITICAL SKILL 4.7: Arrays of Strings........................................................................................................... 21 CRITICAL SKILL 4.8: Pointers........................................................................................................................ 23 CRITICAL SKILL 4.9: The Pointer Operators ................................................................................................. 24 CRITICAL SKILL 4.10: Pointer Expressions ................................................................................................... 27 CRITICAL SKILL 4.11: Pointers and Arrays ................................................................................................... 29 CRITICAL SKILL 4.12: Multiple Indirection ................................................................................................... 40 This module discusses arrays, strings, and pointers. Although these may seem to be three disconnected topics, they aren’t. In C++ they are intertwined, and an understanding of one aids in the understanding of the others. An array is a collection of variables of the same type that are referred to by a common name. Arrays may have from one to several dimensions, although the one-dimensional array is the most common. Arrays offer a convenient means of creating lists of related variables. The array that you will probably use most often is the character array, because it is used to hold a character string. The C++ language does not define a built-in string data type. Instead, strings are implemented as arrays of characters. This approach to strings allows greater power and flexibility than are available in languages that use a distinct string type. A pointer is an object that contains a memory address. Typically, a pointer is used to access the value of another object. Often this other object is an array. In fact, pointers and arrays are related to each other more than you might expect. CRITICAL SKILL 4.1: Use one-dimensional arrays A one-dimensional array is a list of related variables. Such lists are common in programming. For example, you might use a one-dimensional array to store the account numbers of the active users on a network. Another array might store the current batting averages for a baseball team. When computing the average of a list of values, you will often use an array to hold the values. Arrays are fundamental to modern programming. The general form of a one-dimensional array declaration is type name[size]; Here, type declares the base type of the array. The base type determines the data type of each element that makes up the array. The number of elements the array can hold is specified by size. For example, the following declares an integer array named sample that is ten elements long: int sample[10]; An individual element within an array is accessed through an index. An index describes the position of an element within an array. In C++, all arrays have zero as the index of their first element. Because sample has ten elements, it has index values of 0 through 9. You access an array element by indexing the array using the number of the element. To index an array, specify the number of the element you want, surrounded by square brackets. Thus, the first element in sample is sample[0], and the last element is sample[9]. For example, the following program loads sample with the numbers 0 through 9: The output from this example is shown here: This is sample[0]: 0 This is sample[1]: 1 This is sample[2]: 2 This is sample[3]: 3 This is sample[4]: 4 This is sample[5]: 5 This is sample[6]: 6 This is sample[7]: 7 This is sample[8]: 8 This is sample[9]: 9 In C++, all arrays consist of contiguous memory locations. (That is, all array elements reside next to each other in memory.) The lowest address corresponds to the first element, and the highest address corresponds to the last element. For example, after this fragment is run: nums looks like this: Arrays are common in programming because they let you deal easily with sets of related variables. Here is an example. The following program creates an array of ten elements and assigns each element a value. It then computes the average of those values and finds the minimum and the maximum value. The output from the program is shown here: Average is 34 Minimum value: -19 Maximum value: 100 Notice how the program cycles through the elements in the nums array. Storing the values in an array makes this process easy. As the program illustrates, the loop control variable of a for loop is used as an index. Loops such as this are very common when working with arrays. There is an array restriction that you must be aware of. In C++, you cannot assign one array to another. For example, the following is illegal: To transfer the contents of one array into another, you must assign each value individually, like this: for(i=0; i < 10; i++) a[i] = b[i]; No Bounds Checking C++ performs no bounds checking on arrays. This means that there is nothing that stops you from overrunning the end of an array. In other words, you can index an array of size N beyond N without generating any compile-time or runtime error messages, even though doing so will often cause catastrophic program failure. For example, the compiler will compile and run the following code without issuing any error messages even though the array crash is being overrun: int crash[10], i; for(i=0; i<100; i++) crash[i]=i; In this case, the loop will iterate 100 times, even though crash is only ten elements long! This causes memory that is not part of crash to be overwritten. Ask the Expert Q: Since overrunning an array can lead to catastrophic failures, why doesn’t C++ provide bounds checking on array operations? A: C++ was designed to allow professional programmers to create the fastest, most efficient code possible. Toward this end, very little runtime error checking is included, because it slows (often dramatically) the execution of a program. Instead, C++ expects you, the programmer, to be responsible enough to prevent array overruns in the first place, and to add appropriate error checking on your own as needed. Also, it is possible for you to define array types of your own that perform bounds checking if your program actually requires this feature. If an array overrun occurs during an assignment operation, memory that is being used for other purposes, such as holding other variables, might be overwritten. If an array overrun occurs when data is being read, then invalid data will corrupt the program. Either way, as the programmer, it is your job both to ensure that all arrays are large enough to hold what the program will put in them, and to provide bounds checking whenever necessary. CRITICAL SKILL 4.2: Two-Dimensional Arrays C++ allows multidimensional arrays. The simplest form of the multidimensional array is the two-dimensional array. A two-dimensional array is, in essence, a list of one-dimensional arrays. To declare a two-dimensional integer array twoD of size 10,20, you would write int twoD[10][20]; Pay careful attention to the declaration. Unlike some other computer languages, which use commas to separate the array dimensions, C++ places each dimension in its own set of brackets. Similarly, to access an element, specify the indices within their own set of brackets. For example, for point 3,5 of array twoD, you would use twoD[3][5]. In the next example, a two-dimensional array is loaded with the numbers 1 through 12. In this example, nums[0][0] will have the value 1, nums[0][1] the value 2, nums[0][2] the value 3, and so on. The value of nums[2][3] will be 12. Conceptually, the array will look like that shown here: Two-dimensional arrays are stored in a row-column matrix, where the first index indicates the row and the second indicates the column. This means that when array elements are accessed in the order in which they are actually stored in memory, the right index changes faster than the left. You should remember that storage for all array elements is determined at compile time. Also, the memory used to hold an array is required the entire time that the array is in existence. In the case of a two-dimensional array, you can use this formula to determine the number of bytes of memory that are needed: bytes = number of rows × number of columns × number of bytes in type Therefore, assuming four-byte integers, an integer array with dimensions 10,5 would have 10×5×4 (or 200) bytes allocated. CRITICAL SKILL 4.3: Multidimensional Arrays C++ allows arrays with more than two dimensions. Here is the general form of a multidimensional array declaration: type name[size1][size2]...[sizeN]; For example, the following declaration creates a 4×10×3–integer array: int multidim[4][10][3]; Arrays of more than three dimensions are not often used, due to the amount of memory required to hold them. Remember, storage for all array elements is allocated during the entire lifetime of an array. When multidimensional arrays are used, large amounts of memory can be consumed. For example, a four-dimensional character array with dimensions 10,6,9,4 would require 10×6×9×4 (or 2,160) bytes. If each array dimension is increased by a factor of 10 each (that is, 100×60×90×40), then the memory required for the array increases to 21,600,000 bytes! As you can see, large multidimensional arrays may cause a shortage of memory for other parts of your program. Thus, a program with arrays of more than two or three dimensions may find itself quickly out of memory! Because a one-dimensional array organizes data into an indexable linear list, it isthe perfect data structure for sorting. In this project, you will learn a simple way to sort an array. As you may know, there are a number of different sorting algorithms. The quick sort, the shaker sort, and the shell sort are just three. However, the best known, simplest, and easiest to understand sorting algorithm is called the bubble sort. While the bubble sort is not very efficient—in fact, its performance is unacceptable for sorting large arrays—it may be used effectively for sorting small ones. Step by Step 1. Create a file called Bubble.cpp. 2. The bubble sort gets its name from the way it performs the sorting operation. It uses repeated comparison and, if necessary, exchange of adjacent elements in the array. In this process, small values move toward one end, and large ones toward the other end. The process is conceptually similar to bubbles finding their own level in a tank of water. The bubble sort operates by making several passes through the array, exchanging out-of-place elements when necessary. The number of passes required to ensure that the array is sorted is equal to one less than the number of elements in the array. Here is the code that forms the core of the bubble sort. The array being sorted is called nums. Notice that the sort relies on two for loops. The inner loop checks adjacent elements in the array, looking for out-of-order elements. When an out-of-order element pair is found, the two elements are exchanged. With each pass, the smallest element of those remaining moves into its proper location. The outer loop causes this process to repeat until the entire array has been sorted. 3. Here is the entire Bubble.cpp program: The output is shown here: Original array is: 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 Sorted array is: 41 6334 11478 15724 18467 19169 24464 26500 26962 29358 4. Although the bubble sort is good for small arrays, it is not efficient when used on larger ones. The best general-purpose sorting algorithm is the Quicksort. The Quicksort, however, relies on features of C++ that you have not yet learned. Also, the C++ standard library contains a function called qsort( ) that implements a version of the Quicksort, but to use it, you will also need to know more about C++. CRITICAL SKILL 4.4: Strings By far the most common use for one-dimensional arrays is to create character strings. C++ supports two types of strings. The first, and most commonly used, is the null-terminated string, which is a null-terminated character array. (A null is zero.) Thus, a null-terminated string contains the characters that make up the string followed by a null. Null-terminated strings are widely used because they offer a high level of efficiency and give the programmer detailed control over string operations. When a C++ programmer uses the term string, he or she is usually referring to a null-terminated string. The second type of string defined by C++ is the string class, which is part of the C++ class library. Thus, string is not a built-in type. It provides an object-oriented approach to string handling but is not as widely used as the null-terminated string. Here, null-terminated strings are examined. String Fundamentals When declaring a character array that will hold a null-terminated string, you need to declare it one character longer than the largest string that it will hold. For example, if you want to declare an array str that could hold a 10-character string, here is what you would write: char str[11]; Specifying the size as 11 makes room for the null at the end of the string. As you learned earlier in this book, C++ allows you to define string constants. A string constant is a list of characters enclosed in double quotes. Here are some examples: “hello there” “I like C++” “Mars” ““ It is not necessary to manually add the null terminator onto the end of string constants; the C++ compiler does this for you automatically. Therefore, the string “Mars” will appear in memory like this: The last string shown is "". This is called a null string. It contains only the null terminator and no other characters. Null strings are useful because they represent the empty string. Reading a String from the Keyboard The easiest way to read a string entered from the keyboard is to use a char array in a cin statement. For example, the following program reads a string entered by the user: Here is a sample run: Enter a string: testing Here is your string: testing Although this program is technically correct, it will not always work the way that you expect. To see why, run the program and try entering the string “This is a test”. Here is what you will see: Enter a string: This is a test Here is your string: This When the program redisplays your string, it shows only the word “This”, not the entire sentence. The reason for this is that the C++ I/O system stops reading a string when the first whitespace character is encountered. Whitespace characters include spaces, tabs, and newlines. One way to solve the whitespace problem is to use another of C++’s library functions, gets( ). The general form of a call to gets( ) is gets(array-name); To read a string, call gets( ) with the name of the array, without any index, as its argument. Upon return from gets( ), the array will hold the string input from the keyboard. The gets( ) function will continue to read characters, including whitespace, until you enter a carriage return. The header used by gets( ) is . This version of the preceding program uses gets( ) to allow the entry of strings containing spaces: C++ A Beginner’s Guide by Herbert Schildt Here is a sample run: Enter a string: This is a test Here is your string: This is a test Now, spaces are read and included in the string. One other point: Notice that in a cout statement, str can be used directly. In general, the name of a character array that holds a string can be used any place that a string constant can be used. Keep in mind that neither cin nor gets( ) performs any bounds checking on the array that receives input. Therefore, if the user enters a string longer than the size of the array, the array will be overwritten. Later, you will learn an alternative to gets( ) that avoids this problem. CRITICAL SKILL 4.5: Some String Library Functions C++ supports a wide range of string manipulation functions. The most common are strcpy( ) strcat( ) strcmp( ) strlen( ) The string functions all use the same header, . Let’s take a look at these functions now. strcpy A call to strcpy( ) takes this general form: strcpy(to, from); The strcpy( ) function copies the contents of the string from into to. Remember, the array that forms to must be large enough to hold the string contained in from. If it isn’t, the to array will be overrun, which will probably crash your program. strcat A call to strcat( ) takes this form: strcat(s1, s2); The strcat( ) function appends s2 to the end of s1; s2 is unchanged. You must ensure that s1 is large enough to hold its original contents and those of s2. strcmp A call to strcmp( ) takes this general form: strcmp(s1, s2); The strcmp( ) function compares two strings and returns 0 if they are equal. If s1 is greater than s2 lexicographically (that is, according to dictionary order), then a positive number is returned; if it is less than s2, a negative number is returned. The key to using strcmp( ) is to remember that it returns false when the strings match. Therefore, you will need to use the ! operator if you want something to occur when the strings are equal. For example, the condition controlling the following if statement is true when str is equal to “C++”: if(!strcmp(str, "C++") cout << "str is C++"; strlen The general form of a call to strlen( ) is strlen(s); where s is a string. The strlen( ) function returns the length of the string pointed to by s. C++ A Beginner’s Guide by Herbert Schildt A String Function Example The following program illustrates the use of all four string functions: // Demonstrate the string functions. #include #include #include using namespace std; int main() { char s1[80], s2[80]; strcpy(s1, "C++"); strcpy(s2, " is power programming."); cout << "lengths: " << strlen(s1); cout << ' ' << strlen(s2) << '\n'; if(!strcmp(s1, s2)) cout << "The strings are equal\n"; else cout << "not equal\n"; strcat(s1, s2); cout << s1 << '\n'; strcpy(s2, s1); cout << s1 << " and " << s2 << "\n"; if(!strcmp(s1, s2)) cout << "s1 and s2 are now the same.\n"; return 0; } Here is the output: lengths: 3 22 not equal C++ is power programming. C++ is power programming. and C++ is power programming. s1 and s2 are now the same. Using the Null Terminator The fact that strings are null-terminated can often be used to simplify various operations. For example, the following program converts a string to uppercase: The output from this program is shown here: THIS IS A TEST This program uses the library function toupper( ), which returns the uppercase equivalent of its character argument, to convert each character in the string. The toupper( ) function uses the header . Notice tha