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

Click Here to Avail GATE CSE Test Series!

Thanks

#DreamStriveSucceed