For something like this you don't really want dynamic memory allocation. What you want instead is an array which uses an index value of the pointed to element instead of an actual pointer.
Suppose you wanted to implement a binary tree. You can model it as follows:
struct tree {
int free;
int value;
int left;
int right;
};
The left and right fields contain the indexes of the nodes to the left and to the right of the given node, with the value -1 indicating no such node (i.e. it is equivalent to a NULL pointer in this context).
The free field can be used as a flag to determine whether a given element of the array is currently in use. If a node is marked with free equal to 1, the left field points to the next free node, making it easy to find free nodes.
Node 0 is special in that it is the start of the free list, and the right field points to the root node of the tree.
Then the following tree:
7
/ \
3 10
/ \ / \
1 4 8 12
Can be modeled as follows:
free value left right
---------------------------
0 | 1 | 0 | 8 | 1 |
---------------------------
1 | 0 | 7 | 2 | 3 |
---------------------------
2 | 0 | 3 | 4 | 5 |
---------------------------
3 | 0 | 10 | 6 | 7 |
---------------------------
4 | 0 | 1 | -1 | -1 |
---------------------------
5 | 0 | 4 | -1 | -1 |
---------------------------
6 | 0 | 8 | -1 | -1 |
---------------------------
7 | 0 | 12 | -1 | -1 |
---------------------------
8 | 1 | 0 | 9 | -1 |
---------------------------
9 | 1 | 0 | -1 | -1 |
---------------------------
Such a tree can either be memmapped, or kept in memory using malloc / realloc to manage the size.
If your data structure holds any kind of string, you'll want your structure to contain fixed size character arrays instead of pointers so that they serialize correctly.
