2.1       Array Definition

2.2       Representation

2.3       Analysis

2.4       Single and Multidimensional Arrays

2.5       Address calculation

2.6       Application of arrays

2.7       Character String in C

2.8       Character string operation

2.9       Array as Parameters

2.10      Ordered List

2.11      Sparse Matrices

2.12      Vectors.

Representation of One-dimensional array in memory:-

Suppose name of linear array is arr and it has 5 elements. Then its elements are represented as:

                             arr

          0           1           2           3           4  

arr[0], arr[1], arr[2], arr[3], arr[4].

Address calculation in one-dimensional Array:-

Since array elements are stored in contiguous memory locations, the computer needs to not to know the address of every element but the address of only first element. The address of first element is called base address of array. Given the address of first element, address of any other element is calculated using the formula:-

Loc (arr [k]) =base (arr) + w * k (in C/C++/Java)

Where k is the index of array whose address we want to calculate and w is the number of bytes per storage location of for one element of array.

If not given explicitly, we take index set as 1,2,3,4,……n where n the upper bound of the array.

Example:- Suppose that array arr is declared as integers with size 20 and its first element is stored at address 1000. Calculate the address of 4^th element of array when the index of the array starts from 0.

Here, base address=1000, k=3, w=2.

Thus, loc(arr[3])=1000 + 2*3=1006

Representation of two dimensional array in memory:

Suppose name of two-dimensional array is mat and it has 3 rows and 4 columns. Then its elements are represented as:

mat[0][0],    mat[1][0],    mat[2][0]

mat[0][1],     mat[][1],     mat[2][1]

mat[0][2],    mat[1][2],    mat[2][2]

mat

          0                1                      3

0
1
2

Elements of two-dimensional arrays are stored in two ways:-

(i)         Column major order: Elements are stored column by column, i.e. all elements of first column are stored, and then all elements of second column stored and so on.

mat[0][0]

Column 0   mat[1][0]

mat[2][0]

mat[0][1]

Column 1   mat[1][1]

mat[2][1]

mat[0][2]

Column 2   mat[1][2]

mat[2][2]

(ii)       Row major order: Elements are stored row by row, i.e. all elements of first row are stored, and then all elements of second row stored and so on.

mat[0][0]

Row 0   mat[0][1]

mat[0][2]

mat[1][0]

Row 1   mat[1][1]

mat[1][2]

mat[2][1]   mat[2][0]

Row 2

mat[2][2]

Address calculation in two-dimensional Array:-

The address of the element in the ith row and jth column is given by:

(i)         Column major order:

Loc(arr[i][j])=base(arr) + w (m *j + i) in C/C++/java

Loc(arr[i][j])=base(arr) w[m(j - lbc) +(i – lbr)] in general

Where array is m x n matrix,

lbc is the lower bound of column,

lbr is the lower bound of row.

(ii)       Row major order:-

Loc(arr[i][j])=base(arr) + w (n*i + j) in C/C++/java

Loc (arr[i][j])=base(arr) w[n(I - lbr) +(j – lbc)] in general

Where array is m x n matrix,

lbc is the lower bound of column,

lbr is the lower bound of row.

Applications of Arrays

Although useful in their own right, arrays also form the basis for several more complex data structures, such as heaps, hash tables, and vlists, and can be used to represent strings, stacks and queues. They also play a more minor role in many other data structures. All of these applications benefit from the compactness and locality benefits of arrays.

One of the disadvantages of an array is that it has a single fixed size, and although its size can be altered in many environments, this is an expensive operation. Growable arrays or dynamic arrays are arrays which automatically perform this resizing as late as possible, when the programmer attempts to add an element to the end of the array and there is no more space. To average the high cost of resizing over a long period of time (we say it is an amortized cost), they expand by a large amount, and when the programmer attempts to expand the array again, it just uses more of this reserved space.

In the C programming language, one-dimensional character arrays are used to store null-terminated strings, so called because the end of the string is indicated with a special reserved character called a null character ('\0') (see also C string).

