Implement a non-rectangular array in C

Question

I am trying to implement a non-rectangular, multi-dimensional array in C, i.e. something like this:

[1, 2, [3, [4, 5, [6]]], 7]

As of now I am using a tree like this:

enum item_type { ELEMENT, ARRAY };
struct item {
    int value;
    struct item *next;
    enum item_type type;
};

Could this be simplified or improved somehow?

EDIT: to clarify more this a part of an exercise to "translate" some concepts from higher level languages, like for example the following python code:

array = [1, 2, [3, [4, 5, [6]]], 7]

I think you do not need to use an enum since an element can be considered to be an array of size 1. Just dynamically allocate size of the array rows. — Amit Singh, Mar 01 '18 at 05:57
@Amit Singh, example array is 4 dim irregular, so not that simple I think. But item_type can be eliminated, if item*=0(null) is used as flag for non array. — visibleman, Mar 01 '18 at 06:03

Basile Starynkevitch · Accepted Answer · 2018-03-01T06:36:12.670

Reason in terms of abstract data types. Perhaps your thing is more a tree (or maybe a DAG) than an array.

So first, define exhaustively (on paper) all the operations on your non-rectangular "arrays" (I have no precise idea about them, since your question is vague). Think more about how you create, access and perhaps modify your things.

Then implement that abstract data type. See this for a simpler example (matrixes). Perhaps you might use flexible array members and tagged unions.

Read some Introduction to Algorithms and about S-expressions (and perhaps about ASTs).

score 0 · Answer 2 · answered Mar 01 '18 at 05:51

0

you could make it generic. instead of

int value;

your struct can hold

void* data;

and then dynamically allocate space for it on the heap i guess.

answered Mar 01 '18 at 05:51

milesdavis

1

score 0 · Answer 3 · answered Mar 01 '18 at 06:22

4 points away from adding comments to other good answers ... so I hope others will accept my apology ...

Python makes this very easy by allowing "objects of type list" to be embedded in lists and no requirement is "rectangular" is stated. C makes it very manual.

I have used this approach before to implement a "hash-set of very many integers" of general format XXXXXYYYY. I declared a fixed array of 10000 pointers-to-structures to represent the YYYY portion and dynamically allocated links to represent the XXXXX parts ... very rapid searches for a particular element.

In your case you can do the same and even have lists-within-lists (like a snowflake's arms), but the pointer management will be daunting. Not because of any skill level in you but because the placement of the "*" (2 and 3 and beyond) must be correct ... C compiler will guess what you meant if you are not precise in your code. Even veteran C coders find this work challenging.

Implement a non-rectangular array in C

3 Answers3