Data Structures and Programming : Arrays Study Notes

By Mukesh Kumar|Updated : December 4th, 2021
  • An array is defined as a collection of similar elements having the same data type accessed using a common name.
  • Array elements occupy contiguous memory locations.
  • Array indices start at zero in C and go to one less than the size of the array.
  • An array is defined as a collection of similar elements having the same data type accessed using a common name.
  • Array elements occupy contiguous memory locations.
  • Array indices start at zero in C and go to one less than the size of the array.
  • Declaration of an Array:

    type variable[num_elements]; 

    Example: int A[100];

    • It creates an array A with 100 integer elements.
    • The size of array A can't be changed.
    • The number between the brackets must be a constant.

    Initialization of an Array :

    • int A[5]= {1,2,3,4,5}; /*Array can be initialized during declaration*/
    • int A[5]={1,2,3}; /* Remaining elements are automatically initialized to zero*/
    • int A[5]={1,[1]=2, 3,4,[4]=0};/* Array element can be initialized by specifying its index location*/

    Problems with Arrays :

    • There is no checking at run-time or compile-time to see whether the reference is within array bounds.
    • The size of an array must be known at compile time.
    • The increasing size of an array is not always possible.
    • Inserting an element in the array takes O(n) time in the worst case.

    Pointers & Arrays: 

    Let a[10] be an array with 10 elements.

    • The name a of the array is a constant expression, whose value is the address of the 0th location.
    • An array variable is actually just a pointer to the first element in the array.
    • You can access array elements using array notation or pointers.
    • a[0] is the same as *a
    • a[1] is the same as *(a + 1)
    • a[2] is the same as *(a + 2)
    • a = a+0 = &a[0]
    • a+1 = &a[1]
    • a+i = &a[i]
    • &(*(a+i)) = &a[i] = a+i
    • *(&a[i]) = *(a+i) = a[i]
    • Address of an element i of array a = a + i * sizeof(element)

    Multi-Dimensional Array

    In C language, one can have arrays of any dimensions. Arrays can be 1-dimensional, 2-dimensional, 3-dimensional, etc.

    Let b be the Two Dimensional Array b[i][j]

    • For Row Major Order: Size of b[i][j] = b + ( Number of rows * i + j )*sizeof(element)
    • For Column Major Order: Size of b[i][j] = b + ( Number of Columns * j + i )*sizeof(element)
    • *(*(b + i) + j) is equivalent to b[i][j]
    • *(b + i) + j is equivalent to &b[i][j]
    • *(b[i] + j) is equivalent to b[i][j]
    • b[i] + j is equivalent to &b[i][j]
    • (*(b+i))[j] is equivalent to b[i][j]

    Calculating address of an element in an array :

    1. 1-D Arrays

    Consider a single dimensional array as A[lb------ub]

    The base address of array = BA

    Size of each element in array = c

    Total elements in the array are given by (ub-lb+1)

    Then the address of any random element A[i] is given by :

    Location[A[i]] = BA + (i-lb)*c

    2. 2-D Arrays

    2-D arrays can be stored in the system in two ways: Row Major order and Column Major order.

    Consider a 2-D array as A[lb1-----ub1][lb2------ub2]

    The base address of array = BA

    Size of each element in array = c

    Number of rows = ub1-lb1+1

    Number of columns = ub2-lb2+1

    If stored in Row Major order , then address of any random element A[i][j] is given by :

    Location[A[i][j]] = BA + [(i-lb1)*(ub2-lb2+1)+(j-lb2)]*c, 

    where c is the size of an element. 

    If stored in Column Major order , then address of any random element A[i][j] is given by :

    Location[A[i][j]] = BA + [(j-lb2)*(ub1-lb1+1)+(i-lb1)]*c,

    where c is the size of an element. 

    Strings

    In C language, strings are stored in an array of character (char) types and the null terminating character "\0" at the end.

    Printf and scanf use "%s" format character for string. Printf print characters up to terminating zero. Scanf read characters until whitespace, store result in the string and terminate with zero.

    Example: 

    char name[ ] = "GATETOP";

    OR char name[ ] = { 'G', 'A', 'T','E', 'T', 'O', 'P', '\O'};

     

    • '\0' = Null character impended at last of the array whose ASCII value is O.
    •  '0' = Zero character whose ASCII value is 48.
    • C inserts the null character automatically. '\0' is not necessary for the above declaration. 
    •  %s is used in printf ( ) for the format specification to print a string. 
    • Following notations refers to the same element: name [i] , * (name + i), * (i + name), i [name]
    • We don't consider the null character in the length of the string, but we consider it in the size of the string.

    For Example: 

    Assume, char name[ ] = { 'G', 'A', 'T','E', 'T', 'O', 'P', '\O'};

    • length of string= 7
    • size of string= 8

Comments

write a comment

Follow us for latest updates