Tài liệu Module 4 Arrays, Strings, and Pointers pptx

5
C++ A Beginner’s Guide by Herbert Schildt


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

6
C++ A Beginner’s Guide by Herbert Schildt


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.

7
C++ A Beginner’s Guide by Herbert Schildt



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.

8
C++ A Beginner’s Guide by Herbert Schildt


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.

9
C++ A Beginner’s Guide by Herbert Schildt


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:

10
C++ A Beginner’s Guide by Herbert Schildt




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

11
C++ A Beginner’s Guide by Herbert Schildt


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:

12
C++ A Beginner’s Guide by Herbert Schildt




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
<cstdio>.
This version of the preceding program uses gets( ) to allow the entry of strings containing spaces:

13
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( )

14
C++ A Beginner’s Guide by Herbert Schildt


The string functions all use the same header, <cstring>. 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.

Xem chi tiết: Tài liệu Module 4 Arrays, Strings, and Pointers pptx