WEEK 7 FOR i_GotchA

Data are the lifeblood of computer programs—most useful programs manipulate data of various kinds. In module 2, we presented a hierarchy of different kinds of data, and we studied unstructured data types in detail.

In this module, we turn our attention to structured data types, which can be custom-tailored to individual needs. These data types are also called, naturally, user-defined types. A structured data element is a composite entity that has accessible and manipulable "internal parts," which is in contrast to data types like chars and ints that usually are defined by a programming language and that can be considered  atomic  at a certain level.

We will examine the following important structured data types—arrays, structures (records), classes, and files. We also briefly discuss pointers in this module.

I. Arrays

An array is a data structuring mechanism that groups together in a computer's memory data elements that have the same type. Just as we had variables that were ints, floats, and so on, we can also have variables that are arrays. The only difference is that whereas variables of the former kind can hold just one value, array variables can hold many values (all of the same type, of course).

Array variables have names—we will use A, B, C, and so on to represent array variables throughout this section. Many programming languages follow the convention that the initial letter of all structured data types is capitalized.

Here are the fundamental properties of arrays.

· All of the data elements are of the  same type .

· It takes the same amount of time to access any data element.

Elements can be organized in an array in several ways. They can be organized in

· a simple row or column (1-dimensional array)

· a rectangular matrix (2-dimensional array)

· a three-dimensional matrix (3-dimensional array)

and so on.

A 1-dimensional array often is referred to simply as "an array" (if no dimension is specified, one dimension is the default).

Each dimension of an array will contain an index (or subscript). In pseudocode, the index runs from 1 to some positive integer that specifies the size of that dimension. One way to visualize arrays is to imagine that "storage cells" are located at the index positions along each dimension.

For example, if we had a 2-dimensional array B, and the sizes of the two dimensions are 4 and 5 respectively, then the indices of the first dimension are 1, 2, 3, 4, and the indices of the second dimension are 1, 2, 3, 4, 5.

The size of the array, which gives the total number of elements that can be stored in the array, is obtained by multiplying the sizes of all the dimensions (in this case, 4 x 5 = 20).

We will use the following arrays as examples in this section, and you should study this table carefully.

Figure 5-1 Arrays Used in this Section

Array Name	Array Type	Number of Dimensions	Sizes of Dimensions	Permitted Indices	Array Size
A	int	1	8	1, 2, 3, 4, 5, 6, 7, 8	8
B	char	2	4 5	1, 2, 3, 4 1, 2, 3, 4, 5	4 × 5 = 20
C	bool	3	4 3 6	1, 2, 3, 4 1, 2, 3 1, 2, 3, 4, 5, 6	4 × 3 × 6 = 72

A. Accessing Array Elements

To access an element stored in an array, we have to specify one index for each dimension of the array. The index to be specified is written within brackets

[ ]

placed after the name of the array. Obviously, each index must not exceed the size of the corresponding dimension, and permitted values must be specified for the indices for each dimension of the array. For example, the reference B[3] would be illegal. ( Why? )

· A[5] (read as "A sub 5") will access the fifth int stored in array A.

· B[3, 5] (read as "B sub 3, 5") will access the char stored at location [3, 5].

· C[2, 3, 1] will access the Boolean value stored at location [2, 3, 1].

Attempting to access B[3, 7] would be illegal. ( Why? ). 

The diagrams in figure 5-2 will help you visualize these arrays (it is difficult to visualize arrays with more than three dimensions). Be sure you understand how the indices access various elements in the arrays.

Figure 5-2 Array Elements

Arrays are stored in consecutive locations in a computer's memory. Although beyond the scope of this course, you may be interested in seeing how many programming languages, including C++ and Java, store the elements consecutively in  row-major order . 

B. Array Declarations

The arrays defined in figure 5-1 above would be declared in our pseudocode as follows:

Declare A[8] of int Declare B[4, 5] of char Declare C[4, 3, 6] of bool

Note that although our pseudocode (and other programming languages) do provide the generic array type, the particulararrays defined above have been created by the user.

