Data Structures and Programming : Arrays Study Notes

• 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

  For the detailed schedule of the GATE Computer Science Engineering(CSE) 2021 Champion Study Plan, click here.

GATE Computer Science Engineering(CSE) 2022 Champion Study Plan

Click Here to Avail GATE CSE Test Series!

Thanks