Movatterモバイル変換

Software Design Using C++

Arrays

Array Basics

char CharArray[5];

This array would be indexed 0, 1, 2, 3, 4. We could put the character 'R',for example, into the array location at index 0 by using the following:

CharArray[0] = 'R';

We could put data at the other array locations in a similar manner. In fact,we could input data intoCharArray[0],print outCharArray[0], etc. The arraycan be pictured as shown below (with additional characters filled in at the other array slots):

Using Loops with Arrays

Let's look at some of the details of this program. Note that it sets upa constant calledArrayMax for the maximum number of items thatcan be placed in the array, as well as a type name,ArrayType, for the array. Here thetypedef is used to defineArrayType to be a type name for any array ofArrayMax integers.

Inthemain function you see thatMyArray is declaredto be of typeArrayType. Note, too, that the functions useArrayType as the type for the array parameters.You may wonder why there is no & on theArrayType parameterin theFillArray function. Since this function is obviouslychanging the array by placing data in it, we want to send the changedarray back out of the function. You would think that a referenceparameter would be needed. However, as you will learn in more detaillater, an array parameter is automatically a reference parameter ofsorts. This is because an array name is seen as a pointer to thefirst data item in the array. This will become clearer when youstudypointersin more detail. For the moment just remember that youdo not use the & with array parameters.

Expanding the Example

Once again the program sets up a constant for the maximum number of itemsthe array can hold as well as a type name for an array of this many integers.ThePrintArray andmain functions are straightforward.

