Contents |
|
|
|
|
| Simplified for loop | |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Up to now, we've been able to use variables of the data types predefined in Java. Each variable can store exactly one value of that data type. Arrays now allow us to create and use any number of variables of the same type simultaneously. The space for the data is provided on the heap . Only a reference is stored on the stack, which holds the local data of a subroutine .
Variables that can hold arrays (actually references to arrays) are enclosed in square brackets [] . The array itself must be provided using ` new` . In the following example, we want to create 1000 variables of type ` double` , which will be grouped into an array.
double a[]; a = new double[1000];
or shorter
double a[] = new double[1000];
An alternative syntax is
double[] a = new double[1000];
This syntax relies on the fact that the array's data type can be denoted by ` double[]` . Unlike other programming languages, a concrete array has a fixed size, but this size is not specified in the data type. It only needs to be specified when the array is created. The array's size can be changed later using `a`.Determine the length , but do not change it. There are also dynamically growing arrays, which are somewhat less efficient. We will learn about these arrays later.
The command above provides 1000 double variables. Access to a single variable is achieved through indexing. The desired index is specified in square brackets. As an example, we will store the square numbers 1^2, 2^2, ..., 1000^2 in the array.
for (i=0; i<1000; i++) a[i]=i*i;
Caution: Note that the numbering starts with 0! The last element therefore has the index 999 (size minus 1).
The general syntax of an indexed array variable is therefore
arrayname [ index ]
where `index` must be an expression of type ` int` . Such an indexed variable can be used like any other variable of the corresponding type (in the example, `double` ).
Here is another example where a variable of the array appears both to the right and to the left of = .
a[0] = 1.0; for (i=1; i<1000; i++) a[i] = 1.01*a[i-1];
This example sets each element of the array to 1.01 times the previous one, starting with 1. Therefore, you have to set the first element and then process the remaining ones in a loop.
Overall, arrays are stored as follows.
Reference a on the stack ---> a[0] ,..., a[n-1] on the heap
Here, n is the size of the array.
If an index lies outside the bounds 0 to n-1 , an index-out-of-bounds exception is generated. In our simple test programs, this leads to program termination with an error message.
If the array is not initialized with `new` , the reference will have the predefined value `null` . Any attempt to access the array will then generate a so-called `NullPointerException` .
Arrays are automatically removed from the heap when they are no longer needed in the program. Java can determine when this is the case. This process is called garbage collection .
There's a simpler way to access each element of an array. A loop variable isn't needed at all. Here's how.
int a[] = new int[10]; for (int i=0; i<10; i++) a[i]=i*i; for (int k : a) System.out.println(k);
The first loop, in which the content of `a` is set, is already familiar to us. The second loop is a shorthand version where the variable `k` iterates through all elements of `a`. As with the regular `for` loop, this variable can also be declared directly within the loop.
Note two important things.
Because of these limitations, this loop form is more suitable for accessing general collector classes, which we will learn about later.
We generate 10000 random numbers and determine the mean, the standard deviation, and count how many numbers lie in each interval 0 to 0.1 , 0.1 to 0.2 , etc.
First, space is created in an array for 10,000 numbers. Then, 10,000 random numbers are generated and stored in the array. When working with the array, always remember that the index must range from 0 to 9999.
Finally, another array I of size 10 stores the counters. I[0] should, for example, contain the number of random numbers between 0 and 0.1. The index of the counter interval is determined from the random number by multiplying it by 10 and truncating the decimal part.
public class Test
{
public static void main(String args[])
{
int n = 10000; // Number of random numbers
double R[] = new double[n]; // Creates space for n numbers
int i;
// Random numbers:
for (i = 0; i < n; i++)
R[i] = Math.random();
// Average:
double sum = 0;
for (i = 0; i < n; i++)
sum += R[i]; // calculate sum
double mean = sum / n;
System.out.println("Average : " + mean);
// Sample deviation:
sum = 0;
for (i = 0; i < n; i++)
sum += (mean - R[i]) * (mean - R[i]);
// Calculate variance:
System.out.println("Standard deviation : " + Math.sqrt(sum / (n - 1)));
// Distribution:
int m = 10;
int I[] = new int[m]; // Space for m counters
int j;
for (j = 0; j < m; j++)
I[j] = 0; // initialize with 0
for (i = 0; i < n; i++) // count
{
// In which interval does R[i] lie?
j = (int) Math.floor(R[i] * m);
I[j]++; // increment counter
}
// Edition:
for (j = 0; j < m; j++) // Output the counts
System.out.println((j + 1) + " : " + I[j]);
}
}
Some things require explanation.
Note that the size of the array in the `new` command can also be specified using a variable or an expression. The program produces the following output.
Average: 0.5000445575184346 Standard deviation: 0.28746642473628076 1:967 2:991 3 : 1060 4:992 5 : 1001 6:988 7 : 1065 8:952 9:993 10:991
This output is not the same every time. Unlike in C, the random number generator is initialized with the system time on each run.
The following program generates random numbers and sorts them. The sorting algorithm is the worst imaginable, but also the simplest. Therefore, this program is only suitable for small datasets.
The algorithm works as follows: The numbers R[2] to R[n] are repeatedly swapped forward until they are in the correct position. This is called bubble sort.
Steps 2 and 3 sort the j-th number into the correct position.
public class Test
{
public static void main(String args[])
{
int n = 20;
double R[] = new double[n];
double h;
int i, j;
// Generate random numbers:
for (i = 0; i < n; i++)
R[i] = Math.random();
// Sort:
for (i = 1; i < n; i++)
{
j = i; // Sort R[i]
while (j > 0) // as long as it is not at the very beginning
{
if (R[j - 1] > R[j]) // is still incorrect
{
h = R[j];
R[j] = R[j - 1];
R[j - 1] = h; // swap
}
else break; // is correct
j--;
}
}
// Edition:
for (i = 0; i < n; i++)
System.out.println(R[i]);
}
}
You can assign values to an array when you declare it. In this case, no `new` is necessary. Example:
int n[] = {2,5,3,1};
System.out.println(n.length); // prints 4
The size of the array is determined by the number of specified values. These values do not need to be constants.
In Java, multidimensional arrays (matrices, etc.) are created by arrays of arrays. This is sometimes transparent to the programmer, meaning they don't need to worry about it. For example, if you want to create space for three rows of four elements each, it's sufficient to...
int M[][] = new int[3][4];
to set. This matrix is a 2-dimensional array. Loops over such matrices usually have to be nested loops. For example.
int i,j;
for (i=0; i<3; i++)
for (j=0; j<4; j++)
M[i][j] = i*j;
Access is therefore achieved through as many pairs of parentheses as the dimension of the array indicates.
The following program demonstrates that this is indeed an array of three arrays.
int a[]=M[0]; for (i=0; i<a.length; i++) a[i]=i; System.out.println(a.length);
Here, the first row of M is assigned to a one-dimensional array with four elements. Therefore, M is stored as follows.
M ----> M[0] , M[1] ,
M[2]
M[0] ----> M[0,0] , M[0,1] ,
M[0,2] , M[0,3]
M[1] ----> M[1,0] , M[1,1] ,
M[1,2] , M[1,3]
M[2] ----> M[2,0] , M[2,1] ,
M[2,2] , M[2,3]
It is indeed not necessary for multidimensional arrays to be rectangular. Each row can have a different size.
int M[][] = new int[3][]; for (int i=0; i<3; i++) M[i] = new int[i+1];
In this example, the rows of M have lengths of 1, 2, 3. This creates a triangular array.
The main difference between the commands
new int [3][4]; new int[3][];
The difference is that in the first case, references to the lines are created automatically, and in the second case, they are not. In the latter case, the programmer must initialize each individual line before the elements can be accessed.
The same applies to three-dimensional and multi-dimensional arrays.
We generate the first n prime numbers. We will first describe the algorithm used.
The difficulty lies in implementing this simple algorithm into a program.
public class Test
{
public static void main(String args[])
{
int n = 10;
int p[] = new int[n];
// Set the first two prime numbers
p[0] = 2;
if (n > 1)
p[1] = 3;
// generate the rest:
int i, j;
for (i = 2; i < n; i++) // generate p[2] to p[n-1]
{
int m = p[i - 1] + 2;
// try last prime number plus 2, 4,...
search: while (true) // actually a continuous loop
{
j = 0;
while (true)
// test for divisibility by p[0],...,p[i-1]
{
if (m % p[j] == 0)
break;
// m is not prime
if (p[j] * p[j] > m || j >= i)
// m is prime, sufficiently sought
{
p[i] = m;
break search;
}
j++;
}
m += 2;
}
}
// Edition:
for (i = 0; i < n; i++)
System.out.println(p[i]);
}
}
Here, the `break` statement is used with a label. This stops the search for the next prime number as soon as a prime number is found. This example becomes much more readable if you use subroutines.
The following code solves a system of equations using Gaussian elimination . This example is probably only of interest to mathematicians. We will first describe the algorithm used.
public class Test
{
public static void main(String args[])
{
double a[][] =
{
{ 1, 2, 3 },
{ 4, 5, 6 },
{ 7, 8, 1 } };
double b[] =
{ 6, 15, 16 };
double h[];
int i, j, k, n = b.length;
double m;
int mk;
// Make M the upper triangular matrix:
for (i = 0; i < n - 1; i++)
{
// Search for maximum in a column below M[i][i]:
m = Math.abs(a[i][i]);
mk = i;
// previous maximum and its row
for (k = i + 1; k < n; k++)
{
if (Math.abs(a[k][i]) > m)
{
m = Math.abs(a[k][i]);
mk = k;
}
}
// Possibly swap lines:
if (mk != i)
{
h = a[i];
a[i] = a[mk];
a[mk] = h;
m = b[i];
b[i] = b[mk];
b[mk] = m;
}
// Set the column below M[i][i] to 0:
for (k = i + 1; k < n; k++)
{
double lambda = a[k][i] / a[i][i];
for (j = i + 1; j < n; j++)
a[k][j] -= lambda * a[i][j];
b[k] -= lambda * b[i];
}
}
// Make M the diagonal matrix:
for (i = n - 1; i >= 1; i--)
{
for (k = i - 1; k >= 0; k--)
b[k] -= b[i] * a[k][i] / a[i][i];
}
// Make M the identity matrix:
for (i = 0; i < n; i++)
b[i] /= a[i][i];
// Output result:
for (i = 0; i < n; i++)
System.out.println(b[i]);
}
}
The code in this example is quite complex. It can be difficult to find a bug in it. This program, too, can be made more readable by structuring it with subroutines.