Re: Linked Lists and Arrays

From: Patrick Dughi (dughi@imaxx.net)
Date: 05/01/00


> Well, I figured out how I mistyped my question.  What it was supposed to be
> was "how to implement a MULTI-DIMENSIONAL array to represent the world," and
> so on.  From looking at the replies, this wasn't really a very clear point,
> and this should help get some clearer answers.  What I need to know if
> there's a method for predetermining the limits of the 3-d array without
> constant mem_allocs().
>

        So, you want to predetermine the limits of a 3-d array.  I fail
right now to remember what the limit to array dimensionality is, but I
know you can at least do 3 *someone who knows, write me.. I think it's 18,
but I can't remember, and now it's bugging me*

  struct your_roomtype[10][10][10];

  Will create an uninitalized 10x10x10 array.  No malloc required (at
least by you).

  Now, if you - for some reason - want to allocate memory dynamically for
a multidimensional array, it gets complicated because dynamic allocation
of an n-dimensional array actually requires dynamic allocation of n
1-dimensional arrays. To allocate a 2-dimensional array one must first
allocate memory sufficient to hold all the elements of the array, then
allocate memory for pointers to each row of the array.  A for loop will do
this pretty well.

/* for x[nrows][ncols] */

int **x = (int **)malloc(nrows * sizeof(int *));

for(i = 0; i < nrows; i++) {
  x[i] = (int *)malloc(ncols * sizeof(int));
}

        You can then access x just like normal; x[5][5].  A three
dimensional array is just an extra level of for loops and pointer
dereferencing. Er would that be indirection. I forget.

        If you're picky like me, you'll notice that that doesn't allocate
contigious pieces of memory, which means you can't do pointer arithimetic
among other things.  Probably best to allocate the memory all in one
chunk - and this can be done easily.. after you've completed the first
malloc as above, just allocate (sizeof(int) * nrows * ncolumns) to the
first member of the array (x[0]), and then walk though and assign the
pointers in column sized chunks:

/* start at 1 cause 0 is already setup */
for(i=1;i < nrows;i++) {
  x[i]=x[0] + i*ncols;
}

        Matter of fact, use this method instead of the first one when you
can.  It just makes more sense to me, and sure enough someone's going to
try to scan entries in using pointer arithimetic, and there'll be hell to
pay.

        Scanning for references to this around on the web, I found a novel
solution, using something (frankly) I have never before used or seen.  It
looks something like this:

int (*x)[ncols] =(int(*)[ncols])malloc(nrows *sizeof(*x));

        But you have to know at least one of the dimensions before you
compile, and for some reason I'm having problems getting this to work as
advertised.

        - oh, stupid me. You have to know all BUT one of the dimensions so
this is probably mostly useless -

        Don't forget, when you're done with them, you have to free them in
nearly the same way, which is a pain.  You also don't have the ability to
use something like realloc to resize.  You'll have to create the new
array, transfer over the relevant info, free up the original, and reassign
the pointers.  It will be quite painful.

                                        PjD


     +------------------------------------------------------------+
     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     |  http://qsilver.queensu.ca/~fletchra/Circle/list-faq.html  |
     +------------------------------------------------------------+



This archive was generated by hypermail 2b30 : 04/10/01 PDT