home *** CD-ROM | disk | FTP | other *** search
/ The C Users' Group Library 1994 August / wc-cdrom-cusersgrouplibrary-1994-08.iso / vol_300 / 344_01 / mtx.doc < prev    next >
Text File  |  1991-01-01  |  4KB  |  90 lines
  1.  
  2.                            RUN-TIME ARRAYS IN C
  3.  
  4.                     Dynamic Allocation and Usage of Array
  5.                 Structures Composed during Run-Time Operations
  6.  
  7.                           Bill Forseth, Duluth MN
  8.  
  9.    One of the problems frequently faced by programmers is the fact that
  10. array allocation is a compile-time operation. If the size of an array is
  11. unknown during the compilation process one usually needs to implement some
  12. form of linked list, with all the attendant overhead and occasionally
  13. debugging grief.
  14.  
  15.    This need not be so. Conceptually, an array is a group of like items,
  16. (or records), with individual elements made available through sub-
  17. scripting.  An array can be passed as a pointer, (which in fact it is),
  18. which can lead to speedy operations. Arrays need not be traversed, nor do
  19. they have to be freed. An array element contains only the space needed to
  20. hold the specified value(s), no pointers to next, last, head, tail, etc.
  21. nodes.
  22.  
  23.    These basic problems need to be overcome in creating run-time arrays:
  24.         1. declaring the basic element type
  25.         2. allocation for the array as a whole
  26.         3. element accessing
  27.  
  28.    The solution for the first problem, 99 out of a hundred times, is simple
  29. enough - hard-code the type, perhaps in a header file. For that hundredth
  30. time, (which we needn't get into for the purposes of this article), C's
  31. invaluable "sizeof" operator can be used.
  32.  
  33.    For the second problem, an example would be more instructive than my
  34. words. Given that the type is float, and the need is for an array of N
  35. elements, (where the value of N is determined, like any other variable, at
  36. run-time). An array called 'A' can be created with this simple operation:
  37.  
  38.                A = (float)malloc(sizeof(float)*N);
  39.  
  40.    (Note that A should be declared as a POINTER to a float in it's own
  41. declaration).
  42.  
  43.    Now A points to a memory location containing the number of bytes (in the
  44. system definition of a float) times N, which is our original working
  45. definition of an array's memory space.
  46.  
  47.    Number three says we need to solve the element accessibility problem,
  48. which given C's pointer arithmetic, is efficient and relatively painless.
  49. To access the i-th element of array A, all we need to do is use this simple
  50. formula:
  51.  
  52.                               *(A + i)
  53.  
  54.    The compiler already knows that A is a float pointer, so *(A + 0) will
  55. access the first element. *(A + 1) will access the second, and so on.
  56.  
  57.    So far, so good. Now what about multi-dimensional arrays? The theory is
  58. the same, although the implementation may be a bit more complex.
  59.  
  60.    Problem one stays the same. Problem two demands only one more operation
  61. in the allocation phase. Say one needed an N by M array. The allocation
  62. could look like this:
  63.  
  64.                     A=(float)malloc(sizeof(float) * N * M);
  65.  
  66.    Now the sticky part - not too bad, yet easy enough to mis-calculate,
  67. (especially in a computation-heavy program). The solution to number three
  68. in this case is two fold. First, say we want to access the element normally
  69. associated in array operations as A[i][j]. For our purposes this becomes:
  70.  
  71.                      *(A + (N * i) + j);
  72.  
  73.    Which still doesn't look too bad - until you get a group on the left or
  74. right hand side of an operation. For that reason, I usually use a macro
  75. defined as the above. Or more specifically:
  76.  
  77.                       #define A_(N,i,j)  *(A+(N*i)+j)
  78.  
  79.    If 'N' is a variable globally accessible to all procedures needing to
  80. access elements, then the #define could be identified as simply:
  81.  
  82.                       #define A_(i,j)   . . .
  83.  
  84. Which is much easier to read, and hence debug, than *(A+(N*i)+j).
  85.  
  86.    The same type of operations can be defined for multi-dimension arrays
  87. bigger that two, (although the memory does tend to get a bit stretched with
  88. these).
  90.