The Array Data Structure: Chapter XI Topics

Download as doc, pdf, or txt
Download as doc, pdf, or txt
You are on page 1of 27

Chapter XI The Array Data Structure

Chapter XI Topics
11.1 11.2 11.3 11.4 11." 11.' Introduction to Data Structures One-Dimensional Array Definition Accessing Array Elements by Index Assigning andom Array !alues

Array #rocessing $it% t%e Arrays &lass Summary

&%a(ter )I

*%e Array Data Structure

1+,

11.1 Introduction to Data Structures


Early in the course you were introduced to simple data types, like int, float, char, double, and boolean. Each one of these data types can be used to create a variety of required variables. A simple data type variable is a location in memory that stores a single value that can be used by a computer program. Single values are practical for loop counter variables, maximum number of grades, the height of Pikes Peak and the number of medals won by the United States at the last lympics. !rograms that handle passenger airline reservations, student college transcripts, employee payroll records and hospital patient information, require massive data storage. Such ma"or storage requirements cannot be handled efficiently by thousands of simple data type variables, each storing a single value. #ou will need more sophisticated data types. $t can be argued that you have been storing multiple values inside ob"ects since the very beginning, and that is very true. %owever, the data stored inside the classes and ob"ects so far have been one or more simple data types. &here are many situations where data needs to hold more than one value. Such a situation calls for using a data structure. So what is a data structure' (ook at a building. )ote that it is made up of smaller structures like rooms, halls, stairways, etc. A room is made up of walls, floors, ceilings, desks, chairs, etc. Another example can be found with animals. Animals are organisms made up of organ systems. Each organ system is made up of organs. rgans are made up of tissues, and tissues are made up of cells. *e could continue and work down to the molecular and atomic level, but for this analogy, assume that the cell is the simplest, lowest level. &he whole point is that the structure, an organism in this case, is made up of other, smaller structures, until eventually you reach the smallest component. &hese two examples are used to motivate the definition of a data structure. $n computer science it really is the same idea. &he only difference in structures is the nature of the smallest building block used to create the structure. $n an animal organism it is a cell. $n a building it may be a brick or a plank and in a computer science data structure it is a simple data type.

First Data Structure Definition A data structure is a data ty(e $%ose com(onents are smaller data structures and-or sim(le data ty(es.
#ou will note that it states First Data Structure Definition . &his definition is not quite finished. *e will revisit the data structure definition again and make some revisions. &he complete, and more accurate, definition will only add unnecessary
#age 11+ Ex(osure .a/a 2+110 #reA#&S Edition +"-31-11

complexity right now. +irst we need to spend some time with a variety of data structure examples before it makes sense to become more precise. &his approach is quite similar to teaching somebody to play a new card game. $t "ust does not make sense to explain all the more intricate details of the game when playing for the first time. +requently, the best approach is to deal the cards and explain as you go along. After several hands are dealt, it is easier to summari,e a variety of rules. $n other words, let us deal some hands first and then we talk some more. So what is the bottom line essence of this data structure, right now at this early stage' $t is simple. #ou no longer have a data type that stores a single value. #ou can store more than one value in a data type that is a data structure. !ut in other words, any data type that can store more than one value is a data structure.

Data Structure Starting Point Any data ty(e t%at can store more t%an one /alue is a data structure.

Alright, we have a starting point. )ow we need to look and see what computer science has to offer for us in the data structures department. Exactly, what types of data structures exist and what can they do for us. #ou may have noticed that the title of this chapter talks about arrays, which is one kind of data structure. &he importance of data structures is such that frequently one whole chapter is devoted to one data structure in many computer science text books. Since this is the very first chapter about any kind of data structure, it will help to give a brief overview of several different types of data structures.

The Array Data Structure


&he array is the first historical data structure. &his data structure became popular with the introduction of the first commercially, wide-used programming language, FORTRAN. + .&.A), which means + .mula &.A)slator, was designed for the scientific - number crunching - community. A data structure, like an array, was necessary for the storing of large quantities of numbers. *hat does an array bring to mind' %ow about an array of flowers or an array of books, or an array of anything else' *e think of an array as having multiple items - not a single item - and an array has the same type of items. *e can have an array of integers, an array of real numbers, an array of characters, and an array of strings. An array can have any kind of element, as long as each element is the

&%a(ter )I

*%e Array Data Structure

111

same data type. #ou will find the name vector used frequently for onedimensional arrays and matrix for two-dimensional arrays.

First Array Definition An array is a data structure $it% one0 or more0 elements of t%e same ty(e. A one-dimensional array is fre1uently also called a vector. A t$o-dimensional array is fre1uently also called a matrix.

nce again you see this first definition expression. &his is the same story as the data structure definition. All this business is tied together. /ore complete definitions will come later when each data structure is explained in more detail.

The ecord Data Structure


&he business community was not very happy with the + .&.A) language and particularly with the data structure limitation of having an array and nothing else. $n the business world, data is not of the same type. &his is lovely in science and math where numbers rule the discipline, but in business it is another story. 0ata storage in business requires storing names, addresses, birth dates, number of dependents, social security numbers, credit cards numbers, flight numbers, years worked, pay rates, credit balance available, etc. etc. etc. ne solution was to create many different arrays. Each array speciali,ed in one part of some business record. &here was an array of names, an array of addresses, an array of pay rates and so on, which were called parallel arrays. &his worked, but it was tedious. A new programming language became popular, called 1 2 ( 31 mmon 2usiness riented (anguage4, which introduced the record data structure. *hat does the word record bring to mind' %ow about a student5s record, an employee5s record, a patient5s record, a passenger5s record' Each one of these records has the common thread of multiple information fields that can be of many different types. &his type of data structure is precisely what the business world required. 1 2 ( became a highly successful language 3it helped that the 0epartment of 0efense adopted the language4 and the record is now an integral part of programming. $nitially, records only stored data of different types. ver time, records have evolved and now improved records store actions that process the data inside the same data structure. #ou have seen this improved record

#age 112

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

structure already in 6ava as the class, which is the primary component of riented !rogramming.

b"ect

ecord Definition A record is a data structure $it% one0 or more0 elements0 called fields0 of t%e same or different data ty(es.

The Fi!e Data Structure


!rogramming languages have a convenient data structure that facilitates the transfer of data to and from external storage. &he array and record may be lovely to store a complex set of data in the memory of a computer, but this data often needs to be used at some future date. &he data needs to be stored in some permanent manner. &he file data structure provides this ability.

Fi!e Definition A fi!e is an internal data structure - $it% an uns(ecified number of elements of t%e same ty(e - assigned to an external file name. *%e file data structure allo$s transfer of data bet$een internal and external storage.

"ther Data Structures


&he three data structures - array, record 3class now4 and file - introduced in this section are built-in 6ava data types. &hese data types are ready to go and can be used with very little effort. Using built-in data structures is a good starting point in an introductory computer science course. &here are many other types of data structures that the programmer can create for a wide variety of special purposes. &he study and practice of these special user-created data structures is a ma"or focus of the second semester college-level computer science course. ne example of such a special data structure will be presented here, the stack.

&%a(ter )I

*%e Array Data Structure

113

The Stac# Data Structure


ne important data structure in computer science is the stack. &his data structure will be explained, and used, in considerable detail in the future. .ight now consider the following stack definition.

Stac# Definition A stac2 is a data structure $it% elements of t%e same ty(e. Data elements of t%e stac2 data structure can only be accessed 3stored or retrie/ed4 at one end of t%e stac2 in a $IF" 35ast In0 6irst Out4 manner.

(et us go to a large home improvement store to create an analogy about this data structure business. #ou walk through one isle to get a variety of bolts and nuts of different si,es. All the hardware is neatly organi,ed in separate containers that are clearly labeled. #ou might think that the isle containing all the screws, bolts, nuts and hooks is a large record of hardware data. &here is one organi,ed isle for many different types of hardware. #ou walk directly to a container that is marked with the si,e bolt that you need. After that you walk to another container that stores the correct si,ed nut that you need. &his is random access. #ou can select to access any items in any random pattern. A little later you need to pick up a new lawnmower. All the new lawnmowers are stored in neat stacks, eight boxes high. &he particular lawnmower that you need happens to be the third box from the bottom of one stack. $t is not possible for you to access this lawnmower randomly or directly. &he stack only allows access at the top. Store employees carefully remove one box at a time with a forklift from the top of the stack, until your lawn mower can be accessed. &his is not random access. 0ata access to the lawnmowers or a computer science stack is only possible at one end. +urthermore, the access is Last n! First Out 3L FO". )ow why do you need to use a stack data structure in computer science' &his is a topic for later discussion. .ight now you need to learn about arrays. &he forward peek to the stack was provided to make a relevant comparison of different data access. $t was used strictly to help explain that the manner of data access is fundamental to a data structure7s definition. &he understanding and use of data structures is one of the most significant components of successful programming. #ou will be using many data structures8 both 6ava provided data structures, and user-created data structures.
#age 114 Ex(osure .a/a 2+110 #reA#&S Edition +"-31-11

&he definition of a data structure, given at the beginning of this introduction -- and this has been a long introduction -- will be repeated here. (ook at this short sentence closely. &he definition is strictly limited to the storing of information. )othing is stated about how the information accessed.

First Data Structure Definition A data structure is a data ty(e $%ose com(onents are smaller data structures and-or sim(le data ty(es.

&his is precisely why this is called First Data Structure Definition . &he definition was fine for the very first introduction of a data structure, but it is not complete. &here is more to the story. Something has to be mentioned about the manner in which data is accessed. (et us make an analogy with a car here. A car is a complex piece of machinery that consists of many components. *e can somewhat think of a car as a data structure with components like doors, lights, transmissions, radios, steering wheels, etc. $t is not sufficient to define a car by specifying that the car has doors, lights, a transmission, a radio, a steering wheel, etc. &he access of these components is a ma"or part of the overall definition or understanding of the car. 0o the doors only open with a key, or does it have remote access, or perhaps a combination code that must be entered to unlock the doors' $s the transmission automatic, or manual, and if it is manual, how many gears are there and what is the pattern' +urthermore, is the transmission two-wheel drive or four-wheel drive' &he steering wheel controls the direction of the car, but is it direct access or is it indirect access with power steering' &hese are all questions that must be answered before somebody purchases a car. &he precise definition of a car cannot be summed up by its components. &he manner in which the components are accessed or operate has to be part of a complete definition. &he same is true with data structures. #es, we need to know how data is stored and what type of data can be stored. ne ma"or difference between an array and a record is the fact that an array can only store data of the same type, while the record can store data of many different types. &hat is great, but it is not sufficient. %ow do we access the data and what can be done to the data is another question' 1onsider the following altered data structure definition.

&%a(ter )I

*%e Array Data Structure

11"

Improved Data Structure Definition A data structure is a data ty(e $%ose com(onents are smaller data structures and-or sim(le data ty(es. *%e storing and retrie/al of t%e data elements is (erformed by accessing met%ods t%at c%aracteri7e t%e data structure.

All of a sudden the clean and simple data structure definition has become rather nasty looking. %opefully, it will not seem all that bad. &he first sentence is old stuff. *e have been there before talking about data storage. &he second sentence explains that data has to be accessed and the manner in which data is accessed and processed defines the nature of the data structure. &he remainder of this chapter will concentrate completely on arrays or subscripted variables. &he long introduction was provided to get some basic feel about the nature of data structures. 0o not be concerned if you know little about arrays. &he purpose of this chapter is precisely to clarify the array data structure. .ight now it is hoped that you have some feel for data structures in general

11.% "ne&Dimensiona! Array Definition


*hat comes to mind when you think of an array' &here is an array of flowers, and you may also have an array of 2arbie dolls, or perhaps an array of kitchen pots and pans. $n each case the array has a dual meaning. #ou are talking about more than one element. And you are also indicating that these elements are alike. &hey do not all need to be identical, but they are of an identical type. &he array of flowers may include many different flowers, but they are all flowers. $f we only consider data storage, the following array definition is quite adequate. &he definition explains that an array is a data structure, and it explains that the multiple elements of the array are fixed in number and they are of the same type. &his is the definition that was presented in the introduction, a few pages back.

First Array Definition

#age 11'

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

An array is a data structure $it% a fixed number of elements of t%e same ty(e.

0ata structures are more than a means to store data. &hat was the main point made in switching from the first data structure definition to the improved data structure definition. &he way in which the stored data is accessed is part of the data structure definition. &his really is the essence of ! encapsulation. Store both the data and the actions that access the data. &his means that the first array definition is not complete. Some indication must be given about data access. 0o not get too excited because Array data access is quite simple.

Improved Array Definition An array is a data structure $it% a fixed number of elements of t%e same ty(e. E/ery element of t%e array can be accessed directly.

&he improved array definition indicates that arrays can be accessed directly. %ow is this accomplished if there are many different values stored in the same data type' Arrays use some unique index or subscript to identify each element in the data structure. &he indexing approach is all around us. Streets are arrays of homes. $t is not sufficient to state that you live on #ain $treet. #ou need something like %&'( #ain $treet. An airplane contains an array of seats, but flight '%) specifies the flight, not the location where you sit in the plane. A boarding pass will say something like Flight '%)! Row *)! $eat +. A similar system applies to a football game5s reserved seat. #our ticket specifies the stadium and date along with the location of the seat. Another way to explain this array indexing business is to consider an array of desks in a classroom, more commonly known as a seating chart. $magine that it is the first school day. Some teacher believes in assigned seats and also wants to be organi,ed. Each student is given an assigned seat number. &he teacher7s seating chart, for Room J116 below, is one example. 81'9 Ingrid 8119 =olly 81:9 Darlene 8129 >la2e 81;9 <ene 8139 ?ic%elle 81,9 Sean 8149 emy 82+9 Ste(%anie 81"9 =aley

&%a(ter )I

*%e Array Data Structure

11:

8+'9 Diana 8+19 Isolde

8+:9 .essica 8+29 .o%n

8+;9 Da/id 8+39 <reg

8+,9 Ant%ony 8+49 ?aria

81+9 Alec 8+"9 =eidi

&he seating chart demonstrates a very important array feature. 0o not confuse the array index, with the contents at the array location, specified by the index. $n other words, ,%%-.(/0 is the desk for +avid. .oom ,%%-, seat number .(/0 is not equal to +avid. $t is the location where 0avid is supposed to sit. As you look at the examples in this chapter, and as you write your own programs with an array data structure, be aware of the difference between index and content.

11.' Accessing Array (!ements )y Index


1onsider program ,ava%%(%12ava, in +igure 99.9. &his program has ten integer declarations, assigns ten integer values to the variables and then displays the values of each one of the ten variables. $t may seem that working with ten variables, as shown here, is not that bad. 2ut is there a better way' Figure 11.1
-- .a/a11+1.@a/a -- *%is (rogram declares 1+ different int /ariables. -- Eac% /ariable is assigned a /alue and eac% -- /ariable /alue is dis(layed. -- *%is a((roac% is /ery inefficient for a large number of /ariables. (ublic class .a/a11+1 A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+1CnB4D int number+ E 1++D int number1 E 1+1D int number2 E 1+2D int number3 E 1+3D int number4 E 1+4D int number" E 1+"D int number' E 1+'D int number: E 1+:D

#age 11;

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

int number; E 1+;D int number, E 1+,D System.out.(rint3number+ F B B4D System.out.(rint3number1 F B B4D System.out.(rint3number2 F B B4D System.out.(rint3number3 F B B4D System.out.(rint3number4 F B B4D System.out.(rint3number" F B B4D System.out.(rint3number' F B B4D System.out.(rint3number: F B B4D System.out.(rint3number; F B B4D System.out.(rint3number, F B B4D G System.out.(rintln34D

!rogram ,ava%%()12ava, in +igure 99.:, does not appear very different from the previous program. &he similarity with the previous program is by the fact that ten integer values are assigned to ten variables. &hen the program continues and displays each one of the ten values. %owever, there is something odd about these ten variables. &here is some strange looking operator in use with a set of square brackets. Additionally, it seems that every one of the ten variables is called list. #ou are actually looking at the declaration of an integer array. Specifically, this is a declaration for a single variable, called list, which can store ten integer variables. /any streets have an array of homes. &he street has a single name, like #ain $treet or 3ing Road. A street can be considered an array of homes. Since there is a single street name, it becomes necessary to give a label to each home that identifies the home. Each home has a street number. $n the case of the list array, each element of the array has an index, which is placed between brackets. Figure 11.%
-- .a/a11+2.@a/a -- *%is (rogram declares an array of 1+ int elements. -- Eac% array element /alue is indi/idually assigned and dis(layed. -- *%ere does not a((ear any real benefit from t%e from (rogram exam(le. (ublic class .a/a11+2 A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+2CnB4D int list89D -- declares t%e array ob@ect identifier list E ne$ int81+9D -- allocates memory for 1+ array elements list8+9 E 1++D list819 E 1+1D list829 E 1+2D list839 E 1+3D

&%a(ter )I

*%e Array Data Structure

11,

list849 E 1+4D list8"9 E 1+"D list8'9 E 1+'D list8:9 E 1+:D list8;9 E 1+;D list8,9 E 1+,D System.out.(rint3list8+9 F B B4D System.out.(rint3list819 F B B4D System.out.(rint3list829 F B B4D System.out.(rint3list839 F B B4D System.out.(rint3list849 F B B4D System.out.(rint3list8"9 F B B4D System.out.(rint3list8'9 F B B4D System.out.(rint3list8:9 F B B4D System.out.(rint3list8;9 F B B4D System.out.(rint3list8,9 F B B4D System.out.(rintln34D

+igure 99.; displays a segment of the previous program. (et us examine each one of the program statements. Figure 11.'

int list89D list E ne$ int81+9D list8+9 E 1++D list819 E 1+1D list829 E 1+2D

-- line 1 -- line 2 -- line 3 -- line 4 -- line "

(ine 9 declares variable list to be an array of int values. (ine : allocates space with the new operator for ten int values in the list array. (ine ; assigns value %(( to the first list space. 0o not get confused, because access to array elements is done by using index .(0 for the first element. &his also means that the index of the last element of an array is always one less than the number of elements in the array. !rogram ,ava%%()12ava, which used an array variable, did not seem to provide much of an improvement to program ,ava%%(%12ava, which used ten variables. 2oth programs appeared functional and they were both about the same length. )ow look at program ,ava%%(*12ava, in figure 99.<. #ou see far fewer statements, yet it generates the same result as the two previous program examples.
#age 12+ Ex(osure .a/a 2+110 #reA#&S Edition +"-31-11

Figure 11.*
-- .a/a11+3.@a/a -- *%e (re/ious (rogram $it% se(arate statements for eac% array member assignment -- and dis(lay is no$ re(laced $it% t$o loo(s. *%e loo( counter0 index0 is used -- to s(ecify eac% array element in an efficient manner. (ublic class .a/a11+3 A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+3CnB4D int list89D list E ne$ int81+9D for 3int index E +D index HE,D indexFF4 list8index9 E index F 1++D for 3int index E +D index HE,D indexFF4 System.out.(rint3list8index9 F B B4D G System.out.(rintln34D

Figure 11.* Continued

+igure 99.= isolates how cleverly an array uses a loop structure. $n this example the loop repeats ten times. &he loop counter, called index, starts at ( and ends at 4, which is the range of the list index values. !reviously, you saw statements, like list.50 6 *((7 but now in place of a fixed integer, an integer variable 3index4 is used to assign ten values to ten list locations. Figure 11.+

for ,int index - ./ index 0-1/ index223 !ist4index5 - index 2 1../

!rogram ,ava%%(512ava, in figure 99.>, repeats the looping access shown in the previous program. &his time the array declaration is done in a single statement rather than the two statements used previously. Figure 11.6
-- .a/a11+4.@a/a -- *%is (rogram is t%e same list array and t%e same list /alues as t%e (re/ious (rogram. -- *%is time note t%at t%e array declaration is accom(lis%ed $it% one statement.

&%a(ter )I

*%e Array Data Structure

121

(ublic class .a/a11+4 A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+4CnB4D int list89 E ne$ int81+9D for 3int index E +D index HE,D indexFF4 list8index9 E index F 1++D for 3int index E +D index HE,D indexFF4 System.out.(rint3list8index9 F B B4D

+igure 99.? pulls the array declarations from two previous programs. &he first example uses two statements. &he second example combines the two statements into one. &he one-statement approach is more commonly used. Figure 11.7 +eclaring an array with two 8rogram statements

int !ist4 5/ !ist - ne8 int41.5/


+eclaring an array with one 8rogram statement

int !ist4 5 - ne8 int41.5/

$t is not necessary to declare the si,e of an array if an initializer list is used. !rogram ,ava%%('12ava, in figure 99.@, shows a set of integer values placed between braces. &his type of syntax tells the computer that list is an integer array with ten elements and it simultaneously assigns the ten provided values. Figure 11.9
-- .a/a11+".@a/a -- *%is (rogram demonstrates %o$ to initiali7e array elements. -- *%e Hne$I o(erator is not necessary in t%is case. (ublic class .a/a11+" A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+"CnB4D int list89 E A1++01+101+201+301+401+"01+'01+:GD for 3int 2 E +D 2 HE :D 2FF4 System.out.(rintln3Blist8B F 2 F B9 E B F list8294D System.out.(rintln34D G G

#age 122

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

*hat you have seen so far is an integer array called list. Arrays are not limited to storing integer values. +igure 99.A repeats list as an integer array, continues with names as a character array, and finishes with grades as a real number array. Figure 11.1 int list8 9D list E ne$ int81+9D c%ar names8 9D names E ne$ c%ar82"9D -- declares t%e array !ist identifier -- allocates memory for 1+ int /ariables -- declares t%e names array identifier -- allocates memory for 2" char /ariables

double grades8 9D -- declares t%e grades array identifier grades E ne$ double8"+9D -- allocates memory for "+ dou)!e /ariables !rogram ,ava%%(-12ava, in figure 99.9B, demonstrates that is no problem to create arrays with data values besides integers. &he same syntax is used for initiali,er lists that contain characters and arrays. $t is important to reali,e that character values require singles quotes and string values require double quotes. Figure 11.1.
-- .a/a11+'.@a/a -- *%is (rogram demonstrates a c%aracter array and a string array. -- >ot% arrays use an initiali7er list. (ublic class .a/a11+' A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+'CnB4D c%ar list189 E AJAJ0J>J0J&J0JDJ0JEJ0J6J0J<J0J=J0JIJ0J.J0JKJ0J5J0J?J0JLJ0JOJ0J#J0JMJ0J J0JSJ0J*J0JNJ0J!J0JOJ0J)J0JPJ0JQJGD for 3int 2 E +D 2 H 2'D 2FF4 System.out.(rint3list18294D System.out.(rintln3BCnB4D String list289 E AB.o%nB0B<regB0B?ariaB0B=eidiB0BDianaB0BDa/idBGD for 3int 2 E +D 2 H 'D 2FF4 System.out.(rintln3list28294D System.out.(rintln34D

&%a(ter )I

*%e Array Data Structure

123

11.* Assigning andom Array :a!ues


%ard coding array elements during array definitions can be tedious. &his is especially tedious if there are many arrays values. Entering array elements during program execution also becomes quite annoying when there are many numbers to be added. +requently, in the process of learning computer science it is important to process a large quantity of data, and such data in many cases does not need to be any specific values. $n other words, random data is "ust fine. &he only issue left is the nature of the random data. Are integers, real numbers, characters or strings required' $n this brief section you will learn how to assign a variety of data types randomly to an array. &he 9x8o class, introduced in 1hapter $C, provides a convenient random method. &his method requires two parameters. &he first parameter indicates the smallest possible number generated for the random list and the second parameter indicates the largest possible number that will be generated by the method. !rogram ,ava%%(&12ava, in figure 99.99, demonstrates how to generate random numbers in a specified range, which is D9BB..AAAE in this case, and assigns these numbers to a sequence of integer array elements. *hen you run this program, you may not get the exact same set of numbers, but they will be in the same range from 9BB to AAA. Figure 11.11
-- .a/a11+:.@a/a -- *%is (rogram fills an integer array $it% a random set of numbers. -- *%e random numbers $ill be generated in t%e 81++..,,,9 range. -- Lote t%at a Bfixed loo(B is used for t%e data entry into t%e array -- as $ell as t%e dis(lay of t%e array elements. (ublic class .a/a11+: A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+:CnB4D int list89 E ne$ int82+9D for 3int 2 E +D 2 H 2+D 2FF4 list829 E Ex(o.random31++0,,,4D for 3int 2 E +D 2 H 2+D 2FF4

#age 124

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

System.out.(rintln3Blist8B F 2 F B9 E B F list8294D System.out.(rintln34D

Figure 11.11 Continued

!rogram ,ava%%(/12ava, in figure 99.9:, demonstrates the length keyword, which has nothing to do with randomness. (ength is too small a topic to devote an entire section to it and length will be used frequently in future program examples. Arrays provide a convenient way to know how large an array is. $t is possible to keep track of the si,e of an array with a user-defined variable, but you can use length at any time to determine the si,e of the array. &he length keyword is somewhat of a strange creature. #ou may be tempted to use syntax like list1length:", because the dot notation does give the impression that length is a method of the list ob"ect8 however, length is ) & a method. length is actually a field similar to the ; field of the #ath class. Another similarity is that both length and ; are final variables or constants which means they cannot be changed. #ou may notice the last line in the program tries to change the length field. &he program compiles because that line is commented out. $f the comment symbols were to be removed, the program would no longer compile. Figure 11.1%
-- .a/a11+;.@a/a -- *%is (rogram introduces t%e lengt% field to determine t%e -- number of elements in t%e array. emo/e t%e comments from line 1'

&%a(ter )I

*%e Array Data Structure

12"

-- to obser/e $%at %a((ens $%en t%e lengt% field is altered. (ublic class .a/a11+; A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+;CnB4D String names89 E AB.oeB0B*omB0BSueB0B?egBGD int n E names.lengt%D

-- data field accessD not a met%od call

-G

System.out.(rintln3B*%ere are B F n F B array elements.B4D for3int 2 E +D 2 H nD 2FF4 System.out.(rintln3Bnames8B F 2 F B9 E B F names8294D names.lengt% E 1+D

Figure 11.1% Continued

.andom strings are an interesting problem. &here are an incredible number of possible strings and a random string method would be very cumbersome, and actually totally unnecessary. An array of strings or an array of any conceivable data type will still always use an integer value for the index. 1onsider the seating chart, shown earlier, and imagine a teacher randomly generating numbers to call on students. As numbers pop up, the teacher treats each number as a reference or index to a desk, looks at the seating chart, and then calls on the student by name. $t is also possible that the teacher keep the responsibility of knowing the index with the student. A rude teacher might call on a student strictly by using the desk number. At any rate you should be convinced that we can map a numerical value, which will be used to identify an array index, with the contents at that indexed location. &he contents can be anything, but the index will always be an integer in a range starting at ,ero and up to one less the number of elements in the array. !rogram ,ava%%(412ava, in figure 99.9;, constructs an array ob"ect with ten $trings. A random number between B and A is assigned to the rnd nt, which is used for the index. &his makes Frandom stringsG possible. #our display should be similar to what is in the book. #our output will probably be in a different order because we are working with random data. Figure 11.1'
-- .a/a11+,.@a/a -- *%is (rogram demonstrates %o$ to dis(lay an array of random strings.

#age 12'

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

(ublic class .a/a11+, A (ublic static /oid main3String args894 A System.out.(rintln3B.a/a11+,CnB4D int rndIntD String names89 E ABAAB0B>>B0B&&B0BDDB0BEEB0B66B0B<<B0B==B0BIIB0B..BGD for3int 2 E 1D 2 H 1"D 2FF4 A rndInt E Ex(o.random3+0names.lengt%-14D System.out.(rintln3Bnames8B F rndInt F B9 E B F names8rndInt94D G System.out.(rintln34D G G

Figure 11.1' Continued

11.+ Array Processing 8ith the Arrays C!ass


!rogram design includes two related concepts. +irst, there is the business of abstraction, which is the process of utili,ing program features without any concern about the implementation of such features. Second, there is the process of implementing features based on certain specifications. Using existing methods without concern about the details of the methods is certainly easier than creating your very own code to write the methods you need. 2asically, this means to use what is already available. Do not reinvent the heel. At the same time, it is not possible to have tools available for every possible program need. #ou will need to

&%a(ter )I

*%e Array Data Structure

12:

design and implement your own classes and methods. #ou will need to know both how to use existing tools and create your own tools. 0ata structures require processing. Array processing includes element display, assigning values, sorting elements and searching elements. 6ava has very conveniently provided us with an Arrays class, which can perform all these array processing needs.

Disp!aying Array (!ements 8ith toString


All the previous program examples required a loop structure to display array elements. #ou learned how to use a for loop to access, and display, array elements. %owever, a loop structure was required to visit the array elements. $n program ,ava%%%(12ava, in figure 99.9<, you see that the elements of four different array ob"ects are displayed with the help of the to$tring method of the Arrays class. /ethod to$tring, like all Arrays methods, is static, which means that you need to use the Arrays identifier, like you have done with class methods. Figure 11.1*
-- .a/a111+.@a/a -- *%is (rogram introduces t%e static HArraysI class. -- In t%is (rogram t%e HtoStringI met%od is used to dis(lay t%e array elements. im(ort @a/a.util.ArraysD -- necessary to use t%e HArraysI class

(ublic class .a/a111+ A (ublic static /oid main 3String args894 A System.out.(rintln3B.a/a111+CnB4D int list189 E A110220330440""0''0::0;;0,,GD double list289 E A1.102.203.304.40"."0'.'0:.:0;.;0,.,GD c%ar list389 E AJAJ0J>J0J&J0JDJ0JEJ0J6J0J<J0J=J0JIJGD String list489 E ABAAB0B>>B0B&&B0BDDB0BEEB0B66B0B<<B0B==B0BIIBGD System.out.(rintln3Arrays.toString3list144D System.out.(rintln3Arrays.toString3list244D System.out.(rintln3Arrays.toString3list344D System.out.(rintln3Arrays.toString3list444D System.out.(rintln3BCnCnB4D G G

#age 12;

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

C!ass Arrays; <ethod toString <ethod toString disp!ays the e!ements of an array o)=ect separated )y commas and )ounded )y s>uare )rac#ets. int list.0 6 <%%!))!**!55!''!--!&&!//!44=7 $ystem1out18rintln:Arrays1to$tring:list""7

Assigning Array (!ement :a!ues 8ith fi!!


$t is possible to assign values to an array ob"ect with an initiali!er list. &his is convenient and practical if the list is fairly small. &he biggest advantage is that the initiali,er list can assign different values to every array element location. !rogram ,ava%%%%1"ava, in figure 99.9=, shows that it is also possible to assign the same value to each array element using the fill method. &he si,e of the array does not matter, but you can only assign the same values to every array element. Figure 11.1+
-- .a/a1111.@a/a -- *%is (rogram demonstrates t%e HfillI met%od of t%e HArraysI class. -- *%e HfillI met%od assigns t%e same /alue to e/ery array element. im(ort @a/a.util.ArraysD -- necessary to use t%e HArraysI class

(ublic class .a/a1111 A (ublic static /oid main 3String args894 A System.out.(rintln3B.a/a1111CnB4D int list189 E ne$ int81+9D double list289 E ne$ double81+9D c%ar list389 E ne$ c%ar81+9D String list489 E ne$ String81+9D Arrays.fill3list101234D Arrays.fill3list201.234D Arrays.fill3list30JMJ4D Arrays.fill3list40BNSAB4D System.out.(rintln3Arrays.toString3list144D System.out.(rintln3Arrays.toString3list244D System.out.(rintln3Arrays.toString3list344D System.out.(rintln3Arrays.toString3list444D System.out.(rintln3BCnCnB4D

Figure 11.1+ Continued

&%a(ter )I

*%e Array Data Structure

12,

C!ass Arrays; <ethod fi!! <ethod fi!! assigns the same va!ue to every array e!ement. int list%.0 6 new int.%(07 double list).0 6 new double.%(07 char list*.0 6 new char.%(07 $tring list5.0 6 new $tring.%(07 Arrays1fill:list%!%)*"7 Arrays1fill:list)!%1)*"7 Arrays1fill:list*!>?>"7 Arrays1fill:list5!@A$A@"7

Sorting Array (!ements 8ith sort


Sorting is an extremely important array process. *hy exactly is sorting so important' 0o we like to see elements appear in sorted sequence' &he answer is much simpler. Sorting is important, because there is a need to search data. Every time that a credit card is approved for a purchase, the credit card holder7s information must be found before approval is granted. 0oes the card exist' $s there sufficient credit left on the account for the purchase' &hese questions can only be answered after performing a search, and searching is far more efficient when items are sorted. 6ust imagine finding somebody7s phone number in a telephone book where the names are not sorted. !rogram ,ava%%%)12ava, in figure 99.9>, demonstrates the sort method. +our arrays are sorted in ascending order. +or characters and strings this means in alphabetical order. 0o keep in mind that sorting with characters and strings is
#age 13+ Ex(osure .a/a 2+110 #reA#&S Edition +"-31-11

based on the numerical values of the characters. &his can have some interesting results. (ower-case >a> has a larger numerical code than upper-case >B>, which means that in a mixed upper"case#lo er"case sorting environment, you will find that the B will be placed before the a. )otice that the program output for list' does not appear correct. 1orrect sorting of strings requires that the strings are all lower-case or all upper-case. Figure 11.16
-- .a/a1112.@a/a -- *%is (rogram demonstrates t%e HsortI met%od of t%e HArraysI class. -- ?et%od HsortI arranges array elements in ascending order. im(ort @a/a.util.ArraysD -- necessary to use t%e HArraysI class

(ublic class .a/a1112 A (ublic static /oid main 3String args894 A System.out.(rintln3B.a/a1112CnB4D int list189 E A110,,0220;;0330::0440''0""GD double list289 E A1.102.203.304.40"."0'.'0:.:0;.;0,.,GD c%ar list389 E AJAJ0JIJ0J>J0J=J0J&J0J<J0JDJ0J6J0JEJGD String list489 E ABAAB0BIIB0B>>B0B==B0B&&B0B<<B0BDDB0B66B0BEEBGD String list"89 E ABaard/ar2B0BbobcatB0BcougarB0BdogB0BE5E6AL*B0B6O)B0B<O I55AB0B=A EBGD Arrays.sort3list14D Arrays.sort3list24D Arrays.sort3list34D Arrays.sort3list44D Arrays.sort3list"4D System.out.(rintln3Arrays.toString3list144D System.out.(rintln3Arrays.toString3list244D System.out.(rintln3Arrays.toString3list344D System.out.(rintln3Arrays.toString3list444D System.out.(rintln3Arrays.toString3list"44D System.out.(rintln3BCnCnB4D

C!ass Arrays; <ethod sort <ethod sort arranges the array e!ements in ascending order.

&%a(ter )I

*%e Array Data Structure

131

String and character array e!ements are sorted in ascending order of the numerica! code va!ues. Incorrect processing may occur if string va!ues are mixed upper&case and !o8er& case. int list%.0 6 <%%!44!))!//!**!&&!55!--!''=7 double list).0 6 <%1%!)1)!*1*!515!'1'!-1-!&1&!/1/!414=7 char list*.0 6 <>A>!> >!>C>!>D>!>E>!>F>!>+>!>F>!>9>=7 Arrays1sort:list%"7 Arrays1sort:list)"7 Arrays1sort:list*"7

Searching Array (!ements 8ith )inarySearch


&he sort method does not give a clue how array elements are sorted. &he method is simply called sort. n the other hand, the Arrays search method is called binary$earch, which is one specific searching process. #ou will fully appreciate the mechanics of the binary search in the later algorithm chapter. .ight now a brief explanation will help to clarify the name. &hink of the manner in which you search for a name in a telephone book. #ou know that the names are in alphabetical order. +ew people start at the first page and steadily work forward. )o, you roughly split the book open at some estimate location and conclude that you need to move forward or backward. Each time an ever smaller section is split again until the correct page is found. !rogram ,ava%%%*12ava, in figure 99.9?, demonstrates the binary$earch method. $t returns the index of the array element if the element value exists. A negative index value is returned if the element does not exist. .emember that the first element in an array ob"ect starts with index ,ero.

Figure 11.17
-- .a/a1113.@a/a -- *%is (rogram demonstrates t%e HbinarySearc%I met%od of t%e HArraysI class. -- ?et%od HbinarySearc%I returns t%e index of a searc% element if it exists0 -- and returns a negati/e index /alue ot%er$ise. im(ort @a/a.util.ArraysD -- necessary to use t%e HArraysI class

#age 132

Ex(osure .a/a 2+110 #reA#&S Edition

+"-31-11

(ublic class .a/a1113 A (ublic static /oid main 3String args894 A System.out.(rintln3B.a/a1113CnB4D int list89 E A110,,0220;;0330::0440''0""GD System.out.(rintln3Arrays.toString3list44D Arrays.sort3list4D System.out.(rintln3Arrays.toString3list44D System.out.(rintln34D System.out.(rintln3BIndex of 33 is B F Arrays.binarySearc%3list03344D System.out.(rintln3BIndex of 11 is B F Arrays.binarySearc%3list01144D System.out.(rintln3BIndex of ,, is B F Arrays.binarySearc%3list0,,44D System.out.(rintln3BIndex of 1+ is B F Arrays.binarySearc%3list01+44D System.out.(rintln3BCnCnB4D

$t was mentioned earlier that the whole point in sorting is the ability to search efficiently. $n the case of the binary search sorting is not simply a matter of efficiency8 it is a matter of accuracy. nce again you will appreciate this problem better when you actually implement a binary search yourself. $t is easy to imagine that an unsorted list causes problems. 1an you find a number in a phone book when the names are not sorted' #ou make the assumptions to move forward or backward in your search precisely because the phone book is alphabeti,ed. !rogram ,ava%%%512ava, in figure 99.9@, attempts to perform various searches on lists that are not properly sorted. &he results are very inconclusive. $n many cases a negative index is returned, when in fact the array element does exist. Figure 11.19
-- .a/a1114.@a/a -- *%is (rogram demonstrates t%at an array must be sorted before -- t%e HbinarySearc%I met%od is called. Erroneous indexes are -- returned if t%e list is not sorted. im(ort @a/a.util.ArraysD -- necessary to use t%e HArraysI class

(ublic class .a/a1114 A (ublic static /oid main 3String args894 A

&%a(ter )I

*%e Array Data Structure

133

System.out.(rintln3B.a/a1114CnB4D int list89 E A110,,0220;;0330::0440''0""GD System.out.(rintln3Arrays.toString3list44D System.out.(rintln34D System.out.(rintln3BIndex of 33 is B F Arrays.binarySearc%3list03344D System.out.(rintln3BIndex of 11 is B F Arrays.binarySearc%3list01144D System.out.(rintln3BIndex of ,, is B F Arrays.binarySearc%3list0,,44D System.out.(rintln3BIndex of 1+ is B F Arrays.binarySearc%3list01+44D System.out.(rintln3BCnCnB4D

C!ass Arrays; <ethod )inarySearch <ethod )inarySearch searches the e!ements of an array o)=ect for a specified va!ue. The index of the array e!ement is returned; if the e!ement is found and a negative index is returned other8ise. Array e!ements must )e sorted; other8ise the )inarySearch method returns incorrect information. int list.0 6 <%%!44!))!//!**!&&!55!--!''=7 $ystem1out18rintln:@ ndex of )) is @ G Arrays1binary$earch:list!**""7

11.6 Summary
&his chapter introduced the concept of a data structure. $t is important to reali,e that a data structure is more than some means to store data. &he manner in which the data is accessed is an integral part of a data structure. &he most common data structure in computer programming is the array. An array is a data structure with a fixed number of elements of the same type. Every element of the array can be accessed directly. $t is convenient to enter large sets of array values randomly. &his can be done with a loop structure and the random method of the 9x8o class. $t is also possible to
#age 134 Ex(osure .a/a 2+110 #reA#&S Edition +"-31-11

generate random string values by using a random index of a string array to specify some unknown string value. Arrays can be declared for one, two or more dimensions. Each dimension requires its own index and access loop. Elements in an array are processed with four common algorithms. Elements are displayed, entered, sorted and searched. &here exist algorithms for each one of these processes. $n this chapter the Arrays class is used with methods to$tring, fill, sort and binary$earch to perform array processing. Using these methods is done without knowledge of the algorithm implementation. &he implementation of these methods will be learned in a later chapter.

&%a(ter )I

*%e Array Data Structure

13"

You might also like