Triangular array

Question

I want to construct a 2d array in C where each row will have different number of elements. Specifically I want to construct a triangular 7x6 array. In order to save memory I want to avoid storing the zeros as in the following example.

                               1 0 0 0 0 0 0
                               1 1 0 0 0 0 0
                                     ...
                               1 1 1 1 1 1 1   

How can I do this?

Answer 1

Formulation

Won't this system of indexing work?

0
1 2
3 4 5
6 7 8 9
...

Just store your data in a single-dimensional array, using this mapping to the triangular matrix/array.

Bijection

One-dimensional zero-based index k and two-dimensional zero-based row i and column j are the same when k = i(i+1)/2 + j (where j <= i).

Note

The above is for a lower-triangular square matrix/array. You could do something very similar for

• an upper-triangular square matrix/array
  • simply swap i and j
• a rectangular lower- or upper-triangular matrix/array
  • this is a little trickier (you need to reason by cases), but the same idea of mapping the one-dimensional array (implementation) to the conceptual two-dimensional array (view) can be accomplished