Solved

Double dimensional array formula *(*(arr+i)+j) confusion

Posted on 2003-12-12
12
747 Views
Last Modified: 2010-04-15
Ok, we all know since time in memorial that double dimensional arrays are essentinally pointers to pointers and arr[i][j] is equivalent to *(*(arr+i)+j)  where address of arr is de-referenced twice to get to the location desired. But, when u check memory address given by arr, it points to a linear sequence where all values of all dimensions are placed side-by-side. So, the first time u de-reference *(arr+i) u get the value at this address which is basically a 'value in array' instead of an address of an array, and so when this expression is dereferenced second time it should crash. Why is this and why do we all believe in the pointer-to-pointer interpretation of 2D array when its all values and not addresses??
0
Comment
Question by:gottahaveanswers
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
  • 2
  • +2
12 Comments
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9926770
Hi gottahaveanswers,

int ** a;
a = (int **) malloc ( sizeof(int *) *10 );

for ( i=0; i <10 ; i++ )
     a[i] = (int *) malloc ( sizeof(int ) *10 );

to get to [i][j], you need to access the ith * in a ... and in the array pointed to by a[i], you need to refer to jth element

consider the overall organization

a =    ptr0           ptr1           ptr2      .....                ptr9
           |                 |                |                                 |
           \/               \/               \/                                \/
        int[10]         int[10]       int[10]                         int[10]

a is the beginning address of a
a + i is the address of the ith element
*(a+i) is the address of array of 10 ints
*(a+i) + j is the address of jth element in this array
*(*(a+i) + j ) is the value of the jth element of this array

Hope this clears up your confusions
0
 
LVL 4

Expert Comment

by:skypalae
ID: 9926776
Hi gottahaveanswers,

Writing 'int array[m][n];' creates linear chunk of memory. It's in fact one dimensional array except the compiler knows how to translate its indexing (it's (m*n)+n respectively). Same is with higher dimensional arrays. So you oughta know that double dimensional array is not a pointer to array of pointers, since you create it on your own (using malloc()).

Cheers!
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9926795
Questions Asked: 4
Questions Open: 3
Questions Graded: 1
Questions Deleted: 0
Last 10 Grades Given: A

and the acepted answer is CVed one ... thats a bad record ... You should take time to maintain your questions
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 4

Expert Comment

by:skypalae
ID: 9926818
Mistake ... that 'since' in my last sentence should be replaced by 'until' i think.
But the point stays the same.



We all know since time in memorial that double dimension arrays are NOT pointers to pointers until you make them on your own.

S.
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 9926821
another thing... the representation in my first post is fundamentally different from

a[10][10]

a is the address of beginning of array
a+i is the address of ith element... what this element is depends on value of i (read about row major and column major ordering?)
*(a+i) is the value at that location

*(a+i)+j is that value+j

*(*(a+i) + j )
is trying to derefernce that value and is likely to crash ...

So it seems that your confusion was due to representation of arrays ...

>we all know since time in memorial that double dimensional arrays are essentinally pointers to pointers
thats a way to visulaize them but there is fundamental difference in organization as I just posted
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 9927292
gottahaveanswers,

The fundamental thing you should know in C is that, C doesn't have multi-dimentional arrays!
The only thing it has got is a single dimentional array and the multi-dimentional array declaration just creates an impression that you are using a multi-dimentional array.....though it is a single dimentional array.......so, that you can go ahead with logic of multi-dimentional arrays problems!!
This is implementation related detail, which an user of C need not know and go ahead assuming that it provides multi-dimentional array.....
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 9927294
gottahaveanswers,

The fundamental thing you should know in C is that, C doesn't have multi-dimentional arrays!
The only thing it has got is a single dimentional array and the multi-dimentional array declaration just creates an impression that you are using a multi-dimentional array.....though it is a single dimentional array.......so, that you can go ahead with logic of multi-dimentional arrays problems!!
This is implementation related detail, which an user of C need not know and go ahead assuming that it provides multi-dimentional array.....
0
 
LVL 45

Accepted Solution

by:
Kent Olsen earned 250 total points
ID: 9929215

This has been a fun thread.  :)  Too bad I got here late.

Hi gottahaveanswers,

