lang/C/the.ansi.c.programming.language/c.programming.notes.int/sx9b.html

   1 <!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
   2 <!-- This collection of hypertext pages is Copyright 1995-7 by Steve Summit. -->
   3 <!-- This material may be freely redistributed and used -->
   4 <!-- but may not be republished or sold without permission. -->
   5 <html>
   6 <head>
   7 <link rev="owner" href="mailto:scs@eskimo.com">
   8 <link rev="made" href="mailto:scs@eskimo.com">
   9 <title>23.2: Dynamically Allocating Multidimensional Arrays</title>
  10 <link href="sx9a.html" rev=precedes>
  11 <link href="sx10.html" rel=precedes>
  12 <link href="sx9.html" rev=subdocument>
  13 </head>
  14 <body>
  15 <H2>23.2: Dynamically Allocating Multidimensional Arrays</H2>
  16
  17 <p>We've seen that it's straightforward to call <TT>malloc</TT> to
  18 allocate a block of memory which can simulate an array,
  19 but with a size which we get to pick at run-time.
  20 Can we do the same sort of thing to simulate multidimensional arrays?
  21 We can, but we'll end up using pointers to pointers.
  22 </p><p>If we don't know how many columns the array will have,
  23 we'll clearly allocate
  24 memory for
  25 each row
  26 (as many columns wide as we like)
  27 by calling <TT>malloc</TT>,
  28 and each row will therefore be represented by a pointer.
  29 How will we keep track of those pointers?
  30 There are, after all, many of them, one for each row.
  31 So we want to simulate an array of pointers,
  32 but we don't know how many rows there will be, either,
  33 so we'll have to simulate that array (of pointers) with another pointer,
  34 and this will be a pointer to a pointer.
  35 </p><p>This is best illustrated with an example:
  36 <pre>
  37         #include &lt;stdlib.h&gt;
  38
  39         int **array;
  40         array = malloc(nrows * sizeof(int *));
  41         if(array == NULL)
  42                 {
  43                 fprintf(stderr, "out of memory\n");
  44                 <I>exit or return</I>
  45                 }
  46         for(i = 0; i &lt; nrows; i++)
  47                 {
  48                 array[i] = malloc(ncolumns * sizeof(int));
  49                 if(array[i] == NULL)
  50                         {
  51                         fprintf(stderr, "out of memory\n");
  52                         <I>exit or return</I>
  53                         }
  54                 }
  55 </pre>
  56 <TT>array</TT> is a pointer-to-pointer-to-<TT>int</TT>:
  57 at the first level,
  58 it points to a block of pointers,
  59 one for each row.
  60 That first-level pointer is the first one we allocate;
  61 it has <TT>nrows</TT> elements,
  62 with each element
  63 big enough to hold
  64 a pointer-to-<TT>int</TT>,
  65 or
  66 <TT>int *</TT>.
  67 If we successfully allocate it,
  68 we then fill in
  69 the pointers
  70 (all
  71 <TT>nrows</TT> of them)
  72 with a pointer (also obtained from <TT>malloc</TT>)
  73 to <TT>ncolumns</TT>
  74 number of
  75 <TT>int</TT>s,
  76 the storage for that row of the array.
  77 If this isn't quite making sense,
  78 a picture should make everything clear:
  79 <br>
  80 <center><img src="fig23.1.gif"></center>
  81 <br>
  82 </p><p>Once we've done this, we can (just as for the one-dimensional case)
  83 use array-like syntax to access our simulated multidimensional array.
  84 If we write
  85 <pre>
  86         array[i][j]
  87 </pre>
  88 we're asking for the <TT>i</TT>'th pointer pointed to by <TT>array</TT>,
  89 and then for the <TT>j</TT>'th int pointed to by that inner pointer.
  90 (This is a pretty nice result:
  91 although some completely different machinery,
  92 involving two levels of pointer dereferencing,
  93 is going on behind the scenes,
  94 the simulated, dynamically-allocated two-dimensional ``array''
  95 can still be accessed just as if it were an array of arrays,
  96 i.e. with the same pair of bracketed subscripts.)
  97 </p><p>If a program uses simulated, dynamically allocated
  98 multidimensional arrays,
  99 it becomes possible to write ``heterogeneous''
 100 functions which
 101 <em>don't</em> have to know (at compile time)
 102 how big the ``arrays'' are.
 103 In other words,
 104 one function can operate
 105 on ``arrays'' of various sizes and shapes.
 106 The function will look something like
 107 <pre>
 108         func2(int **array, int nrows, int ncolumns)
 109         {
 110         }
 111 </pre>
 112 This function does accept a pointer-to-pointer-to-<TT>int</TT>,
 113 on the assumption that we'll only be calling it with simulated,
 114 dynamically allocated multidimensional arrays.
 115 (We must not call this function on
 116 arrays like
 117 the ``true''
 118 multidimensional array <TT>a2</TT> of the previous sections).
 119 The function also accepts the dimensions of the arrays as
 120 parameters,
 121 so that it will know how many ``rows'' and
 122 ``columns'' there are,
 123 so that it can iterate over them correctly.
 124 Here is a function which zeros out a pointer-to-pointer,
 125 two-dimensional ``array'':
 126 <pre>
 127         void zeroit(int **array, int nrows, int ncolumns)
 128         {
 129         int i, j;
 130         for(i = 0; i &lt; nrows; i++)
 131                 {
 132                 for(j = 0; j &lt; ncolumns; j++)
 133                         array[i][j] = 0;
 134                 }
 135         }
 136 </pre>
 137 </p><p>Finally, when it comes time to free one of these dynamically
 138 allocated multidimensional ``arrays,'' we must
 139 remember to free each of the chunks of memory that we've
 140 allocated.
 141 (Just freeing the top-level pointer, <TT>array</TT>,
 142 wouldn't cut it;
 143 if we did,
 144 all the second-level pointers would be lost but not freed, and would waste
 145 memory.)
 146 Here's what the code might look like:
 147 <pre>
 148         for(i = 0; i &lt; nrows; i++)
 149                 free(array[i]);
 150         free(array);
 151 </pre>
 152 </p><hr>
 153 <p>
 154 Read sequentially:
 155 <a href="sx9a.html" rev=precedes>prev</a>
 156 <a href="sx10.html" rel=precedes>next</a>
 157 <a href="sx9.html" rev=subdocument>up</a>
 158 <a href="top.html">top</a>
 159 </p>
 160 <p>
 161 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 162 // <a href="copyright.html">Copyright</a> 1996-1999
 163 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 164 </p>
 165 </body>
 166 </html>