The type of each element of the array follows the word of. Because all elements in an array have to be of the same type, all the 8 elements in array A will be ints, all the 20 elements in B will be chars, and so on. Both the number of dimensions and the size of each dimension of each array are evident from the declarations. 

It is usually better (for reasons we will discuss a bit later) to not mention any numbers (e.g., 8, 4, 5, 3 ) in an array declaration. It is much better to use symbolic names for such constants. We will use array B as an example:

 /* better pseudocode declaration for arrays */ 

Declare B_size1 as constant 4 // symbolic constant  Declare B_size2 as constant 5 // symbolic constant 

Declare B[B_size1, B_size2] of char // declaration of array B 

Here, B_size1 and B_size2 are declared as symbolic constants having certain values (4 and 5 respectively), and array B itself is declared using these symbolic constants. It is important to realize that the value of a declared symbolic constant cannot be changed at run time (that's why it is called a constant!). Similar declarations, using symbolic constants can be written for arrays A and C also. 

Examples of array declarations in C++ and Java, using symbolic constants are: 

const int A_size  = 8 ; // C++ constant declarations  const int B_size1 = 4 ;  const int B_size2 = 5 ; 

// C++ or Java array declarations using symbolic constants 

int A[A_size] ;  char B[B_size1][B_size2] ; 

In Java, the arrays are declared as shown above for C++, but the definition of symbolic constants differs slightly: 

final int A_size  = 8 ; // Java constant declarations  final int B_size1 = 4 ;  final int B_size2 = 5 ; 

Arrays in C++ and Java have certain  distinctive features , which do not immediately concern us. 

C. Operations on Arrays

Most programming languages (APL is an exception) do not allow direct operations on entire arrays—e.g., comparisons of two arrays, direct assignments to entire arrays, and so on. Operations are permitted only on individual array elements. 

D. Array Indices

Part of the power of arrays comes from the fact that array indices can be arbitrary expressions, not just numbers as we have used previously. For example, the following are all proper ways to access array elements in arrays A, B, and C: 

· A[2*i] 

· B[3, j] 

· C[2*x, y, x–y] 

What happens at run time is that the expressions are evaluated to numbers using the current values of the referenced variables, and the array elements stored in those positions are accessed. Only expressions that yield integer results can be used for indices. 

For example, if the current values of i, j, x, and y are 4, 3, 2, and 3, respectively, then the array elements accessed in the examples shown above will be 

A[8],  B[3,3]  C[4,3, –1] 

The first two accesses are correct, but the last one is incorrect. ( Why ?)

Java will perform run-time checks for array indices and will report an error for the reference involving array C, whereas C++ will simply access a memory location that corresponds to [4,3, –1], and return the value stored there, though that location definitely does not belong to array C! It is always good programming practice for the program to ensure that array indices fall within the allowed bounds. 

E. Using Array Elements

Array elements can be used just like ordinary variables of the type of the array. An array element can be used wherever it is appropriate to use an ordinary variable of the same type as the array. Thus, for example, the following are all valid uses of array elements: 

· // A[j] is an int, and ints can be used in  // arithmetic expressions. 

 temp = (A[j] + 30) * 2 

· // B[3, 2] is a char that is compared with char 'X' 

 if  (B[3,2] == 'X') then      . . .   End if 

· // C[i,j,k] is a Boolean value, and can be negated 

 if  (!C[i,j,k]) then     . . .   End if 

Here is an example of how array elements are used in C++ or Java: 

// C++ or Java array element assignment 

C[4][3][6] = false ; 

Note that brackets are placed around each index (this differs from our pseudocode convention). 

F. Using Arrays in Computations

Arrays often are used when the same computation is performed on a number of variables, all of which have the same type. 

The for loop (discussed in module 4) plays a prominent part in array computations. If we set the following values in a forloop, 

· initial value = 1 

· final value = size of an array dimension 

· step value = 1 

the loop will access systematically each element of the array. We must use nested for loops to process multidimensional arrays. The advantage of using for loops is that if we have correctly set the parameters of the for loops, each array index will always be within the bounds for that dimension. 

Example 1

The program in the trace below will initialize each element of array E. Though we have shown a simple computation (i + j) for the initialization in the code, you should appreciate that we could have performed any other complex computation in its place. Note that we have deliberately not used symbolic constants in this code. 

To understand the power of arrays, imagine what would happen if we had to initialize 20,000 int variables or perform some other identical computation on all of them. We would need to write 20,000 different assignment statements! But if these variables were elements of an array, our work would be reduced to writing three or four lines of code in a for loop. 

Here, we should pause to understand the use of symbolic constants. In the pseudocode given above, we see references to numbers like 4 and 5. These seemingly arbitrary numbers are often called  magic numbers .

Programs in which magic numbers are strewn throughout the code are difficult to read and modify, so there are disadvantages in using magic numbers .

Example 2

Let us consider another example involving arrays. This time, we are required to write a function that will accept an array index and a value, and will assign the specified value to the specified index position in array A. Here is the function that accomplishes this task.

void function array_assign(int index, int value, int array_size) {       If ((1 <= index)&&(index <= array_size)) then       Set A[index]= value       End if }

The function is a void function because it does not return anything—its only effect is to change one element of array A. You may wonder  why a function is being written  to do this—after all, it is perfectly simple to assign values to array elements! 

Example 3

As a final example of array processing, we will consider a simple sorting algorithm called insertion sort. The principle used in insertion sort is similar to what you use when you are assembling a hand of cards in certain card games—as you pick up each dealt card, you put it in its proper place in your hand. Insertion sort is quite efficient in sorting small sets of numbers. 

We want the numbers to be assembled in sorted order, from low to high, in the array. We will first show an animation that depicts how the algorithm works (using the numbers 3, 8, 4, 5, 7, 1, 6, 2 ), and then we will give the pseudocode algorithm for the insertion sort.

Click successively on the "next" button to see how to sort the numbers 3, 8, 4, 5, 7, 1, 6, and 2. The "Show me" button will animate the process to illustrate the more complicated steps. You can click on the "Show me" button to repeat the process if you wish.

After you have stepped through the insertion sort animation several times, trace through the pseudocode algorithm below yourself, using the same values (3, 8, 4, 5, 7, 1, 6, 2). 

/*Insertion Sort in pseudocode*/ Declare A_size as constant 8  Declare A[A_size] of int 

Declare next_item as int // next item to be stored  Declare i, j as integer  // counters 

Input next_item          // Store first element in A[1]  Set A[1] = next_item 

For i = 2 step 1 to A_size     {        Input next_item     // read next item to be sorted 

      // determine location j where next_item belongs        // all elements that are greater than next_item        // should be "bumped down" by one position 

      Set j = i

      While ((next_item < A[j-1])&&(j > <a[j-1])&&(j>0))           {              Set A[j] = A[j-1]              Set j = j - 1           }        End while 

      A[j] = next_item    } End for

G. Strings

To illustrate another use of arrays, we will consider how strings are implemented in the C language. Recall that a string contains zero or more chars, and strings are represented by placing the associated chars between double quotes. A string with no chars, called the empty string, is represented by two double quotes with nothing between them: 

"" 

Note that the string "1" is different from the character '1' . The latter is represented by one of the character codes (ASCII, UNICODE, and so on), whereas the former involves a more complicated representation such as the one shown below. And both of them are different from the number 1! 

In the C language, a string is represented by a 1-dimensional array whose elements are the chars inside the string, with a marker (called Null) added after the last character of the string. For example, the strings 

· ""         (the empty string) 

· "a" 

· "String in C" 

are represented in the C language as follows, using arrays. 

Figure 5-3  String Representation

The blanks between the words in the last string are chars also and are shown in the array representation. Note that the number of elements in each array is one more than the number of characters in the corresponding string—because one slot in the array will be needed to store Null.