There are some good posts here.  Things are slow here at the office, so I'm gonna add anoth $0.02 to the discussion.

Array addressing can be "right to left" or "left to right".  Most languages, including C, are "left to right" so that when you increment the rightmost index, you increment the memory location by the size of the arrayed item.  When you increment the first (or any index except the rightmost) you change memory locations by the width of the sturcture.  Consider a simple character array of 6x2.

char CharArray[6][2];

In memory this is 12 consecutive bytes that the C language treats as a matrix.  We tend to think of CharArray as a structure that looks like this:

AB
CD
EF
GH
IJ
KL

When, in fact, it is contiguous memory that looks like this:

ABCDEFGHIJKL

CharArray[0][0] is the first position in the table (an 'A').
CharArray[0][1] is the second position in the table (a 'B').
CharArray[1][0] is the third position in the table (a 'C').  etc...

As I said, increment the rightmost index moves a single position in memory (when using chars).  Incrementing the leftmost index moves the width of the rightmost index.

The general form of this evalution is:

Offset = ((LeftIndex * RightIndexPositions) + RightIndex) * sizeof (array item type);

This same logic extends to all arrays of more than 2 dimensions:

char NewCharArray[3][4][5];

Offset == ((LeftIndex * MiddleIndexPositions * RightIndexPositions) + (MiddleIndex * RightIndexPositions) + RightIndex) * sizeof (array item type);

There are a lot of ways to programmatically produce the offset, perhaps the cleanest is a recursive function.  Here's an entire program that will compute the offset 1,3,2,4,6,1 into "char BigCharArray[3][4][5][6][7][8]";


#include <stdlib.h>

int BigCharArrayLimits[7] = {8, 7, 6, 5, 4, 3, 0};  /* Note - items are backwards for convenience  */
int BigCharArrayOffset[6] = {1, 6, 4, 2, 3, 1};     /* Note - these items are in the same order  */

int ComputeOffset (int *Limit, int *Index);
int ComputeSubOffset (int *Limit, int *Index, int Current);

int ComputeOffset (int *Limit, int *Index)
{
    return ComputeSubOffset (Limit, Index, *Index);
}

int ComputeSubOffset (int *Limit, int *Index, int Current)
{
  if (*Limit == 0)  /*  We've gone through the entire table */
    return 0;
  printf ("index=%6d of %6d, Current = %6d\n", *Index, *Limit, Current);
  return  ComputeSubOffset (Limit+1, Index+1, Current * (*Limit)) + Current * (*Index);
}

main ()
{
  printf ("Array[1][3][2][4][6][1] is at %d\n", ComputeOffset (BigCharArrayLimits, BigCharArrayOffset));
}


It would look better as a class so that ComputeSubOffset() could be hidden, but this is a C forum, not C++.  ")


Hi Sunny,

Things are back to normal, huh?  re:  http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20822860.html#9926371

:)
0
 
LVL 8

Expert Comment

by:ssnkumar
ID: 10028173
gottahaveanswers,

Why don't you provide feedback?
If you are no more interested in this discussion, then close this Q.

-ssnkumar
0
 

Expert Comment

by:varunhome
ID: 14792123
Hi,
This is regarding the question asked at the very beginning of the post. I have written a detailed article on using multi-dimensional pointers in C++. It should be helpful to resolve all doubts unambiguously.

The obvious issue here is that while compiler automatically allocates memory for arrays, memory for pointers must be dynamically allocated. The exact syntax for doing it is described in the article on my home page:

Article link:
http://www.geocities.com/varunhostel/TechnicalArticles/PointerArticle/PointerArticle_Intro.html

Some of the questions relevant to the post answered in the article are:

Chapter 9: How do I dynamically allocate memory for a 3-dimensional pointer equivalent to an array a[2][3][4]?

Chapter 6: To what extent can I inter-change pointer and array syntax in C++?

Chapter 11: How do I decipher very long function pointer declarations? Is there a standard approach for it?

Chapter 11: What is the difference between the two declarations: int *ptr[5] and int (*ptr) [5]?
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
mixing C++ and C code elegantly 10 162
Adjust Mfcapp 29 185
Why does module make constant click noise ? 9 148
First character of input string truncated with scanf 3 117
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and inf…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

751 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question