Sunday, November 6, 2011

Static and Dynamic One-Dimensioned Arrays in C

Implement a dynamic one-dimensioned array in C and understand how it compares with static arrays.

Study the following C program that works with a one-dimensioned array x having 5 elements and of type float.
#include <stdio.h>


int main() {
  float x[5], *p = x;
  int i;


  printf("x = %d, p = %d\n", x, p);


  for(i = 0; i < 5; i++) {
    x[i] = i + 1;
    printf("%6.2f ", x[i]);
  }
  printf("\n");


  for(i = 0; i < 5; i++) {
    p[i] = i + 1;
    printf("%6.2f ", p[i]);
  }
  printf("\n");


  for(i = 0; i < 5; i++) {
    p[i] = i + 1;     printf("%6.2f ", *(p + i));   }
  printf("\n");
}
The program above demonstrates the following important points:
  1. Name of an array is the address of the initial element of the array. In fact, it is a constant pointer, so that the value it stores (the address of the initial element of the array) is assigned at compile time and cannot be changed at run time.
  2. A pointer to float, such as p in the above prorgam, behaves just like the one-dimensioned array x, except that its value (the address of the initial element of the array) can be changed at run time. That is, after the program begins to run, it can be reassigned to a different one-dimensioned array.
  3. It is possible to access elements of the array using pointer arithmetic, as shown in the last segment of the program. In fact, replacing *(p + i) with *(x + i) would work in the same way.
Here is a diagrammatic representation of a static array:

Let us now completely dispense with static array and show how we could use a dynamic array. As with all things, additional features come with additional complexity. The programmer must now take the responsibility of allocating the required amount of memory and of freeing it up when it is no longer required.
#include <stdio.h>
#include <stdlib.h>

int main() {
  float *x;
  int i, n;

  scanf("%d", &n);
  p = (float *) malloc(sizeof(float) * n);
  if (p != null) {
    for(i = 0; i < n: i++) {
      x[i] = i + 1;
      printf("6.2f ", x[i]);
    }
  }
  else {
    fprintf(stderr, "Error: malloc() failed\n");
  }
  free(x);
}
Note the following points in the second program:
  1. Standard library header file stdlib.h is included because it contains the declaration of the function malloc().
  2. The number of elements n to be allocated is decided at run time, not at compile time.
  3. It is necessary to check if malloc() succeeded, and print an error message if it failed.
  4. When the array is no longer needed, programmer must free up the memory allocated to x. Program can deallocate only that memory that was allocated at compile time. It doesn't known how to deallocate memory allocated at run time.
Here is a diagram to illustrate dynamic arrays:

While using dynamic arrays, programmer is responsible for allocating and deallocating memory to the pointer. If a pointer is deleted (or goes out of scope) before the memory allocated to it is deallocated, this block of memory is not available for reallocation. Of course, all memory allocated to a program is deallocated when it exits, but during the running of the program, it leaves a "hole" in the memory.

The same logic could be extended to 2, 3 and multi-dimensioned arrays. But as can be expected, the story get a little murkier as the order of the array increases. For example, to create a dynamic two-dimensioned array, we need a pointer to pointer to float. To each element of this dynamically allocated array (which points to one row of the array), we must allocate enough memory to hold the elements of one row. Deallocating memory will have to undo these steps backwards. Memory allocated to individual rows must first be deallocated, and then the memory allocated to the pointers to the rows. This implementation of a 2D array requires more memory than the standard C array, as additional memory is required for the pointer each row.

If you don't take care of it, the memory allocated to different rows may not be contiguous. If we wanted the dynamic 2D array to be contiguous, we must allocate enough memory for the entire array in one chunk and set the pointers to the correct positions within this allocated memory. Deallocating memory is a little complicated because we need the pointer to which memory was originally allocated while deallocating the memory. So while the order of deallocating is unimportant, one more pointer (of type float* if the array contains elements of type float) is required for each array.

Doing the same in C++ is little simpler. You can use the new operator to allocate memory and delete to deallocate memory. Otherwise, it is essentially the same as in the above two programs. While allocating an array of elements, use x = new [n], and the corresponding deallocation call is delete [] x. Number of elements being allocated is n, and the number of elements allocated is not required while deallocating.

No comments:

Post a Comment

Your comments are ciritical input for the sustainance and improvement of this blog.