📄 chapter10.html
字号:
<HTML><HEAD> <TITLE>Chapter 10</TITLE> <LINK REL="STYLESHEET" HREF="downey.css" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/downey.css"></HEAD><BODY><H2>Chapter 10</H2><H1>Vectors</H1><P>A <B>vector</B> is a set of values where each value is identified by a number(called an index). An <TT>apstring</TT> is similar to a vector, since it is made up of an indexed set of characters. The nice thing about vectors is that they can be made up of any type of element, including basic types like <TT>int</TT>s and <TT>double</TT>s, and user-defined types like <TT>Point</TT> and <TT>Time</TT>.</P><P>The vector type that appears on the AP exam is called <TT>apvector</TT>. In order to use it, you have to include the header file <TT> apvector.h</TT>; again, the details of how to do that depend on your programming environment.</P><P>You can create a vector the same way you create other variable types:</P><PRE> apvector<int> count; apvector<double> doubleVector;</PRE><P>The type that makes up the vector appears in angle brackets (<TT><</TT> and <TT>></TT>). The first line creates a vector of integers named <TT>count</TT>; the second creates a vector of <TT>double</TT>s. Although these statements are legal, they are not very useful because they create vectors that have no elements (their length is zero). It is more common to specify the length of the vector in parentheses:</P><PRE> apvector<int> count (4);</PRE><P>The syntax here is a little odd; it looks like a combination of a variable declarations and a function call. In fact, that's exactly what it is. The function we are invoking is an <TT>apvector</TT> constructor. A <B>constructor</B> is a special function that creates new objects and initializes their instance variables. In this case, the constructor takes a single argument, which is the size of the new vector.</P><P>The following figure shows how vectors are represented in state diagrams:</P><P CLASS=1><IMG SRC="images/vector.png" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/vector.png" ALT="Vector Image"></P><P>The large numbers inside the boxes are the <B>elements</B> of the vector. The small numbers outside the boxes are the indices used to identify each box.When you allocate a new vector, the elements are not initialized. They could contain any values.</P><P>There is another constructor for <TT>apvector</TT>s that takes two parameters; the second is a ``fill value,'' the value that will be assigned to each of the elements.</P><PRE> apvector<int> count (4, 0);</PRE><P>This statement creates a vector of four elements and initializes all of them to zero.</P><BR><BR><H3>10.1 Accessing elements</H3><P>The <TT>[]</TT> operator reads and writes the elements of a vector in much the same way it accesses the characters in an <TT>apstring</TT>. As with <TT>apstring</TT>s, the indices start at zero, so <TT>count[0]</TT> refers to the ``zeroeth'' element of the vector, and <TT>count[1]</TT> refers to the ``oneth'' element. You can use the <TT>[]</TT> operator anywhere in an expression:</P><PRE> count[0] = 7; count[1] = count[0] * 2; count[2]++; count[3] -= 60;</PRE><P>All of these are legal assignment statements. Here is the effect of this code fragment:</P><P CLASS=1><IMG SRC="images/vector2.png" tppabs="http://rocky.wellesley.edu/downey/ost/thinkCS/c++_html/images/vector2.png" ALT="Vector2 Images"></P><P>Since elements of this vector are numbered from 0 to 3, there is no element with the index 4. It is a common error to go beyond the bounds of a vector, which causes a run-time error. The program outputs an error message like ``Illegal vector index'', and then quits.</P><P>You can use any expression as an index, as long as it has type <TT>int</TT>.One of the most common ways to index a vector is with a loop variable. For example:</P><PRE> int i = 0; while (i < 4) { cout << count[i] << endl; i++; }</PRE><P>This <TT>while</TT> loop counts from 0 to 4; when the loop variable <TT>i</TT> is 4, the condition fails and the loop terminates. Thus, the body ofthe loop is only executed when <TT>i</TT> is 0, 1, 2 and 3.</P><P>Each time through the loop we use <TT>i</TT> as an index into the vector, outputting the <TT>i</TT>th element. This type of vector traversal is very common. Vectors and loops go together like fava beans and a nice Chianti.</P><BR><BR><H3>10.2 Copying vectors</H3><P>There is one more constructor for <TT>apvector</TT>s, which is called a copyconstructor because it takes one <TT>apvector</TT> as an argument and creates a new vector that is the same size, with the same elements.</P><PRE> apvector<int> copy (count);</PRE><P>Although this syntax is legal, it is almost never used for <TT>apvector</TT>s because there is a better alternative:</P><PRE> apvector<int> copy = count;</PRE><P>The <TT>=</TT> operator works on <TT>apvector</TT>s in pretty much the way you would expect.</P><BR><BR><H3>10.3 <TT>for</TT> loops</H3><P>The loops we have written so far have a number of elements in common. All ofthem start by initializing a variable; they have a test, or condition, that depends on that variable; and inside the loop they do something to that variable, like increment it.</P><P>This type of loop is so common that there is an alternate loop statement, called <TT>for</TT>, that expresses it more concisely. The general syntax lookslike this:</P><PRE> for (INITIALIZER; CONDITION; INCREMENTOR) { BODY }</PRE><P>This statement is exactly equivalent to</P><PRE> INITIALIZER; while (CONDITION) { BODY INCREMENTOR }</PRE><P>except that it is more concise and, since it puts all the loop-related statements in one place, it is easier to read. For example:</P><PRE> for (int i = 0; i < 4; i++) { cout << count[i] << endl; }</PRE><P>is equivalent to</P><PRE> int i = 0; while (i < 4) { cout << count[i] << endl; i++; }</PRE><BR><BR><H3>10.4 Vector length</H3><P>There are only a couple of functions you can invoke on an <TT>apvector</TT>.One of them is very useful, though: <TT>length</TT>. Not surprisingly, it returns the length of the vector (the number of elements).</P><P>It is a good idea to use this value as the upper bound of a loop, rather than a constant. That way, if the size of the vector changes, you won't have togo through the program changing all the loops; they will work correctly for anysize vector.</P><PRE> for (int i = 0; i < count.length(); i++) { cout << count[i] << endl; }</PRE><P>The last time the body of the loop gets executed, the value of <TT>i</TT> is<TT>count.length() - 1</TT>, which is the index of the last element. When <TT>i</TT> is equal to <TT>count.length()</TT>, the condition fails and the body is not executed, which is a good thing, since it would cause a run-time error.</P><BR><BR><H3>10.5 Random numbers</H3><P>Most computer programs do the same thing every time they are executed, so they are said to be <B>deterministic</B>. Usually, determinism is a good thing, since we expect the same calculation to yield the same result. For some applications, though, we would like the computer to be unpredictable. Games arean obvious example.</P><P>Making a program truly <B>nondeterministic</B> turns out to be not so easy, but there are ways to make it at least seem nondeterministic. One of them is togenerate pseudorandom numbers and use them to determine the outcome of the program. Pseudorandom numbers are not truly random in the mathematical sense, but for our purposes, they will do.</P><P>C++ provides a function called <TT>random</TT> that generates pseudorandom numbers. It is declared in the header file <TT>stdlib.h</TT>, which contains a variety of ``standard library'' functions, hence the name.</P><P>The return value from <TT>random</TT> is an integer between 0 and <TT>RAND_MAX</TT>, where <TT>RAND_MAX</TT> is a large number (about 2 billionon my computer) also defined in the header file. Each time you call <TT>random</TT> you get a different randomly-generated number. To see a sample,run this loop:</P><PRE> for (int i = 0; i < 4; i++) { int x = random (); cout << x << endl; }</PRE><P>On my machine I got the following output:</P><PRE>180428938384693088616816927771714636915</PRE><P>You will probably get something similar, but different, on yours.</P><P>Of course, we don't always want to work with gigantic integers. More often we want to generate integers between 0 and some upper bound. A simple way to dothat is with the modulus operator. For example:</P><PRE> int x = random (); int y = x % upperBound;</PRE><P>Since <TT>y</TT> is the remainder when <TT>x</TT> is divided by <TT>upperBound</TT>, the only possible values for <TT>y</TT> are between 0 and <TT>upperBound - 1</TT>, including both end points. Keep in mind, though, that <TT>y</TT> will never be equal to <TT>upperBound</TT>.</P><P>It is also frequently useful to generate random floating-point values. A common way to do that is by dividing by <TT>RAND_MAX</TT>. For example:</P><PRE> int x = random (); double y = double(x) / RAND_MAX;</PRE><P>This code sets <TT>y</TT> to a random value between 0.0 and 1.0, including both end points. As an exercise, you might want to think about how to generate a random floating-point value in a given range; for example, between 100.0 and 200.0.</P><BR><BR><H3>10.6 Statistics</H3><P>The numbers generated by <TT>random</TT> are supposed to be distributed uniformly. That means that each value in the range should be equally likely. Ifwe count the number of times each value appears, it should be roughly the same for all values, provided that we generate a large number of values.</P><P>In the next few sections, we will write programs that generate a sequence ofrandom numbers and check whether this property holds true.</P><BR><BR><H3>10.7 Vector of random numbers</H3><P>The first step is to generate a large number of random values and store themin a vector. By ``large number,'' of course, I mean 20. It's always a good ideato start with a manageable number, to help with debugging, and then increase itlater.</P><P>The following function takes a single argument, the size of the vector. It allocates a new vector of <TT>int</TT>s, and fills it with random values between 0 and <TT>upperBound-1</TT>.</P><PRE>apvector<int> randomVector (int n, int upperBound) { apvector<:int> vec (n); for (int i = 0; i < vec.length(); i++) { vec[i] = random () % upperBound; } return vec;}</PRE><P>The return type is <TT>apvector<int></TT>, which means that this function returns a vector of integers. To test this function, it is convenient to have afunction that outputs the contents of a vector.</P><PRE>void printVector (const apvector<int>& vec) { for (int i = 0; i < vec.length(); i++) { cout << vec[i] << " "; }⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -