Array



Array

Objectives

• To understand the concept of arrays

• To understand the purpose to which we use arrays.

• To be able to declare references to arrays.

• To be able to create one-dimensional and two-dimensional arrays.

• To be able to initialize one-dimensional and two-dimensional arrays

• To be able manipulate one-dimensional numeric arrays.

• To become familiar with arrays of strings.

• To be able to apply the concept of arrays to searching and sorting.

Introduction

An array is a contiguous set of storage locations set aside to hold a fixed number of homogenous data elements. This means that all the elements in the array have the same data type, and the size of the size of the array is fixed and cannot be increased or decreased during compilation time or run time.

Sometimes we have large sets of data that are needed at anytime in a program. If we should use a single variable then each new data value would over write the previous one, so that at any point in time only one value could be accounted for; all the previous values would have been lost. To safe guard against such incident from happening, we could store the data contiguously in memory and use one common name to refer to each location where a data element is stored. In its simplest form, Figure 8.1 shows an array of ten storage locations pointed to by a reference variable.

referenceVariable The array

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

Figure 8.1 shows an array of ten contiguous chunks of memory pointed to by a reference variable.

This arrangement makes it convenient to refer to the element in each chunk of memory. Later we will see exactly how this is achieved.

Arrays are regarded as real objects in Java. Array can be of primitive types or reference types. In the case of primitive types, all elements or data values in the array are of a specific primitive data type. In the case of the reference type, all elements are references of a specific reference type, such as string values or objects. Each array object has an instance variable called length, which specifies the size of the array; i.e., the number of elements the array can accommodate.

Declaring One-Dimensional Array Variables

To use arrays in a program, you must declare a variable to reference the array. That is you must specify the name of the variable that will reference the array and the type of data values that the array is expected to contain. The format for declaring a one-dimensional array is as follows:

data_type arr[];

or

data_type [] arr;

Where data_type is any valid data type whether it be primitive type or reference type, and arr is the name of the array variable. The name given to an array follows the convention for naming a variable. Notice that the order of placing the array operator [] is commutative.

Example 8.1 Declaring a one-dimensional arrays.

a) int numbers[];

b) String str[];

c) byte[] someBytes;

d) areaAndCircumference measurements[];

e) char [] consonants;

The above declarations signal an intention to create an array. That is, the array itself has not been created; only a reference address has been set up for each variable name. Figure 8.2 depicts the situation in the case of the declaration of the integer array called numbers.

int numbers[];

Figure 8.2 A reference address for an integer array called numbers.

No use can be made of this declaration; any attempt to use the reference variable at this time will constitute syntax error. In Listing 8.1 Line 5 shows the declaration of the reference variable, and Line 7 shows an attempted is being made to compile the code.

1. class arrayDeclaration

2. {

3. public static void main(String[] arg)

4. {

5. int numbers[];

6.

7. System.out.println(numbers);

8. }

9. }

Listing 8.1 Declaring and attempting to use an array reference variable.

Figure 8.2 shows the result when an attempt is made to compile the code.

| |

|-------------------Configuration: j2sdk1.4.1_03 -------------------- |

|C:\listing8.1\arrayDeclaration.java:7: variable numbers might not have been initialized |

|System.out.println(numbers); |

|^ |

|1 error |

Figure 8.2 Compilation error occurs when an attempt is made to use an array reference variable.

Creating One-Dimensional Array

Before you can use an array reference variable you have to make it point to an existing array, or create the array using the new operator.

Storage space is not allocated for an array during compilation time, but rather during execution time. This means that when you declare an array no storage is allocated; it is only an intention that an array will be addressed. The format for creating a one-dimensional array is as follows:

data_type arr[];

arr = new data_type[numberOfCells];

or

data_type []arr = new data_type[numberOfCells];

or

data_type arr[] = new data_type[numberOfCells];

Example 8.2 Creating one-dimensional arrays.

a) x = new int[10];

b) str = new String[10];

c) someBytes = new byte[10];

d) measurements = new areaAndCircumference [10];

e) consonants = new char [10];

Each of the above statements creates an array of ten contiguously placed storage locations similar to the depiction of Figure 8.1. However, only data of the specified type can be stored at each location for each of the arrays.

Accessing The Cells Of The Array

The cells in a linear (one-dimensional) array are numbered by the operating system. The numbering scheme begins with the first cell labeled cell 0, the second is labeled cell 1, the third is labeled cell 2, and so on. These numbers are referred to as the array indexes. Figure 8.3 illustrates the indexing scheme of a linear array of size 10.

Indeces

referenceVariable

|0 | |

|1 | |

|2 | |

|3 | |

|4 | |

|5 | |

|6 | |

|7 | |

|8 | |

|9 | |

Figure 8.3 An array of size 10. The numbers to the left depicts the index for each position in the array. The cells to the right represent the space for allocated to hold data values.

From the analysis if an array has n cells then the indices go from 0 to n-1. It is important to know this because one would never want to write a program in which the array index is exceeded. Although the whole array is referenced by its name, the array operator [] is used to access the individual elements. Once the array has been created then values can now be assigned to each cell otherwise called location. Usually we do not put the indices.

Initializing a One Dimensional Array

Java provides an alternate way of declaring, constructing, and explicitly initializes an array. The construct is as follows:

data_type [] arrayName = {};

When using this construct you must observe the following:

• Each individual numeric data value must be separated by a comma

• Character values must be separated by comma too, and each value must be placed within single quotation marks.

• String values must be separated by commas, and must be placed within double quotation marks.

• Commas must only separate Boolean values.

Example 8.3 Creating and explicitly initializing one-dimensional arrays

a) Create an array of the first 10 even integers beginning with the number two.

Let us call the array evenNumbers, the the declaration, construction, and initialization is as follows:

int evenNumbers[] = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};

b) Create an array of all the vowels.

char [] vowels = {‘a’, ‘e’, ‘i’, ‘o’, ‘u’};

c) Create an array of the character escape sequence. Character escape sequence must also be placed within single quotation marks. For instance, the following declaration and initialization are valid:

char escapes[] = {'\n', '\r', '\b', '\t', '\\', '\"', '\''};

d) Create an array of menu-items for File, Edit, Insert, and Help.

String[] myMenu = {“File”, “Edit”, “Insert, “Help”};

An array can be assigned values after the array has been created; that is, the values are stored in each cell directly by assignment.

The general format of the assignment is as follows:

arr[i] = value;

Where:

• arr is the name of the array

• i is the array index, and

• value is the data value being assigned to cell.

For instance, using the declaration evenNumbers we could write something of the form:

evenNumbers [i] = 10;

or

evenNumbers [i] = getData.getInt(“Enter an even integer”);

Accessing the Elements of A One Dimensional Array

The cells or elements of an array are accessed by using the [] operator. The general format is:

arrayReferenceVariable[index]

Example 8.4 Using the arrays in Example 8.3.

a) System.out.println(evenNumbers[ 0 ] );

The print statement causes the first value in the array evenNumbers to be printed.

b) evenNumbers[5] = 30;

This statement causes the sixth element in the array evenNumbers to be replaced with the value 30.

c) Print all the values in the array myMenu.

If you are given an array and you are not told the size of the array, then you may use the instance variable length mentioned earlier, to determine the size of the array. The general construct is:

arr.length;

Applying this concept to the above, code is as follows:

int size = myMenu.length;

for (int i = 0; i < size; i++)

System.out.println(myMenu[I] + “\n”);

Whenever we do not know the array values ahead of time, we create the array and then assign the values at a later date. The data values are assigned by using the index. The values may be assigned to the array serially or randomly.

Example 8.5

Define a class called binaryDigits that converts an integer value into its binary equivalence.

Solution

• The class receives an integer value.

• Define a method that decomposes the number into binary digits.

• Return the binary digits.

Algorithm for converting an integer into binary.

1. Divide the original number by 2 and

a) Record the remainder.

b) Set the number to the quotient

2. Repeat the process until the new number becomes zero.

3. When the process stops, rewrite the result starting with the last value first.

Let us use the number 53 to test this algorithm.

53/2 = 26 remainder 1

26/2 = 13 remainder 0

13/2 = 6 remainder 1

6/2 = 3 remainder 0

3/2 = 1 remainder 1

2/2 = 0 remainder 1

Hence the binary equivalence of 53 is 1 1 0 1 0 1

Principal variables are:

• The number

• An array to store the remainder

• An integer value to which to set the size of the array

• An indexing variable.

Principal methods are:

• The constructor

• An instance method to implement the above algorithm

Listing 8.2 shows the class binaryDigits that does the conversion of integer values to binary digits.

1. class BinaryDigits

2. {

3. int binary[],

4. x,

5. theNumber,

6. index;

7.

8. final int MAX = 32;

9.

10. BinaryDigits(int x)

11. {

12. binary = new int[MAX];

13. this.x = x;

14. index = 0;

15. theNumber = x;

16. }

17.

18. void makeBinaryDigits()

19. {

20. int remainder;

21.

22. while (x > 0 && index < MAX)

23. {

24. remainder = x % 2;

25. binary[index] = remainder;

26. x = x/ 2;

27. index = index + 1;

28. }

29. }

30.

31. public String toString()

32. {

33. String s = "The number " + theNumber + " = ";

34.

35. int index = this.index - 1;

36.

37. for (int i = index; i >= 0; i--)

38. s = s + binary[i] + " ";

39.

40. return s + " in binary";

41. }

42. }

Listing 8.2 The class binaryDigits.

• In the code above Line 3 shows the declaration of the array, Line 8 sets the size of the array.

• Line 12 shows the creation of the array, and Line 14 sets the index of the array.

• Line 25 shows how the values are assigned; Line 22 increments the index variable.

• Line 53 sets the loop variable to 1 less the last index for the array.

• Line 38 simple accesses the array.

