sparse array

[ARCITS]

Please could someone explain to me how a 2D sparse array works and provide an example.

I understand the principle but how are the elements indexed for example?

Are there two arrays in fact?

i.e. first array has all elements in it but mostly empty and then second array points to indexes of where first array has data?


any help or example appreciated


thanks

 

[Cagliostro]

2D array means a 1D array of 1D arrays. In memory often it is a continuous range, for example

int x[a][b];

in memory is represented by a continuous 1D range with a*b elements. Remember, you can do like above only if a and b are constants or constant variables.

But if you do like this:
int** x;
x = new int*[a];
for(int i = o; i < a; i++) x[i] = new int[b];

you will get an array or segments, and in usualy don't know where  is situated each segment(a segment I mean a x[i] pointer to it). There is no problem to use any kind of integer variables, constants there are not required.

To access a 2D array is simple, like this:
for(i = 0; i < a; i++)
  for(j = 0; j < b; j++)
     ...x[i][j]....

By the way, in C++ you can not know if an array is empty or not. There is quite no difference. Usualy in C++ if an array is empty, it means it is not allocated in memory. For objects (pointers to classes) you can set a 0 (more correctly is NULL, but physically is no difference) value to say what it is a null object.  Better is to use wrapper classes instead of just arrays. You will store class members which will give you information about the encapsulated array in some more convenable way.

Ion Filipski

 

[Salem]

> Please could someone explain to me how a 2D sparse array works and provide an example.
2-second google search

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node9.html

--