Finally, in some applications where the data is the same or is missing for most values of the indexes, or for large ranges of indexes, space is saved by not storing an array at all, but having an associative array with integer keys. There are many specialized data structures specifically for this purpose, such as Patricia tries and Judy arrays. Example applications include address translation tables and routing tables.

Array as Parameter

Every parameter of a C-function must be declared within the function. However, the range of a one-dimensional array parameter is only specified in the main program. This is because in C new storage is not allocated for an array parameter. Rather, the parameter refers to the original array that was allocated in the calling program.

For example:- consider the following function to compute the average of the elements of an array:-

float avg(float a[], int size)

{

    int I;

    float sum;

    sum=0;

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

         sum+=a[i];

    return (sum/size);

}

In the main(), we might have written

#define RANGE 100

float a[RANGE};

…………………………….

…………………………….

avg(a,RANGE);

Note that if the array is needed in the function, it must be passed separately. Since an array variable in C is a pointer, array parameters are passed by reference, rather than by value. That is unlike simple variables, that are passed by value, an array’s contents are not copied when it is passed as a parameter in C. Instead, the base address of array is passed.

If a calling function contains the call func(a), where ‘a’ is an array, and the function func() has the prototype

        Void func(int b[]);

The statement

           b[i]=x;

inside the function func() modifies the value of a[i] inside the calling function.

“b” inside function func() refers to the same array of locations as “a” in the calling function.

Passing an array by reference rather than by value is more efficient in both time and space. The time that would require to copy an entire array on invoking a function is eliminated.

Also, the space that would be needed for a second copy of the array in the called function is reduced to space for only a single pointer variable.

Character Strings in C.

A string in C is defined as an array of characters. Each string is terminated by the NULL character, which indicates the end of the string.

A string constant is denoted by any set of characters enclosed in double quote marks(“ “).

The NULL character is automatically appended to the end of the characters in the string constant when they are stored.

Within a program, NULL character is denoted by the escape sequence ‘\0’.

A string constant represents an array whose lower bound is 0 and whose upper bound is the number of characters in the string.

For example, the string “HELLO C” is an array of 8 characters, the blank and the \0 each count as a character.

Character String Constant

Let us learn C-functions to implement some primitive operations on character strings. For all these functions, we assume the global declarations:-

#define STRSIZE 80

The first function finds the current length of a string.

int mystrlen(char string[])

{

  int i;

     for(i=0;string[i]!= ’\0’; i++);

           return i;

}

The function obtains two strings as parameters. The function returns an integer indicating the starting location of the first occurrence of the second parameter string within the first parameter string. If the second string does not exist within the first, -1 is returned.

   int strops(char s1[], char s2[])

         {

               int len1, len2;

               int I,j1,j2;

               len1=strlen(s1);

               len2=strlen(s2);

             for(i=0 i+len2<=len1; i++)

                for(j1=i,j2=0;j2<=len2 && s1[j1]==s2[j2]; j1++,j2++)  

                   if(j2==len2)

                       return (i);

             retrun (-1);

         }

Example:-

Another common operation on string is concatenation. The result of concatenating two strings consists of the characters of the first followed by the characters of the second.

The following function sets s1 to the concatenation of s1 and s2.

void strcat( char s1[], char s2[])

   {

       int i,j;

           for( i=0; s1[i]!=’\0’; i++);

           for(j=0;s2[j]!=’\0’; s1[i++]=s2[j++]);

   }

Another common operation on string is the substring operation. Substr(s1,I,j,s2) sets the string s2 to the j characters beginning at s1[i].

void substr(char s1[], int i, int j, char s2[])

      {

           int k, m;

               for(k=I,m=0;m<j;s2[m++]=s1[k++]);

               S2[m]=’\0’;

      }

      

              

Ordered List:

A list in which the elements are arranged so that the key values are placed in ascending or descending sequence.

Ordered Lists are maintained in sequence according to the data or, when available a key that identifies the data.

Sparse Matrices:-

An mxn matrix A is said to be sparse if many of its elements are zero. A matrix that is not sparse is called dense matrix. It is not possible to define an exact boundary between dense and sparse matrices.