Figure 8.3 show the test class, and Figure 8.4 shows the output from the program.

1. class TestBinary

2. {

3. public static void main(String[] arg)

4. {

5. BinaryDigits b = new BinaryDigits(53);

6. b.makeBinaryDigits();

7. System.out.println(b.toString());

8. }

9. }

Listing 8.3

[pic]

Figure 8.4

Common Elementary Algorithms

This section discusses some of the most basic but frequently used algorithms for manipulating data stored in an array. These algorithms are so important that some programming languages including Java make them a standard part of their definition. On the other hand, from a pedagogical point of view they are so important that every scholar studying computer science should understand them from first principle and be able to code them in exercises.

One of the simplest array applications is to list some or all the elements in an array. Another application is to list the array elements in the reverse order of how they were stored. Other applications are finding the aggregate, the mean, and the standard deviation of a numeric array.

The concept of searching and sorting play vital role from the early inception of computer science. A high percentage of computer time is spent on these two activities. These concepts are so important that although a large collection has been developed over the years, they are still being critiqued and researched continually.

Process Array In Reverse Order

There are times when it is necessary to access the elements of an array in the reverse order in which they were stored. This concept requires us to understand the indexing format of an array firmly. That is, given an array arr of size N, the first index value is 0 and the last is N-1. This means that if we want to access the elements in the reverse order of how they were stored, we would write something of the form:

for (int i = N-1; i >= 0; i--)

Example 8.2

The following arrays show the average monthly rainfall for a given year:

double rainfall[] = {6.2, 7.2, 9.5, 10.8, 8.1, 7.5, 7.7, 11.3, 12.4, 15.9, 7.9, 12.5};

String[] months = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"};

Write appropriate codes that would:

a) Print array values in reverse order the rainfall reading for each ending quarter.

b) Sum the rainfall readings.

c) Find the average of the rainfall reading.

d) List all of the reading above or below the average reading.

e) Find the standard deviation of the rainfall readings.

f) Find the highest or the lowest rainfall reading for the year

g) Make a horizontal bar graph of the rainfall readings.

h) Search the array of readings for a specific reading.

i) Sort the reading in ascending or descending order.

(a) Print Reading.

This exercise requires a traversal of the array for all of the data values. The array index ranges from 0 to rainfall.length - 1 (11) inclusive. Since there are four quarters in the year we must divide the index range by three. The values must be printed when the indices are: 11, 8, 5, and 2. Hence, the printing must be done when index % 3 is 2.

The following piece of code illustrates the concept.

1. String print()

2. {

3. String s = “”;

4.

5. for (int i = rainfall.length-1; i >= 0; i--)

6. if (i%3 == 2)

7. s = s + months[i] + " " + rainfall[i] + "\n");

8. }

Listing 8.4 Print values in an array

(b) Sum Rainfall Reading

This exercise follows similar patter to exercise (a), in which the array must be traversed. As each element is encountered it gets added to for the aggregate of all readings.

1. double sumArr()

2. {

3. double sum = 0;

4.

5. for (int i = 0; i < rainfall.length; i++)

6. sum = sum + rainfall [i];

7. return sum;

8. }

Listing 8.5 Sum array values.

(c) Find Average

Once the aggregate is known the average is found by simply dividing the aggregate by the number of readings. See Listing 8.6

1. double average()

2. {

3. return sumArr()/rainfall.length;

4. }

Listing 8.6 Finding average

d) List Elements above average

This exercise requires getting the average and traversing the list comparing the average to each array element. On condition that an element is larger than the average, a note is mad of that element. Listing 8.7 shows how this is done.

1. String aboveAvarage()

2. {

3. String s = "";

4. double avg = average();

5.

6. for (int i = 0; i < rainfall.length; i++)

7. if (avg > rainfall [i])

8. s = months[i] + " " + copy[i] + "\n";

9. return s;

10. }

Listing 8.7

(e) Standard Deviations

The standard deviation is the square root of, the sum of the squared difference of an observation and the mean, divided by the number of observations. See formula below.

((((xi - ū)2/N), I є [0, MAX]

The expression ((xi - ū)2 can be expressed as follows:

sumDifference = sumDifference + Math.pow((rainfall [i] - mean), 2);

where:

(xi - ū)2 is Math.pow((rainfall [i] - mean), 2);

xi is rainfall [i]

ū is the mean that was already calculated, and

MAX is rainfall.length – 1

Listing 8.8 show the method that does the calculation.

1. double standardDeviation()

2. {

3. double sumDifference = 0;

4. double mean = average();

5.

6. for (int i = 0; i < rainfall.length; i++)

7. sumDifference = sumDifference + Math.pow((rainfall [i] - mean), 2);

8.

9. return Math.sqrt(sumDifference/rainfall.length);

10. }

Lisitng 8.8 Finding standard deviation.

• PublixSupermarket s = new PublixSupermarket[5];

• PublixPerCounty p = new PublixPerCounty[3][];

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download