TheLoadArray routine is vastly different. It uses the fact that after reading a dataitem,EOF (end of file) is true if we tried to read beyond the end of the datafile. In reading from the keyboard, the user can press CTRL z to signal the endof data. (Note that in Windows the user may have to press ENTER once or twice after theCTRL z. Also note that Linux uses CTRL d to end data input, as CTRL z is used to suspendthe current process.) There is afail function whichis true when the user has pressed CTRL z instead of entering a data item (or when the inputcommand failed to read a data item). This could be because we areat the end of file or because the item entered is not valid. For example,since this program is trying to read an integer, entering a character like Awill makefail true. (There is also aneof function in C++, but it doesn't always work as you wouldexpect or want. Use thefail function instead.See the discussion in thestreams section of these web pages.)

Sometimes students ask why we don't useCount <= ArrayMax inthewhile loop condition in theLoadArray function. See if you cananswer that question. If need be change the program to use the abovecondition and then run the program, trying to enter more data items than will fit.

Another common question is why we don't use a test likeCount >= ArrayMax in anif test after thewhile loop to tellus whether not all of the data would fit. See if you can answer this beforereading on for the answer! Part of the answer is thatCount cannever become larger thanArrayMax. Just read through thewhile loop to see that.Count mightequalArrayMax, but that might be because therewere just as many data items entered as there were array slots. However,that means that all is OK, there is no "too much data" error condition.

TheFindMax function is not difficult to understand, but isimportant because the algorithm is often used. Note how it assumesthat the first data item is the maximum and then loops through the remainingdata items to see if it can find any that are bigger. One can easilyadapt this algorithm to the task of finding the minimum.

Analysis of Algorithms

As a simple example, consider the following section of code. Suppose thatwe want to estimate its running time. Suppose further that thecomputefunction does something that is simple and that takes about the same amountof time each time it is called. Since there is not much else in this codebut repeated calls to thiscompute function,a good estimate of the amount of running time can be made by adding up howmany timescompute gets called. What do you think we get?

for (k = 0; k< n; k++)   {   for (j = 0; j< n; j++)      compute(k, j);   compute(k, n);   }

Note that the number of calls ofcompute depends on the variablen. It is very common for the running time to be a function of avariable or variables liken. Since the outer loopexecutes its loop body n times and the inner loop as well, thecompute(k, j) is calledn^2 times.(Note that n^2 is being used to indicate n to the second power.) Since thecompute(k, n) is outside of the inner loop, it is simply executedn times. The total number of calls of ourcomputefunction is thusn^2 + n. If one such function calltakes about A seconds, the total running time is aboutA(n^2 + n) seconds. We write this running time function ast(n) = A(n^2 + n). As explained below, this particularfunction is anO(n^2) function.

Definition: A running time functiont(n) isO(f(n))provided that there is a constantc such thatt(n) <= c * f(n) for alln beyond some numberK. (In other words,t is eventually bounded by amultiple off.)

We usually read the statement that "t(n) isO(f(n))"as "t(n) isbig-O off(n)".The definition can best be understood by looking at a graph:

Note that this only tells you what happens eventually; it says nothing abouthowt andf compare initially. TheO()notation looks at behavior for largen(where running times are very important). The following definition sayssomething even more exact about the growth of a running time function:

Definition: A running time functiont(n) isTheta(f(n))provided that there are constantsc andd such thatc * f(n) <= t(n) <= d * f(n) for allnbeyond some numberK. (In other words,t is eventuallybounded above and below by multiples off.)

Of course, this is usually written with a Greek letter capital Theta, but we willwrite it out here. We read the statement that "t(n) isTheta(f(n))"as "t(n) isbig-Theta off(n)".We also sometimes say that "t(n) hasorder f(n)" or that"t(n) has the sameorder of magnitude as f(n)".In a picture we have something like the following:

Theorem: Any polynomial with leading termc * n^k isO(n^k). In fact, it isTheta(n^k).

We won't prove this, but will just look at examples of its use:

Roughly speaking, aTheta(n^2) function grows like then^2 function, at least for large values of n. For example,if you triplen, you would expect the functionvalue to be about 3^2 = 9 times as much. ATheta(n^3)function grows roughly like then^3 function, at least forlargen. Thus, if you triplen, you would expectthe function value to be about 3^3 = 27 times as large. You might want totry graphing aTheta(n^3) function versus aTheta(n^2) one. Beyond a certain point then^3 one takes much more time. Asnincreases, the difference gets progressivelyworse.

Exponential functions (such ast(n) = 2^n) areincredibly bad for running time functions. They are known to have a worse orderof magnitude thanany polynomial function. An algorithm with exponential running time may take centuries to complete even for only moderately large values ofn.

The following chart gives a comparison of some common orders of magnitude for runningtime functions. Note that lg(n) is used to mean log base 2 of n.

BEST                                            ||       WORST-----------------------------------------------------------------lg(n)   n   n*lg(n)   n^2   n^3   n^4  etc...   ||   2^n   n!                               fairly good      ||   hopeless                                                ||

As a general rule, polynomial running times are fairly good, but exponential running times are totally impractical except for very small values on n.

Searching an Array

Sequential Search

A very common operation is to search an array for a particular item.Check out theseqsrch.cpp example for one wayto do this. The method used is commonly called a sequential search. Thisalgorithm checks each item in the array, in sequential order, to see if itmatches the one that we seek. TheSequentialSearch function isshort and easy to read. Note that it returns in the function name the arrayindex of where it found the match or -1 if no match was found. The -1 canbe used because it is not a valid array index.

What is the running time of this sequential search? Let's usen instead ofCount, the number of data items in thearray. Since the main task that gets repeatedin the search is theif test thatcompares an item in the array with theTarget, it makes sense toestimate the running time by counting the number of such data items tested.(This is sometimes called the number ofprobes of the array.)

In thebest case, we find a match on the first probe. The first dataitem in the array is the one we wanted. In theworst case thenumber of probes isn; we have to check all of the data items inthe array. In theaverage case the number of probes is approximatelyn/2. We can summarize the results as follows:

TheLoadArray function uses a random number generator to get datato place into the array. The first step is to "seed" the random number generator to a fairly random starting point by using thesrandfunction. Here the starting point is based on thecurrent system time as reported by thetime function. Each time anew random integer is desired one just calls therand function.The result is then scaled to be between 0 and 1000 in this program.Note that computer-based random number generators really generate pseudorandom numbers. The numbers appear to be random but in actualityare not quite random. In particular, the sequence of numbers generatedform a long loop. Eventually the first number returns, with the secondnumber coming after it, etc. Also, if the random number generator is calledupon with the same seed it will produce exactly the same sequence of "random" numbers.

ThePrintArray function in this example is interesting in that itshows one way to line up the output in columns. Here the% function(mod) is used to get the remainder after division by 15. When this remainder is 14a newline is output. This has the effect of printing 15 items per line. Thesetw function is also used to get a field width of 5 for eachinteger printed. Read this carefully to see if you can follow it.

Binary Search

Another wayto look for a target item in an array is by using a binarysearch. A binary search requires that all of the data be in order, typicallyinascending order. (Ascending order means that as you follow the indicesin order 0, 1, 2,... you get the data items in order such as 125, 200, 219,...). Look at thebsearch.cpp example.

This program fillsIntArray with 100 numbers generated byLoadArray so as to be in increasing order. The first number isarbitrarily 1. Each succeeding number is generated by adding some random positivenumber to the previous number. This guarantees that the resulting data is inascending order.

TheDoSearches function allows the user to repeatedly look upan item in the array using binary search. Note how it uses thetolower function to make sure that the character in theReply variable is in lower case. This makes testing for a yesanswer easier because there is no need to test for both 'y' and 'Y'.

One way to visualize what functions call what other functions is to draw astructure chart. A structure chart for the bsearch.cpp programis shown below. It is like an organization chart for a company. It showsthemain function at the top. Undermain it shows thefunctions that are called from withinmain.SinceDoSearches callsBinarySearch, that isshown with a line fromDoSearches down to a box containingBinarySearch. This type of chart can be helpful in seeing theoverall organization of "procedural programming". (Procedural programmingconsists in using functions to organize the program. Later you will studyobject-oriented programming, where objects are used to group data and the functionsthat operate on the data.)

TheBinarySearch function has as parameters the array to be searched,theLow andHighindices for the section of array to search (typically 0 to Count - 1),as well as theTarget item for which to search.The function returns in the function name the indexof whereTarget was found or -1 if it was not found.

Binary search uses a "divide and conquer" approach. You can see that itfirst finds a middle index,Mid, betweenLow andHigh. It then checks to seeif the data item in the array at indexMid matchesTarget. If so, we are done; just return thisindexMid. Otherwise, check to see if the data itemat indexMid is smaller thanTarget.If so, we only need to check the section of the array to the rightofMid; anything to the left ofMid isonly smaller and cannot possibly match. We arrange to search the right "half"of the array by changingLow to beMid + 1 and looparound to get the midpoint of that section, etc.

Similarly, if the data item at indexMidis larger thanTarget, we just needto search the left half of the array. We set up to do so by changingHigh to beMid - 1. You can seethe divide and conquer nature of the algorithm in how each probe of the array at a midpoint narrows the searchto either the section to the right or left of the midpoint (or else findsa match). At each such probe we approximately divide the search spacein half. For long arrays this is much faster than using a sequentialsearch to methodically check every data item in the array!

It can be shown that binary search hasTheta(lg(n)) worst caseand average case running time, wheren is the number of dataitems in the array. Of course, the bestcase running time isTheta(1), sincewe might find the desired match on the first probe of the array.In general, based on their average case behaviors, binary search is knownas aTheta(lg(n)) search, whereas sequential search is knownas aTheta(n) search. As you can tell by graphing the functionslg(n) andn, the binary search will have a lotsmaller running time for large values ofn, and so is preferredwhen it is applicable. (Remember that the data in the array must be inorder for binary search to be applicable. If it is not already in order,it could be sorted, but sorting is time-consuming. Sorting makes sense ifwe can sort the data once and then do a lot of searches through it, butif we keep adding new data items, for example, so that the array has tobe sorted over and over, it is probably faster to skip the sorting andjust use sequential search.)

The following drawings attempt to trace a binary search for a target of23 in an array of 8 integers. The first probe of the array checks location3 but does not find a match. Thus we narrow the search to the items tothe left of index 3. The second probe checks location 1 but does not finda match. Thus we search the section to the right of index 1, a sectionwith only 1 number in it. At this point,Low,High, andMid all become 2.The third probe finds the 23. (Note that the item checked in each probe is underlined.)

What happens if we search for an item that is not in the array? This iscalled an unsuccessful search. For example, let's search the following array for 88.

Note that things proceed much like before. The first probe checks the 45,and the second probe checks the 90. Since the target 88 is smaller thanthe 90, we makeHigh to beMid - 1,which is 2. This is so that we cansearch the items to the left of index 3. However, there are no items tothe left of index 3. The empty array section to be searched is drawnsimply as a vertical line.The code detects this condition in thewhile loop test. SinceLow > High thewhile loop ends, and the function returns a -1 to indicate that the 88 could not be found.

Sorting an Array

Bubblesort

Another common operation is to sort the data in an array. We usuallywant to put the data intoascending order,but sometimes descending (backwards) order is used. Look atbubble.cpp for an example program using thewell-known bubblesort algorithm.

Bubblesort is based on swapping out-of-order pairs of data items, in sequence, so as to bubble to the top of the array (if pictured vertically)the largest data item. That largest item is somehow marked as done andthe same game of bubbling the largest (of the rest of the data items) to thetop is played all over again, etc. Thus we get the largest at the top, thenthe second largest, then the third largest, etc.

Although our program sorts an array of integers, for the purpose oftracing the workings of bubblesort let's pretend that we have modifiedit to sort an array of characters. This leads to the following drawings,where each row (or "pass") is handled by the for loop and the successionof passes is handled by the while loop. The bracket in each drawing ofthe array shows the two data items that are being compared to see ifthey are out of order.

This is a "smart" version of bubblesort in that it uses a flag calledDoneto keep track of whether or not any swaps were made on a pass. If no swaps are made on a pass that means that all of the items must have beenin order, so that the sort can quit without doing any additional passes.

Inline Function

Note, too, the use of aninlineSwap function. That means that the normal function call and return mechanism is not used.Instead a copy of the function code replaces the function call. This is faster and is appropriate for very short functions (so as tonot add greatly to the program's length by inserting the samecode everywhere where the function is called). An inlinefunction can only be usedafter this section where it isdefined; function prototypes are not used.

Let's use this program as another opportunity to draw a structure chart.Note that all of the functions other thanSwap get called fromthemain function.

Let's analyze the efficiency of bubblesort, especially in regard toits running time. This is usually estimated by counting the numberof swaps of array items or by counting the number of key comparisons.In our simple example, the keys are the data items themselves, so thatthe key comparisons referred to are the greater than tests in the followingif:

if (IntArray[k] > IntArray[k + 1])   {   Done = false;   // because we are making a swap   Swap(IntArray[k], IntArray[k + 1]);   }

In the worst case (when the data is in descending order), every comparisonwill show that the data is out of order and thus result in a swap.In the worst case, then, the number of swaps equals the number of key comparisons.If the number of data items in the array isn, the number of swapsin the worst case is clearly(n-1) + (n-2) + ... + 3 + 2 + 1 = n*(n-1)/2 = n^2/2 - n/2,which is aTheta(n^2) function. Note that the running time forthis sort grows much faster than the running time for either of our searches.Overall, bubblesort is known as aTheta(n^2) sort. Here is a summary:

By the way, what is the best case? (It's when the data is already in order.) In such a case, bubblesort just does one pass with no swaps, so it isdone with onlyn-1 comparisons. Bubblesort, then, is very fastwhen the data is already in order (or probably when it is close to being in order).

As for memory space efficiency, bubblesort uses no appreciable extra memory space.There are no temporary arrays that consume a lot of space, etc.

Selection Sort

Another common sort routine is selection sort. Look at theselect.cpp example program. It is essentiallyidentical to the bubble.cpp program that we just looked at above, exceptthat it sorts the array by using a selection sort, not a bubblesort.

The basic idea of ourSelectionSort function is that it makesa pass through the array to find the index of the minimum item and then swapsthat minimum item with the item at the bottom of the array. That bottom itemis then marked as done. (This is shown in the drawing below by putting a solidline across.) Then the same game is played with the remaining items abovethat solid line: find the index of the minimum and swap it with the item atthe bottom. By the time you reach the last picture in the drawing below,the smallest item is at index 0, the second smallest at index 1, etc. Theonly seemingly unchecked item is the one at the top, but it must be thelargest by default. Thus the array has been sorted.

In the drawing above, the index of the minimum is shown below each picture of the array.A selection sort can also be based on finding the index of the maximum oneach pass. Note that ourSelectionSort function may onoccasion end up swapping an item with itself. If you want, you can add anextra condition to check that the indices are different before attempting a swap.

Let's estimate the running time of our selection sort as a functionof the number of data items n in the array.As usual we can count the number of swaps or the number of key comparisons.The following chart shows the results:

There is no best case or worst case, it always follows the same pattern.Overall, then, selection sort is obviously a Theta(n^2) sort just likebubblesort. Still, because the number of swaps is less than that of bubblesort,selection sort is probably a little bit faster than bubblesort.The following summarizes our results:

As with bubblesort, selection sort requires no appreciable amount of extra memory space.

Character Arrays

An array of characters is a simple way to implement a string. The usualmethod is to end the string with aNULL character (ASCII 0) to mark theend. The NULL character can be written as the literal '\0', should you ever need it.A number of functions are available for working withNULL-terminated strings.

However, character array strings are not the safest. In particular, they make it easier tointroducebuffer overflow flaws when copying strings.For this reason, theSTL string class is usually the preferred wayto handle strings.

Look at the programstrings.cpp as a simple exampleof how to use the character array type of string. This program sets upMaxStringas the maximum number of characters one of our strings can hold. Note that thisincludes theNULL character, so most people wouldsay that the length of the string can be at most 11. Also,StringType is set up as a type namefor any array ofMaxString characters.

const int MaxString = 12;typedef char StringType[MaxString];

The most obvious method to try in reading a string from the keyboard is probably the following:

cin >> Message;

There are several problems with this approach. First, the loading ofcharacters intoMessage stops when a whitespace character such as a spaceis reached. That is a considerable problem if you are trying to read in a name such as"Jane Smith". Second, the newline that results from the user pressing the ENTER key at the endof whatever the person typed would still be sitting there in the inputstream. If a second input statement is used, that input statement would seethe input stream as having an empty string followed by a newline. To getaround this second problem our program explicitly reads the newline (anddoes not store it anywhere) by using the following:

cin.get();

Although this fixes the second problem, the first problem remains. Inaddition, there is a third problem in that data entry of 12 or more charactersresults in the array being filled with characters without aNULLmarking the end of the string. If more than 12 characters are entered,the program will try to write characters beyond the end of the array,possibly overwriting other data. This can lead to a run-time crash of the program.

Another way to read strings is to use thegetline function as shown below.

cin.getline(Message, MaxString);

Thegetline function by default reads until a newline is reached or untilit has readMaxString - 1 characters.Note that it is smart enough to leave room for theNULL character marking the end of the string andof course stores theNULL in the array. Thusgetline reads in spaces without a problem. However, you do need to specifyin the second parameter the maximum number of characters your string can hold(including the NULL). Thefirst parameter is the string itself. Another advantage ofgetline is thatit reads in and disposes of the newline character for you; no longer do weneed to use aget to read the newline directly.

Note that even thegetline method has some limitations.It cannot handle any string longer than 11 characters. The extra characters mayend up being used for the next item of input or may be thrown away.The program may breeze right past the next input statement due to the extracharacters. In any case, the results are not dependable if too many characters are entered.

The program ends by showing how to use the library functionsstrcpy andstrcat. Thestrcpy function copiesthe string given by the second parameter into the first.Thestrcat function appends the string given bythe second parameter to the string given by the first parameter. Note thatstrcat does not check if it runs off the end of the array.It is up to the programmer to verify that sufficient space is availablein the string given as the first parameter. Our example program makes nosuch check. Thestrcpy function also does not check if itoverflows the array that it is copying to. This can open up one's software to abuffer overflow attack, a well-known typeof dangerous security flaw. A safer way to copy (and append) strings can befound in theSTL string class. This class also provides theat() method for accessing individual characterswithin a string object with proper bounds checking instead. (The [] array subscript notationcan be used to access individual characters of a string object but does not providebounds checking.)

Two-Dimensional Arrays

char CharArray[3][4];

One of the most important things to remember about two-dimensional arraysis that the row number always comes before the column number. This is trueabove where the array is sized, and it is true below where we arbitrarilyplace the letter 'G' into the location given by row 1, column 2.

CharArray[1][2] = 'G';

A Two-Dimensional Array Example

const int MaxSize = 11;typedef int ArrayType[MaxSize][MaxSize];

TheFillSquare function contains the code to place values intothe array. Note that it essentially amounts to the following two nestedfor loops:

for (Row = 0; Row < Size; Row++)   for (Col = 0; Col < Size; Col++)      {      cout << "Enter a number: ";      cin >> Value;      Square[Row][Col] = Value;      }

Nestedfor loops are commonly used with two-dimensional arrays.The code in thePrintSquare function that prints out the arraylooks very similar to the above:

for (Row = 0; Row < Size; Row++)   for (Col = 0; Col < Size; Col++)      cout << Square[Row][Col];

Read through the rest of the program to see if you can understand bothwhat it does and how it does it. Although this program appears not to doanything very useful, it turns out that subtracting from each item in arow the minimum for the row is used as part of the algorithm to solvecertain problems in the field of operations research.

Using An Index Array

for (k = 0; k < 5; k++)   cout << A[Index[k]];

The following drawing attempts to show the index array and data arrayAbefore the bubblesort is done, after one swap was done, and after the entiresort has completed. Note that the data inAis never changed; all changes take place in the index array.

Of course, the code for our bubblesort also has to be modified. The essential change is in theif test that decideswhether or not to swap. As shown below, it mustnow access the data arrayA via the index arrayand must also swap indices in the index array. A complete program is leftas one of those proverbial exercises for the reader.

if (A[Index[k]] > A[Index[k + 1]])   {   Done = false;   Swap(Index[k], Index[k + 1]);   }

Related Items